Location: PHPKode > scripts > pTree > ptree/class.pTree.php
<?php

/**
 * pTree - Generic Tree Implementation
 *
 * This class provides a Tree Data Structure implementation
 *
 * @package pTree
 * @created 2005-02-20 01:04 GMT - 3:00hs
 * @updated 2005-02-20 20:28 GMT - 3:00hs
 *
 * @author Guilherme Blanco <hide@address.com>
 * @copyright Copyright® 2005, PontUKom Corp
 *
 * @version 1.0 Corrected isRoot, hasChilds, hasValue 
 *              Avoid removed nodes wrong parsing
 * @version 0.9 First public release
 *
 * @access protected
 */

/**
 * @global boolean Tree Data Structure Loaded
 */
if (!defined("ADT_TREE"))
    define("ADT_TREE", 1);

class pTree extends pTreeNode
{
    /**
     * @var string $separator Tree Path Separator
     * @access protected
     */
    protected $separator = "/";


    /**
     * Constructor - Generates a Tree Data Structure
     *
     * @access public
     * @param string $treeSeparator Path Char Separator
     * @param string $rootName Name of Root
     * @return object $this Tree
     */
    public function __construct($treeSeparator = "/", $rootName = "root")
    {
        parent::__construct($rootName);

        $this->separator = $treeSeparator;
    }


    /**
     * Add - Insert OR Update Tree Node with Value
     *
     * @access public
     * @param mixed $node Node Path or Object
     * @param mixed $value Node Value
     * @return object $treeNode Tree Node Created OR Updated
     */
    public function add($node, $value = null)
    {
        // Grabbing Node
        $treeNode = $this->getChild($node);
        
        // Retrieving basename
        $nodeName = $this->getLastName($node);

        // Checking possible node update
        if ($treeNode->getName() == $nodeName)
            // Node update
            $treeNode->setValue($value);
        else
            // Creating and returning Node
            $treeNode = $treeNode->addChild($nodeName, $value);

        // Returning Node
        return $treeNode;
    }


    /**
     * Remove - Remove Tree Node and All Sub-Childs
     *
     * @access public
     * @param mixed $node Node Name or Object
     */
    public function remove($node)
    {
        // Grabbing Node
        $treeNode = $this->getChild($node);
        // Retrieving Parent Node
        $parentNode = $treeNode->getParent();
        // Removing Node
        $parentNode->removeChild($treeNode);
    }


    /**
     * Get - Retrieves Node Value
     *
     * @access public
     * @param mixed $node Node Path or Object
     * @return mixed $nodeValue Tree Node Value
     */
    public function get($node)
    {
        // Grabbing Node
        $treeNode = $this->getChild($node);
        // Retrieving Node Value
        return $treeNode->getValue();
    }


    /**
     * Comment - Insert a Tree Node Comment
     *
     * @access public
     * @param mixed $node Node Name or Object
     * @param string $comment Node Comment
     */
    public function comment($node, $comment)
    {
        // Grabbing Node
        $treeNode = $this->getChild($node);
        // Inserting Node Comment
        $treeNode->addComment($comment);
    }


    /**
     * Get Child - Retrieve a Child Node of Tree
     *
     * @access protected
     * @param string $nodeName Name of Child Node
     * @return mixed $treeNode Tree Node
     */
    protected function getChild($nodeName)
    {
        // Splitting Path in an array
        $arr = explode($this->separator, trim(str_replace(" ", "_", $nodeName)));
        $child_block = $this;

        // Retrieving Node Inheritance
        for ($i = 0; $i < count($arr); $i++)
        {
            if (array_key_exists($arr[$i], $child_block->getAllChilds()))
                $child_block = $child_block->getChildNode($arr[$i]);
        }

        // Returning Node
        return $child_block;
    }


    /**
     * Get Root - Retrieve Root Node
     *
     * @access public
     * @return object $this Root Node of Tree
     */
    public function getRoot()
    {
        return $this;
    }


