include/Tree/NTree.hpp

Go to the documentation of this file.
00001 #ifndef hpp_TPP_NTree_TPP_hpp
00002 #define hpp_TPP_NTree_TPP_hpp
00003 
00004 namespace Tree
00005 {
00006     // Forward declaration
00007     template <class T> class NTree;
00008     template <class T> class PrivateNode;
00009 
00010     
00012     template <class T>
00013     struct DeleterObject
00014     {
00015         virtual void deleteNode(PrivateNode<T> * node) const = 0;
00016     };
00017 
00018     template <class T>
00019     struct DefaultDeleter : public DeleterObject<T>
00020     {
00021         virtual void deleteNode(PrivateNode<T> * node) const { delete node; }
00022     };
00023 
00025     template <class T>
00026     class PrivateIterator
00027     {
00028     private:
00029         typedef const PrivateNode<T> CNode;
00030         CNode * current;
00031 
00032     public:
00033         inline bool isValid() const { return current != 0; }
00034         inline CNode * getNode() const { return current; }
00035         inline void goNext() { current = current ? current->next : 0; }
00036 
00037         PrivateIterator(CNode * cur) : current(cur /*? (cur->children ? cur->children : cur) : 0*/) {}
00038     };
00039 
00041     template <class T>
00042     class PrivateChildIterator
00043     {
00044     private:
00045         typedef const PrivateNode<T> CNode;
00046         CNode * current;
00047         int     level;
00048 
00049     public:
00050         inline bool isValid() const { return current != 0; }
00051         inline CNode * getNode() const { return current; }
00052         inline int getLevel() const { return level; }
00053         inline void goNext() 
00054         { 
00055             if (current)
00056             {
00057                 if (current->children) { current = current->children; level++; return; }
00058                 if (current->next) { current = current->next; return; }
00059                 while (current) 
00060                 {   
00061                     level--;
00062                     if (current->parent && current->parent->next) 
00063                     { 
00064                         current = current->parent->next; 
00065                         return; 
00066                     } 
00067                     current = current->parent;
00068                 }
00069             }
00070         }
00071 
00072         PrivateChildIterator(CNode * cur, const uint32 startLevel = 0) : current(cur), level(startLevel) {}
00073     };
00074 
00076     template <class T>
00077     class PrivateNode
00078     {
00079         // Members
00080     private:
00082         T                           data;
00084         PrivateNode *               children;
00086         PrivateNode *               next;
00088         PrivateNode *               parent;
00090         uint32                      childrenCount;
00092         DeleterObject<T> const &    deleterObject;
00093 
00094         // Helper method
00095     private:
00097         inline void deleteNode(PrivateNode * node) const { deleterObject.deleteNode(node); }
00098 
00099     public:
00100         typedef PrivateIterator<T> Iterator;
00101         typedef PrivateChildIterator<T> ChildIterator;
00102 
00103         // Interface
00104     public:
00105         // Member access
00108         inline PrivateNode *  firstChild() const throw() { return children; }
00111         inline PrivateNode *  nextNode() const throw() { return next; }
00114         inline PrivateNode *  parentNode() const throw() { return parent; }
00117         inline T &     getData() throw() { return data; }
00120         inline const T &     getData() const throw() { return data; }
00123         inline const uint32  getChildrenCount() const throw() { return childrenCount; }
00124 
00125     
00126         // Operations
00129         inline void appendChild(PrivateNode * node) throw() { if (!node) return; node->parent = this; PrivateNode * last = lastChild(); if (last) last->next = node; else children = node; childrenCount ++; }    
00133         inline PrivateNode * lastChild() const throw() { PrivateNode * child = children; while (child) { if (!child->next) break; child = child->next; } return child; }
00135         inline void deleteChildren() throw()    { PrivateNode * child = children; while (child) { PrivateNode * _next = child->next; deleteNode(child); child = _next; } }
00139         inline PrivateNode * childAtIndex(uint32 index) const throw() { if (index >= childrenCount) return 0; PrivateNode * child = children; while (child && index--) { child = child->next; } return child; } 
00143         inline const uint32 findChildIndex(const T lookFor) const throw() { uint32 index = 0; PrivateNode * child = children; while (child && !(child->data == lookFor)) { child = child->next; ++index; } return index; } 
00147         inline void insertChildBefore(PrivateNode * node, uint32 index = 0) throw() { if (!node) return; node->parent = this; if (!index) { node->next = children; children = node; } else { PrivateNode * before = childAtIndex(index - 1); if (!before) { appendChild(node); return; } node->next = before->next; before->next = node; } childrenCount++; }
00158         inline PrivateNode * forgetChildAtIndex(uint32 index) throw() 
00159         {
00160             PrivateNode * node = childAtIndex(index); 
00161             if (!node) return 0; 
00162             if (node->parent)
00163             {
00164                 // Is it the first child of a list ?
00165                 if (node->parent->children == node) node->parent->children = node->next; 
00166                 // Find the node that is just before this one
00167                 else 
00168                 {
00169                     PrivateNode * before = node->parent->children;
00170                     while (before && before->next != node) { before = before->next; }
00171                     if (!before) return 0;
00172 
00173                     before->next = node->next;
00174                 }
00175                 --node->parent->childrenCount;
00176                 // Don't allow the destructor to modify the parent
00177                 node->parent = 0;
00178             } 
00179             return node;
00180         }
00184         inline bool   deleteChildAtIndex(uint32 index) throw() 
00185         { 
00186             PrivateNode * node = forgetChildAtIndex(index);
00187             if (node) { deleteNode(node); return true; }
00188             return false;
00189         } 
00206         template <typename Obj, typename Process>
00207         inline PrivateNode * findChild(const Obj & instance, const Process & method, bool searchInChildren) const throw()
00208         {
00209             PrivateNode * child = children;
00210             // If compilation stops here, you need to make sure the method signature is correct
00211             if (searchInChildren)
00212                 while (child && !(instance.*method)(child->data)) { if (child->children) { PrivateNode * result = child->findChild(instance, method, searchInChildren); if (result) return result; } child = child->next; }
00213             else
00214                 while (child && !(instance.*method)(child->data)) { child = child->next; }
00215 
00216             return child;
00217         }
00234         template <typename Obj, typename Process>
00235         inline bool applyOnChildrenNode(const Obj & instance, const Process & method, bool applyInChildren) throw()
00236         {
00237             PrivateNode * child = children;
00238             if (!child) return false;
00239 
00240             if (applyInChildren)
00241             {
00242                 ChildIterator iter = child->getChildIterator(); 
00243                 while (iter.isValid() && (instance.*method)(iter.getNode())) { iter.goNext(); }
00244                 return iter.isValid() ? false : true;
00245             }
00246             else
00247             {
00248                 Iterator iter = child->getAllIterator(); 
00249                 while (iter.isValid() && (instance.*method)(iter.getNode())) { iter.goNext(); }
00250                 return iter.isValid() ? false : true;
00251             }
00252         }        
00269         template <typename Obj, typename Process>
00270         inline bool applyOnChildrenData(const Obj & instance, const Process & method, bool applyInChildren) throw()
00271         {
00272             PrivateNode * child = children;
00273             if (!child) return false;
00274             if (applyInChildren)
00275             {
00276                 ChildIterator iter = child->getChildIterator(); 
00277                 while (iter.isValid() && (instance.*method)(iter.getNode()->data)) { iter.goNext(); }
00278                 return iter.isValid() ? false : true;
00279             }
00280             else
00281             {
00282                 Iterator iter = child->getAllIterator(); 
00283                 while (iter.isValid() && (instance.*method)(iter.getNode()->data)) { iter.goNext(); }
00284                 return iter.isValid() ? false : true;
00285             }
00286         }
00303         template <typename Obj, typename Process>
00304         inline bool applyOnChildrenDataLevel(const Obj & instance, const Process & method, const uint32 startLevel = 0) throw()
00305         {
00306             PrivateNode * child = children;
00307             if (!child) return false;
00308             ChildIterator iter = child->getChildIterator(startLevel); 
00309             while (iter.isValid() && (instance.*method)(iter.getNode()->data, iter.getLevel())) { iter.goNext(); }
00310             return iter.isValid() ? false : true;
00311         }
00312 
00313 
00317         inline Iterator getAllIterator() const { return Iterator(this); }
00318 
00322         inline ChildIterator getChildIterator(const uint32 startLevel = 0) const { return ChildIterator(this, startLevel); }
00323 
00324     public:
00326         PrivateNode (const T & _data, PrivateNode * root = 0, const DeleterObject<T> & xDO = getDefaultDeleterInstance()) : data(_data), children(0), parent(root), next(0), childrenCount(0), deleterObject(xDO) {}
00328         ~PrivateNode() { if (parent) --parent->childrenCount; deleteChildren(); }
00330         inline void Suicide() { deleteNode(this); }
00331         
00332         // The default deleter when none is specified
00333     private:
00334         static DefaultDeleter<T> & getDefaultDeleterInstance() { static DefaultDeleter<T> xDD; return xDD; }
00335 
00336         // Allow iterators to directly manipulate us
00337     public:
00338         friend class PrivateChildIterator<T>;
00339         friend class PrivateIterator<T>;
00340         // Allow the Tree to access us (required to comply with C++ standard)
00341         friend class NTree<T>;
00342     };
00343 
00344 
00350     template <class T>
00351     class NTree
00352     {
00353     public:
00354         // Forward declaration
00355         typedef PrivateNode<T> Node;
00356 
00357     private:
00359         typedef T type;
00360         typedef const Node CNode;
00361 
00362         // Member
00363     private:
00365         Node *                  root;
00366 
00367     public:
00369         NTree(const T & _root, const DeleterObject<T> & xDO = Node::getDefaultDeleterInstance()) : root(0)  
00370         { 
00371             root = new Node(_root, 0, xDO); 
00372         }
00373 
00375         ~NTree() { if (root) root->Suicide(); root = 0; }
00376 
00378         inline Node * getRootNode() { return root; }
00380         static DefaultDeleter<T> & getDefaultDeleterInstance() { return Node::getDefaultDeleterInstance(); }
00381     };
00382 
00383 
00384 
00385 }
00386 
00387 
00388 
00389 #endif

(C) An X-Ryl669 project 2007

This document describes Unlimited Zooming Interface source code. UZI stands for Unlimited Zooming Interface, and source code license is