Tree/src/backends/xml.php - zetacomponents - Git at Google

 <?php
 /**
  * File containing the ezcTreeXml 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
  */

 /**
  * ezcTreeXml is an implementation of a tree backend that operates on
  * an XML file.
  *
  * Example:
  * <code>
  * <?php
  *     // Create a new tree in a new XML file
  *     $tree = ezcTreeXml::create(
  *         'new-tree.xml',
  *         new ezcTreeXmlInternalDataStore()
  *     );
  *
  *     // Open an existing XML file containing a tree structure
  *     $tree = new ezcTreeXml(
  *         'existing-tree.xml',
  *         new ezcTreeXmlInternalDataStore()
  *     );
  * ?>
  * </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-read string              $prefix
  *                The prefix that is used to prefix node IDs with in the tree.
  * @property      string              $nodeClassName
  *                Which class is used as tree node - this class *must* inherit
  *                the ezcTreeNode class.
  *
  * @package Tree
  * @version //autogentag//
  * @mainclass
  */
 class ezcTreeXml extends ezcTree
 {
     /**
      * Contains the relax-NG schema to validate the tree XML.
      */
     const relaxNG = '<?xml version="1.0" encoding="UTF-8"?>
 <grammar xmlns:etd="http://components.ez.no/Tree/data" ns="http://components.ez.no/Tree" xmlns="http://relaxng.org/ns/structure/1.0" datatypeLibrary="http://www.w3.org/2001/XMLSchema-datatypes">
   <start>
     <element name="tree">
       <optional>
         <attribute name="prefix">
           <data type="ID"/>
         </attribute>
       </optional>
       <optional>
         <attribute name="lastNodeId">
           <data type="string"/>
         </attribute>
       </optional>
       <optional>
         <ref name="node"/>
       </optional>
     </element>
   </start>
   <define name="node">
     <element name="node">
       <attribute name="id">
         <data type="ID"/>
       </attribute>
       <optional>
         <element name="etd:data">
           <text/>
         </element>
       </optional>
       <zeroOrMore>
         <ref name="node"/>
       </zeroOrMore>
     </element>
   </define>
 </grammar>';

     /**
      * Contains the DOM Tree that all operations will be done on.
      *
      * When the tree object is constructed the XML is parsed with DOM and
      * stored into this member variable. When the tree is modified the changes
      * are then flushed to disk with the saveFile() method.
      *
      * @var DOMDocument $dom
      */
     private $dom;

     /**
      * The file name that contains the tree as XML string.
      *
      * @var string $xmlFile
      */
     private $xmlFile;

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

     /**
      * Constructs a new ezcTreeXml object from the XML data in $xmlFile and using
      * the $store to retrieve data from.
      *
      * @param string $xmlFile
      * @param ezcTreeXmlDataStore $store
      */
     public function __construct( $xmlFile, ezcTreeXmlDataStore $store )
     {
         if ( !file_exists( $xmlFile ) )
         {
             throw new ezcBaseFileNotFoundException( $xmlFile, "XML" );
         }

         $previous = libxml_use_internal_errors( true );

         $dom = new DomDocument();
         $dom->load( $xmlFile );
         $dom->formatOutput = true;

         $errors = libxml_get_errors();
         libxml_clear_errors();
         if ( count( $errors ) )
         {
             throw new ezcTreeInvalidXmlException( $xmlFile, $errors );
         }

         $valid = $dom->relaxNGValidateSource( self::relaxNG );
         if ( !$valid )
         {
             $errors = libxml_get_errors();
             libxml_clear_errors();
             throw new ezcTreeInvalidXmlFormatException( $xmlFile, $errors );
         }

         libxml_use_internal_errors( $previous );

         // Associate the DOM tree with the data store
         $store->setDomTree( $dom );

         // Figure out the prefix - which is the "prefix" attribute on the root node.
         $document = $dom->documentElement;
         $prefix = $document->getAttribute( 'prefix' );

         // Figure out the last auto generated ID
         $autoId = false;
         $this->autoNodeId = $document->getAttribute( 'lastNodeId' );
         if ( $this->autoNodeId !== "" )
         {
             $autoId = true;
         }

         // Set member variables
         $this->dom = $dom;
         $this->xmlFile = $xmlFile;
         $this->properties['store'] = $store;
         $this->properties['prefix'] = $prefix;
         $this->properties['autoId'] = $autoId;
     }

     /**
      * Returns the value of the property $name.
      *
      * @throws ezcBasePropertyNotFoundException if the property does not exist.
      * @param string $name
      * @ignore
      */
     public function __get( $name )
     {
         switch ( $name )
         {
             case 'prefix':
                 return $this->properties[$name];
         }
         return parent::__get( $name );
     }

     /**
      * Sets the property $name to $value.
      *
      * @throws ezcBasePropertyNotFoundException if the property does not exist.
      * @throws ezcBasePropertyPermissionException if a read-only property is
      *         tried to be modified.
      * @param string $name
      * @param mixed $value
      * @ignore
      */
     public function __set( $name, $value )
     {
         switch ( $name )
         {
             case 'prefix':
                 throw new ezcBasePropertyPermissionException( $name, ezcBasePropertyPermissionException::READ );

             default:
                 return parent::__set( $name, $value );
         }
     }

     /**
      * Returns true if the property $name is set, otherwise false.
      *
      * @param string $name
      * @return bool
      * @ignore
      */
     public function __isset( $name )
     {
         switch ( $name )
         {
             case 'prefix':
                 return isset( $this->properties[$name] );

             default:
                 return parent::__isset( $name );
         }
     }

     /**
      * Creates a new XML tree in the file $xmlFile using $store as data store.
      *
      * The $prefix option can be used to change the prefix that is used for IDs
      * in the created tree. By default this is set to "id" so that numerical
      * node IDs are not a problem.
      *
      * @param string $xmlFile
      * @param ezcTreeXmlDataStore $store
      * @param string $prefix
      * @return ezcTreeXml
      */
     public static function create( $xmlFile, ezcTreeXmlDataStore $store, $prefix = 'id' )
     {
         $dom = new DomDocument( '1.0', 'utf-8' );
         $dom->formatOutput = true;

         $element = $dom->createElement( 'tree' );
         $element->setAttributeNode( new DOMAttr( 'xmlns', 'http://components.ez.no/Tree' ) );
         $element->setAttributeNode( new DOMAttr( 'xmlns:etd', 'http://components.ez.no/Tree/data' ) );
         if ( $prefix !== null )
         {
             $element->setAttributeNode( new DOMAttr( 'prefix', $prefix ) );
         }

         $dom->appendChild( $element );

         $dom->save( $xmlFile );
         return new ezcTreeXml( $xmlFile, $store, $prefix );
     }

     /**
      * Saves the internal DOM representation of the tree back to disk.
      */
     public function saveFile()
     {
         $this->dom->save( $this->xmlFile );
     }

     /**
      * This method generates the next node ID.
      *
      * It uses the stored last generated ID, and also stores this in an
      * attribute on the root node so that it can be correctly incremented
      * without having to search for the last generated ID in the whole tree.
      *
      * @return integer
      */
     protected function generateNodeID()
     {
         $this->autoNodeId++;

         $document = $this->dom->documentElement;
         $document->setAttributeNode( new DOMAttr( 'lastNodeId', $this->autoNodeId ) );

         return $this->autoNodeId;
     }

     /**
      * Returns whether the node with ID $nodeId exists.
      *
      * @param string $nodeId
      * @return bool
      */
     public function nodeExists( $nodeId )
     {
         $elem = $this->dom->getElementById( "{$this->properties['prefix']}$nodeId" );
         return ( $elem !== null ) ? true : false;
     }

     /**
      * Retrieves a DOMElement containing the node with node ID $nodeId.
      *
      * @param string $nodeId
      * @return DOMElement
      */
     private function getNodeById( $nodeId )
     {
         $node = $this->dom->getElementById( "{$this->properties['prefix']}$nodeId" );
         if ( !$node )
         {
             throw new ezcTreeUnknownIdException( $nodeId );
         }
         return $node;
     }

     /**
      * Fetches all the child "node" DOM elements of the node with ID $nodeId.
      *
      * @param string $nodeId
      * @return array(string)
      */
     private function fetchChildIds( $nodeId )
     {
         $childNodes = array();
         $elem = $this->getNodeById( $nodeId );
         $children = $elem->childNodes;
         foreach ( $children as $child )
         {
             if ( $child->nodeType === XML_ELEMENT_NODE && $child->tagName == "node" )
             {
                 $nodeId = substr( $child->getAttribute( 'id' ), strlen( $this->properties['prefix'] ) );
                 $childNodes[] = $nodeId;
             }
         }
         return $childNodes;
     }

     /**
      * Returns all the children of the node with ID $nodeId.
      *
      * @param string $nodeId
      * @return ezcTreeNodeList
      */
     public function fetchChildren( $nodeId )
     {
         $className = $this->properties['nodeClassName'];
         $list = new ezcTreeNodeList;
         foreach ( $this->fetchChildIds( $nodeId ) as $childId )
         {
             $list->addNode( new $className( $this, $childId ) );
         }
         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 )
     {
         $className = $this->properties['nodeClassName'];
         $elem = $this->getNodeById( $nodeId );
         $elem = $elem->parentNode;
         $parentId = $elem !== null ? substr( $elem->getAttribute( 'id' ), strlen( $this->properties['prefix'] ) ) : null;
         if ( $parentId === false )
         {
             return null;
         }
         return new $className( $this, $parentId );
     }

     /**
      * 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 )
     {
         $className = $this->properties['nodeClassName'];

         $nodes = array();
         $nodes[] = new $className( $this, $nodeId );

         $elem = $this->getNodeById( $nodeId );
         $elem = $elem->parentNode;

         while ( $elem !== null && $elem->nodeType == XML_ELEMENT_NODE && $elem->tagName == 'node' )
         {
             $id = substr( $elem->getAttribute( 'id' ), strlen( $this->properties['prefix'] ) );
             $nodes[] = new $className( $this, $id );
             $elem = $elem->parentNode;
         }

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

     /**
      * Adds the children nodes of the node with ID $nodeId to the
      * ezcTreeNodeList $list.
      *
      * @param ezcTreeNodeList $list
      * @param string          $nodeId
      */
     private function addChildNodesDepthFirst( ezcTreeNodeList $list, $nodeId )
     {
         $className = $this->properties['nodeClassName'];
         foreach ( $this->fetchChildIds( $nodeId ) as $childId )
         {
             $list->addNode( new $className( $this, $childId ) );
             $this->addChildNodesDepthFirst( $list, $childId );
         }
     }

     /**
      * Returns the node with ID $nodeId and all its children, sorted according to
      * the {@link http://en.wikipedia.org/wiki/Depth-first_search Depth-first sorting}
      * algorithm.
      *
      * @param string $nodeId
      * @return ezcTreeNodeList
      */
     public function fetchSubtreeDepthFirst( $nodeId )
     {
         $className = $this->properties['nodeClassName'];
         $list = new ezcTreeNodeList;
         $list->addNode( new $className( $this, $nodeId ) );
         $this->addChildNodesDepthFirst( $list, $nodeId );
         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 with ID $nodeId to the
      * ezcTreeNodeList $list.
      *
      * @param ezcTreeNodeList $list
      * @param string          $nodeId
      */
     private function addChildNodesBreadthFirst( ezcTreeNodeList $list, $nodeId )
     {
         $className = $this->properties['nodeClassName'];
         $childIds = $this->fetchChildIds( $nodeId );
         foreach ( $childIds as $childId )
         {
             $list->addNode( new $className( $this, $childId ) );
         }
         foreach ( $childIds as $childId )
         {
             $this->addChildNodesDepthFirst( $list, $childId );
         }
     }

     /**
      * 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 )
     {
         $className = $this->properties['nodeClassName'];
         $list = new ezcTreeNodeList;
         $list->addNode( new $className( $this, $nodeId ) );
         $this->addChildNodesBreadthFirst( $list, $nodeId );
         return $list;
     }

     /**
      * Returns the number of direct children of the node with ID $nodeId.
      *
      * @param string $nodeId
      * @return int
      */
     public function getChildCount( $nodeId )
     {
         $count = 0;
         $elem = $this->getNodeById( $nodeId );
         $children = $elem->childNodes;
         foreach ( $children as $child )
         {
             if ( $child->nodeType === XML_ELEMENT_NODE && $child->tagName == "node" )
             {
                 $count++;
             }
         }
         return $count;
     }

     /**
      * Adds the number of children with for the node with ID $nodeId nodes to
      * $count, recursively.
      *
      * @param int $count
      * @param string $nodeId
      */
     private function countChildNodes( &$count, $nodeId )
     {
         foreach ( $this->fetchChildIds( $nodeId ) as $childId )
         {
             $count++;
             $this->countChildNodes( $count, $childId );
         }
     }

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

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

         while ( $elem !== null && $elem->nodeType == XML_ELEMENT_NODE )
         {
             $elem = $elem->parentNode;
             $length++;
         }
         return $length;
     }

     /**
      * Returns whether the node with ID $nodeId has children.
      *
      * @param string $nodeId
      * @return bool
      */
     public function hasChildNodes( $nodeId )
     {
         $elem = $this->getNodeById( $nodeId );
         $children = $elem->childNodes;
         foreach ( $children as $child )
         {
             if ( $child->nodeType === XML_ELEMENT_NODE && $child->tagName == "node" )
             {
                 return true;
             }
         }
         return false;
     }

     /**
      * 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 )
     {
         $elem = $this->getNodeById( $childId );
         $parentElem = $elem->parentNode;
         $nodeId = $parentElem->getAttribute( 'id' );
         if ( $nodeId === "{$this->properties['prefix']}$parentId" )
         {
             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 )
     {
         $elem = $this->getNodeById( $childId );
         $elem = $elem->parentNode;

         while ( $elem !== null && $elem->nodeType == XML_ELEMENT_NODE )
         {
             $nodeId = $elem->getAttribute( 'id' );
             if ( $nodeId === "{$this->properties['prefix']}$parentId" )
             {
                     return true;
             }
             $elem = $elem->parentNode;
         }
         return false;
     }

     /**
      * Returns whether the nodes with IDs $child1Id and $child2Id are siblings
      * (ie, they 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->parentNode->getAttribute( 'id' ) === $elem2->parentNode->getAttribute( 'id' ) )
         );
     }

     /**
      * Sets a new node as root node, this also wipes out the whole tree.
      *
      * @param ezcTreeNode $node
      */
     public function setRootNode( ezcTreeNode $node )
     {
         $document = $this->dom->documentElement;

         // remove old root node(s)
         foreach ( $document->childNodes as $childNode )
         {
             if ( $childNode->nodeType == XML_ELEMENT_NODE && $childNode->tagName === 'node' )
             {
                 $nodeId = substr( $childNode->getAttribute( 'id' ), strlen( $this->properties['prefix'] ) );
                 $this->delete( $nodeId );
             }
         }
         $this->store->deleteDataForAllNodes();

         // Create new root node
         $root = $this->dom->createElement( 'node' );
         $root->setAttributeNode( new DOMAttr( 'id', "{$this->properties['prefix']}{$node->id}" ) );
         $root->setIdAttribute( 'id', true );
         $document->appendChild( $root );
         $this->store->storeDataForNode( $node, $node->data );
         $this->saveFile();
     }

     /**
      * Returns the root node.
      *
      * This methods returns null if there is no root node.
      *
      * @return ezcTreeNode
      */
     public function getRootNode()
     {
         $className = $this->properties['nodeClassName'];
         $document = $this->dom->documentElement;

         foreach ( $document->childNodes as $childNode )
         {
             if ( $childNode->nodeType == XML_ELEMENT_NODE && $childNode->tagName == 'node' )
             {
                 $nodeId = substr( $childNode->getAttribute( 'id' ), strlen( $this->properties['prefix'] ) );
                 return new $className( $this, $nodeId );
             }
         }
         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
         $elem = $this->getNodeById( $parentId );

         // Create new DOM node
         $child = $this->dom->createElement( 'node' );
         $child->setAttributeNode( new DOMAttr( 'id', "{$this->properties['prefix']}{$childNode->id}" ) );
         $child->setIdAttribute( 'id', true );

         // Append to parent node
         $elem->appendChild( $child );
         $this->store->storeDataForNode( $childNode, $childNode->data );

         if ( !$this->inTransactionCommit )
         {
             $this->saveFile();
         }
     }

     /**
      * 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;
         }

         // Delete all the associated data
         $nodeList = $this->fetchSubtree( $nodeId );
         $this->store->deleteDataForNodes( $nodeList );

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

         // Remove the ID on all children by hand as this would crash in PHP <= 5.2.3
         $nodeToDelete->removeAttribute( "id" );

         $children = $nodeToDelete->getElementsByTagName( 'node' );
         foreach ( $children as $child )
         {
             $child->removeAttribute( "id" );
         }

         // Use the parent to remove the child
         $nodeToDelete->parentNode->removeChild( $nodeToDelete );

         if ( !$this->inTransactionCommit )
         {
             $this->saveFile();
         }
     }

     /**
      * 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
         $parent = $this->getNodeById( $targetParentId );

         $parent->appendChild( $nodeToMove );

         if ( !$this->inTransactionCommit )
         {
             $this->saveFile();
         }
     }

     /**
      * Fixates the transaction (saves the XML file).
      */
     public function fixateTransaction()
     {
         $this->saveFile();
     }
 }
 ?>
	<?php
	/**
	* File containing the ezcTreeXml 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
	*/

	/**
	* ezcTreeXml is an implementation of a tree backend that operates on
	* an XML file.
	*
	* Example:
	* <code>
	* <?php
	* // Create a new tree in a new XML file
	* $tree = ezcTreeXml::create(
	* 'new-tree.xml',
	* new ezcTreeXmlInternalDataStore()
	* );
	*
	* // Open an existing XML file containing a tree structure
	* $tree = new ezcTreeXml(
	* 'existing-tree.xml',
	* new ezcTreeXmlInternalDataStore()
	* );
	* ?>
	* </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-read string $prefix
	* The prefix that is used to prefix node IDs with in the tree.
	* @property string $nodeClassName
	* Which class is used as tree node - this class must inherit
	* the ezcTreeNode class.
	*
	* @package Tree
	* @version //autogentag//
	* @mainclass
	*/
	class ezcTreeXml extends ezcTree
	{
	/**
	* Contains the relax-NG schema to validate the tree XML.
	*/
	const relaxNG = '<?xml version="1.0" encoding="UTF-8"?>
	<grammar xmlns:etd="http://components.ez.no/Tree/data" ns="http://components.ez.no/Tree" xmlns="http://relaxng.org/ns/structure/1.0" datatypeLibrary="http://www.w3.org/2001/XMLSchema-datatypes">
	<start>
	<element name="tree">
	<optional>
	<attribute name="prefix">
	<data type="ID"/>
	</attribute>
	</optional>
	<optional>
	<attribute name="lastNodeId">
	<data type="string"/>
	</attribute>
	</optional>
	<optional>
	<ref name="node"/>
	</optional>
	</element>
	</start>
	<define name="node">
	<element name="node">
	<attribute name="id">
	<data type="ID"/>
	</attribute>
	<optional>
	<element name="etd:data">
	<text/>
	</element>
	</optional>
	<zeroOrMore>
	<ref name="node"/>
	</zeroOrMore>
	</element>
	</define>
	</grammar>';

	/**
	* Contains the DOM Tree that all operations will be done on.
	*
	* When the tree object is constructed the XML is parsed with DOM and
	* stored into this member variable. When the tree is modified the changes
	* are then flushed to disk with the saveFile() method.
	*
	* @var DOMDocument $dom
	*/
	private $dom;

	/**
	* The file name that contains the tree as XML string.
	*
	* @var string $xmlFile
	*/
	private $xmlFile;

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

	/**
	* Constructs a new ezcTreeXml object from the XML data in $xmlFile and using
	* the $store to retrieve data from.
	*
	* @param string $xmlFile
	* @param ezcTreeXmlDataStore $store
	*/
	public function __construct( $xmlFile, ezcTreeXmlDataStore $store )
	{
	if ( !file_exists( $xmlFile ) )
	{
	throw new ezcBaseFileNotFoundException( $xmlFile, "XML" );
	}

	$previous = libxml_use_internal_errors( true );

	$dom = new DomDocument();
	$dom->load( $xmlFile );
	$dom->formatOutput = true;

	$errors = libxml_get_errors();
	libxml_clear_errors();
	if ( count( $errors ) )
	{
	throw new ezcTreeInvalidXmlException( $xmlFile, $errors );
	}

	$valid = $dom->relaxNGValidateSource( self::relaxNG );
	if ( !$valid )
	{
	$errors = libxml_get_errors();
	libxml_clear_errors();
	throw new ezcTreeInvalidXmlFormatException( $xmlFile, $errors );
	}

	libxml_use_internal_errors( $previous );

	// Associate the DOM tree with the data store
	$store->setDomTree( $dom );

	// Figure out the prefix - which is the "prefix" attribute on the root node.
	$document = $dom->documentElement;
	$prefix = $document->getAttribute( 'prefix' );

	// Figure out the last auto generated ID
	$autoId = false;
	$this->autoNodeId = $document->getAttribute( 'lastNodeId' );
	if ( $this->autoNodeId !== "" )
	{
	$autoId = true;
	}

	// Set member variables
	$this->dom = $dom;
	$this->xmlFile = $xmlFile;
	$this->properties['store'] = $store;
	$this->properties['prefix'] = $prefix;
	$this->properties['autoId'] = $autoId;
	}

	/**
	* Returns the value of the property $name.
	*
	* @throws ezcBasePropertyNotFoundException if the property does not exist.
	* @param string $name
	* @ignore
	*/
	public function __get( $name )
	{
	switch ( $name )
	{
	case 'prefix':
	return $this->properties[$name];
	}
	return parent::__get( $name );
	}

	/**
	* Sets the property $name to $value.
	*
	* @throws ezcBasePropertyNotFoundException if the property does not exist.
	* @throws ezcBasePropertyPermissionException if a read-only property is
	* tried to be modified.
	* @param string $name
	* @param mixed $value
	* @ignore
	*/
	public function __set( $name, $value )
	{
	switch ( $name )
	{
	case 'prefix':
	throw new ezcBasePropertyPermissionException( $name, ezcBasePropertyPermissionException::READ );

	default:
	return parent::__set( $name, $value );
	}
	}

	/**
	* Returns true if the property $name is set, otherwise false.
	*
	* @param string $name
	* @return bool
	* @ignore
	*/
	public function __isset( $name )
	{
	switch ( $name )
	{
	case 'prefix':
	return isset( $this->properties[$name] );

	default:
	return parent::__isset( $name );
	}
	}

	/**
	* Creates a new XML tree in the file $xmlFile using $store as data store.
	*
	* The $prefix option can be used to change the prefix that is used for IDs
	* in the created tree. By default this is set to "id" so that numerical
	* node IDs are not a problem.
	*
	* @param string $xmlFile
	* @param ezcTreeXmlDataStore $store
	* @param string $prefix
	* @return ezcTreeXml
	*/
	public static function create( $xmlFile, ezcTreeXmlDataStore $store, $prefix = 'id' )
	{
	$dom = new DomDocument( '1.0', 'utf-8' );
	$dom->formatOutput = true;

	$element = $dom->createElement( 'tree' );
	$element->setAttributeNode( new DOMAttr( 'xmlns', 'http://components.ez.no/Tree' ) );
	$element->setAttributeNode( new DOMAttr( 'xmlns:etd', 'http://components.ez.no/Tree/data' ) );
	if ( $prefix !== null )
	{
	$element->setAttributeNode( new DOMAttr( 'prefix', $prefix ) );
	}

	$dom->appendChild( $element );

	$dom->save( $xmlFile );
	return new ezcTreeXml( $xmlFile, $store, $prefix );
	}

	/**
	* Saves the internal DOM representation of the tree back to disk.
	*/
	public function saveFile()
	{
	$this->dom->save( $this->xmlFile );
	}

	/**
	* This method generates the next node ID.
	*
	* It uses the stored last generated ID, and also stores this in an
	* attribute on the root node so that it can be correctly incremented
	* without having to search for the last generated ID in the whole tree.
	*
	* @return integer
	*/
	protected function generateNodeID()
	{
	$this->autoNodeId++;

	$document = $this->dom->documentElement;
	$document->setAttributeNode( new DOMAttr( 'lastNodeId', $this->autoNodeId ) );

	return $this->autoNodeId;
	}

	/**
	* Returns whether the node with ID $nodeId exists.
	*
	* @param string $nodeId
	* @return bool
	*/
	public function nodeExists( $nodeId )
	{
	$elem = $this->dom->getElementById( "{$this->properties['prefix']}$nodeId" );
	return ( $elem !== null ) ? true : false;
	}

	/**
	* Retrieves a DOMElement containing the node with node ID $nodeId.
	*
	* @param string $nodeId
	* @return DOMElement
	*/
	private function getNodeById( $nodeId )
	{
	$node = $this->dom->getElementById( "{$this->properties['prefix']}$nodeId" );
	if ( !$node )
	{
	throw new ezcTreeUnknownIdException( $nodeId );
	}
	return $node;
	}

	/**
	* Fetches all the child "node" DOM elements of the node with ID $nodeId.
	*
	* @param string $nodeId
	* @return array(string)
	*/
	private function fetchChildIds( $nodeId )
	{
	$childNodes = array();
	$elem = $this->getNodeById( $nodeId );
	$children = $elem->childNodes;
	foreach ( $children as $child )
	{
	if ( $child->nodeType === XML_ELEMENT_NODE && $child->tagName == "node" )
	{
	$nodeId = substr( $child->getAttribute( 'id' ), strlen( $this->properties['prefix'] ) );
	$childNodes[] = $nodeId;
	}
	}
	return $childNodes;
	}

	/**
	* Returns all the children of the node with ID $nodeId.
	*
	* @param string $nodeId
	* @return ezcTreeNodeList
	*/
	public function fetchChildren( $nodeId )
	{
	$className = $this->properties['nodeClassName'];
	$list = new ezcTreeNodeList;
	foreach ( $this->fetchChildIds( $nodeId ) as $childId )
	{
	$list->addNode( new $className( $this, $childId ) );
	}
	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 )
	{
	$className = $this->properties['nodeClassName'];
	$elem = $this->getNodeById( $nodeId );
	$elem = $elem->parentNode;
	$parentId = $elem !== null ? substr( $elem->getAttribute( 'id' ), strlen( $this->properties['prefix'] ) ) : null;
	if ( $parentId === false )
	{
	return null;
	}
	return new $className( $this, $parentId );
	}

	/**
	* 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 )
	{
	$className = $this->properties['nodeClassName'];

	$nodes = array();
	$nodes[] = new $className( $this, $nodeId );

	$elem = $this->getNodeById( $nodeId );
	$elem = $elem->parentNode;

	while ( $elem !== null && $elem->nodeType == XML_ELEMENT_NODE && $elem->tagName == 'node' )
	{
	$id = substr( $elem->getAttribute( 'id' ), strlen( $this->properties['prefix'] ) );
	$nodes[] = new $className( $this, $id );
	$elem = $elem->parentNode;
	}

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

	/**
	* Adds the children nodes of the node with ID $nodeId to the
	* ezcTreeNodeList $list.
	*
	* @param ezcTreeNodeList $list
	* @param string $nodeId
	*/
	private function addChildNodesDepthFirst( ezcTreeNodeList $list, $nodeId )
	{
	$className = $this->properties['nodeClassName'];
	foreach ( $this->fetchChildIds( $nodeId ) as $childId )
	{
	$list->addNode( new $className( $this, $childId ) );
	$this->addChildNodesDepthFirst( $list, $childId );
	}
	}

	/**
	* Returns the node with ID $nodeId and all its children, sorted according to
	* the {@link http://en.wikipedia.org/wiki/Depth-first_search Depth-first sorting}
	* algorithm.
	*
	* @param string $nodeId
	* @return ezcTreeNodeList
	*/
	public function fetchSubtreeDepthFirst( $nodeId )
	{
	$className = $this->properties['nodeClassName'];
	$list = new ezcTreeNodeList;
	$list->addNode( new $className( $this, $nodeId ) );
	$this->addChildNodesDepthFirst( $list, $nodeId );
	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 with ID $nodeId to the
	* ezcTreeNodeList $list.
	*
	* @param ezcTreeNodeList $list
	* @param string $nodeId
	*/
	private function addChildNodesBreadthFirst( ezcTreeNodeList $list, $nodeId )
	{
	$className = $this->properties['nodeClassName'];
	$childIds = $this->fetchChildIds( $nodeId );
	foreach ( $childIds as $childId )
	{
	$list->addNode( new $className( $this, $childId ) );
	}
	foreach ( $childIds as $childId )
	{
	$this->addChildNodesDepthFirst( $list, $childId );
	}
	}

	/**
	* 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 )
	{
	$className = $this->properties['nodeClassName'];
	$list = new ezcTreeNodeList;
	$list->addNode( new $className( $this, $nodeId ) );
	$this->addChildNodesBreadthFirst( $list, $nodeId );
	return $list;
	}

	/**
	* Returns the number of direct children of the node with ID $nodeId.
	*
	* @param string $nodeId
	* @return int
	*/
	public function getChildCount( $nodeId )
	{
	$count = 0;
	$elem = $this->getNodeById( $nodeId );
	$children = $elem->childNodes;
	foreach ( $children as $child )
	{
	if ( $child->nodeType === XML_ELEMENT_NODE && $child->tagName == "node" )
	{
	$count++;
	}
	}
	return $count;
	}

	/**
	* Adds the number of children with for the node with ID $nodeId nodes to
	* $count, recursively.
	*
	* @param int $count
	* @param string $nodeId
	*/
	private function countChildNodes( &$count, $nodeId )
	{
	foreach ( $this->fetchChildIds( $nodeId ) as $childId )
	{
	$count++;
	$this->countChildNodes( $count, $childId );
	}
	}

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

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

	while ( $elem !== null && $elem->nodeType == XML_ELEMENT_NODE )
	{
	$elem = $elem->parentNode;
	$length++;
	}
	return $length;
	}

	/**
	* Returns whether the node with ID $nodeId has children.
	*
	* @param string $nodeId
	* @return bool
	*/
	public function hasChildNodes( $nodeId )
	{
	$elem = $this->getNodeById( $nodeId );
	$children = $elem->childNodes;
	foreach ( $children as $child )
	{
	if ( $child->nodeType === XML_ELEMENT_NODE && $child->tagName == "node" )
	{
	return true;
	}
	}
	return false;
	}

	/**
	* 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 )
	{
	$elem = $this->getNodeById( $childId );
	$parentElem = $elem->parentNode;
	$nodeId = $parentElem->getAttribute( 'id' );
	if ( $nodeId === "{$this->properties['prefix']}$parentId" )
	{
	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 )
	{
	$elem = $this->getNodeById( $childId );
	$elem = $elem->parentNode;

	while ( $elem !== null && $elem->nodeType == XML_ELEMENT_NODE )
	{
	$nodeId = $elem->getAttribute( 'id' );
	if ( $nodeId === "{$this->properties['prefix']}$parentId" )
	{
	return true;
	}
	$elem = $elem->parentNode;
	}
	return false;
	}

	/**
	* Returns whether the nodes with IDs $child1Id and $child2Id are siblings
	* (ie, they 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->parentNode->getAttribute( 'id' ) === $elem2->parentNode->getAttribute( 'id' ) )
	);
	}

	/**
	* Sets a new node as root node, this also wipes out the whole tree.
	*
	* @param ezcTreeNode $node
	*/
	public function setRootNode( ezcTreeNode $node )
	{
	$document = $this->dom->documentElement;

	// remove old root node(s)
	foreach ( $document->childNodes as $childNode )
	{
	if ( $childNode->nodeType == XML_ELEMENT_NODE && $childNode->tagName === 'node' )
	{
	$nodeId = substr( $childNode->getAttribute( 'id' ), strlen( $this->properties['prefix'] ) );
	$this->delete( $nodeId );
	}
	}
	$this->store->deleteDataForAllNodes();

	// Create new root node
	$root = $this->dom->createElement( 'node' );
	$root->setAttributeNode( new DOMAttr( 'id', "{$this->properties['prefix']}{$node->id}" ) );
	$root->setIdAttribute( 'id', true );
	$document->appendChild( $root );
	$this->store->storeDataForNode( $node, $node->data );
	$this->saveFile();
	}

	/**
	* Returns the root node.
	*
	* This methods returns null if there is no root node.
	*
	* @return ezcTreeNode
	*/
	public function getRootNode()
	{
	$className = $this->properties['nodeClassName'];
	$document = $this->dom->documentElement;

	foreach ( $document->childNodes as $childNode )
	{
	if ( $childNode->nodeType == XML_ELEMENT_NODE && $childNode->tagName == 'node' )
	{
	$nodeId = substr( $childNode->getAttribute( 'id' ), strlen( $this->properties['prefix'] ) );
	return new $className( $this, $nodeId );
	}
	}
	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
	$elem = $this->getNodeById( $parentId );

	// Create new DOM node
	$child = $this->dom->createElement( 'node' );
	$child->setAttributeNode( new DOMAttr( 'id', "{$this->properties['prefix']}{$childNode->id}" ) );
	$child->setIdAttribute( 'id', true );

	// Append to parent node
	$elem->appendChild( $child );
	$this->store->storeDataForNode( $childNode, $childNode->data );

	if ( !$this->inTransactionCommit )
	{
	$this->saveFile();
	}
	}

	/**
	* 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;
	}

	// Delete all the associated data
	$nodeList = $this->fetchSubtree( $nodeId );
	$this->store->deleteDataForNodes( $nodeList );

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

	// Remove the ID on all children by hand as this would crash in PHP <= 5.2.3
	$nodeToDelete->removeAttribute( "id" );

	$children = $nodeToDelete->getElementsByTagName( 'node' );
	foreach ( $children as $child )
	{
	$child->removeAttribute( "id" );
	}

	// Use the parent to remove the child
	$nodeToDelete->parentNode->removeChild( $nodeToDelete );

	if ( !$this->inTransactionCommit )
	{
	$this->saveFile();
	}
	}

	/**
	* 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
	$parent = $this->getNodeById( $targetParentId );

	$parent->appendChild( $nodeToMove );

	if ( !$this->inTransactionCommit )
	{
	$this->saveFile();
	}
	}

	/**
	* Fixates the transaction (saves the XML file).
	*/
	public function fixateTransaction()
	{
	$this->saveFile();
	}
	}
	?>