<?php
/**
 * File containing the ezcTreeMemory class.
 *
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 * 
 *   http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 *
 * @license http://www.apache.org/licenses/LICENSE-2.0 Apache License, Version 2.0
 * @version //autogentag//
 * @filesource
 * @package Tree
 */

/**
 * ezcTreeMemory is an implementation of a tree backend that operates on
 * an in-memory tree structure. Meta-information is kept in objects of the
 * ezcTreeMemoryNode class.
 *
 * Example:
 * <code>
 * <?php
 *     // Create a new tree
 *     $tree = ezcTreeMemory::create( new ezcTreeMemoryDataStore() );
 *     // or
 *     $tree = new ezcTreeMemory( new ezcTreeMemoryDataStore() );
 * ?>
 * </code>
 *
 * See {@link ezcTree} for examples on how to operate on the tree.
 *
 * @property-read ezcTreeXmlDataStore $store
 *                The data store that is used for retrieving/storing data.
 * @property      string              $nodeClassName
 *                Which class is used as tree node - this class *must* inherit
 *                the ezcTreeNode class.
 *
 * @package Tree
 * @version //autogentag//
 * @mainclass
 */
class ezcTreeMemory extends ezcTree
{
    /**
     * Contains a list of all nodes, indexed by node ID that link directly to the create node so that they can be looked up quickly.
     *
     * @var array(string=>ezcTreeMemoryNode)
     */
    private $nodeList = array();

    /**
     * Contains the root node.
     *
     * @var ezcTreeMemoryNode
     */
    private $rootNode;

    /**
     * Stores the last auto generated ID that was used.
     *
     * @var integer $autoNodeId
     */
    private $autoNodeId = 0;

    /**
     * Constructs a new ezcTreeMemory object.
     *
     * The store that is used for data storage should be passed as the
     * $store argument.
     *
     * @param ezcTreeMemoryDataStore $store
     */
    protected function __construct( ezcTreeMemoryDataStore $store )
    {
        $this->properties['store'] = $store;
        $this->properties['autoId'] = false;
    }

    /**
     * This method generates the next node ID.
     *
     * @return integer
     */
    protected function generateNodeID()
    {
        $this->autoNodeId++;
        return $this->autoNodeId;
    }

    /**
     * A factory method that creates a new empty tree using the data store $store.
     *
     * @param ezcTreeMemoryDataStore $store
     * @return ezcTreeMemory
     */
    public static function create( ezcTreeMemoryDataStore $store )
    {
        $newTree = new ezcTreeMemory( $store );
        $newTree->nodeList = null;
        $newTree->rootNode = null;
        return $newTree;
    }

    /**
     * Returns whether the node with ID $nodeId exists.
     *
     * @param string $nodeId
     * @return bool
     */
    public function nodeExists( $nodeId )
    {
        return isset( $this->nodeList[$nodeId] );
    }

    /**
     * Returns the node identified by the ID $nodeId.
     *
     * @param string $nodeId
     * @throws ezcTreeInvalidIdException if there is no node with ID $nodeId
     * @return ezcTreeNode
     */
    public function fetchNodeById( $nodeId )
    {
        return $this->getNodeById( $nodeId )->node;
    }

    /**
     * Returns the node container for node $nodeId.
     *
     * @param string $nodeId
     * @throws ezcTreeInvalidIdException if there is no node with ID $nodeId
     * @return ezcTreeMemoryNode
     */
    private function getNodeById( $nodeId )
    {
        if ( !$this->nodeExists( $nodeId ) )
        {
            throw new ezcTreeUnknownIdException( $nodeId );
        }
        return $this->nodeList[$nodeId];
    }

    /**
     * Returns all the children of the node with ID $nodeId.
     *
     * @param string $nodeId
     * @return ezcTreeNodeList
     */
    public function fetchChildren( $nodeId )
    {
        $treeNode = $this->getNodeById( $nodeId );
        $list = new ezcTreeNodeList;
        foreach ( $treeNode->children as $nodeId => $child )
        {
            $list->addNode( $child->node );
        }
        return $list;
    }

    /**
     * Returns the parent node of the node with ID $nodeId.
     *
     * This method returns null if there is no parent node.
     *
     * @param string $nodeId
     * @return ezcTreeNode
     */
    public function fetchParent( $nodeId )
    {
        $treeNode = $this->getNodeById( $nodeId );
        $parentNode = $treeNode->parent;
        return $parentNode !== null ? $parentNode->node : null;
    }

