00001 #ifndef hpp_TPP_NTree_TPP_hpp
00002 #define hpp_TPP_NTree_TPP_hpp
00003
00004 namespace Tree
00005 {
00006
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 ) {}
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
00080 private:
00082 T data;
00084 PrivateNode * children;
00086 PrivateNode * next;
00088 PrivateNode * parent;
00090 uint32 childrenCount;
00092 DeleterObject<T> const & deleterObject;
00093
00094
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
00104 public:
00105
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
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
00165 if (node->parent->children == node) node->parent->children = node->next;
00166
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
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
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
00333 private:
00334 static DefaultDeleter<T> & getDefaultDeleterInstance() { static DefaultDeleter<T> xDD; return xDD; }
00335
00336
00337 public:
00338 friend class PrivateChildIterator<T>;
00339 friend class PrivateIterator<T>;
00340
00341 friend class NTree<T>;
00342 };
00343
00344
00350 template <class T>
00351 class NTree
00352 {
00353 public:
00354
00355 typedef PrivateNode<T> Node;
00356
00357 private:
00359 typedef T type;
00360 typedef const Node CNode;
00361
00362
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