<?php
namespace printf;

function pre_print_r($string)
{
   echo("<pre>\n");
   print_r($string);
   echo("\n</pre>\n");
}

<?php
namespace tree;

function get_full_paths(
   $node, $skip_root=False, $path=array(), $paths=array(), $depth=0)
{
   if ($depth > 0 || !$skip_root)
   {
      $path[] = $node->content;
   }
   if (isset($node->children))
   {
      foreach ($node->children as $child)
      {
         $paths = get_full_paths($child, $skip_root, $path, $paths, $depth + 1);
      }
   }
   if (!isset($node->children))
   {
      $paths[] = $path;
   }
   return $paths;
}

<?php
namespace tree;

class Node
{
   public function __construct($content)
   {
      $this->content = $content;
   }
}

<?php
namespace tree;

require_once "Node.php";

function array_to_tree($array, $root=null)
{
   if (is_null($root))
   {
      $root = new Node($array[0]);
      array_splice($array, 0, 1);
   }
   for ($ii = 0; $ii < count($array); $ii++)
   {
      $child = new Node($array[$ii]);
      $root->children[] = $child;
      if ($ii < count($array) - 1)
      {
         array_to_tree(array_slice($array, $ii+1), $child);
      }
   }
   return $root;
}

<?php
namespace tree;

function get_paths_terminating_at_root(
   $node, $length=null, $path=array(), $depth=0, $paths=array())
{
   $path[] = $node->content;
   if (isset($node->children))
   {
      foreach ($node->children as $child)
      {
         $paths = get_paths_terminating_at_root(
            $child, $length, $path, $depth + 1, $paths);
         if ($depth == 0)
         {
            $paths = get_paths_terminating_at_root(
               $child, $length, array(), $depth + 1, $paths);
         }
      }
   }
   if (!isset($node->children))
   {
      if (is_null($length) || count($path) == $length)
      {
         $paths[] = $path;
      }
   }
   rsort($paths);
   return $paths;
}

<?php
namespace tree;

require_once "Node.php";

function matrix_to_tree($matrix, $root=null, $ii=0)
{
   if (is_null($root))
   {
      $root = new Node("Root");
   }
   foreach ($matrix[$ii] as $ancestor)
   {
      $child = new Node($ancestor);
      $root->children[] = $child;
      if ($ii < count($matrix) - 1)
      {
         matrix_to_tree($matrix, $child, $ii + 1);
      }
   }
   return $root;
}

<?php
namespace tree;

require_once "Node.php";

function string_to_tree($str, $root=null)
{
   if (is_null($root))
   {
      $root = new Node($str[0]);
      $str = substr($str, 1);
   }
   for ($ii = 0; $ii < strlen($str); $ii++)
   {
      $child = new Node($str[$ii]);
      $root->children[] = $child;
      if ($ii < strlen($str) - 1)
      {
         string_to_tree(substr($str, $ii+1), $child);
      }
   }
   return $root;
}

<?php

class Node implements Iterator
{
   public $_value = null;
   public $_next = null;
   private $_junctions = array();
   private $_retreating = False;
   private $_current;
   
   public function __construct($value)
   {
      $this->_value = $value;
      $this->_current = $this;
   }

   public function __toString()
   {
      return is_object($this->_value) ? "<Object>" : (string) $this->_value;
   }

   final public function key() { return sizeof($this->_junctions); }
   final public function current() { return $this->_current; }
   final public function valid() { return $this->_current == True; }
   final public function rewind()
   {
      $this->_current = $this;
      $this->_junctions = array();
      $this->_retreating = False;
   }
   
   final public function next()
   {
      while ($this->_current)
      {
         if (is_object($this->_current->_value) && !$this->_retreating)
         {
            array_push($this->_junctions, $this->_current);
            $this->_current = $this->_current->_value;
            return;
         }
         if ($this->_current->_next)
         {
            $this->_current = $this->_current->_next;
            $this->_retreating = False;
            return;
         }
         $this->_current = array_pop($this->_junctions);
         $this->_retreating = True;
      }
   }

   final public function count()
   {
      return ((is_object($this->_value)) ? $this->_value->count() : 0) +
         (($this->_next) ? $this->_next->count() : 0) + 1;
   }