    /**
     * Returns all the nodes in the path from the root node to the node with ID
     * $nodeId, including those two nodes.
     *
     * @param string $nodeId
     * @return ezcTreeNodeList
     */
    public function fetchPath( $nodeId )
    {
        $list = new ezcTreeNodeList;
        $memoryNode = $this->getNodeById( $nodeId );

        $nodes = array();
        $nodes[] = $memoryNode->node;

        $memoryNode = $memoryNode->parent;

        while ( $memoryNode !== null )
        {
            $nodes[] =  $memoryNode->node;
            $memoryNode = $memoryNode->parent;
        }

        $list = new ezcTreeNodeList;
        foreach ( array_reverse( $nodes ) as $node )
        {
            $list->addNode( $node );
        }
        return $list;
    }

    /**
     * Adds the children nodes of the node $memoryNode to the
     * ezcTreeNodeList $list.
     *
     * @param ezcTreeNodeList $list
     * @param ezcTreeMemoryNode $memoryNode
     */
    private function addChildNodesDepthFirst( ezcTreeNodeList $list, ezcTreeMemoryNode $memoryNode )
    {
        foreach ( $memoryNode->children as $nodeId => $childMemoryNode )
        {
            $list->addNode( $childMemoryNode->node );
            $this->addChildNodesDepthFirst( $list, $childMemoryNode );
        }
    }

    /**
     * Returns the node with ID $nodeId and all its children, sorted accoring to
     * the {@link http://en.wikipedia.org/wiki/Depth-first_search Depthth-first sorting}
     * algorithm.
     *
     * @param string $nodeId
     * @return ezcTreeNodeList
     */
    public function fetchSubtreeDepthFirst( $nodeId )
    {
        $list = new ezcTreeNodeList;
        $memoryNode = $this->getNodeById( $nodeId );
        $list->addNode( $memoryNode->node );
        $this->addChildNodesDepthFirst( $list, $memoryNode );
        return $list;
    }

    /**
     * Alias for fetchSubtreeDepthFirst().
     *
     * @param string $nodeId
     * @return ezcTreeNodeList
     */
    public function fetchSubtree( $nodeId )
    {
        return $this->fetchSubtreeDepthFirst( $nodeId );
    }

    /**
     * Adds the children nodes of the node $memoryNode to the
     * ezcTreeNodeList $list.
     *
     * @param ezcTreeNodeList $list
     * @param ezcTreeMemoryNode $memoryNode
     */
    private function addChildNodesBreadthFirst( ezcTreeNodeList $list, ezcTreeMemoryNode $memoryNode )
    {
        foreach ( $memoryNode->children as $nodeId => $childMemoryNode )
        {
            $list->addNode( $childMemoryNode->node );
        }
        foreach ( $memoryNode->children as $nodeId => $childMemoryNode )
        {
            $this->addChildNodesBreadthFirst( $list, $childMemoryNode );
        }
    }

    /**
     * Returns the node with ID $nodeId and all its children, sorted according to
     * the {@link http://en.wikipedia.org/wiki/Breadth-first_search Breadth-first sorting}
     * algorithm.
     *
     * @param string $nodeId
     * @return ezcTreeNodeList
     */
    public function fetchSubtreeBreadthFirst( $nodeId )
    {
        $list = new ezcTreeNodeList;
        $memoryNode = $this->getNodeById( $nodeId );
        $list->addNode( $memoryNode->node );
        $this->addChildNodesBreadthFirst( $list, $memoryNode );
        return $list;
    }

    /**
     * Returns the number of direct children of the node with ID $nodeId.
     *
     * @param string $nodeId
     * @return int
     */
    public function getChildCount( $nodeId )
    {
        return count( $this->getNodeById( $nodeId )->children );
    }

    /**
     * Helper method that iterates recursively over the children of $node to
     * count the number of children.
     *
     * @param integer $count
     * @param ezcTreeMemoryNode $node
     */
    private function countChildNodes( &$count, ezcTreeMemoryNode $node )
    {
        foreach ( $node->children as $nodeId => $node )
        {
            $count++;
            $this->countChildNodes( $count, $node );
        }
    }

    /**
     * Returns the number of children of the node with ID $nodeId, recursively
     *
     * @param string $nodeId
     * @return int
     */
    public function getChildCountRecursive( $nodeId )
    {
        $count = 0;
        $node = $this->getNodeById( $nodeId );
        $this->countChildNodes( $count, $node );
        return $count;
    }

    /**
     * Returns the distance from the root node to the node with ID $nodeId
     *
     * @param string $nodeId
     * @return int
     */
    public function getPathLength( $nodeId )
    {
        $childNode = $this->getNodeById( $nodeId );
        $length = -1;

        while ( $childNode !== null )
        {
            $childNode = $childNode->parent;
            $length++;
        }
        return $length;
    }

    /**
     * Returns whether the node with ID $nodeId has children
     *
     * @param string $nodeId
     * @return bool
     */
    public function hasChildNodes( $nodeId )
    {
        return count( $this->getNodeById( $nodeId )->children ) > 0;
    }