    /**
     * Is Root - Checks if a given Tree Node is the Root of Tree
     *
     * @access public
     * @param string $node Node Name
     * @return boolean $boolReturn Returns TRUE is Tree Node is the Root of the Tree; FALSE instead
     */
    public function isRoot($node)
    {
        // Grabbing Node
        $possRoot = $this->getChild($node);
        // Retrieving basename
        $nodeName = $this->getLastName($node);

        if ($possRoot->getName() === $nodeName && $possRoot->getParent() === $this)
            return true;
        else
            return false;
    }


    /**
     * Has Childs - Checks if a Tree Node has Childs or not
     *
     * @access public
     * @param string $node Node Name
     * @return boolean $boolReturn Returns TRUE is Tree Node has Childs and FALSE if not
     */
    public function hasChilds($node)
    {
        // Getting Node
        $treeNode = $this->getChild($node);
        // Retrieving basename
        $nodeName = $this->getLastName($node);

        if ($treeNode->getName() === $nodeName && count($treeNode->getAllChilds()) > 0)
            return true;

        return false;
    }


    /**
     * Has Value - Checks if a Tree Node has Value or not
     *
     * @access public
     * @param string $node Node Name
     * @return boolean $boolReturn Returns TRUE is Tree Node has Value; FALSE instead
     */
    public function hasValue($node)
    {
        // Getting Node
        $treeNode = $this->getChild($node);
        // Retrieving basename
        $nodeName = $this->getLastName($node);

        if ($treeNode->getName() === $nodeName && $treeNode->getValue() != null)
            return true;

        return false;
    }


    /**
     * To String - Creates a Human readable output of Tree Node
     *
     * @access public
     * @param integer $mode Output Mode
     * @return string $output Formatted readable output of Tree
     */
    public function toString($mode = 0)
    {
        $str = "";

        // Building formatted output of first level child Nodes
        foreach ($this->childNodes as $block_name => $block)
            $str .= $block->toString($mode);

        return $str;
    }


    /**
     * Get Last Name - Retrieves the basename of a given Node Path
     *
     * @access protected
     * @param string $nodePath Tree Node Path
     * @return string $nodeName Tree Node Basename (Node Name)
     */
    protected function getLastName($nodePath)
    {
        return substr(trim(str_replace(" ", "_", $nodePath)), ((strrpos($nodePath, $this->separator) == false) ? 0 : strrpos($nodePath, $this->separator) + 1), strlen($nodePath));
    }
};



/**
 * pTreeNode - Generic Node for Tree Implementation
 *
 * This class provides a Tree Node definition for generic tree data structure implementation
 *
 * @package pTreeNode
 * @created 2005-02-19 16:04 GMT - 3:00hs
 * @updated No updates yet
 *
 * @author Guilherme Blanco <hide@address.com>
 * @copyright Copyright® 2005, PontUKom Corp
 *
 * @version 1.0 First public release
 *
 * @access protected
 */

class pTreeNode
{
    /**
     * @var string $name Node Name
     * @access protected
     */
    protected $name = "";

    /**
     * @var string $value Node Value
     * @access protected
     */
    private $value = null;

    /**
     * @var object $parentNode Parent TreeNode Reference
     * @access protected
     */
    private $parentNode = null;

    /**
     * @var string $comment Node Comment
     * @access protected
     */
    private $comment = "";

    /**
     * @var array $childNodes Child Nodes
     * @access protected
     */
    protected $childNodes = array();

    /**
     * @var integer $depth Depth of Node
     * @access protected
     */
    private $depth = -1;


    /**
     * Constructor - Should not be called directly. Please use {@link addChild} instead.
     *
     * @access public
     * @param string $nodeName Name of Tree Node
     * @param object $parentNode Parent Tree Node reference, if any
     * @return object $this Tree Node
     * @see addChild
     */
    public function __construct($nodeName, $parentNode = null)
    {
        $this->name = trim(str_replace(" ", "_", $nodeName));

        // Checking level
        if ($parentNode != null)
        {
            $this->parentNode = $parentNode;
            $this->depth = $parentNode->depth + 1;
            $parentNode->childNodes[$this->name] = $this;
        }
    }


    /**
     * Destructor - Should not be called directly. This does the same as {@link removeAllChilds} method.
     *
     * @access private
     * @see removeAllChilds
     */
    public function __destruct()
    {
        $this->removeAllChilds();
    }


