Skip to end of metadata
Go to start of metadata

<ac:macro ac:name="note"><ac:parameter ac:name="title">Under Construction</ac:parameter><ac:rich-text-body>
<p>This proposal is under construction and is not ready for review.</p>

<p>When Zend_Tree got proposed (April 2006) the Zend team was very much focused on making enough progress on what they considered the absolutely must-have components. </p>

<p>For that reason, Zend_Tree had to be put aside because even if the Zend team doesn't do the proposal writing and coding, each such component requires a significant amount of energy on their side on reviewing, helping with, and polishing up the component and making it ready for release.</p>

<p>I have received an email from Andi Gutmans, where he tells me that we are at the point now where most of what we labeled "must-have" is starting to stabilize. He asked me if I was still interested in "re-proposing" Zend_Tree, so it could be reconsidered.</p>

<p>This proposal is a revised proposal, based on the feedback that I have received throughout the months, from various contributors.</p>

<p>I have decided to put this proposal in the standard proposal template, as fast as possible, so we can gather feedback from the very start.</p></ac:rich-text-body></ac:macro>

<ac:macro ac:name="unmigrated-inline-wiki-markup"><ac:plain-text-body><![CDATA[

<ac:macro ac:name="unmigrated-inline-wiki-markup"><ac:plain-text-body><![CDATA[

Zend Framework: Zend_Tree Component Proposal

Proposed Component Name Zend_Tree
Developer Notes http://framework.zend.com/wiki/display/ZFDEV/Zend_Tree
Proposers Andries Seutens
Revision 0.1 - 28 January 2007: Added first draft for proposal (wiki revision: 13)

Table of Contents

1. 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.

2. References

Other known components

Popular tree data structures:

Other tree data structures:

3. Component Requirements, Constraints, and Acceptance Criteria

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;

4. Dependencies on Other Framework Components

  • Zend_Exception

5. Theory of Operation

todo

6. Milestones / Tasks

  • 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

7. Class Index

  • Zend_Tree
  • Zend_Tree_Exception
  • Zend_Tree_Adapter_Abstract
  • Zend_Tree_Adapter_Db
  • Zend_Tree_Adapter_Xml
  • Zend_Tree_Adapter_Array

8. Use Cases

Working with XML (comparible to simple xml)

9. Class Skeletons

todo

]]></ac:plain-text-body></ac:macro>

]]></ac:plain-text-body></ac:macro>

