View Full Version : How do I loop without knowing the ending criteria ??

02-12-2010, 08:28 PM
I want build a nav tree based on the page currently displayed.
I've got an array of the pages on my site (via a SQL query).

Lets say it looks like this (i've simplified it):

'pageTitle'=>'Contact VCI',
'pageTitle'=>'Apply for an Open Account',
'pageTitle'=>'Request an RMA',
'pageTitle'=>'Brands Carried',
'pageTitle'=>'Types of Products Carried',
'pageTitle'=>'Brand A',
'pageTitle'=>'Brand B',
'pageTitle'=>'Product Type A',
'pageTitle'=>'Product Type B',
'pageTitle'=>'Product Search',

This shows parent child relationships of pages.
All pages are descendants of the "home" root, and there are many branches from there.
My goal is to dynamically build a nav menu specific for that "branch" of the site tree.

I already wrote the code to determine the ancestor which is the direct child of home (ie: if I'm on typea.php, I've identified products.php as that ancestor).
Now I want to build the nav tree for all descendants of products.php.

Building the links is no problem (and I know I will be using a nested loop), I just need to know how to loop through it with the array on hand without having to resort to more DB queries (I mean, after all, I do already have all the info that I need).
WHILE doesn't seem to be a proper fit, and I don't see how to define the iteration count for a FOR loop.

What's a good way of attacking this ??
What am I missing ?

~ Mo

FYI: The nav tree will look like:

<ul id="contentNav">
<li><a href="search.php">Product Search</a></li>
<li><a href="prodbrands.php">Brands Carried</a>
<ul class="navSub">
<li><a href="branda.php">Brand A</a></li>
<li><a href="brandb.php">Brand B</a></li>
<li><a href="prodtypes.php">Types of Products Carried</a>
<ul class="navSub">
<li><a href="typea.php">Product Type A</a></li>
<li><a href="typeb.php">Product Type B</a></li>

02-12-2010, 08:38 PM
Without reading this entire post (skipped the last two paragraphs, sorry :P) the answer is (somewhat) simple.
To me, it sounds like you want to use a datastructure called a graph. The plus side, they are mostly easy to make. Essentially you plop you're vertices on you're graph, then reloop you're array and attach edges to the vertices. Think of like a map, each item is a city, each edge is a highway. You can actually attach edges the same time you attach vertices, but you must be 100% certain that you're sorted by an order which allows the linked node to be in place when adding the current node.

Another solution is to write a custom iterator thats recursive and wrap the entire array as an arrayobject, provide it you're custom recursive iterator, and use a foreach to iterate what you need. Still will be unpleasant, and I would suspect this will run slow.

Personally, I use the graph to write breadcrumbs with a depth search, and link trees with breadth-first traversal. The most important part for these implementations is to never loose track of the 'root' node.

02-12-2010, 10:34 PM
Ok, I started looking into graphs, and WOW !!
That's a deep subject.
It may be beyond the scope of this project. =)

Regardless, I'm interested in figuring it out.
Do you have any good links or resources you can share on that?

~ Mo

02-12-2010, 11:08 PM
Hmm, I thought I did but they are all books 24x7 links (which you need access for; costs money but mines free from school).
Aside from wikipedia, I don't have any other links to graphs I'm afraid. What you'll want is a sparse graph, so look for adjacency graphs, not matrix graphs. Directional versus bi-directional are irrelevant, all they are is two directional edges, so thats no concern (for the record, write it as a directional graph, not a bi-directional one; you can always extend this later).
Graphs will use massive amounts of memory compared to an array, but will access substantially faster than a custom iterator or array manipulations. Adding is also extremely easy, and will self link the structures. Removing is also easy. The only 'addon' I can suggest for it is to keep a list of every vertex not just the adjacency list or matrix for easy lookup. With PHP5 objects, these will all be by reference anyway, so finding a single node then looking up its relations (breadth first or depth first for example to another node) is super easy.

I'm pretty certain one of the pages in the wiki for graph datastructures is really well detailed on how to construct one (both OO and proceedurally), and there are liks to traversals with prims and dijkstra's algorithms and whatnots (not sure about the spellings, but I'm sure you'll notice them ;))

Good luck, datastructures are probably one of my favorite parts of programming! Once you learn them, you can write you're own graphs, hashtables, lists, collections, etc.

02-13-2010, 12:41 AM