in reply to Re: Re: So you think you're good with structures?
in thread So you think you're good with structures?

I think it's more important that you defined the structure you want to traverse versus design the traversal for a given structure. Most people don't realize this, but the data structure you design will make or break your sanity. It's not as easy as saying "Can you traverse this or not?"

If I was going to design a data structure to traverse, I would do things completely differently. However, I suspect that traversal isn't the only thing you're planning on doing.

In addition, you still haven't fully laid out the rules for the traversal. Here are the rules I've seen you lay out. You tell me if they make sense:

  1. Take a key from the table you're in and append it to the list.
  2. If there are no children, go to 1.
  3. Grab the list of child records.
  4. Append each child record to the list.
  5. For each child record, go to 1.
Am I missing anything?

------
/me wants to be the brightest bulb in the chandelier!

  • Comment on Re: Re: Re: So you think you're good with structures?

Replies are listed 'Best First'.
Re: Re: Re: Re: So you think you're good with structures?
by clintp (Curate) on Aug 03, 2001 at 23:50 UTC
    It's not as easy as saying "Can you traverse this or not?"
    Of course it is! All of the relationships between the nodes are present and accounted for. Printing this out, I've explained this to two nonprogrammers; they recognize the pattern after a walkthrough, and given a much more complex example than the one I posted can easily traverse it. I've explained it to programmers and they can recognize the pattern and have so far failed to be able to write code to do it -- including me.

    suspect that traversal isn't the only thing you're planning on doing
    No, it's not. In fact, there's a whole ad-hoc report generation system which uses the "output" of this problem to produce reports. Sorts, breaks, totals, summary, detail, etc... The earlier incarnations of this routine suffered from bugs which caused either duplicate traversals or missed traversals in some very odd places.
    In addition, you still haven't fully laid out the rules for the traversal.
    That's because every time I try to quantify it, it breaks down at some level or another. Step 4.5 (which everyone seems to grasp intuitively, but not be able to describe) is "only after each child, once we've fully descended into the tree do we have a complete record; on the next child, the nodes descended by the first have to be thrown away and re-done". Sort of. But that's not clean enough to code and may not be entirely accurate.

    I have much, much larger examples that aren't nearly so neat and tidy if necessary. They all follow this pattern though.

[reply]

In Section Seekers of Perl Wisdom