    /**
     * Get Child - Retrieve a Child Node of the given Tree Node
     *
     * @access protected
     * @param string $nodeName Name of Child Node
     * @return mixed $treeNode Tree Node
     */
    protected function getChildNode($nodeName)
    {
        return ((array_key_exists($nodeName, $this->childNodes)) ? $this->childNodes[$nodeName] : null);
    }


    /**
     * Get All Childs - Retrieve All Child Nodes of the given Tree Node
     *
     * @access protected
     * @return array $arrayTreeNodes Tree Nodes array
     */
    protected function getAllChilds()
    {
        return $this->childNodes;
    }


    /**
     * Remove Child - Remove Child Node
     *
     * @access protected
     * @param mixed $node Name of Child Node or Child Tree Node Object
     * @return boolean $boolRemoved TRUE
     * @see removeAllChilds
     */
    protected function removeChild($node)
    {
        // Retrieve Node, if node is a string
        $nodeItem = (!is_object($node)) ? $this->getChild($node) : $node;

        // Remove sub-Childs of Child
        $nodeItem->removeAllChilds();

        // Removing from Parent Tree Node
        $this->childNodes[$nodeItem->name] = null;
        unset($this->childNodes[$nodeItem->name]);
        unset($nodeItem);

        return true;
    }


    /**
     * Remove All Childs - Remove All Child Nodes
     *
     * @access protected
     * @return boolean $boolRemoved TRUE
     */
    protected function removeAllChilds()
    {
        // Removing childs
        foreach ($this->childNodes as $key => $value)
        {
            $this->childNodes[$key]->removeAllChilds();
            $this->childNodes[$key] = null;
            unset($this->childNodes[$key]);
        }

        $this->childNodes = array();
        $this->value = null;
    }


    /**
     * Add - Add a Tree Node with Value
     *
     * @access protected
     * @param string $node Node Name
     * @param mixed $value Value of new Node
     * @return object $generatedTreeNode Generated Tree Node
     */
    protected function addChild($node, $value = null)
    {
        // Tree Node doesn't exist; create one
        $nodeItem = new pTreeNode($node, $this);

        // Set up a Value
        $nodeItem->setValue($value);

        // Return new Tree Node
        return $nodeItem;
    }


    /**
     * Get Parent - Retrieve the parent Tree Node of item, or item if none
     *
     * @access public
     * @return object $treeNode Tree Node
     */
    public function getParent()
    {
        return (($this->parentNode != null) ? $this->parentNode : $this);
    }


    /**
     * Set Value - Set up a Value in Tree Node
     *
     * @access protected
     * @param mixed $nodeValue Value of a Tree Node
     */
    protected function setValue($nodeValue)
    {
        $this->value = $nodeValue;
    }


    /**
     * Get Value - Get the Value of given Tree Node
     *
     * @access public
     * @return mixed $nodeValue Value of Tree Node
     */
    public function getValue()
    {
        return $this->value;
    }


    /**
     * Get Depth - Grab Tree Node Depth
     *
     * @access public
     * @return integer $nodeDepth Depth of Tree Node
     */
    public function getDepth()
    {
        return $this->depth;
    }


    /**
     * Get Name - Retrieve Tree Node Name
     *
     * @access public
     * @return string $nodeName Name of Tree Node
     */
    public function getName()
    {
        return $this->name;
    }


    /**
     * Add Comment - Set up a Tree Node Comment
     *
     * @access protected
     * @param string $nodeComment Comment of Tree Node
     */
    protected function addComment($nodeComment = "")
    {
        $this->comment = $nodeComment;
    }


    /**
     * To String - Creates a Human readable output of Tree Node (reverse of {@link fromString} method)
     *
     * @access public
     * @param integer $mode Output Mode
     * @return string $output Formatted readable output of Tree
     * @see fromString
     */
    public function toString($mode = 0)
    {
        // Checking Mode Variables
        $creturn = (($mode === 0) ? "<br />" : "\r\n");
        $blank = (($mode === 0) ? "&nbsp;" : " ");
        $ident = str_repeat($blank, 4 * $this->depth);

        $str = "";

        // Building Node Comment
        if ($this->comment != "")
            $str .= $ident."#".$blank.str_replace(array("<br />", "<br>", "\r\n", "\n"), $creturn.$ident."#".$blank, $this->comment).$creturn;

        // Create Node
        $str .= $ident."[".$this->name." = ".$this->parseValue($this->value)."] {".((count($this->childNodes) > 0) ? $creturn : "");

        // Creating inner Nodes
        foreach ($this->childNodes as $block_name => $block)
            $str .= $block->toString($mode);

        // Finishing Node
        $str .= ((count($this->childNodes) > 0) ? $ident : "")."}".$creturn;

        // Returning...
        return $str;
    }


