Author: dr
Date: Thu Jul 19 16:18:55 2007
New Revision: 5720
Log:
- Added the draft of the design document.
Added:
experimental/Tree/design/design.txt (with props)
Modified:
experimental/Tree/design/requirements.txt
Added: experimental/Tree/design/design.txt
==============================================================================
--- experimental/Tree/design/design.txt (added)
+++ experimental/Tree/design/design.txt [iso-8859-1] Thu Jul 19 16:18:55 2007
@@ -1,0 +1,213 @@
+eZ Component: Tree, Design
+~~~~~~~~~~~~~~~~~~~~~~~~~~
+:Author: Derick Rethans
+:Revision: $Revision:$
+:Date: $Date:$
+
+.. contents:: Contents
+
+Design description
+==================
+
+The design of the component allows to be flexible in where the tree structure
+information is stored (called Backends) and where the data that is associated
+with the tree structure is stored (called DataStore). The backends provide
+methods to operate on the tree and fetch nodes. All different data stores
+can theoretically be used through any backend. All database related backends
+and data stores will reside in the TreeDatabaseTiein component, and the
+persistent object related data store in the TreePersistentObjectTiein
component.
+
+
+Utility Classes
+---------------
+
+ezcTreeNode
+```````````
+
+A small class containing the node ID and data belonging to the node. Objects
+of this class are the main interface to nodes. The data in the node can be
+either pre-fetched or fetch on demand. That depends whether pre-fetching is
+turned on, and whether a data store supports it. Operations can be done on tree
+nodes as well, such as checking whether it has children, fetching a sub tree.
+Those methods will call corresponding methods on the tree object to actually
+perform the check/action.
+
+Example::
+
+ <?php
+ $node2 = $tree->fetchById( 2 );
+ $node1 = $tree->fetchById( 1 );
+ $node2->isChildOf( $node1 );
+
+ $node2->hasChildren();
+ $subTree = $node1->fetchSubtree();
+ ?>
+
+
+
+ezcTreeNodeList
+```````````````
+
+Contains a list of ezcTreeNode nodes that can also be accessed (read-only) like
+an array. Example::
+
+ <?php
+ $list = new ezcTreeNodeList;
+ $list->addNode( $nodeId, new ezcTreeNode( $this, $nodeId ) );
+ ?>
+
+ezcTreeNodeListIterator
+```````````````````````
+
+Implements an iterator over a ezcTreeNodeList and fetches data on-demand in
case
+it was not prefetched yet. Example::
+
+ <?php
+ foreach ( new ezcTreeNodeListIterator( $tree, $nodeList ) as $id => $data )
+ {
+ self::assertSame( "Node $id", $data );
+ }
+ ?>
+
+
+Backends
+--------
+
+ezcTree
+```````
+
+An abstract class from which all the other backends extend. It provides
+functionality to access the datastore and creating a new tree node. It will
+also define the methods that operate on whole trees, such as sorting.
+
+ezcTreeDb
+`````````
+
+This abstract class is the base class for all backends that work on databases.
+It implements the ezcTreeBackend that defines which operations are possible
+on the tree structure (such as fetchChildren(), fetchPath() etc). It can
+also offer some of the generic functions that all the database backends will
have
+in common (such as checking if a node exists f.e.).
+
+ezcTreeDbParentChild
+````````````````````
+
+Is one of the implementations of a Database backend. This one models the tree
+structure as a simple parent-child node ID list. The backend implements
+all the necessary operations which can not be shared between the different
+algorithms of storing trees. Example::
+
+ <?php
+ $tree = new ezcTreeDbParentChild(
+ ezcDbInstance::get(),
+ 'parent_child_table',
+ $store
+ );
+ ?>
+
+
+ezcTreeDbSerializedPath
+```````````````````````
+
+Is an implementation of a Serialized/`Materialized path`_ algorithm for
+storing tree structures in a database.
+
+ezcTreeDbNestedSet
+``````````````````
+
+Is another implementation of a Database backend, where the tree information
+is kept like a `nested set`_.
+
+
+ezcTreeXml
+``````````
+
+This class implements the tree structure in an XML file. The structure of
+this XML file is simply a nested set of nodes. See `XML schema`_ for a
+Relax NG-C version of the structure.
+
+Data Stores
+-----------
+
+ezcTreeDataStore
+````````````````
+
+Interface that defines the methods that all data stores should implement, such
+as retrieving data for a node ID, or a list of node IDs, storing data by ID
+etc. Stores are simple to implement, as the interfaces only consists of a few
+types. The component will standard have the following stores.
+
+ezcTreeDbDataStore
+``````````````````
+
+Abstract base class that can define some methods that can be shared by all the
+different database related backends.
+
+ezcTreeDbExternalTableDataStore
+```````````````````````````````
+
+A data store that implements storing of data in table different from the table
+that defines the tree structure. Example::
+
+ <?php
+ $store = new ezcTreeDbExternalTableDataStore( $this->dbh );
+ // table name, ID field, data field
+ $store->setDataTable( 'data', 'id', 'data' );
+ ?>
+
+ezcTreePersistentObjectDataStore
+````````````````````````````````
+
+Uses eZ Component's PersistentObject as a place to store data that is
associated
+in a tree structure.
+
+
+
+Algorithms
+==========
+
+_`Materialized Path`
+--------------------
+
+An algorithm that stores parent-child relations in the form of paths. For an
+overview of how this works, see `Trees in SQL
+<http://www.dbazine.com/oracle/or-articles/tropashko4>`_
+
+
+_`Nested Set`
+-------------
+
+An algorithm that stores parent-child relations with the help of left-right
+integers. For an overview of how this works, see `Trees in SQL
+<http://www.dbazine.com/oracle/or-articles/tropashko4>`_
+
+
+_`Topological Sorting`
+----------------------
+
+A sorting method that can sort the information in a tree in such a way that the
+leaf nodes are on top. See: http://en.wikipedia.org/wiki/Topological_sorting
+
+
+Data Structures
+===============
+
+Node IDs
+ All node IDs can be strings, but their charaters are restricted to what
+ you can put into a PHP array key and XML attribute string.
+
+_`XML Schema` for ezcDbXml
+
+ RelaxNG::
+
+ default namespace = "http://components.ez.no/Tree";
+ namespace etd = "http://components.ez.no/Tree/data";
+
+ start = element tree { node }
+ node =
+ element node {
+ attribute id { xsd:integer },
+ element etd:data { text }?,
+ (node)*
+ }
+
Propchange: experimental/Tree/design/design.txt
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: experimental/Tree/design/design.txt
------------------------------------------------------------------------------
--- svn:keywords (added)
+++ svn:keywords Thu Jul 19 16:18:55 2007
@@ -1,0 +1,2 @@
+Revision
+Date
Modified: experimental/Tree/design/requirements.txt
==============================================================================
--- experimental/Tree/design/requirements.txt [iso-8859-1] (original)
+++ experimental/Tree/design/requirements.txt [iso-8859-1] Thu Jul 19 16:18:55
2007
@@ -38,13 +38,15 @@
The following operations should be possible on the trees:
+- Fetching operations: subtree, children
+- Analytic operations to check whether there are children, how many children,
+ what the length to the root node is, if a node is a child or decendent of
+ another, etc.
+- Path operations: retrieving paths, iterate over paths
- Normal tree operations: adding, moving, deleting - multiple operations
should be done in one "transaction" if a backend can support that.
-- Path operations: retrieving paths, iterate over paths
+- Sorting operations: by deepness of subtree, `topological sort`_
- Iterating over subtrees
-- Analytic operations to check whether there are children, how many children,
- what the length to the root node is, etc.
-- Sorting operations: by deepness of subtree, `topological sort`_
- Conversion between backends (import/export to an internal structure)
Of course there can be data associated with each of the leaves in the
--
svn-components mailing list
[email protected]
http://lists.ez.no/mailman/listinfo/svn-components
