HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
UT_BidirectionalTree.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * NAME: UT_BidirectionalTree.h (UT Library, C++)
7  *
8  * COMMENTS: A simple templatized intrusive n-ary tree class using
9  * doubly-linked parent and sibling pointers. It supports O(1)
10  * addition and removal from any tree node. Tree nodes are
11  * automatically removed from the tree when deleted.
12  *
13  * For a lighter singly-linked version, see UT_Tree.
14  *
15  * *** To be extended as required by users of this class. ***
16  *
17  * USAGE: Declare your tree node class like so:
18  *
19  * class MyType : public UT_BidirectionalTree<MyType>
20  *
21  */
22 
23 #ifndef __UT_BIDIRECTIONALTREE_H__
24 #define __UT_BIDIRECTIONALTREE_H__
25 
26 #include "UT_API.h"
27 #include <stddef.h>
28 #include "UT_Assert.h"
29 
30 template <typename T>
32 {
33 public:
35 
37  : myParent(NULL)
38  , myChildren(NULL)
39  , myPrevSibling(NULL)
40  , myNextSibling(NULL)
41  {
42  }
44  {
45  unlinkAll();
46  }
47 
48  /// Unlink this node from the tree completely.
49  void unlinkAll()
50  {
51  setParent(NULL);
53  }
54 
55  /// Set the parent of this node. If it already belongs to a tree, it will
56  /// first be removed from it.
57  void setParent(NodeType *parent)
58  {
59  if (myParent == parent)
60  return;
61 
62  if (myParent)
63  {
64  myParent->removeChild(this);
65  UT_ASSERT(myParent == NULL);
66  UT_ASSERT(myPrevSibling == NULL);
67  UT_ASSERT(myNextSibling == NULL);
68  }
69  if (parent)
70  {
71  parent->addChildToHead(this);
72  UT_ASSERT(myParent == parent);
73  }
74  }
75 
76  /// Add a child node to the head of the children list. O(1)
77  void addChildToHead(NodeType *child)
78  {
79  UT_ASSERT(child->myParent == NULL);
80  UT_ASSERT(child->myPrevSibling == NULL);
81  UT_ASSERT(child->myNextSibling == NULL);
82 
83  child->myParent = this;
84  child->setNextSibling(myChildren);
85  myChildren = child;
86  }
87 
88  /// Remove the given child node.
89  void removeChild(NodeType *child)
90  {
91  NodeType * old_prev;
92  NodeType * old_next;
93 
94  UT_ASSERT(child->myParent == this);
95 
96  if (child == myChildren)
97  myChildren = child->myNextSibling;
98 
99  child->myParent = NULL;
100  old_prev = child->setPrevSibling(NULL);
101  old_next = child->setNextSibling(NULL);
102  if (old_prev)
103  (void) old_prev->setNextSibling(old_next);
104  else if (old_next)
105  (void) old_next->setPrevSibling(old_prev);
106 
107  UT_ASSERT(myChildren == NULL || myChildren->myPrevSibling == NULL);
108  }
109 
110  /// Remove all children from the tree.
112  {
113  while (myChildren)
114  removeChild(myChildren);
115  }
116 
117  /// Iterators
118  // @{
119  T *getParent() const
120  {
121  UT_ASSERT(myParent || (!myPrevSibling && !myNextSibling));
122  return (T *)myParent;
123  }
124  T *getFirstChild() const
125  {
126  return (T *)myChildren;
127  }
128  T *getPrevSibling() const
129  {
130  return (T *)myPrevSibling;
131  }
132  T *getNextSibling() const
133  {
134  return (T *)myNextSibling;
135  }
136  // @}
137 
138  /// Some utility methods
139  // @{
140  bool hasParent() const { return (myParent != NULL); }
141  bool hasChildren() const { return (myChildren != NULL); }
142  bool hasSiblings() const { return (myPrevSibling || myNextSibling); }
143  bool isInTree() const { bool yesno = hasParent() || hasChildren();
144  UT_ASSERT(yesno || !hasSiblings());
145  return yesno; }
146  // @}
147 
148 private:
149  NodeType *setNextSibling(NodeType *next)
150  {
151  NodeType *old = myNextSibling;
152 
153  if (myNextSibling)
154  myNextSibling->myPrevSibling = NULL;
155  myNextSibling = next;
156  if (myNextSibling)
157  myNextSibling->myPrevSibling = this;
158 
159  return old;
160  }
161  NodeType *setPrevSibling(NodeType *prev)
162  {
163  NodeType *old = myPrevSibling;
164 
165  if (myPrevSibling)
166  myPrevSibling->myNextSibling = NULL;
167  myPrevSibling = prev;
168  if (myPrevSibling)
169  myPrevSibling->myNextSibling = this;
170 
171  return old;
172  }
173 
174 private:
175  NodeType * myParent;
176  NodeType * myChildren;
177  NodeType * myPrevSibling;
178  NodeType * myNextSibling;
179 };
180 
181 #endif // __UT_BIDIRECTIONALTREE_H__
UT_BidirectionalTree< T > NodeType
typedef void(APIENTRYP PFNGLCULLFACEPROC)(GLenum mode)
bool isInTree() const
Some utility methods.
T * getParent() const
Iterators.
void unlinkAll()
Unlink this node from the tree completely.
#define UT_ASSERT(ZZ)
Definition: UT_Assert.h:102
bool hasSiblings() const
Some utility methods.
bool hasChildren() const
Some utility methods.
T * getNextSibling() const
Iterators.
T * getPrevSibling() const
Iterators.
void removeAllChildren()
Remove all children from the tree.
T * getFirstChild() const
Iterators.
bool hasParent() const
Some utility methods.
void addChildToHead(NodeType *child)
Add a child node to the head of the children list. O(1)
void setParent(NodeType *parent)
void removeChild(NodeType *child)
Remove the given child node.