    /**
     * Returns whether the node with ID $childId is a direct child of the node
     * with ID $parentId
     *
     * @param string $childId
     * @param string $parentId
     * @return bool
     */
    public function isChildOf( $childId, $parentId )
    {
        $childNode = $this->getNodeById( $childId );
        $parentNode = $this->getNodeById( $parentId );

        if ( $childNode->parent->node === $parentNode->node )
        {
            return true;
        }
        return false;
    }

    /**
     * Returns whether the node with ID $childId is a direct or indirect child
     * of the node with ID $parentId
     *
     * @param string $childId
     * @param string $parentId
     * @return bool
     */
    public function isDescendantOf( $childId, $parentId )
    {
        $childNode = $this->getNodeById( $childId );
        $parentNode = $this->getNodeById( $parentId );

        if ( $childNode === $parentNode )
        {
            return false;
        }

        while ( $childNode !== null )
        {
            if ( $childNode->node === $parentNode->node )
            {
                    return true;
            }
            $childNode = $childNode->parent;
        }
        return false;
    }

    /**
     * Returns whether the nodes with IDs $child1Id and $child2Id are siblings
     * (ie, the share the same parent)
     *
     * @param string $child1Id
     * @param string $child2Id
     * @return bool
     */
    public function isSiblingOf( $child1Id, $child2Id )
    {
        $elem1 = $this->getNodeById( $child1Id );
        $elem2 = $this->getNodeById( $child2Id );
        return (
            ( $child1Id !== $child2Id ) && 
            ( $elem1->parent === $elem2->parent )
        );
    }

    /**
     * Sets a new node as root node, this wipes also out the whole tree
     *
     * @param ezcTreeNode $node
     */
    public function setRootNode( ezcTreeNode $node )
    {
        // wipe nodelist and data
        $this->nodeList = array();
        $this->store->deleteDataForAllNodes();

        // replace root node
        $newObj = new ezcTreeMemoryNode( $node, array() );
        $this->rootNode = $newObj;

        // Add to node list
        $this->nodeList[$node->id] = $newObj;
    }

    /**
     * Returns the root node
     *
     * This methods returns null if there is no root node.
     *
     * @return ezcTreeNode
     */
    public function getRootNode()
    {
        if ( $this->rootNode )
        {
            return $this->rootNode->node;
        }
        return null;
    }

    /**
     * Adds the node $childNode as child of the node with ID $parentId
     *
     * @param string $parentId
     * @param ezcTreeNode $childNode
     */
    public function addChild( $parentId, ezcTreeNode $childNode )
    {
        if ( $this->inTransaction )
        {
            $this->addTransactionItem( new ezcTreeTransactionItem( ezcTreeTransactionItem::ADD, $childNode, null, $parentId ) );
            return;
        }

        // Locate parent node
        $parentMemoryNode = $this->getNodeById( $parentId );

        // Create new node
        $newObj = new ezcTreeMemoryNode( $childNode, array(), $parentMemoryNode );

        // Append to parent node
        $parentMemoryNode->children[$childNode->id] = $newObj;

        // Add to node list
        $this->nodeList[$childNode->id] = $newObj;
    }

    /**
     * Deletes the node with ID $nodeId from the tree, including all its children
     *
     * @param string $nodeId
     */
    public function delete( $nodeId )
    {
        if ( $this->inTransaction )
        {
            $this->addTransactionItem( new ezcTreeTransactionItem( ezcTreeTransactionItem::DELETE, null, $nodeId ) );
            return;
        }

        // locate node to move
        $nodeToDelete = $this->getNodeById( $nodeId );

        // fetch the whole subtree and delete all the associated data
        $children = $nodeToDelete->node->fetchSubtree();
        $this->store->deleteDataForNodes( $children );

        // Use the parent to remove the child
        unset( $nodeToDelete->parent->children[$nodeId] );

        // Remove the node and all its children
        foreach ( new ezcTreeNodeListIterator( $this, $children ) as $nodeId => $data )
        {
            unset( $this->nodeList[$nodeId] );
        }
    }

    /**
     * Moves the node with ID $nodeId as child to the node with ID $targetParentId
     *
     * @param string $nodeId
     * @param string $targetParentId
     */
    public function move( $nodeId, $targetParentId )
    {
        if ( $this->inTransaction )
        {
            $this->addTransactionItem( new ezcTreeTransactionItem( ezcTreeTransactionItem::MOVE, null, $nodeId, $targetParentId ) );
            return;
        }

        // locate node to move
        $nodeToMove = $this->getNodeById( $nodeId );

        // locate new parent
        $newParent = $this->getNodeById( $targetParentId );

        // new placement for node
        $newParent->children[$nodeId] = $nodeToMove;

        // remove old location from previous parent
        unset( $nodeToMove->parent->children[$nodeId] );

        // update parent attribute of the node
        $nodeToMove->parent = $newParent;
    }

    /**
     * Fixates the transaction.
     */
    public function fixateTransaction()
    {
    }
}
?>