    /**
     * From String - Generates Tree Structure using Formatted String Entry (reverse of {@link toString} method)
     *
     * @access public
     * @param string $input Formatted input of Tree
     * @return object $this Tree
     * @see toString
     */
    public function fromString($input = "")
    {
        // No String, return
        if ($input == "") return;

        $curObj = $this;
        $curComment = "";

        // Wrap new lines
        $lines = explode("\n", $input);

        foreach ($lines as $line)
        {
            $line = trim(str_replace("\r", "", $line));

            // Comment line
            if (eregi('#(.*)', $line, $res))
                $curComment .= trim($res[1])."\n";
            // Node definition
            elseif (eregi('\[(.[^=]*)\s*=\s*(.*)\]\s*(.*)', $line, $res))
            {
                $value = $this->parseValue($res[2], 1);
                $curObj = $curObj->addChild(trim($res[1]), $value);
                $curObj->addComment(substr($curComment, 0, strlen($curComment) - 1));
                if (strstr($res[3], "}"))
                    $curObj = $curObj->getParent();
                $curComment = "";

            }
            // Bracket close
            elseif (substr($line, 0, 1) == "}")
                $curObj = $curObj->getParent();

            unset($res);
            unset($line);
        }

        // Checking error
        if ($curObj !== $this)
            trigger_error("<b>Tree:</b> Missing brackets in Node [".$curObj->getName()."]", E_USER_ERROR);
    }


    /**
     * Parse Value - Encode/Decode Value parameter
     *
     * @access private
     * @param mixed $nodeValue Value of Node (encoded or decoded)
     * @param integer $type Type of processment: [0] Encode / [1] Decode
     * @return mixed $nodeValue Value of Node
     */
    private function parseValue($nodeValue, $type = 0)
    {
        // Encode Type (Called with type argument set as 0 [default])
        if ($type == 0)
        {
            // Array
            if (is_array($nodeValue))
            {
                $newNodeValue = "(";
                foreach ($nodeValue as $key => $value)
                    $newNodeValue .= ((is_numeric($key)) ? $key : "\"".$key."\"")." => ".((is_numeric($value)) ? $value : "\"".$value."\"").", ";
                $newNodeValue = substr($newNodeValue, 0, strlen($newNodeValue) - 2).")";
            }
            // Object
            elseif (is_object($nodeValue))
                $newNodeValue = serialize($nodeValue);
            // String
            elseif (!is_numeric($nodeValue))
                $newNodeValue = "\"".$nodeValue."\"";
            // Number
            else
                $newNodeValue = $nodeValue;
        }
        // Decode Type (Called with type argument set and different of 0)
        else
        {
           $nodeValue = trim($nodeValue);

           // Array
           if (substr($nodeValue, 0, 1) == "(")
           {
               $newNodeValue = array();
               eregi('\((.[^\)]*)\)', $nodeValue, $nodeValue);
               $nodeValue= $nodeValue[1];
               $itens = explode(",", $nodeValue);

               for ($i = 0; $i < count($itens); $i++)
               {
                   eregi("[\"]*([^\"=]+)[\"]* => [\"]*([^\"]*)[\"]*", $itens[$i], $res);
                   if (isset($res))
                       $newNodeValue[trim($res[1])] = $res[2];
               }
           }
           // Object
           elseif (substr($nodeValue, 0, 2) == "O:")
               // Object serialized
               $newNodeValue = unserialize($nodeValue);
           // String
           elseif (!is_numeric($nodeValue))
                $newNodeValue = substr($nodeValue, 1, strlen($nodeValue) - 2);
           // Number
           else
                $newNodeValue = (($nodeValue == "") ? null : $nodeValue);
        }

        return $newNodeValue;
    }
};

?>
Return current item: pTree