   final public function measure_depth()
   {
      $current = $this;
      while ($current)
      {
         if (is_object($current->_value))
         {
            $nodes[] = 1 + $current->_value->measure_depth();
         }
         $current = $current->_next;
      }
      return ($nodes) ? max($nodes) : 1;
   }

   public function adopt($new, $unique, $offset=0, $additional_unique_field="")
   {
      if ($unique)
      {
         if ($this->replace_child($new, $offset, $additional_unique_field))
         {
            return;
         }
      }
      $this->insert_child($new);
   }

   private function replace_child($new, $offset=0, $additional_field="")
   {
      $current_offset = 0;
      $current = $this->_value;
      while ($current && $next = $current->_next)
      {
         $fields = array("_name", $additional_field);
         if ($this->match_fields($next, $new, $fields))
         {
            if ($current_offset++ == $offset)
            {
               $new->_next = $next->_next;
               $current->_next = $new;
               return True;
            }
         }
         $current = $current->_next;
      }
      return False;
   }

   private function match_fields($current, $new, $fields)
   {
      if (!is_array($fields)) $fields = array($fields);

      foreach ($fields as $field)
      {
         if ($field && $current->$field != $new->$field)
         {
            return False;
         }
      }
      return True;
   }

   private function insert_child($new)
   {
      if ($this->check_for_static_data())
      {
         echo "Can't adopt $new, static data exists in parent\n";
         return;
      }
      if (is_null($this->_value))
      {
         $this->_value = $new;
         return;
      }
      $current = $this->_value;
      while ($current->_next && $current = $current->_next);
      $current->_next = $new;
   }

   private function check_for_static_data()
   {
      if ($this->_value && !is_object($this->_value))
      {
         return True;
      }
      return False;
   }

   public function remove_child($name, $offset=0)
   {
      $previous = null;
      $current = $this->_value;
      $current_offset = 0;
      while ($current)
      {
         if ($current->_name == $name)
         {
            if ($offset == $current_offset++)
            {
               $this->delete_node($current, $previous);
               return True;
            }
         }
         $previous = $current;
         $current = $current->_next;
      }
      return False;
   }

   private function delete_node($node, $previous=null)
   {
      if (!$previous)
      {
         $this->_value = $node->_next;
         return;
      }
      $previous->_next = $node->_next;
   }

   public function search(
      $token, $recursive=False, $match_by_class=False, $offset=null,
      $include_root=True, $depth=0, $current_offset=0, $matches=array())
   {
      if ($include_root || $depth > 0)
      {
         $this->add_match(
            $token, $matches, $match_by_class, $offset, $current_offset);
      }
      if (is_object($this->_value) && ($recursive || $depth == 0))
      {
         $matches = $this->_value->search(
            $token, $recursive, $match_by_class, $offset, $include_root, $depth+1,
            0, $matches);
      }
      if ($depth > 0 && $this->_next)
      {
         $matches = $this->_next->search(
            $token, $recursive, $match_by_class, $offset, $include_root, $depth,
            $current_offset, $matches);
      }
      return is_array($matches) && sizeof($matches) == 1 ? $matches[0] : $matches;
   }

   private function add_match(
      $token, &$matches, $match_by_class, $offset, &$current_offset)
   {
      $match = $this->inspect_token($token, $match_by_class);
      if (!is_null($match))
      {
         $current_offset++;
         if (is_null($offset) || $offset == $current_offset)
         {
            if (!is_array($matches))
            {
               $matches = array($matches);
            }
            $matches[] = $match;
         }
      }
   }

   protected function find_next_capable_sibling($method)
   {
      $match = method_exists($this, $method) ? $this : null;
      if (!$match)
      {
         if ($this->_next)
         {
            $match = $this->_next->find_next_capable_sibling($method);
         }
      }
      return $match;
   }

   public function find_next_particular_sibling($class_name)
   {
      $match = $this instanceof $class_name ? $this : null;
      if (!$match)
      {
         if ($this->_next)
         {
            $match = $this->_next->find_next_particular_sibling($class_name);
         }
      }
      return $match;
   }
}