aGrUM  0.14.2
binTreeNode_tpl.h
Go to the documentation of this file.
1 /***************************************************************************
2  * Copyright (C) 2005 by Christophe GONZALES and Pierre-Henri WUILLEMIN *
3  * {prenom.nom}_at_lip6.fr *
4  * *
5  * This program is free software; you can redistribute it and/or modify *
6  * it under the terms of the GNU General Public License as published by *
7  * the Free Software Foundation; either version 2 of the License, or *
8  * (at your option) any later version. *
9  * *
10  * This program is distributed in the hope that it will be useful, *
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of *
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
13  * GNU General Public License for more details. *
14  * *
15  * You should have received a copy of the GNU General Public License *
16  * along with this program; if not, write to the *
17  * Free Software Foundation, Inc., *
18  * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. *
19  ***************************************************************************/
20 
28 #ifndef DOXYGEN_SHOULD_SKIP_THIS
29 
30 namespace gum {
31 
32  template < typename Val >
33  INLINE BinTreeNode< Val >::BinTreeNode(const Val& v) :
34  _val(v), _parent(0), _parent_dir(BinTreeDir::NO_PARENT) {
35  // for debugging purposes
36  GUM_CONSTRUCTOR(BinTreeNode);
37 
38  // set the children
39  _children[0] = nullptr;
40  _children[1] = nullptr;
41  }
42 
43  template < typename Val >
44  INLINE BinTreeNode< Val >::BinTreeNode(const BinTreeNode< Val >& from) :
46  // for debugging purposes
47  GUM_CONS_CPY(BinTreeNode);
48 
49  // set the children
50  _children[0] = nullptr;
51  _children[1] = nullptr;
52  }
53 
54  template < typename Val >
56  // for debugging purposes
57  GUM_DESTRUCTOR(BinTreeNode);
58 
59  // update the tree accordingly to the removal of this
60  if (_parent)
61  _parent->_children[static_cast< int >(_parent_dir)] =
62  nullptr; // parent_dir can not be NO_PARENT (... sure ?)
63 
64  if (_children[0]) {
65  _children[0]->_parent = nullptr;
66  _children[0]->_parent_dir = BinTreeDir::NO_PARENT;
67  }
68 
69  if (_children[1]) {
70  _children[1]->_parent = nullptr;
71  _children[1]->_parent_dir = BinTreeDir::NO_PARENT;
72  }
73  }
74 
78  template < typename Val >
79  INLINE BinTreeNode< Val >& BinTreeNode< Val >::
80  operator=(const BinTreeNode< Val >& from) {
81  // avoid self assignment
82  if (this != &from) {
83  GUM_OP_CPY(BinTreeNode);
84  _val = from._val;
85  }
86 
87  return *this;
88  }
89 
90  template < typename Val >
91  INLINE Val& BinTreeNode< Val >::value() {
92  return _val;
93  }
94 
95  template < typename Val >
96  INLINE Val& BinTreeNode< Val >::operator*() {
97  return _val;
98  }
99 
100  template < typename Val >
101  INLINE BinTreeNode< Val >* BinTreeNode< Val >::child(BinTreeDir dir) const {
102  return _children[static_cast< int >(dir)];
103  }
104 
105  template < typename Val >
106  INLINE BinTreeNode< Val >* BinTreeNode< Val >::leftChild() const {
107  return _children[static_cast< int >(BinTreeDir::LEFT_CHILD)];
108  }
109 
110  template < typename Val >
111  INLINE BinTreeNode< Val >* BinTreeNode< Val >::rightChild() const {
112  return _children[static_cast< int >(BinTreeDir::RIGHT_CHILD)];
113  }
114 
115  template < typename Val >
116  INLINE BinTreeNode< Val >* BinTreeNode< Val >::parent() const {
117  return _parent;
118  }
119 
120  template < typename Val >
122  return _parent_dir;
123  }
124 
125  template < typename Val >
126  INLINE void BinTreeNode< Val >::insertLeftChild(BinTreeNode< Val >& new_child) {
127  if (new_child._parent) {
128  GUM_ERROR(DuplicateElement, "this child already has a parent in the BST");
129  }
130 
131  if (_children[static_cast< int >(BinTreeDir::LEFT_CHILD)]) {
132  GUM_ERROR(DuplicateElement, "this child already has a parent in the BST");
133  }
134 
135  // proceed to the chaining
136  new_child._parent = this;
137  new_child._parent_dir = BinTreeDir::LEFT_CHILD;
138  _children[static_cast< int >(BinTreeDir::LEFT_CHILD)] = &new_child;
139  }
140 
141  template < typename Val >
142  INLINE BinTreeNode< Val >* BinTreeNode< Val >::insertLeftChild(const Val& val) {
143  if (_children[static_cast< int >(BinTreeDir::LEFT_CHILD)]) {
144  GUM_ERROR(DuplicateElement, "this child already has a parent in the BST");
145  }
146 
147  BinTreeNode< Val >* new_child = new BinTreeNode< Val >(val);
148 
149  // proceed to the chaining
150  new_child->_parent = this;
151  new_child->_parent_dir = BinTreeDir::LEFT_CHILD;
152  _children[static_cast< int >(BinTreeDir::LEFT_CHILD)] = new_child;
153 
154  return new_child;
155  }
156 
157  template < typename Val >
158  INLINE void BinTreeNode< Val >::insertRightChild(BinTreeNode< Val >& new_child) {
159  if (new_child._parent) {
160  GUM_ERROR(DuplicateElement, "this child already has a parent in the BST");
161  }
162 
163  if (_children[static_cast< int >(BinTreeDir::RIGHT_CHILD)]) {
164  GUM_ERROR(DuplicateElement, "this node already has a right child");
165  }
166 
167  // proceed to the chaining
168  new_child._parent = this;
169  new_child._parent_dir = BinTreeDir::RIGHT_CHILD;
170  _children[static_cast< int >(BinTreeDir::RIGHT_CHILD)] = &new_child;
171  }
172 
173  template < typename Val >
174  INLINE BinTreeNode< Val >* BinTreeNode< Val >::insertRightChild(const Val& val) {
175  if (_children[static_cast< int >(BinTreeDir::RIGHT_CHILD)]) {
176  GUM_ERROR(DuplicateElement, "this node already has a right child");
177  }
178 
179  BinTreeNode< Val >* new_child = new BinTreeNode< Val >(val);
180 
181  // proceed to the chaining
182  new_child->_parent = this;
183  new_child->_parent_dir = BinTreeDir::RIGHT_CHILD;
184  _children[static_cast< int >(BinTreeDir::RIGHT_CHILD)] = new_child;
185 
186  return new_child;
187  }
188 
189  template < typename Val >
190  INLINE void BinTreeNode< Val >::insertChild(BinTreeNode< Val >& new_child,
191  BinTreeDir child_dir) {
192  if (new_child._parent) {
193  GUM_ERROR(DuplicateElement, "this child has already a parent");
194  }
195 
196  if (_children[static_cast< int >(child_dir)]) {
197  GUM_ERROR(DuplicateElement, "this node has already this child");
198  }
199 
200  // proceed to the chaining
201  new_child._parent = this;
202  new_child._parent_dir = child_dir;
203  _children[static_cast< int >(child_dir)] = &new_child;
204  }
205 
206  template < typename Val >
207  INLINE BinTreeNode< Val >*
208  BinTreeNode< Val >::insertChild(const Val& val, BinTreeDir child_dir) {
209  if (_children[static_cast< int >(child_dir)]) {
210  GUM_ERROR(DuplicateElement, "this node has already this child");
211  }
212 
213  BinTreeNode< Val >* new_child = new BinTreeNode< Val >(val);
214 
215  // proceed to the chaining
216  new_child->_parent = this;
217  new_child->_parent_dir = child_dir;
218  _children[static_cast< int >(child_dir)] = new_child;
219 
220  return new_child;
221  }
222 
223  template < typename Val >
224  INLINE void BinTreeNode< Val >::eraseLeftLink() {
225  if (_children[static_cast< int >(BinTreeDir::LEFT_CHILD)]) {
226  _children[static_cast< int >(BinTreeDir::LEFT_CHILD)]->_parent = nullptr;
227  _children[static_cast< int >(BinTreeDir::LEFT_CHILD)]->_parent_dir =
229  _children[static_cast< int >(BinTreeDir::LEFT_CHILD)] = nullptr;
230  }
231  }
232 
233  template < typename Val >
234  INLINE void BinTreeNode< Val >::eraseRightLink() {
235  if (_children[static_cast< int >(BinTreeDir::RIGHT_CHILD)]) {
236  _children[static_cast< int >(BinTreeDir::RIGHT_CHILD)]->_parent = nullptr;
237  _children[static_cast< int >(BinTreeDir::RIGHT_CHILD)]->_parent_dir =
239  _children[static_cast< int >(BinTreeDir::RIGHT_CHILD)] = nullptr;
240  }
241  }
242 
243  template < typename Val >
244  INLINE void BinTreeNode< Val >::eraseLink(BinTreeDir tree_dir) {
245  if (_children[static_cast< int >(tree_dir)]) {
246  _children[static_cast< int >(tree_dir)]->_parent = nullptr;
247  _children[static_cast< int >(tree_dir)]->_parent_dir = BinTreeDir::NO_PARENT;
248  _children[static_cast< int >(tree_dir)] = nullptr;
249  }
250  }
251 
252  template < typename Val >
253  INLINE BinTreeNode< Val >* BinTreeNode< Val >::leftmostNode() const {
254  BinTreeNode< Val >* node = const_cast< BinTreeNode< Val >* >(this);
255 
256  while (node->_children[static_cast< int >(BinTreeDir::LEFT_CHILD)])
257  node = node->_children[static_cast< int >(BinTreeDir::LEFT_CHILD)];
258 
259  return node;
260  }
261 
262  template < typename Val >
263  INLINE BinTreeNode< Val >* BinTreeNode< Val >::rightmostNode() const {
264  BinTreeNode< Val >* node = const_cast< BinTreeNode< Val >* >(this);
265 
266  while (node->_children[static_cast< int >(BinTreeDir::RIGHT_CHILD)])
267  node = node->_children[static_cast< int >(BinTreeDir::RIGHT_CHILD)];
268 
269  return node;
270  }
271 
272  template < typename Val >
273  INLINE BinTreeNode< Val >* BinTreeNode< Val >::root() const {
274  BinTreeNode< Val >* node = const_cast< BinTreeNode< Val >* >(this);
275 
276  while (node->_parent)
277  node = node->_parent;
278 
279  return node;
280  }
281 
282 } // namespace gum
283 
284 #endif // DOXYGEN_SHOULD_SKIP_THIS
BinTreeNode< Val > * child(BinTreeDir dir) const
Returns the given child of a node.
Val & value()
Returns the value stored in a node of the binary search tree.
BinTreeNode< Val > * leftmostNode() const
Returns the leftmost node of the current tree.
Val _val
The value stored in a node of the tree.
Definition: binTreeNode.h:316
BinTreeNode< Val > * insertLeftChild(const Val &val)
Adds a new left child to the current node.
void eraseLeftLink()
Remove the link between the current node and its left child.
BinTreeNode< Val > * leftChild() const
Returns the given child of a node.
BinTreeNode< Val > * _children[2]
The children of the current node.
Definition: binTreeNode.h:325
gum is the global namespace for all aGrUM entities
Definition: agrum.h:25
BinTreeNode(const Val &v)
Basic constructor: a node without parent nor children.
void eraseLink(BinTreeDir tree_dir)
Remove the link between the current node and one of its children.
BinTreeDir
The direction of a given edge in a binary tree.
Definition: binTreeNode.h:34
BinTreeNode< Val > & operator=(const BinTreeNode< Val > &from)
Copy operator: copy the value of from into this.
BinTreeNode< Val > * rightmostNode() const
Returns the rightmost node of the current tree.
BinTreeDir _parent_dir
the direction to follow from the parent to reach the current node.
Definition: binTreeNode.h:322
void eraseRightLink()
Remove the link between the current node and its right child.
BinTreeDir parentDir() const
Returns the direction of the edge parent->current node, if any.
BinTreeNode< Val > * root() const
Returns the top ancestor of the current tree.
BinTreeNode< Val > * rightChild() const
Returns the given child of a node.
BinTreeNode< Val > * parent() const
Returns the parent of a node.
Val & operator*()
Alias for method value.
BinTreeNode< Val > * _parent
The parent of the node.
Definition: binTreeNode.h:319
BinTreeNode< Val > * insertRightChild(const Val &val)
Adds a new left child to the current node.
~BinTreeNode()
Class destructor.
#define GUM_ERROR(type, msg)
Definition: exceptions.h:52
BinTreeNode< Val > * insertChild(const Val &val, BinTreeDir child_dir)
Adds a new child to the current node.