Implementation of a Tree Structure in PHP – II

I received an excellent comment by ‘Chris Rogers’ on my earlier post Implementation of a Tree Structure in PHP. He commented to the fact that the iterator does not work if the child was created prior to the parent. Excellent catch!

To that end I have modified the class, specifically the iterator’s ‘createNode’ method which takes care of this fact. The final code can be found on Github: tree-php


/**
 * JTreeRecursiveIterator
 *
 * To use a recursive iterator you have to extend of the RecursiveIteratorIterator
 * As an example I have built an unordered list
 * For detailed information on please see RecursiveIteratorIterator
 * http://us.php.net/manual/en/class.recursiveiteratoriterator.php
 *
 * @package   JTree
 * @author Jayesh Wadhwani
 * @copyright Jayesh Wadhwani
 * @license  GNU GENERAL PUBLIC LICENSE 3.0
 * @version 1.0 2011
 */
class JTreeRecursiveIterator extends RecursiveIteratorIterator {
   /**
   * @var _jTree the JTree object
   */
	private $_jTree;
   /**
   * @var _str string with ul/li string
   */
	private $_str;

	/**
	 * JTreeRecursiveIterator::__construct()
	 *
	 * @param mixed $jt - the tree object
	 * @param mixed $iterator - the tree iterator
	 * @param mixed $mode
	 * @param integer $flags
	 * @return
	 */
	public function __construct(JTree $jt, $iterator, $mode = RecursiveIteratorIterator::LEAVES_ONLY, $flags = 0) {

		parent::__construct($iterator, $mode, $flags);
		$this->_jTree = $jt;
		$this->_str = "<ul>\n";
	}

	/**
	 * JTreeRecursiveIterator::endChildren()
	 * Called when end recursing one level.(See manual)
	 * @return void
	 */
	public function endChildren() {
		parent::endChildren();
		$this->_str .= "</ul></li>\n";
	}

	/**
	 * JTreeRecursiveIterator::callHasChildren()
	 * Called for each element to test whether it has children. (See Manual)
    *
	 * @return mixed
	 */
	public function callHasChildren() {
		$ret = parent::callHasChildren();
		$value = $this->current()->getValue();

		if($ret === true) {
			$this->_str .= "<li>{$value}<ul>\n";
		} else {
			$this->_str .= "<li>{$value}</li>\n";
		}
		return $ret;
	}

	/**
	 * JTreeRecursiveIterator::__destruct()
	 * On destruction end the list and display.
	 * @return void
	 */
	public function __destruct() {
		$this->_str .= "</ul>\n";
      echo $this->_str;
	}

}

Now if you were to re-arrange the array like so where I have made ‘Fires'(id=5) as a child of Hurricanes(id=9)

$categories = array();
$categories[] = array('id' => 1, 'weather_condition' => 'weather', 'parent_id' => 9999);
$categories[] = array('id' => 2, 'weather_condition' => 'Earthquakes', 'parent_id' => 1);
$categories[] = array('id' => 3, 'weather_condition' => 'Major', 'parent_id' => 2);
$categories[] = array('id' => 4, 'weather_condition' => 'Minor', 'parent_id' => 2);
$categories[] = array('id' => 5, 'weather_condition' => 'Fires', 'parent_id' => 9);
$categories[] = array('id' => 6, 'weather_condition' => 'Rain', 'parent_id' => 1);
$categories[] = array('id' => 7, 'weather_condition' => 'Flooding', 'parent_id' => 6);
$categories[] = array('id' => 8, 'weather_condition' => 'Washout', 'parent_id' => 6);
$categories[] = array('id' => 9, 'weather_condition' => 'Hurricanes', 'parent_id' => 1);

And run it

//create a new tree object
$jt = new JTree();

//iterate building the tree
foreach($categories as $category) {
   $uid = $jt->createNode($category['weather_condition'],$category['id'], $category['parent_id']);
}

//update: removed third variable. Use defaults 
$it = new JTreeRecursiveIterator($jt, new JTreeIterator($jt->getTree()));

//iterate to create the ul list
foreach($it as $k => $v) {}

Note that I have removed addChild. It is included in createNode.

The result being:

  • weather
    • Earthquakes
      • Major
      • Minor
    • Rain
      • Flooding
      • Washout
    • Hurricanes
      • Fires

Many thanks to Chris for pointing this out.

Happy computing!

Advertisements

13 thoughts on “Implementation of a Tree Structure in PHP – II

  1. Hi!
    Thanks for sharing your awesome work…
    I’m having trouble building a tree using data retrieved from mysql table.
    I’ve used the following code to store data into $categories array:

    mysql_connect(“localhost”, “user”, “pass”);
    mysql_select_db(“mydb”);
    $result = mysql_query(“SELECT id,name,parentId FROM webcats”);
    $categories = array();
    while ($row = mysql_fetch_assoc($result)) {
    $categories[] = $row;
    }

    $jt = new JTree();
    foreach($categories as $category) {
    $uid = $jt->createNode($category[‘name’],$category[‘id’], $category[‘parentId’]);
    }
    $it = new JTreeRecursiveIterator($jt, new JTreeIterator($jt->getTree()), true);
    foreach($it as $k => $v) {}

    The tree appears empty… What I’m doing wrong?

    Thanks for your time….

    Like

  2. Hi! I’m using your classes, but I have some problems with JTree->modifyNode (updating root node for linking to other existing node).
    Seems it dosn’t updates childrens information on parent node, it’s right?
    All works fine if I use createNode for update info

    thanks,
    Antonio

    Like

    • Hi Antonio,

      Yes, you are correct. It will not update the children’s info. All modifyNode() does is given the uid of a node(it fetches the actual node) it modifies the value and its parent’s uid. By changing the parent UID it allows you to move the node anywhere in the tree.

      Thank you

      Jayesh

      Like

    • Hi Jonathan,

      Thanks for your question.

      The quickest way that comes to mind is to sort the children.
      So in the JtreeIterator class I would do this:

       /**
           * JTreeIterator::getChildren()
           *
           * @return JTreeIterator
           */
          public function getChildren() {
              $childObj = $this->_list[$this->key()];
              $children = $childObj->getChildren();
              
              usort($children, array($this, '_cmp'));
              
              return new JTreeIterator($this->_list, $children);
          }
          
          private function _cmp($a, $b)
          {
              $a = strtolower($this->_list[$a]->getValue());
              $b = strtolower($this->_list[$b]->getValue());
              
              if ($a == $b) {
                  return 0;
              }
              return ($a < $b) ? -1 : 1;
          }
          
      

      You can tweak the functions to your liking. Give it a go and hopefully this gives you the desired results.

      -Jayesh

      Like

  3. Hi, I found, that multiple values can be inserted as string or array in first parameter of $jt->createNode,
    but is there a simple way to display first parent (id => 1, ‘weather_condition’ => ‘weather’… ) in ul list?

    Like

      • Hi Jayesh,
        thanks for that change with top parent, its great.

        And one thing what I notice:
        First item in array must be the parent of all items (tree root). Or only part of the tree will display.

        Like

    • If you are looking for an array which has an one-to-one correspondance to the tree then that will be difficult as both are different structures. On the other hand if you want to build a custom array for a specific task then that is not too difficult. Just initialize the array in the constructor for JTreeRecursiveIterator class and then replace the statements such as $this->_str = “html stuff”; with your specific code.

      Hope this helps.

      Jayesh

      Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s