<?php

error_reporting(E_STRICT);

/**
 * Given a flat array of nodes in a mptt (nested set) tree, in ascending order
 * of their left id, figure out what level each node is on. The only things
 * required to figure out what level a node is on is its left and right ids.
 * This iterator uses a stack to keep track of levels.
 * 
 * @author Peter Goodman
 * @copyright Copyright (c) 2008, Peter Goodman. All rights reserved.
 */
class NestedSetIterator extends IteratorIterator {
    
    const LEFT_ID = 'left',
          RIGHT_ID = 'right',
          LEVEL = '_level';
    
    private $nodes,
            $level,
            $stack;
    
    /* Constructor, take in an array or iterator. If an array is passed, turn
       it into an iterator.
     */
    public function __construct(&$nodes = NULL) {
        
        if(!($nodes instanceof Iterator) && is_array($nodes))
            $nodes =& new ArrayIterator($nodes);
        
        parent::__construct($nodes);
        $this->rewind();
    }

    /* Push an item onto the stack. The stack holds arrays of pairs that have
       the number of children of a given node. Pair[0] is reduced when an item
       is consumed and pair[1] is kept to reduce the parent stack elements
       pair[0] when the current top stack element is popped.
     */
    private function push(&$node) {
        
        if(!is_array($node) && !($node instanceof ArrayAccess))
            throw new Exception("Node is not an array nor has array access.");
        
        $num = ($node[self::RIGHT_ID] - $node[self::LEFT_ID] - 1) / 2;
        $this->stack[] = array($num, $num);
        $this->level++;
    }
    
    /* Pop a pair off the stack and update the number of consumed nodes of the
       new top node.
     */
    private function pop() {
        
        $level = array_pop($this->stack);
        $this->level--;
        
        /* We have just popped a level off of the stack. Consume works by
           decreasing the number of nodes on the top of the stack, but each
           stack elem knows the *total* number of nodes below it, and so 
           consuming nodes on the top of the stack doesn't account for lower
           elements (parent nodes). Therefor we decrease the current top of
           stack (after the pop) by how many total nodes there were originally
           in the node elem we just popped off.
         */
        $this->consume($level[1]);
    }
    
    /* Reduce the number of nodes consumed for the top pair of the stack. */
    private function consume($num = 1) {
        if(isset($this->stack[$this->level]))
            $this->stack[$this->level][0] -= $num;
    }
    
    /* Clean up after stack elements that have no more nodes to consume. */
    private function cleanup() {
        
        /* Move down the stack elems until we hit a level that still has nodes
           that haven't been consumed.
         */
        for($i = $this->level; isset($this->stack[$i]); $i--) {
            
            if($this->stack[$i][0] > 0)
                break;
            
            $this->pop();
        }
    }
    
    /*
     * Iterator methods
     */
    
    /* Get the current node */
    public function &current() {
        
        $node = parent::current();
        
        /* Use cached version of level so that it doesn't need to go through
           the normal consume/push/pop phase.
         */
        if(isset($node[self::LEVEL]))
            return $node;
        
        /* Cache doesn't exist, consume the node and push a new element onto
           the stack.
         */
        $this->consume();
        $this->push(&$node);
        
        /* Store the level in an unique name */
        $node[self::LEVEL] = $this->level;
        
        return $node;
    }
    
    /* Move to the next node. */
    public function next() {
        $this->cleanup();
        parent::next();
    }
    
    /* Reset everything. */
    public function rewind() {
        $this->stack = array();
        $this->level = -1;
        parent::rewind();
    }
}


$items = array(
    array(
        'left' => 1,
        'right' => 8,
        'name' => 'Top',
    ),
    array(
        'left' => 2,
        'right' => 5,
        'name' => 'below',
    ),
    array(
        'left' => 3,
        'right' => 4,
        'name' => 'below below',
    ),
    array(
        'left' => 6,
        'right' => 7,
        'name' => 'below',
    ),
    array(
        'left' => 9,
        'right' => 12,
        'name' => 'Second Top',
    ),
    array(
        'left' => 10,
        'right' => 11,
        'name' => 'below',
    ),
    array(
        'left' => 13,
        'right' => 14,
        'name' => 'Third Top',
    ),
);

$items = new NestedSetIterator($items);

echo'<html><body>';
foreach($items as $item) {
    echo str_repeat('&nbsp; &nbsp; &nbsp; ', $item['_level']) . $item['name'] .'<br />';
}
echo'</body></html>';

/*
Output:

Top
      below
            below below
      below
Second Top
      below
Third Top


*/