aGrUM  0.13.2
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, "key already defined in binary search tree");
476  }
477  }
478  }
479 
480  // here the tree is empty, just create a new node
481  _root = new Node(val);
482  ++_nb_elements;
483  return _root;
484  }
485 
486  template < typename Val, class Cmp, class Node >
487  INLINE const Val& BinSearchTree< Val, Cmp, Node >::insert(const Val& val) {
488  return _insert(val)->value();
489  }
490 
491  template < typename Val, class Cmp, class Node >
492  INLINE const Val& BinSearchTree< Val, Cmp, Node >::rootValue() const {
493  if (_root == 0) {
494  GUM_ERROR(NotFound, "no value in an empty Binary Search tree");
495  }
496 
497  return _root->value();
498  }
499 
500  template < typename Val, class Cmp, class Node >
501  INLINE const Val& BinSearchTree< Val, Cmp, Node >::minValue() const {
502  if (_root == 0) {
503  GUM_ERROR(NotFound, "no minimal value in an empty Binary Search tree");
504  }
505 
506  return _minNode(_root)->value();
507  }
508 
509  template < typename Val, class Cmp, class Node >
510  INLINE const Val& BinSearchTree< Val, Cmp, Node >::maxValue() const {
511  if (_root == 0) {
512  GUM_ERROR(NotFound, "no maximal value in an empty Binary Search tree");
513  }
514 
515  return _maxNode(_root)->value();
516  }
517 
518  template < typename Val, class Cmp, class Node >
519  INLINE Node* BinSearchTree< Val, Cmp, Node >::_getNode(const Val& val) const {
520  // if the tree is not empty, search the binary search tree to know
521  // where the node could be
522  if (_root) {
523  Node* node = _root;
524 
525  while (true) {
526  if (_cmp(val, node->value())) {
527  if (!node->leftChild())
528  return 0;
529  else
530  node = node->leftChild();
531  } else if (_cmp(node->value(), val)) {
532  if (!node->rightChild())
533  return 0;
534  else
535  node = node->rightChild();
536  } else
537  return node;
538  }
539  } else {
540  return 0;
541  }
542  }
543 
544  template < typename Val, class Cmp, class Node >
545  INLINE bool BinSearchTree< Val, Cmp, Node >::contains(const Val& val) const {
546  return (_getNode(val) != 0);
547  }
548 
549  template < typename Val, class Cmp, class Node >
551  return _nb_elements;
552  }
553 
554  template < typename Val, class Cmp, class Node >
555  INLINE bool BinSearchTree< Val, Cmp, Node >::empty() const {
556  return (_nb_elements == 0);
557  }
558 
559  template < typename Val, class Cmp, class Node >
560  const std::string BinSearchTree< Val, Cmp, Node >::toString() const {
561  bool deja = false;
562  std::stringstream stream;
563  stream << "[";
564 
565  for (const_iterator iter = begin(); iter != end(); ++iter, deja = true) {
566  if (deja) stream << " , ";
567 
568  stream << *iter;
569  }
570 
571  stream << "]";
572 
573  return stream.str();
574  }
575 
576  template < typename Val, class Cmp, class Node >
578  return _uniqueness_policy;
579  }
580 
581  template < typename Val, class Cmp, class Node >
582  INLINE void
584  _uniqueness_policy = new_policy;
585  }
586 
587  template < typename Val, class Cmp, class Node >
588  INLINE BinSearchTreeIterator< Val, Cmp, Node >
590  BinSearchTreeIterator< Val, Cmp, Node > iter;
591  iter._initialize(this, _minNode(_root), true);
592  return iter;
593  }
594 
595  template < typename Val, class Cmp, class Node >
596  INLINE BinSearchTreeIterator< Val, Cmp, Node >
598  BinSearchTreeIterator< Val, Cmp, Node > iter;
599  iter._initialize(this, _minNode(_root), true);
600  return iter;
601  }
602 
603  template < typename Val, class Cmp, class Node >
604  INLINE BinSearchTreeIterator< Val, Cmp, Node >
606  BinSearchTreeIterator< Val, Cmp, Node > iter;
607  iter._initialize(this, _maxNode(_root), true);
608  return iter;
609  }
610 
611  template < typename Val, class Cmp, class Node >
612  INLINE BinSearchTreeIterator< Val, Cmp, Node >
614  BinSearchTreeIterator< Val, Cmp, Node > iter;
615  iter._initialize(this, _maxNode(_root), true);
616  return iter;
617  }
618 
619  template < typename Val, class Cmp, class Node >
620  INLINE const BinSearchTreeIterator< Val, Cmp, Node >&
622  return _iter_end;
623  }
624 
625  template < typename Val, class Cmp, class Node >
626  INLINE const BinSearchTreeIterator< Val, Cmp, Node >&
628  return _iter_end;
629  }
630 
631  template < typename Val, class Cmp, class Node >
632  INLINE const BinSearchTreeIterator< Val, Cmp, Node >&
634  return _iter_end;
635  }
636 
637  template < typename Val, class Cmp, class Node >
638  INLINE const BinSearchTreeIterator< Val, Cmp, Node >&
640  return _iter_end;
641  }
642 
643  template < typename Val, class Cmp, class Node >
644  INLINE BinSearchTreeIterator< Val, Cmp, Node >
646  BinSearchTreeIterator< Val, Cmp, Node > iter;
647  iter._initialize(this, _root, true);
648  return iter;
649  }
650 
651  template < typename Val, class Cmp, class Node >
652  INLINE BinSearchTreeIterator< Val, Cmp, Node >
654  BinSearchTreeIterator< Val, Cmp, Node > iter;
655  iter._initialize(this, _root, true);
656  return iter;
657  }
658 
659  template < typename Val, class Cmp, class Node >
660  void BinSearchTree< Val, Cmp, Node >::_erase(Node* node) {
661  if (!node) return;
662 
663  // update all the iterators pointing to node that they should point
664  // elsewhere
665  __updateEraseIterators(node);
666 
667  // update the number of elements contained in the tree
668  --_nb_elements;
669 
670  // now remove the node from the tree:
671 
672  // if the node has no children, then just remove it
673  if (!node->leftChild() && !node->rightChild()) {
674  // if the node was the only one in the tree, then the tree becomes empty
675  if (!node->parent()) _root = 0;
676 
677  // note that, when node has a parent, there is no need to remove the
678  // link between node and this parent: this will be taken care of by
679  // node's destructor.
680  }
681  // if there is just a right child
682  else if (!node->leftChild()) {
683  // just relink the right child with the parent (if any)
684  if (!node->parent()) {
685  // in this case, no need to remove the link between "node" and its
686  // child:
687  // this will be taken care of by the destructor of "node"
688  _root = node->rightChild();
689  } else {
690  Node * parent = node->parent(), *child = node->rightChild();
691  BinTreeDir dir = node->parentDir();
692  parent->eraseLink(dir);
693  node->eraseRightLink();
694  parent->insertChild(*child, dir);
695  }
696  }
697  // if there is just a left child
698  else if (!node->rightChild()) {
699  // just relink the left child with the parent (if any)
700  if (!node->parent()) {
701  // in this case, no need to remove the link between "node" and its
702  // child:
703  // this will be taken care of by the destructor of "node"
704  _root = node->leftChild();
705  } else {
706  Node * parent = node->parent(), *child = node->leftChild();
707  BinTreeDir dir = node->parentDir();
708  parent->eraseLink(dir);
709  node->eraseLeftLink();
710  parent->insertChild(*child, dir);
711  }
712  }
713  // ok, here there are two children
714  else {
715  __eraseWithTwoChildren(node);
716  }
717 
718  // now we shall physically remove node from memory
719  delete node;
720  }
721 
722  template < typename Val, class Cmp, class Node >
724  // the idea is to get the successor of "node" and substitute "node" by
725  // it. As "node" has two children, we are sure that the successor is one
726  // of node's descendants. Moreover, by its very definition, this
727  // successor has no left child. Hence, two cases can obtain:
728  // 1/ the successor is precisely node's right child. In this case, we just
729  // have to make node's left child be the left child of the successor,
730  // and node's parent be the successor's parent, and the tree is again
731  // a binary search tree.
732  // 2/ the successor is not node's right child. In this case, we know that
733  // the successor has a parent different from node and that the
734  // successor
735  // is a left child of this parent. We just need to put the right child
736  // of the successor (if any) as the left child of its parent, and to
737  // replace "node" by the successor.
738  Node* successor = _succNode(node);
739 
740  if (successor == node->rightChild()) { // proceed to case 1:
741  Node* left_child = node->leftChild();
742  node->eraseLeftLink();
743  node->eraseRightLink();
744  successor->insertLeftChild(*left_child);
745 
746  if (!node->parent()) {
747  // in this case, no need to remove the link between "node" and the
748  // successor: this will be taken care of by the destructor of "node"
749  _root = successor;
750  } else {
751  // rechain node's parent with its successor
752  BinTreeDir par_dir = node->parentDir();
753  Node* parent = node->parent();
754  parent->eraseLink(par_dir);
755  parent->insertChild(*successor, par_dir);
756  }
757  } else { // proceed to case 2:
758  Node* parent = successor->parent();
759  parent->eraseLeftLink();
760 
761  if (successor->rightChild()) {
762  Node* succ_child = successor->rightChild();
763  successor->eraseRightLink();
764  parent->insertLeftChild(*succ_child);
765  }
766 
767  Node *left = node->leftChild(), *right = node->rightChild();
768  node->eraseLeftLink();
769  node->eraseRightLink();
770  successor->insertLeftChild(*left);
771  successor->insertRightChild(*right);
772 
773  if (!node->parent()) {
774  _root = successor;
775  } else {
776  // rechain node's parent with its successor
777  BinTreeDir par_dir = node->parentDir();
778  Node* parent = node->parent();
779  parent->eraseLink(par_dir);
780  parent->insertChild(*successor, par_dir);
781  }
782  }
783  }
784 
785  template < typename Val, class Cmp, class Node >
786  INLINE void BinSearchTree< Val, Cmp, Node >::erase(const Val& val) {
787  Node* n = _getNode(val);
788 
789  if (n == nullptr)
790  GUM_ERROR(gum::NotFound, "Value \"" << val << "\" not found");
791 
792  _erase(n);
793  }
794 
795  template < typename Val, class Cmp, class Node >
796  INLINE void BinSearchTree< Val, Cmp, Node >::erase(const iterator& iter) {
797  _erase(iter._node);
798  }
799 
800  template < typename Val, class Cmp, class Node >
802  for (iterator* iter = _iterator_list; iter; iter = iter->_next_iter) {
803  // if the iterator points toward the node to be deleted, make its _node
804  // field point to 0 and update accordingly its other fields
805  if (iter->_node == node) {
806  iter->_node = 0;
807  iter->_next_node = _succNode(node);
808  iter->_prev_node = _prevNode(node);
809  iter->_parent = node->parent();
810  iter->_left_child = node->leftChild();
811  iter->_right_child = node->rightChild();
812  } else if (!iter->_node) {
813  if (iter->_next_node == node) iter->_next_node = _succNode(node);
814 
815  if (iter->_prev_node == node) iter->_prev_node = _prevNode(node);
816 
817  if (iter->_parent == node) iter->_parent = node->parent();
818 
819  if (iter->_left_child == node) iter->_left_child = node->leftChild();
820 
821  if (iter->_right_child == node) iter->_right_child = node->rightChild();
822  }
823  }
824  }
825 
826 } // namespace gum
827 
828 #endif // DOXYGEN_SHOULD_SKIP_THIS
Node * _prevNode(Node *node) const
Returns the previous node according to weak ordering Cmp.
virtual ~BinSearchTree()
Class destructor.
BinSearchTree< Val, Cmp, Node > * _tree
The binary search tree pointed to by the iterator.
unsigned long Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:50
BinSearchTreeIterator< Val, Cmp, Node > & operator--()
Point the iterator to the preceding value in the binary search tree.
const Val & minValue() const
Returns the value of the leftmost node with the minimal key in the tree.
bool operator==(const BinSearchTreeIterator< Val, Cmp, Node > &from) const
Checks whether two iterators are pointing toward identical elements.
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.
Node * _succNode(Node *node) const
Returns the next node according to the weak ordering Cmp.
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.
void clear()
Detach the iterator from its current tree (if any) and reset it.
bool operator!=(const BinSearchTreeIterator< Val, Cmp, Node > &from) const
Checks whether two iterators are pointing toward different elements.
gum is the global namespace for all aGrUM entities
Definition: agrum.h:25
BinSearchTreeIterator()
Class Constructors and Destructors.
iterator rbegin()
Reverse iterator.
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.
const Val & rootValue() const
Returns the value of the root of the tree.
Node * _getNode(const Val &val) const
Returns the node containing a given value.
BinTreeDir
The direction of a given edge in a binary tree.
Definition: binTreeNode.h:34
iterator root()
Returns an iterator at the root of the tree.
BinSearchTreeIterator< Val, Cmp, Node > & operator++()
Point the iterator to the next value in the binary search tree.
virtual const std::string toString() const
Displays the content of the tree, in increasing order w.r.t.
bool empty() const
Indicates whether the gum::BinSearchTree search tree is empty.
Node * _minNode(Node *node) const
Returns the smallest node w.r.t.
Node * _parent
The parent to be used when _node=0 (if operation up is applied).
aGrUM&#39;s exceptions
BinSearchTreeIterator< Val, Cmp, Node > & up()
Makes the iterator move to its parent node.
bool contains(const Val &val) const
Returns true if the gum::BinSearchTree contains the value.
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.
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.
bool uniquenessPolicy() const
Returns the current uniqueness policy.
BinSearchTreeIterator< Val, Cmp, Node > & downLeft()
Makes the iterator move to the left child of the node it points to.
const Val & operator*() const
Returns the value pointed to by the iterator.
const iterator & rend()
Reverse end iterator.
void erase(const Val &val)
Erase the leftmost node with the given (key,val) pair.
const Val & maxValue() const
Returns the value of the rightmost node with the maximal key in the tree.
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.
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 * _maxNode(Node *node) const
Returns the greatest node w.r.t.
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.
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:66
void __eraseWithTwoChildren(Node *node)
Erase a node with two children.