Need iterator advice to traverse tree

Question

Hi I need some iterator advice.

I have a Category object which can contain a collection of items and also can have children categories.

From doctrine ORM I do get a collection of category objects. Now I want to traverse this collection and flatten the category tree structure. So the children categories are at the same level as it's parent. I would also like to filter the children.

Maybe somebody can point me in the right direction, currently a bit lost in the Iterator cloud.

<?php

class Category
{
    private $name;

    private $children;

    private $type;

    private $parent;

    private $items;

    //parent category
    public function getParent()
    {
        return $this->parent;
    }

    public function setItems($items)
    {
        $this->items = $items;
    }


    public function getItems()
    {
        return $this->items;
    }

    //colelction of categories
    public function getChildren()
    {
        return $this->children;
    }
}

Answer 1

You simply need to implement the RecursiveIterator interface. Then, you can iterate over it using the concrete RecursiveIteratorIterator.

To help you understand...

A RecursiveIterator isn't very, um, "recursive" by itself. It is just something that offers up certain methods that can be used to get the children(the subproblem in recursion can be thought of as "children"). Notice that RecursiveIterator.getChildren() must return its children in the form of another RecursiveIterator.

You could manually iterate a plain RecursiveIterator, but, it would be pretty painful to keep track of all the sub iterators returned by the recursive calls to getChildren, and maintain the proper depth etc...thats where RecursiveIteratorIterator comes in...

A RecursiveIteratorIterator is the thing that does the actual work to systematically traverse the structure, mimicking recursion. It iterates through a RecursiveIterator as if it were a flat list, but at each element in the list, it tests the current element for the presence of children. If it hasChildren, it calls getChildren and stores the reference to this new child iterator in a Stack. It manages the Stack in a fashion that provides the recursive behavior you expect(much the same way you manually transform a recursive function into an iterative version).

To be clear, you don't code your own RecursiveIteratorIterator, just instantiate php's concrete implementation. This class exists purely to hide the complications and manage all the many RecursiveIterator objects that get instantiated in the traversal process from you, and presenting the result of the traversal to you as what seems like a flat list. RecursiveIteratorIterator is a very complicated class internally.

As for filtering-

There's a few ways. For ease of use, I recommend to use CallbackFilterIterator if you have php 5.4. Otherwise, you must extend FilterIterator.

However, both of those filter the elements out after the, um, view of the recursive structure has been flattened into a list like structure. So, your filter cannot for example say "skip this entire subtree", it can only say "skip this single element". If you need to say "skip this entire subtree" you need to use RecursiveCallbackFilterIterator or extend RecursiveFilterIterator if you dont have php 5.4

you probably want to start with

class RecursiveCategoryIterator implements RecursiveIterator {...

And that should contains a list of Category objects.

Answer 2

You have to start at the root node and recursively traverse each $this->getChildren() (of the nodes and the subnodes (and their subnodes (and their subnodes (and their subnodes)))) (recursion) until it is null. This will result in something like this:

(Start)
Root node
-> 1st Child node
--> Grandchild node
-> 2nd Child node
-> 3rd Child node
-> 4th Child node
--> Grandhild node
(No more children so exit)