aGrUM  0.14.1
binSearchTree_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  ***************************************************************************/
27 #include <sstream>
28 #include <string>
29 
31 #include <agrum/core/exceptions.h>
32 
33 #ifndef DOXYGEN_SHOULD_SKIP_THIS
34 
35 namespace gum {
36 
37  // ===========================================================================
38  // ===========================================================================
39  // === GENERIC BINARY SEARCH TREE ITERATORS ===
40  // ===========================================================================
41  // ===========================================================================
42 
43  template < typename Val, class Cmp, class Node >
45  _node(0), _next_node(0), _prev_node(0), _parent(0), _left_child(0),
46  _right_child(0), _tree(0), _next_iter(0) {
47  GUM_CONSTRUCTOR(BinSearchTreeIterator);
48  }
49 
50  template < typename Val, class Cmp, class Node >
52  const BinSearchTreeIterator< Val, Cmp, Node >& from) :
53  _node(from._node),
56  _right_child(from._right_child), _tree(from._tree) {
57  GUM_CONS_CPY(BinSearchTreeIterator);
58 
59  if (_tree) {
60  _next_iter = _tree->_iterator_list;
61  _tree->_iterator_list = this;
62  } else
63  _next_iter = 0;
64  }
65 
66  template < typename Val, class Cmp, class Node >
69  const Node* current_node,
70  bool add_to_iterator_list) {
71  // remember: we do not check here whether the iterator already belongs to
72  // a tree. We assume that it is not so.
73 
74  _tree = const_cast< BinSearchTree< Val, Cmp, Node >* >(tree);
75  _node = const_cast< Node* >(current_node);
76 
77  if (add_to_iterator_list && _tree) {
78  _next_iter = _tree->_iterator_list;
79  _tree->_iterator_list = this;
80  }
81  }
82 
83  template < typename Val, class Cmp, class Node >
85  if (_tree) {
86  BinSearchTreeIterator< Val, Cmp, Node >*iter, *prev_iter = 0;
87 
88  for (iter = _tree->_iterator_list; iter != this && iter;
89  prev_iter = iter, iter = iter->_next_iter) {}
90 
91  if (iter) {
92  if (prev_iter)
93  prev_iter->_next_iter = _next_iter;
94  else
95  _tree->_iterator_list = _next_iter;
96  }
97  }
98  }
99 
100  template < typename Val, class Cmp, class Node >
102  GUM_DESTRUCTOR(BinSearchTreeIterator);
103 
104  // remove the iterator from its tree iterator's list
105  _detachFromTree();
106  }
107 
108  template < typename Val, class Cmp, class Node >
110  // remove the iterator from its tree iterator's list
111  _detachFromTree();
112 
113  // reset the iterator
114  _node = 0;
115  _next_node = 0;
116  _prev_node = 0;
117  _parent = 0;
118  _left_child = 0;
119  _right_child = 0;
120  _tree = 0;
121  _next_iter = 0;
122  }
123 
124  template < typename Val, class Cmp, class Node >
125  INLINE BinSearchTreeIterator< Val, Cmp, Node >&
127  operator=(const BinSearchTreeIterator< Val, Cmp, Node >& from) {
128  // avoid self assignment
129  if (this != &from) {
130  GUM_OP_CPY(BinSearchTreeIterator);
131 
132  // if from and this belong to different trees, detach this from its
133  // current tree
134  if (from._tree != _tree) {
135  _detachFromTree();
136  _tree = from._tree;
137 
138  if (_tree) {
139  _next_iter = _tree->_iterator_list;
140  _tree->_iterator_list = this;
141  } else
142  _next_iter = 0;
143  }
144 
145  // make the iterators point to the same element
146  _node = from._node;
147  _next_node = from._next_node;
148  _prev_node = from._prev_node;
149  _parent = from._parent;
150  _left_child = from._left_child;
151  _right_child = from._right_child;
152  }
153 
154  return *this;
155  }
156 
157  template < typename Val, class Cmp, class Node >
158  INLINE const Val& BinSearchTreeIterator< Val, Cmp, Node >::operator*() const {
159  if (_node) return _node->value();
160 
161  GUM_ERROR(UndefinedIteratorValue,
162  "the iterator does not point to a node of the binary tree");
163  }
164 
165  template < typename Val, class Cmp, class Node >
166  INLINE Node* BinSearchTree< Val, Cmp, Node >::_minNode(Node* node) const {
167  Node* prevNode = 0;
168 
169  for (; node; prevNode = node, node = node->leftChild()) {}
170 
171  return prevNode;
172  }
173 
174  template < typename Val, class Cmp, class Node >
175  INLINE Node* BinSearchTree< Val, Cmp, Node >::_maxNode(Node* node) const {
176  Node* prevNode = 0;
177 
178  for (; node; prevNode = node, node = node->rightChild()) {}
179 
180  return prevNode;
181  }
182 
183  template < typename Val, class Cmp, class Node >
184  INLINE Node* BinSearchTree< Val, Cmp, Node >::_succNode(Node* node) const {
185  if (!node) return 0;
186 
187  if (node->rightChild()) return _minNode(node->rightChild());
188 
189  Node* par = node->parent();
190 
191  while (par && (node->parentDir() == BinTreeDir::RIGHT_CHILD)) {
192  node = par;
193  par = par->parent();
194  }
195 
196  return par;
197  }
198 
199  template < typename Val, class Cmp, class Node >
200  INLINE Node* BinSearchTree< Val, Cmp, Node >::_prevNode(Node* node) const {
201  if (!node) return 0;
202 
203  if (node->leftChild()) return _maxNode(node->leftChild());
204 
205  Node* par = node->parent();
206 
207  while (par && (node->parentDir() == BinTreeDir::LEFT_CHILD)) {
208  node = par;
209  par = par->parent();
210  }
211 
212  return par;
213  }
214 
215  template < typename Val, class Cmp, class Node >
216  INLINE BinSearchTreeIterator< Val, Cmp, Node >&
218  // if there is a current node, use it to compute the next node, else use
219  // directly _next_node (this case obtains when the iterator was pointing
220  // toward a node that has been deleted before we use operator++)
221  _node = _node ? _tree->_succNode(_node) : _next_node;
222 
223  if (!_node) {
224  _next_node = 0;
225  _prev_node = 0;
226  _parent = 0;
227  _left_child = 0;
228  _right_child = 0;
229  }
230 
231  return *this;
232  }
233 
234  template < typename Val, class Cmp, class Node >
235  INLINE BinSearchTreeIterator< Val, Cmp, Node >&
237  // if there is a current node, use it to compute the preceding node, else
238  // use
239  // directly _prev_node (this case obtains when the iterator was pointing
240  // toward a node that has been deleted before we use operator--)
241  _node = _node ? _tree->_prevNode(_node) : _prev_node;
242 
243  if (!_node) {
244  _next_node = 0;
245  _prev_node = 0;
246  _parent = 0;
247  _left_child = 0;
248  _right_child = 0;
249  }
250 
251  return *this;
252  }
253 
254  template < typename Val, class Cmp, class Node >
256  operator==(const BinSearchTreeIterator< Val, Cmp, Node >& from) const {
257  if (_node)
258  return (_node == from._node);
259  else
260  return ((_node == from._node) && (_tree == from._tree)
261  && (_next_node == from._next_node) && (_prev_node == from._prev_node)
262  && (_parent == from._parent) && (_left_child == from._left_child)
263  && (_right_child == from._right_child));
264  }
265 
266  template < typename Val, class Cmp, class Node >
268  operator!=(const BinSearchTreeIterator< Val, Cmp, Node >& from) const {
269  if (_node)
270  return (_node != from._node);
271  else
272  return ((_node != from._node) || (_tree != from._tree)
273  || (_next_node != from._next_node) || (_prev_node != from._prev_node)
274  || (_parent != from._parent) || (_left_child != from._left_child)
275  || (_right_child != from._right_child));
276  }
277 
278  template < typename Val, class Cmp, class Node >
279  INLINE BinSearchTreeIterator< Val, Cmp, Node >&
281  // if there is a current node, use it to compute its parent node, else use
282  // directly _parent (this case obtains when the iterator was pointing
283  // toward a node that has been deleted before we use operation up)
284  _node = _node ? _node->parent() : _parent;
285 
286  if (!_node) {
287  _next_node = 0;
288  _prev_node = 0;
289  _parent = 0;
290  _left_child = 0;
291  _right_child = 0;
292  }
293 
294  return *this;
295  }
296 
297  template < typename Val, class Cmp, class Node >
298  INLINE BinSearchTreeIterator< Val, Cmp, Node >&
300  // if there is a current node, use it to compute its left child, else use
301  // directly _left_child (this case obtains when the iterator was pointing
302  // toward a node that has been deleted before we use operation downLeft)
303  _node = _node ? _node->leftChild() : _left_child;
304 
305  if (!_node) {
306  _next_node = 0;
307  _prev_node = 0;
308  _parent = 0;
309  _left_child = 0;
310  _right_child = 0;
311  }
312 
313  return *this;
314  }
315 
316  template < typename Val, class Cmp, class Node >
317  INLINE BinSearchTreeIterator< Val, Cmp, Node >&
319  // if there is a current node, use it to compute its right child, else use
320  // directly _right_child (this case obtains when the iterator was pointing
321  // toward a node that has been deleted before we use operation downRight)
322  _node = _node ? _node->rightChild() : _right_child;
323 
324  if (!_node) {
325  _next_node = 0;
326  _prev_node = 0;
327  _parent = 0;
328  _left_child = 0;
329  _right_child = 0;
330  }
331 
332  return *this;
333  }
334 
335  // ===========================================================================
336  // ===========================================================================
337  // === GENERIC BINARY SEARCH TREE ===
338  // ===========================================================================
339  // ===========================================================================
340 
341  template < typename Val, class Cmp, class Node >
342  BinSearchTree< Val, Cmp, Node >::BinSearchTree(bool uniqueness_policy) :
343  _root(0), _iterator_list(0), _uniqueness_policy(uniqueness_policy),
344  _nb_elements(0) {
345  GUM_CONSTRUCTOR(BinSearchTree);
346  _iter_end._initialize(this, 0, false);
347  }
348 
349  template < typename Val, class Cmp, class Node >
351  const BinSearchTree< Val, Cmp, Node >& from) :
352  _root(0),
353  _iterator_list(0), _uniqueness_policy(from._uniqueness_policy) {
354  // for debugging purposes
355  GUM_CONS_CPY(BinSearchTree);
356 
357  // copy the content of BinSearchTree "from"
358  _root = _copy(from._root);
359  _nb_elements = from._nb_elements;
360 
361  // initialize the end/rend iterator
362  _iter_end._initialize(this, 0, false);
363  }
364 
365  template < typename Val, class Cmp, class Node >
367  // first we clear all the iterators, i.e., we detach them from the tree
368  for (iterator *iter = _iterator_list, *next_iter = 0; iter; iter = next_iter) {
369  next_iter = iter->_next_iter;
370  iter->clear();
371  }
372 
373  // now, delete the whole tree
374  _deleteSubTree(_root);
375  _root = 0;
376  _nb_elements = 0;
377 
378  // note that there is no need to redefined end/rend as they do not rely
379  // on the content of the tree
380  }
381 
382  template < typename Val, class Cmp, class Node >
385  // avoid self assignment
386  if (this != &from) {
387  // for debugging purposes
388  GUM_OP_CPY(BinSearchTree);
389 
390  // if the tree is not currently empty, remove it
391  clear();
392 
393  // copy binary tree "from"
394  _uniqueness_policy = from._uniqueness_policy;
395  _root = _copy(from._root); // note that we can copy from's tree structure
396  // as from and this have the same ordering _cmp
397  _nb_elements = from._nb_elements;
398 
399  // note that we do not need to update the end/rend iterator as, besides
400  // field _tree, no other field is related to the current tree (i.e., all
401  // _*_node are set to 0
402  }
403 
404  return *this;
405  }
406 
407  template < typename Val, class Cmp, class Node >
409  // for debugging purposes
410  GUM_DESTRUCTOR(BinSearchTree);
411 
412  // clear all the iterators and remove all nodes
413  clear();
414  }
415 
416  template < typename Val, class Cmp, class Node >
418  Node* parent,
419  BinTreeDir dir) {
420  // if there is no node to copy, abort
421  if (!node) return 0;
422 
423  // create the copy of node
424  Node* new_node = new Node(*node);
425 
426  if (parent) parent->insertChild(*new_node, dir);
427 
428  // if necessary, create the left and right subgraphs
429  _copy(node->leftChild(), new_node, BinTreeDir::LEFT_CHILD);
430  _copy(node->rightChild(), new_node, BinTreeDir::RIGHT_CHILD);
431 
432  return new_node;
433  }
434 
435  template < typename Val, class Cmp, class Node >
437  // if there is no node to remove, return
438  if (!node) return;
439 
440  // delete the left and right subgraphs
441  _deleteSubTree(node->leftChild());
442  _deleteSubTree(node->rightChild());
443 
444  // delete the node itself
445  delete node;
446  }
447 
448  template < typename Val, class Cmp, class Node >
449  INLINE Node* BinSearchTree< Val, Cmp, Node >::_insert(const Val& val) {
450  // if the tree is not empty, search the binary search tree to know
451  // where the node should be inserted
452  if (_root) {
453  Node* node = _root;
454 
455  while (true) {
456  if (_cmp(val, node->value()))
457  if (!node->leftChild()) {
458  // here we are on a leaf => insert the new node
459  ++_nb_elements;
460  return node->insertLeftChild(val);
461  } else {
462  node = node->leftChild();
463  }
464  else if (_cmp(node->value(), val) || !_uniqueness_policy)
465  if (!node->rightChild()) {
466  // here we are on a leaf => insert the new node
467  ++_nb_elements;
468  return node->insertRightChild(val);
469  } else {
470  node = node->rightChild();
471  }
472  else {
473  // here we found a node with the same key and the uniqueness policy
474  // is set. So we should raise an exception
475  GUM_ERROR(DuplicateElement,
476  "Val " << val << " already in the binary search tree");
477  }
478  }
479  }
480 
481  // here the tree is empty, just create a new node
482  _root = new Node(val);
483  ++_nb_elements;
484  return _root;
485  }
486 
487  template < typename Val, class Cmp, class Node >
488  INLINE const Val& BinSearchTree< Val, Cmp, Node >::insert(const Val& val) {
489  return _insert(val)->value();
490  }
491 
492  template < typename Val, class Cmp, class Node >
493  INLINE const Val& BinSearchTree< Val, Cmp, Node >::rootValue() const {
494  if (_root == 0) {
495  GUM_ERROR(NotFound, "no value in an empty Binary Search tree");
496  }
497 
498  return _root->value();
499  }
500 
501  template < typename Val, class Cmp, class Node >
502  INLINE const Val& BinSearchTree< Val, Cmp, Node >::minValue() const {
503  if (_root == 0) {
504  GUM_ERROR(NotFound, "no minimal value in an empty Binary Search tree");
505  }
506 
507  return _minNode(_root)->value();
508  }
509 
510  template < typename Val, class Cmp, class Node >
511  INLINE const Val& BinSearchTree< Val, Cmp, Node >::maxValue() const {
512  if (_root == 0) {
513  GUM_ERROR(NotFound, "no maximal value in an empty Binary Search tree");
514  }
515 
516  return _maxNode(_root)->value();
517  }
518 
519  template < typename Val, class Cmp, class Node >
520  INLINE Node* BinSearchTree< Val, Cmp, Node >::_getNode(const Val& val) const {
521  // if the tree is not empty, search the binary search tree to know
522  // where the node could be
523  if (_root) {
524  Node* node = _root;
525 
526  while (true) {
527  if (_cmp(val, node->value())) {
528  if (!node->leftChild())
529  return 0;
530  else
531  node = node->leftChild();
532  } else if (_cmp(node->value(), val)) {
533  if (!node->rightChild())
534  return 0;
535  else
536  node = node->rightChild();
537  } else
538  return node;
539  }
540  } else {
541  return 0;
542  }
543  }
544 
545  template < typename Val, class Cmp, class Node >
546  INLINE bool BinSearchTree< Val, Cmp, Node >::contains(const Val& val) const {
547  return (_getNode(val) != 0);
548  }
549 
550  template < typename Val, class Cmp, class Node >
552  return _nb_elements;
553  }
554 
555  template < typename Val, class Cmp, class Node >
556  INLINE bool BinSearchTree< Val, Cmp, Node >::empty() const {
557  return (_nb_elements == 0);
558  }
559 
560  template < typename Val, class Cmp, class Node >
561  const std::string BinSearchTree< Val, Cmp, Node >::toString() const {
562  bool deja = false;
563  std::stringstream stream;
564  stream << "[";
565 
566  for (const_iterator iter = begin(); iter != end(); ++iter, deja = true) {
567  if (deja) stream << " , ";
568 
569  stream << *iter;
570  }
571 
572  stream << "]";
573 
574  return stream.str();
575  }
576 
577  template < typename Val, class Cmp, class Node >
579  return _uniqueness_policy;
580  }
581 
582  template < typename Val, class Cmp, class Node >
583  INLINE void
585  _uniqueness_policy = new_policy;
586  }
587 
588  template < typename Val, class Cmp, class Node >
589  INLINE BinSearchTreeIterator< Val, Cmp, Node >
591  BinSearchTreeIterator< Val, Cmp, Node > iter;
592  iter._initialize(this, _minNode(_root), true);
593  return iter;
594  }
595 
596  template < typename Val, class Cmp, class Node >
597  INLINE BinSearchTreeIterator< Val, Cmp, Node >
599  BinSearchTreeIterator< Val, Cmp, Node > iter;
600  iter._initialize(this, _minNode(_root), true);
601  return iter;
602  }
603 
604  template < typename Val, class Cmp, class Node >
605  INLINE BinSearchTreeIterator< Val, Cmp, Node >
607  BinSearchTreeIterator< Val, Cmp, Node > iter;
608  iter._initialize(this, _maxNode(_root), true);
609  return iter;
610  }
611 
612  template < typename Val, class Cmp, class Node >
613  INLINE BinSearchTreeIterator< Val, Cmp, Node >
615  BinSearchTreeIterator< Val, Cmp, Node > iter;
616  iter._initialize(this, _maxNode(_root), true);
617  return iter;
618  }
619 
620  template < typename Val, class Cmp, class Node >
621  INLINE const BinSearchTreeIterator< Val, Cmp, Node >&
623  return _iter_end;
624  }
625 
626  template < typename Val, class Cmp, class Node >
627  INLINE const BinSearchTreeIterator< Val, Cmp, Node >&
629  return _iter_end;
630  }
631 
632  template < typename Val, class Cmp, class Node >
633  INLINE const BinSearchTreeIterator< Val, Cmp, Node >&
635  return _iter_end;
636  }
637 
638  template < typename Val, class Cmp, class Node >
639  INLINE const BinSearchTreeIterator< Val, Cmp, Node >&
641  return _iter_end;
642  }
643 
644  template < typename Val, class Cmp, class Node >
645  INLINE BinSearchTreeIterator< Val, Cmp, Node >
647  BinSearchTreeIterator< Val, Cmp, Node > iter;
648  iter._initialize(this, _root, true);
649  return iter;
650  }
651 
652  template < typename Val, class Cmp, class Node >
653  INLINE BinSearchTreeIterator< Val, Cmp, Node >
655  BinSearchTreeIterator< Val, Cmp, Node > iter;
656  iter._initialize(this, _root, true);
657  return iter;
658  }
659 
660  template < typename Val, class Cmp, class Node >
661  void BinSearchTree< Val, Cmp, Node >::_erase(Node* node) {
662  if (!node) return;
663 
664  // update all the iterators pointing to node that they should point
665  // elsewhere
666  __updateEraseIterators(node);
667 
668  // update the number of elements contained in the tree
669  --_nb_elements;
670 
671  // now remove the node from the tree:
672 
673  // if the node has no children, then just remove it
674  if (!node->leftChild() && !node->rightChild()) {
675  // if the node was the only one in the tree, then the tree becomes empty
676  if (!node->parent()) _root = 0;
677 
678  // note that, when node has a parent, there is no need to remove the
679  // link between node and this parent: this will be taken care of by
680  // node's destructor.
681  }
682  // if there is just a right child
683  else if (!node->leftChild()) {
684  // just relink the right child with the parent (if any)
685  if (!node->parent()) {
686  // in this case, no need to remove the link between "node" and its
687  // child:
688  // this will be taken care of by the destructor of "node"
689  _root = node->rightChild();
690  } else {
691  Node * parent = node->parent(), *child = node->rightChild();
692  BinTreeDir dir = node->parentDir();
693  parent->eraseLink(dir);
694  node->eraseRightLink();
695  parent->insertChild(*child, dir);
696  }
697  }
698  // if there is just a left child
699  else if (!node->rightChild()) {
700  // just relink the left child with the parent (if any)
701  if (!node->parent()) {
702  // in this case, no need to remove the link between "node" and its
703  // child:
704  // this will be taken care of by the destructor of "node"
705  _root = node->leftChild();
706  } else {
707  Node * parent = node->parent(), *child = node->leftChild();
708  BinTreeDir dir = node->parentDir();
709  parent->eraseLink(dir);
710  node->eraseLeftLink();
711  parent->insertChild(*child, dir);
712  }
713  }
714  // ok, here there are two children
715  else {
716  __eraseWithTwoChildren(node);
717  }
718 
719  // now we shall physically remove node from memory
720  delete node;
721  }
722 
723  template < typename Val, class Cmp, class Node >
725  // the idea is to get the successor of "node" and substitute "node" by
726  // it. As "node" has two children, we are sure that the successor is one
727  // of node's descendants. Moreover, by its very definition, this
728  // successor has no left child. Hence, two cases can obtain:
729  // 1/ the successor is precisely node's right child. In this case, we just
730  // have to make node's left child be the left child of the successor,
731  // and node's parent be the successor's parent, and the tree is again
732  // a binary search tree.
733  // 2/ the successor is not node's right child. In this case, we know that
734  // the successor has a parent different from node and that the
735  // successor
736  // is a left child of this parent. We just need to put the right child
737  // of the successor (if any) as the left child of its parent, and to
738  // replace "node" by the successor.
739  Node* successor = _succNode(node);
740 
741  if (successor == node->rightChild()) { // proceed to case 1:
742  Node* left_child = node->leftChild();
743  node->eraseLeftLink();
744  node->eraseRightLink();
745  successor->insertLeftChild(*left_child);
746 
747  if (!node->parent()) {
748  // in this case, no need to remove the link between "node" and the
749  // successor: this will be taken care of by the destructor of "node"
750  _root = successor;
751  } else {
752  // rechain node's parent with its successor
753  BinTreeDir par_dir = node->parentDir();
754  Node* parent = node->parent();
755  parent->eraseLink(par_dir);
756  parent->insertChild(*successor, par_dir);
757  }
758  } else { // proceed to case 2:
759  Node* parent = successor->parent();
760  parent->eraseLeftLink();
761 
762  if (successor->rightChild()) {
763  Node* succ_child = successor->rightChild();
764  successor->eraseRightLink();
765  parent->insertLeftChild(*succ_child);
766  }
767 
768  Node *left = node->leftChild(), *right = node->rightChild();
769  node->eraseLeftLink();
770  node->eraseRightLink();
771  successor->insertLeftChild(*left);
772  successor->insertRightChild(*right);
773 
774  if (!node->parent()) {
775  _root = successor;
776  } else {
777  // rechain node's parent with its successor
778  BinTreeDir par_dir = node->parentDir();
779  Node* parent = node->parent();
780  parent->eraseLink(par_dir);
781  parent->insertChild(*successor, par_dir);
782  }
783  }
784  }
785 
786  template < typename Val, class Cmp, class Node >
787  INLINE void BinSearchTree< Val, Cmp, Node >::erase(const Val& val) {
788  Node* n = _getNode(val);
789 
790  if (n == nullptr)
791  GUM_ERROR(gum::NotFound, "Value \"" << val << "\" not found");
792 
793  _erase(n);
794  }
795 
796  template < typename Val, class Cmp, class Node >
797  INLINE void BinSearchTree< Val, Cmp, Node >::erase(const iterator& iter) {
798  _erase(iter._node);
799  }
800 
801  template < typename Val, class Cmp, class Node >
803  for (iterator* iter = _iterator_list; iter; iter = iter->_next_iter) {
804  // if the iterator points toward the node to be deleted, make its _node
805  // field point to 0 and update accordingly its other fields
806  if (iter->_node == node) {
807  iter->_node = 0;
808  iter->_next_node = _succNode(node);
809  iter->_prev_node = _prevNode(node);
810  iter->_parent = node->parent();
811  iter->_left_child = node->leftChild();
812  iter->_right_child = node->rightChild();
813  } else if (!iter->_node) {
814  if (iter->_next_node == node) iter->_next_node = _succNode(node);
815 
816  if (iter->_prev_node == node) iter->_prev_node = _prevNode(node);
817 
818  if (iter->_parent == node) iter->_parent = node->parent();
819 
820  if (iter->_left_child == node) iter->_left_child = node->leftChild();
821 
822  if (iter->_right_child == node) iter->_right_child = node->rightChild();
823  }
824  }
825  }
826 
827 } // namespace gum
828 
829 #endif // DOXYGEN_SHOULD_SKIP_THIS
virtual ~BinSearchTree()
Class destructor.
BinSearchTree< Val, Cmp, Node > * _tree
The binary search tree pointed to by the iterator.
BinSearchTreeIterator< Val, Cmp, Node > & operator--()
Point the iterator to the preceding value in the binary search tree.
Node * _getNode(const Val &val) const
Returns the node containing a given value.
Node * _maxNode(Node *node) const
Returns the greatest node w.r.t.
Basic binary search trees.
Size size() const
Returns the number of elements in the binary search tree.
Node * _left_child
The left child to be used when _node=0 and leftdown() is applied.
BinSearchTreeIterator< Val, Cmp, Node > & downRight()
Makes the iterator move to the right child of the node it points to.
Node * _next_node
The next node to be used when _node=0 (if a ++ operator is applied).
const Val & insert(const Val &val)
Creates a copy of the value, insert it in the tree and returns the copy value.
bool operator==(const BinSearchTreeIterator< Val, Cmp, Node > &from) const
Checks whether two iterators are pointing toward identical elements.
void clear()
Detach the iterator from its current tree (if any) and reset it.
gum is the global namespace for all aGrUM entities
Definition: agrum.h:25
BinSearchTreeIterator()
Class Constructors and Destructors.
iterator rbegin()
Reverse iterator.
bool operator!=(const BinSearchTreeIterator< Val, Cmp, Node > &from) const
Checks whether two iterators are pointing toward different elements.
Node * _copy(Node *root_from, Node *parent=0, BinTreeDir dir=BinTreeDir::LEFT_CHILD)
A method for recursively copying the contents of a BinSearchTree.
void _deleteSubTree(Node *node)
A method for recursively deleting a subtree of the gum::BinSearchTree.
BinTreeDir
The direction of a given edge in a binary tree.
Definition: binTreeNode.h:34
bool empty() const
Indicates whether the gum::BinSearchTree search tree is empty.
iterator root()
Returns an iterator at the root of the tree.
const Val & minValue() const
Returns the value of the leftmost node with the minimal key in the tree.
BinSearchTreeIterator< Val, Cmp, Node > & operator++()
Point the iterator to the next value in the binary search tree.
const Val & rootValue() const
Returns the value of the root of the tree.
Node * _parent
The parent to be used when _node=0 (if operation up is applied).
const Val & maxValue() const
Returns the value of the rightmost node with the maximal key in the tree.
aGrUM&#39;s exceptions
BinSearchTreeIterator< Val, Cmp, Node > & up()
Makes the iterator move to its parent node.
Node * _right_child
The right child to be used when _node=0 and rightdown() is applied.
BinSearchTree(bool uniqueness_policy=false)
Basic constructor: returns an empty binary search tree.
Node * _node
The current node pointed to by the iterator.
bool uniquenessPolicy() const
Returns the current uniqueness policy.
virtual Node * _insert(const Val &val)
Creates a copy of the value, insert it in the gum::BinSearchTree and returns the copy value...
void __updateEraseIterators(Node *node)
Update all iterators when a given node is deleted.
void clear()
Removes all the elements from the gum::BinSearchTree.
BinSearchTreeIterator< Val, Cmp, Node > & downLeft()
Makes the iterator move to the left child of the node it points to.
virtual const std::string toString() const
Displays the content of the tree, in increasing order w.r.t.
const iterator & rend()
Reverse end iterator.
void erase(const Val &val)
Erase the leftmost node with the given (key,val) pair.
void setUniquenessPolicy(const bool new_policy)
Enables the user to change dynamically the policy for checking whether there can exist several identi...
Node * _prev_node
The preceding node to be used when _node=0 (if a – operator is applied).
const iterator & end()
End iterator.
const Val & operator*() const
Returns the value pointed to by the iterator.
BinSearchTree< Val, Cmp, Node > & operator=(const BinSearchTree< Val, Cmp, Node > &from)
Copy operator.
BinSearchTreeIterator< Val, Cmp, Node > * _next_iter
The next iterator in the list of iterators of the binSearchTree.
Node * _succNode(Node *node) const
Returns the next node according to the weak ordering Cmp.
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:45
friend class BinSearchTree< Val, Cmp, Node >
To speed-up accesses.
BinSearchTreeIterator< Val, Cmp, Node > & operator=(const BinSearchTreeIterator< Val, Cmp, Node > &from)
Class operators.
~BinSearchTreeIterator()
Class destructor.
bool contains(const Val &val) const
Returns true if the gum::BinSearchTree contains the value.
virtual void _erase(Node *node)
Erase the node passed in argument.
void _initialize(const BinSearchTree< Val, Cmp, Node > *tree, const Node *current_node, bool add_to_iterator_list)
A function called to initialize an iterator.
iterator begin()
Begin iterator.
void _detachFromTree()
a method to detach the current iterator from its tree&#39;s iterator&#39;s list.
#define GUM_ERROR(type, msg)
Definition: exceptions.h:52
Node * _minNode(Node *node) const
Returns the smallest node w.r.t.
void __eraseWithTwoChildren(Node *node)
Erase a node with two children.
Node * _prevNode(Node *node) const
Returns the previous node according to weak ordering Cmp.