Traversing a Data Tree

[xmitchx]

Hi,

Sitepoint has never failed me before, and I really need help this time so here it goes. I have been writing a form component for the Zend Framework for the past week to simplify form data validation and filtering. I am on the last part of a working prototype: page branching. And it is causing me a lot of trouble. Let me explain this feature briefly. Any web developer must have had a form at one point in their lives that "branches" based on user input. For example if you have a "Register a New Domain or Use my Own" option. If the user selects the former option, you want to show one form, while if the user selects the latter, you want to show another, while eventually converging back to the same place. Page branching allows you to do this simply.

You can view the basic syntax, if you're interested, here on the proposal page under the "Page Branching" use case.

The problem that I am having is traversing this tree and finding the next valid page that I should be showing for my form. I created some "dumbed down" version of the actual classes (to simplify things for testing) and wrote a function that is working but is fairly complex.

I'll be honest in saying that I have no formal programming education. I am a freshman in college and everything up to this point I've taught to myself over the past decade. So I am fairly confident I am missing an algorithm of some sort to traverse such a tree.

Anyways, if any of you could help, I would greatly appreciate it, you can view the code here:

http://mitchellhashimoto.com/simplif...-win-a-cookie/

Mitchell Hashimoto

[kromey]

Glanced at your code, and you're right, it is pretty complex. Unfortunately I don't have time right now to really delve into it (have a rapid-fire series of meetings starting in about 15 minutes), so I'll show you the rough logic that I would use in this situation and maybe that will get you moving in the right direction.

First of all, I'd look at this as a sequence, not a tree. Yes, there are branches, but (at least the way you've described it) you'll always start at the same point and always end at the same point, with an indeterminate number of intermediate steps. (Okay, by strict letter-of-the-law interpretation, this may very well be a "tree" (I very nearly failed my Data Structures class), but I've found time and again that what works in my head doesn't work in formal language and vice-versa.)

So we end up with a list of steps. Walk through them one at a time. E.g.:

0: Page 1
1: Page 2
2: Page 3

Conditional branching, at it's simplest, would be an alternative page at one step, e.g.:

0: Page 1
1: condition?Page 2a:Page 2b
2: Page 3

The overall structure is unchanged - we still move from step 0 to step 1 and finally to step 2. The only difference is that at step 1 we check a condition and offer up alternative pages based on the outcome; the structure above could easily accommodate conditions with more than two possible outcomes (i.e. more than simple true/false conditions).

Of course, some branches might be longer than others, so we modify the above sequence to be as follows:

Sequence 0:
0: Page 1
1: condition?Sequence A:Sequence B
2: Page 3

Sequence A:
0: Page 2a1
1: Page 2a2

Sequence B:
0: Page 2b1

From this, we end up with two data structures: Pages and Sequences. A Page would hold all the data necessary to build a given page; we could easily apply inheritance to permit easily making minor differences in branched pages. A Sequence is slightly more tricky: it needs to hold Pages, Conditions (possibly a third data structure, but most likely just data within a Sequence), and Sequences. If we were doing this in C/C++, we'd be in trouble, but PHP's dynamic datatypes make this easy.

I'd implement a Sequence as a class with an array, and store each Page in sequence in that array; then when we need to stick in a Sequence instead of a Page, we just do that, no problem. We'd also need to store Conditions somehow, but that wouldn't be too hard.

I'll revisit this later, I gotta run to my meetings. (Where the hell is the Chandler room?? Why can't we all just use room numbers and be done with it????) PM me if you'd be interested in working more closely to make this project work (I also happen to use the Zend Framework, although only just started, and I also happen to be a current CS student).

[xmitchx]

Thanks kromey, I enjoyed reading your input. What you say is true. I am currently using two classes Page and Branch, as you can see, which is almost the same as Page and Sequence. I was talking this problem over with a CS grad student and he stated it very simply to me by saying, "There are two problems you are trying to solve: Where am I now, and where should I be going next? Once you solve Where am I now, you can solve where I should go next." So I think the crux of my issue lies in the fact that there is no easy way to get directly to a sub-item. I have to traverse the entire tree to find the given item, and then must traverse further from there to find the next item. The way I've "solved" this is with complex recursion and the use of references. But I think there is a more efficient way.

If you are interested in helping me with such a component, I'd be glad to talk it over with you. I'll PM you.