Zend_Tree - Andries Seutens

Zend_Tree
{zone-data}

{zone-data:proposer-list}
[Andries Seutens|mailto:andries.seutens@skynet.be]
{zone-data}

{zone-data:revision}
0.1 - 28 January 2007: Added first draft for proposal
{zone-data}

{zone-data:overview}
*About tree's*
A tree is a data structure that emulates a tree structure with a set of linked nodes. Each node has zero or more child nodes, which are below it in the tree. A node that has a child is called the child's parent node. A node has at most one parent.

*The root node*
The topmost node in a tree is called the root node. Being the topmost node, the root node will not have parents. It is the node at which all operations on the tree begin. All other nodes can be reached from it by following edges or links. Every node in a tree can be seen as the root node of the subtree rooted at that node.

*A subtree*
A subtree is a portion of a tree data structure that can be viewed as a complete tree in itself. Any node in a tree T, together with all the nodes below it, comprise a subtree of T. The subtree corresponding to the root node is the entire tree; the subtree corresponding to any other node is called a proper subtree.

*Leaf nodes*
Nodes at the bottom most level of the tree are called leaf nodes. Since they are at the bottom most level, they will not have any children. An internal node or inner node is any node of a tree data structure that has child nodes and is thus not a leaf node.

*Zend_Tree's role*
Zend_Tree will be a data structure which would probably have three most interesting adapters. Db, PHP array, and XML:

* DB because it will help with catalogues and other Db related data.
* PHP array's for sessions and other PHP centric functionality.
* XML for data exchange.
{zone-data}

{zone-data:references}
*Other known components*

* [PEAR's Tree|http://pear.php.net/package/Tree]
* [Horde Framework's Tree|http://dev.horde.org/api/framework/Horde_Tree/Horde_Tree.html]

*Popular tree data structures:*

* [AA tree|http://en.wikipedia.org/wiki/AA_tree]
* [AVL tree|http://en.wikipedia.org/wiki/AVL_tree]
* [Red-black tree|http://en.wikipedia.org/wiki/Red-black_tree]
* [Splay tree|http://en.wikipedia.org/wiki/Splay_tree]
* [Scapegoat tree|http://en.wikipedia.org/wiki/Scapegoat_tree]

*Other tree data structures:*

* [B-tree (2-3 tree, B+ tree, B*-tree)|http://en.wikipedia.org/wiki/B-tree]
* [DSW algorithm|http://en.wikipedia.org/wiki/DSW_algorithm]
* [Dancing tree|http://en.wikipedia.org/wiki/Dancing_tree]
* [R-tree|http://en.wikipedia.org/wiki/R-tree]
* [Radix tree|http://en.wikipedia.org/wiki/Radix_tree]
* [Skip list|http://en.wikipedia.org/wiki/Skip_list]

{zone-data}

{zone-data:requirements}
*This component will:*

* Allow subclassing;
* Support various import/export formats;
* Support the enumerating all the items;
* Support searching for an item;
* Support adding a new item at a certain position on the tree;
* Support deleting an item;
* Support removing a whole section of a tree;
* Support adding a whole section to a tree;
* Support finding the root for any node;
* Support manipulating hierarchical data;
* Make information easy to search;
* Support exporting to a variety of different formats;
* Know how to serialize itself (could be useful in storing it in Zend_Session);

*This component will not:*

* Create tight connection to Zend_Acl, Zend_Session, or other modules;
{zone-data}

{zone-data:dependencies}
* Zend_Exception
{zone-data}

{zone-data:operation}
todo
{zone-data}

{zone-data:milestones}
* Milestone 1: write proposal / use cases / class skeletons and try to gather feedback from community
* Milestone 2: Class development
* Milestone 3: Unit tests and debugging
* Milestone 4: Documentation
{zone-data}

{zone-data:class-list}
* Zend_Tree
* Zend_Tree_Exception
* Zend_Tree_Adapter_Abstract
* Zend_Tree_Adapter_Db
* Zend_Tree_Adapter_Xml
* Zend_Tree_Adapter_Array
{zone-data}

{zone-data:use-cases}
*Working with XML (comparible to simple xml)*

{code:type=xml}
// zend.xml
<root>
<users>
<user>
<fname>Darby</fname>
<name>Felton</name>
</user>
<user>
<fname>Gavin</fname>
<name>Vess</name>
</user>
</users
</root>
{code}

{composition-setup}
{deck:id=use-cases1}

{card:label=UC 1 : Adding a new item at a certain position on the tree}

'name' => 'Seutens'
)
);
?>
{code}
{card}

{card:label=UC 2 : Searching/looping the tree}

}
?>
{code}
{card}

{deck}

{zone-data}

{zone-data:skeletons}
todo