Author: dr
Date: Thu Aug 2 11:05:25 2007
New Revision: 5802
Log:
- Implemented Breadth-first fetching of subtrees.
Modified:
trunk/Tree/src/backends/db_parent_child.php
trunk/Tree/src/backends/memory.php
trunk/Tree/src/backends/xml.php
trunk/Tree/src/tree_node.php
trunk/Tree/tests/db_parent_child_tree.php
trunk/Tree/tests/memory_tree.php
trunk/Tree/tests/tree.php
trunk/Tree/tests/xml_tree.php
Modified: trunk/Tree/src/backends/db_parent_child.php
==============================================================================
--- trunk/Tree/src/backends/db_parent_child.php [iso-8859-1] (original)
+++ trunk/Tree/src/backends/db_parent_child.php [iso-8859-1] Thu Aug 2
11:05:25 2007
@@ -101,13 +101,13 @@
* @param ezcTreeNodeList $list
* @param string $nodeId
*/
- private function addChildNodes( ezcTreeNodeList $list, $nodeId )
+ private function addChildNodesDepthFirst( ezcTreeNodeList $list, $nodeId )
{
$className = $this->properties['nodeClassName'];
foreach ( $this->fetchChildRecords( $nodeId ) as $record )
{
$list->addNode( new $className( $this, $record['id'] ) );
- $this->addChildNodes( $list, $record['id'] );
+ $this->addChildNodesDepthFirst( $list, $record['id'] );
}
}
@@ -152,6 +152,22 @@
}
/**
+ * Returns the node with ID $id and all its children, sorted accoring to
+ * the `Depth-first sorting`_ algorithm.
+ *
+ * @param string $id
+ * @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 $id
@@ -160,6 +176,27 @@
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'];
+ $childRecords = $this->fetchChildRecords( $nodeId )->fetchAll();
+ foreach ( $childRecords as $record )
+ {
+ $list->addNode( new $className( $this, $record['id'] ) );
+ }
+ foreach ( $childRecords as $record )
+ {
+ $this->addChildNodesBreadthFirst( $list, $record['id'] );
+ }
}
/**
@@ -171,21 +208,10 @@
*/
public function fetchSubtreeBreadthFirst( $nodeId )
{
- }
-
- /**
- * Returns the node with ID $id and all its children, sorted accoring to
- * the `Depth-first sorting`_ algorithm.
- *
- * @param string $id
- * @return ezcTreeNodeList
- */
- public function fetchSubtreeDepthFirst( $nodeId )
- {
$className = $this->properties['nodeClassName'];
$list = new ezcTreeNodeList;
$list->addNode( new $className( $this, $nodeId ) );
- $this->addChildNodes( $list, $nodeId );
+ $this->addChildNodesBreadthFirst( $list, $nodeId );
return $list;
}
Modified: trunk/Tree/src/backends/memory.php
==============================================================================
--- trunk/Tree/src/backends/memory.php [iso-8859-1] (original)
+++ trunk/Tree/src/backends/memory.php [iso-8859-1] Thu Aug 2 11:05:25 2007
@@ -142,35 +142,13 @@
* @param ezcTreeNodeList $list
* @param string $nodeId
*/
- private function addChildNodes( ezcTreeNodeList $list, ezcTreeMemoryNode
$memoryNode )
+ private function addChildNodesDepthFirst( ezcTreeNodeList $list,
ezcTreeMemoryNode $memoryNode )
{
foreach ( $memoryNode->children as $id => $childMemoryNode )
{
$list->addNode( $childMemoryNode->node );
- $this->addChildNodes( $list, $childMemoryNode );
- }
- }
-
- /**
- * Alias for fetchSubtreeDepthFirst().
- *
- * @param string $id
- * @return ezcTreeNodeList
- */
- public function fetchSubtree( $nodeId )
- {
- return $this->fetchSubtreeDepthFirst( $nodeId );
- }
-
- /**
- * Returns the node with ID $id and all its children, sorted accoring to
- * the `Breadth-first sorting`_ algorithm.
- *
- * @param string $id
- * @return ezcTreeNodeList
- */
- public function fetchSubtreeBreadthFirst( $nodeId )
- {
+ $this->addChildNodesDepthFirst( $list, $childMemoryNode );
+ }
}
/**
@@ -185,7 +163,53 @@
$list = new ezcTreeNodeList;
$memoryNode = $this->getNodeById( $nodeId );
$list->addNode( $memoryNode->node );
- $this->addChildNodes( $list, $memoryNode );
+ $this->addChildNodesDepthFirst( $list, $memoryNode );
+ return $list;
+ }
+
+ /**
+ * Alias for fetchSubtreeDepthFirst().
+ *
+ * @param string $id
+ * @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 string $nodeId
+ */
+ private function addChildNodesBreadthFirst( ezcTreeNodeList $list,
ezcTreeMemoryNode $memoryNode )
+ {
+ foreach ( $memoryNode->children as $id => $childMemoryNode )
+ {
+ $list->addNode( $childMemoryNode->node );
+ }
+ foreach ( $memoryNode->children as $id => $childMemoryNode )
+ {
+ $this->addChildNodesBreadthFirst( $list, $childMemoryNode );
+ }
+ }
+
+ /**
+ * Returns the node with ID $id and all its children, sorted accoring to
+ * the `Breadth-first sorting`_ algorithm.
+ *
+ * @param string $id
+ * @return ezcTreeNodeList
+ */
+ public function fetchSubtreeBreadthFirst( $nodeId )
+ {
+ $list = new ezcTreeNodeList;
+ $memoryNode = $this->getNodeById( $nodeId );
+ $list->addNode( $memoryNode->node );
+ $this->addChildNodesBreadthFirst( $list, $memoryNode );
return $list;
}
Modified: trunk/Tree/src/backends/xml.php
==============================================================================
--- trunk/Tree/src/backends/xml.php [iso-8859-1] (original)
+++ trunk/Tree/src/backends/xml.php [iso-8859-1] Thu Aug 2 11:05:25 2007
@@ -216,36 +216,14 @@
* @param ezcTreeNodeList $list
* @param string $nodeId
*/
- private function addChildNodes( ezcTreeNodeList $list, $nodeId )
+ private function addChildNodesDepthFirst( ezcTreeNodeList $list, $nodeId )
{
$className = $this->properties['nodeClassName'];
foreach ( $this->fetchChildIds( $nodeId ) as $childId )
{
$list->addNode( new $className( $this, $childId ) );
- $this->addChildNodes( $list, $childId );
- }
- }
-
- /**
- * Alias for fetchSubtreeDepthFirst().
- *
- * @param string $id
- * @return ezcTreeNodeList
- */
- public function fetchSubtree( $nodeId )
- {
- return $this->fetchSubtreeDepthFirst( $nodeId );
- }
-
- /**
- * Returns the node with ID $id and all its children, sorted accoring to
- * the `Breadth-first sorting`_ algorithm.
- *
- * @param string $id
- * @return ezcTreeNodeList
- */
- public function fetchSubtreeBreadthFirst( $nodeId )
- {
+ $this->addChildNodesDepthFirst( $list, $childId );
+ }
}
/**
@@ -260,7 +238,55 @@
$className = $this->properties['nodeClassName'];
$list = new ezcTreeNodeList;
$list->addNode( new $className( $this, $nodeId ) );
- $this->addChildNodes( $list, $nodeId );
+ $this->addChildNodesDepthFirst( $list, $nodeId );
+ return $list;
+ }
+
+ /**
+ * Alias for fetchSubtreeDepthFirst().
+ *
+ * @param string $id
+ * @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 $id and all its children, sorted accoring to
+ * the `Breadth-first sorting`_ algorithm.
+ *
+ * @param string $id
+ * @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;
}
Modified: trunk/Tree/src/tree_node.php
==============================================================================
--- trunk/Tree/src/tree_node.php [iso-8859-1] (original)
+++ trunk/Tree/src/tree_node.php [iso-8859-1] Thu Aug 2 11:05:25 2007
@@ -170,6 +170,17 @@
}
/**
+ * Returns this node and all its children, sorted accoring to the
+ * Depth-first sorting algorithm.
+ *
+ * @return ezcTreeNodeList
+ */
+ public function fetchSubtreeDepthFirst()
+ {
+ return $this->tree->fetchSubtreeDepthFirst( $this->id );
+ }
+
+ /**
* Alias for fetchSubtreeDepthFirst().
*
* @see fetchSubtreeDepthFirst
@@ -192,17 +203,6 @@
}
/**
- * Returns this node and all its children, sorted accoring to the
- * Depth-first sorting algorithm.
- *
- * @return ezcTreeNodeList
- */
- public function fetchSubtreeDepthFirst()
- {
- return $this->tree->fetchSubtreeDepthFirst( $this->id );
- }
-
- /**
* Returns the number of direct children of this node
*
* @return int
Modified: trunk/Tree/tests/db_parent_child_tree.php
==============================================================================
--- trunk/Tree/tests/db_parent_child_tree.php [iso-8859-1] (original)
+++ trunk/Tree/tests/db_parent_child_tree.php [iso-8859-1] Thu Aug 2 11:05:25
2007
@@ -26,6 +26,18 @@
protected function tearDown()
{
+ }
+
+ protected function setUpEmptyTestTree()
+ {
+ $store = new ezcTreeDbExternalTableDataStore( $this->dbh, 'data',
'id', 'data' );
+ $tree = new ezcTreeDbParentChild(
+ $this->dbh,
+ 'parent_child',
+ $store
+ );
+ $this->emptyTables();
+ return $tree;
}
protected function setUpTestTree()
Modified: trunk/Tree/tests/memory_tree.php
==============================================================================
--- trunk/Tree/tests/memory_tree.php [iso-8859-1] (original)
+++ trunk/Tree/tests/memory_tree.php [iso-8859-1] Thu Aug 2 11:05:25 2007
@@ -18,9 +18,15 @@
{
private $tempDir;
+ protected function setUpEmptyTestTree()
+ {
+ $tree = ezcTreeMemory::create( new ezcTreeMemoryDataStore() );
+ return $tree;
+ }
+
protected function setUpTestTree()
{
- $tree = ezcTreeMemory::create( new ezcTreeMemoryDataStore() );
+ $tree = $this->setUpEmptyTestTree();
$tree->setRootNode( $root = $tree->createNode( 1, 'Node 1' ) );
$root->addChild( $node2 = $tree->createNode( 2, 'Node 2' ) );
Modified: trunk/Tree/tests/tree.php
==============================================================================
--- trunk/Tree/tests/tree.php [iso-8859-1] (original)
+++ trunk/Tree/tests/tree.php [iso-8859-1] Thu Aug 2 11:05:25 2007
@@ -384,6 +384,54 @@
self::assertSame( '8', $nodeList[8]->id );
}
+ public function testTreeFetchSubtreeBreadthFirstOnNode()
+ {
+ $tree = $this->setUpTestTree();
+
+ $nodeList = $tree->fetchNodeById( 4 )->fetchSubtreeBreadthFirst();
+ self::assertSame( 4, $nodeList->size );
+ self::assertSame( '4', $nodeList[4]->id );
+ self::assertSame( '6', $nodeList[6]->id );
+ self::assertSame( '7', $nodeList[7]->id );
+ self::assertSame( '8', $nodeList[8]->id );
+ }
+
+ public function testTreeFetchSubtreeBreadthFirstOnTree()
+ {
+ $tree = $this->setUpTestTree();
+
+ $nodeList = $tree->fetchSubtreeBreadthFirst( 4 );
+ self::assertSame( 4, $nodeList->size );
+ self::assertSame( '4', $nodeList[4]->id );
+ self::assertSame( '6', $nodeList[6]->id );
+ self::assertSame( '7', $nodeList[7]->id );
+ self::assertSame( '8', $nodeList[8]->id );
+ }
+
+ public function testTreeFetchSubtreeDepthFirstOnNode()
+ {
+ $tree = $this->setUpTestTree();
+
+ $nodeList = $tree->fetchNodeById( 4 )->fetchSubtreeDepthFirst();
+ self::assertSame( 4, $nodeList->size );
+ self::assertSame( '4', $nodeList[4]->id );
+ self::assertSame( '6', $nodeList[6]->id );
+ self::assertSame( '7', $nodeList[7]->id );
+ self::assertSame( '8', $nodeList[8]->id );
+ }
+
+ public function testTreeFetchSubtreeDepthFirstOnTree()
+ {
+ $tree = $this->setUpTestTree();
+
+ $nodeList = $tree->fetchSubtreeDepthFirst( 4 );
+ self::assertSame( 4, $nodeList->size );
+ self::assertSame( '4', $nodeList[4]->id );
+ self::assertSame( '6', $nodeList[6]->id );
+ self::assertSame( '7', $nodeList[7]->id );
+ self::assertSame( '8', $nodeList[8]->id );
+ }
+
public function testTreeFetchChildrenOnNode()
{
$tree = $this->setUpTestTree();
@@ -705,6 +753,162 @@
}
}
}
+
+ private function addTestData( $tree )
+ {
+ $primates = array(
+ 'Hominoidea' => array(
+ 'Hylobatidae' => array(
+ 'Hylobates' => array(
+ 'Lar Gibbon',
+ 'Agile Gibbon',
+ 'Müller\'s Bornean Gibbon',
+ 'Silvery Gibbon',
+ 'Pileated Gibbon',
+ 'Kloss\'s Gibbon',
+ ),
+ 'Hoolock' => array(
+ 'Western Hoolock Gibbon',
+ 'Eastern Hoolock Gibbon',
+ ),
+ 'Symphalangus' => array(),
+ 'Nomascus' => array(
+ 'Black Crested Gibbon',
+ 'Eastern Black Crested Gibbon',
+ 'White-cheecked Crested Gibbon',
+ 'Yellow-cheecked Gibbon',
+ ),
+ ),
+ 'Hominidae' => array(
+ 'Pongo' => array(
+ 'Bornean Orangutan',
+ 'Sumatran Orangutan',
+ ),
+ 'Gorilla' => array(
+ 'Western Gorilla' => array(
+ 'Western Lowland Gorilla',
+ 'Cross River Gorilla',
+ ),
+ 'Eastern Gorilla' => array(
+ 'Mountain Gorilla',
+ 'Eastern Lowland Gorilla',
+ ),
+ ),
+ 'Homo' => array(
+ 'Homo Sapiens' => array(
+ 'Homo Sapiens Sapiens'
+ ),
+ ),
+ 'Pan' => array(
+ 'Common Chimpanzee',
+ 'Bonobo',
+ ),
+ ),
+ ),
+ );
+
+ $root = $tree->createNode( 'Hominoidea', 'Hominoidea' );
+ $tree->setRootNode( $root );
+
+ $this->addChildren( $root, $primates['Hominoidea'] );
+ }
+
+ private function addChildren( ezcTreeNode $node, array $children )
+ {
+ foreach( $children as $name => $child )
+ {
+ if ( is_array( $child ) )
+ {
+ $newNode = $node->tree->createNode( $name, $name );
+ $node->addChild( $newNode );
+ $this->addChildren( $newNode, $child );
+ }
+ else
+ {
+ $newNode = $node->tree->createNode( $child, $child );
+ $node->addChild( $newNode );
+ }
+ }
+ }
+
+ public function testTreeCreateExtensive()
+ {
+ $tree = $this->setUpEmptyTestTree();
+ self::assertSame( false, $tree->nodeExists( '1' ) );
+ $this->addTestData( $tree );
+
+ self::assertSame( true, $tree->nodeExists( 'Homo Sapiens Sapiens' ) );
+ self::assertSame( true, $tree->isDecendantOf( 'Common Chimpanzee',
'Hominoidea' ) );
+ self::assertSame( 4, $tree->getChildCount( 'Hominidae' ) );
+ self::assertSame( 16, $tree->getChildCountRecursive( 'Hominidae' ) );
+ self::assertSame( true, $tree->isSiblingOf( 'Gorilla', 'Homo' ) );
+ }
+
+ public function testTreeFetchSubtreeDepthFirst()
+ {
+ $tree = $this->setUpEmptyTestTree();
+ $this->addTestData( $tree );
+
+ $expected = array(
+ 'Gorilla', 'Western Gorilla', 'Western Lowland Gorilla',
+ 'Cross River Gorilla', 'Eastern Gorilla', 'Mountain Gorilla',
+ 'Eastern Lowland Gorilla'
+ );
+ $list = $tree->fetchSubtreeDepthFirst( 'Gorilla' );
+ $nodes = $list->getNodes();
+ self::assertSame( 7, $list->size );
+ self::assertSame( 7, count( $nodes ) );
+
+ // test with fetched nodes as base
+ reset( $expected );
+ foreach ( $nodes as $key => $item )
+ {
+ self::assertSame( current( $expected ), $key );
+ next( $expected );
+ }
+
+ // test with expected array as base
+ reset( $nodes );
+ foreach( $expected as $key )
+ {
+ self::assertType( 'ezcTreeNode', current( $nodes ) );
+ self::assertSame( current( $nodes )->id, $key );
+ next( $nodes );
+ }
+ }
+
+ public function testTreeFetchSubtreeBreadthFirst()
+ {
+ $tree = $this->setUpEmptyTestTree();
+ $this->addTestData( $tree );
+
+ $expected = array(
+ 'Gorilla', 'Western Gorilla', 'Eastern Gorilla',
+ 'Western Lowland Gorilla', 'Cross River Gorilla',
+ 'Mountain Gorilla', 'Eastern Lowland Gorilla'
+ );
+ $list = $tree->fetchSubtreeBreadthFirst( 'Gorilla' );
+ $nodes = $list->getNodes();
+ self::assertSame( 7, $list->size );
+ self::assertSame( 7, count( $nodes ) );
+
+ // test with fetched nodes as base
+ reset( $expected );
+ foreach ( $nodes as $key => $item )
+ {
+ self::assertSame( current( $expected ), $key );
+ next( $expected );
+ }
+
+ // test with expected array as base
+ reset( $nodes );
+ foreach( $expected as $key )
+ {
+ self::assertType( 'ezcTreeNode', current( $nodes ) );
+ self::assertSame( current( $nodes )->id, $key );
+ next( $nodes );
+ }
+ }
}
?>
Modified: trunk/Tree/tests/xml_tree.php
==============================================================================
--- trunk/Tree/tests/xml_tree.php [iso-8859-1] (original)
+++ trunk/Tree/tests/xml_tree.php [iso-8859-1] Thu Aug 2 11:05:25 2007
@@ -26,6 +26,15 @@
protected function tearDown()
{
$this->removeTempDir();
+ }
+
+ protected function setUpEmptyTestTree()
+ {
+ $tree = ezcTreeXml::create(
+ $this->tempDir . '/test.xml',
+ new ezcTreeXmlInternalDataStore()
+ );
+ return $tree;
}
protected function setUpTestTree()
--
svn-components mailing list
[email protected]
http://lists.ez.no/mailman/listinfo/svn-components