Labels:
None
Enter labels to add to this page:
Please wait 
Looking for a label? Just start typing.
  1. Feb 24, 2007

    <p>Representing data as trees crops up time and time again, so I think this is a truly great idea. <ac:emoticon ac:name="smile" /></p>

  2. Feb 26, 2007

    <p>Very nice idea to provide a unified structure from various datasources.<br />
    DB queries should be optimized for various databases: I think Oracle has a special construct to get the complete parent's parent's (etc) from one single menu_id.<br />
    Maybe Mysql and MSSQL (and others) have such functionalities.</p>

    <p>XML and PHP arrays seem mandaory too. Maybe other datasources could be welcome.</p>

    <p>Another point should be a easy function to get the menu item's path directly from one function call as: root > menu level 1 >menu level 2 > item</p>

    <p>Will this class only focus on the processing of menu data (Zend_Tree-Data), or also provide GUI functionalities (Zend_Tree-Menu)?</p>

  3. May 31, 2007

    <p>This proposal is very interesting however I think it needs more content on the following points:</p>

    <p>1. How exactly adapters interact with the main tree class? What is the signature of the adapter and nodes?<br />
    2. From the above, can we make same adapter work with any kind of tree - i.e. usa same adapter to store/load primitive trees and some special trees like red/black, AVL, etc. <br />
    3. It would be nice to be able to decouple generic data storage format (main class and storage adapter) from algorithms on the tree - i.e. that the same generic data structure could be specified with different strategies to implement all kinds of special trees, thus allowing to implement specific tree algorithms without redefining the whole data interactions.</p>

    <p>I would propose to start with defining tree/adapter interaction, and then define the main tree interface while keeping in mind that it should support any kind of tree (i.e. any kind of acyclic directed graph) i.e. there should be no presumptions on how many children or how many values are for the node, etc. Then when we have that we might start thinking about all kinds of special trees we might want to implement. </p>

    <p>And of course it would be nice to see skeletons for tree operations in the proposal.</p>

  4. Jun 05, 2007

    <p>In my day to day work I have 2 use cases when using trees:</p>

    <p><strong>Work in memory only</strong><br />
    To build a navigation menu for example , I set up a tree object manually and when I call $tree->addNode(12, new node(array('id'=>1, 'titre' =>'menu1', 'url'=>'/blog'))) the method is taking effect on the internal structure (memory).</p>

    <p><strong>Work directly on the data storage</strong> <br />
    Then when working with a cms, if I add a new page (node) I want that the addNode() method directly map to the database.</p>

    <p>I started to refactor my php4 tree class to php5 a year and half ago. While I was wondering how the tree should be represented internally (Associative array, Recursive collection of tree nodes, Others? ) I explored some pretty good stuff with the SPL library ( <a class="external-link" href="http://www.php.net/~helly/php/ext/spl/">http://www.php.net/~helly/php/ext/spl/</a> ) : RecursiveIterator, RecursiveArrayIterator, RecursiveTreeIterator but I didn't have time to do much more.</p>

    <p>Then for the Adapter part Array and Xml are well suited for storing hierarchical data but it's a bit more tricky with a database. </p>

    <p>There is 2 main representations and algorithms to represent hierarchical structures with databases :</p>

    <ul>
    <li>nested set also known as modified preorder tree traversal algorithm</li>
    <li>adjacency list model</li>
    </ul>

    <p>It's well explained here:
    <a class="external-link" href="http://www.sitepoint.com/article/hierarchical-data-database">http://www.sitepoint.com/article/hierarchical-data-database</a>
    <a class="external-link" href="http://dev.mysql.com/tech-resources/articles/hierarchical-data.html">http://dev.mysql.com/tech-resources/articles/hierarchical-data.html</a>
    <a class="external-link" href="http://www.evolt.org/article/Four_ways_to_work_with_hierarchical_data/17/4047/index.html">http://www.evolt.org/article/Four_ways_to_work_with_hierarchical_data/17/4047/index.html</a></p>

    <p>Here are some more links that I've collected:</p>

    <p><a class="external-link" href="http://en.wikipedia.org/wiki/Tree_%28data_structure%29">http://en.wikipedia.org/wiki/Tree_%28data_structure%29</a>
    <a class="external-link" href="http://en.wikipedia.org/wiki/Category:Trees_%28structure%29">http://en.wikipedia.org/wiki/Category:Trees_%28structure%29</a></p>

    <p>adjacency list model
    <a class="external-link" href="http://www.sqlteam.com/item.asp?ItemID=8866">http://www.sqlteam.com/item.asp?ItemID=8866</a></p>

    <p>nested set
    <a class="external-link" href="http://www.sqlsummit.com/AdjacencyList.htm">http://www.sqlsummit.com/AdjacencyList.htm</a>
    <a class="external-link" href="http://www.edutech.ch/contribution/nstrees/index.php">http://www.edutech.ch/contribution/nstrees/index.php</a>
    <a class="external-link" href="http://www.phpriot.com/d/articles/php/application-design/nested-trees-1/">http://www.phpriot.com/d/articles/php/application-design/nested-trees-1/</a>
    <a class="external-link" href="http://www.dbmsmag.com/9604d06.html">http://www.dbmsmag.com/9604d06.html</a>
    <a class="external-link" href="http://en.wikipedia.org/wiki/Tree_traversal">http://en.wikipedia.org/wiki/Tree_traversal</a>
    <a class="external-link" href="http://www.cosc.canterbury.ac.nz/mukundan/dsal/BTree.html">http://www.cosc.canterbury.ac.nz/mukundan/dsal/BTree.html</a> (applet java montrant le fonctionnement )</p>

    <p>Graphes
    <a class="external-link" href="http://www.artfulsoftware.com/mysqlbook/sampler/mysqled1ch20.html">http://www.artfulsoftware.com/mysqlbook/sampler/mysqled1ch20.html</a></p>

    <p>Classes :</p>

    <p>Nested Sets DB Tree Adodb
    <a class="external-link" href="http://www.phpclasses.org/browse/package/2547.html">http://www.phpclasses.org/browse/package/2547.html</a><br />
    Visitation Model ADOdb
    <a class="external-link" href="http://www.phpclasses.org/browse/package/2919.html">http://www.phpclasses.org/browse/package/2919.html</a><br />
    PEAR::DB_NestedSet
    <a class="external-link" href="http://pear.php.net/package/DB_NestedSet">http://pear.php.net/package/DB_NestedSet</a><br />
    utilisation : <a class="external-link" href="https://www.entwickler.com/itr/kolumnen/psecom,id,26,nodeid,207.html">https://www.entwickler.com/itr/kolumnen/psecom,id,26,nodeid,207.html</a><br />
    PEAR::Tree
    <a class="external-link" href="http://pear.php.net/package/Tree/download/0.3.0/">http://pear.php.net/package/Tree/download/0.3.0/</a>
    <a class="external-link" href="http://www.phpkitchen.com/index.php?/archives/337-PEARTree-Tutorial.html">http://www.phpkitchen.com/index.php?/archives/337-PEARTree-Tutorial.html</a><br />
    nstrees
    <a class="external-link" href="http://www.edutech.ch/contribution/nstrees/index.php">http://www.edutech.ch/contribution/nstrees/index.php</a></p>

  5. Jan 27, 2008

    <p>My library Ronnie_Tree can be usefull for someone. It is based on ezc tree library according to Zend Framework coding standards. It's fully tested. Only Memory adapter is now usable.</p>

    <p>Download: <a class="external-link" href="http://code.google.com/p/zend-tree/downloads/list">http://code.google.com/p/zend-tree/downloads/list</a></p>

  6. Jan 28, 2008

    <p>Hi!</p>

    <p>I think this proposal is a very nice one! Very useful in many parts of development.</p>

    <p>Do you plan a 'Zend_Tree_Adapter_Filesystem' Adapter? So the contents of an specified directory, subdirectorys and files can be accessed as an tree? I think this would be a nice addition.</p>

  7. Apr 15, 2009

    <p>What's the status of this proposal? The note is a bite confusing, no date. From 2007?</p>

  8. Jun 03, 2009

    <p>I would like also know status of this proposal .... long time no change ...<br />
    Thank You</p>

  9. Feb 02, 2010

    <p>I'm working on a component that does this. I have the XML adapter done. Since this probably isn't getting into ZF I'll create a google code project.</p>

    <p>Update: I have the Array and DB adapters and the main Tree.php file working. Working on the search, move and insert/update functionality.</p>