aGrUM  0.20.2
a C++ library for (probabilistic) graphical models
binSearchTree_tpl.h
Go to the documentation of this file.
1 /**
2  *
3  * Copyright 2005-2020 Pierre-Henri WUILLEMIN(@LIP6) & Christophe GONZALES(@AMU)
4  * info_at_agrum_dot_org
5  *
6  * This library is free software: you can redistribute it and/or modify
7  * it under the terms of the GNU Lesser General Public License as published by
8  * the Free Software Foundation, either version 3 of the License, or
9  * (at your option) any later version.
10  *
11  * This library is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14  * GNU Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public License
17  * along with this library. If not, see <http://www.gnu.org/licenses/>.
18  *
19  */
20 
21 
22 /**
23  * @file
24  * @brief Basic binary tree.
25  *
26  * @author Christophe GONZALES(@AMU) and Pierre-Henri WUILLEMIN(@LIP6)
27  */
28 
29 #include <sstream>
30 #include <string>
31 
32 #include <agrum/tools/core/binSearchTree.h>
33 #include <agrum/tools/core/exceptions.h>
34 
35 #ifndef DOXYGEN_SHOULD_SKIP_THIS
36 
37 namespace gum {
38 
39  // ===========================================================================
40  // ===========================================================================
41  // === GENERIC BINARY SEARCH TREE ITERATORS ===
42  // ===========================================================================
43  // ===========================================================================
44 
45  template < typename Val, class Cmp, class Node >
46  INLINE BinSearchTreeIterator< Val, Cmp, Node >::BinSearchTreeIterator() :
47  node_(0), next_node_(0), prev_node_(0), parent_(0), left_child_(0),
48  right_child_(0), tree_(0), next_iter_(0) {
49  GUM_CONSTRUCTOR(BinSearchTreeIterator);
50  }
51 
52  template < typename Val, class Cmp, class Node >
53  INLINE BinSearchTreeIterator< Val, Cmp, Node >::BinSearchTreeIterator(
54  const BinSearchTreeIterator< Val, Cmp, Node >& from) :
55  node_(from.node_),
56  next_node_(from.next_node_), prev_node_(from.prev_node_),
57  parent_(from.parent_), left_child_(from.left_child_),
58  right_child_(from.right_child_), tree_(from.tree_) {
59  GUM_CONS_CPY(BinSearchTreeIterator);
60 
61  if (tree_) {
62  next_iter_ = tree_->iterator_list_;
63  tree_->iterator_list_ = this;
64  } else
65  next_iter_ = 0;
66  }
67 
68  template < typename Val, class Cmp, class Node >
69  INLINE void BinSearchTreeIterator< Val, Cmp, Node >::initialize_(
70  const BinSearchTree< Val, Cmp, Node >* tree,
71  const Node* current_node,
72  bool add_to_iterator_list) {
73  // remember: we do not check here whether the iterator already belongs to
74  // a tree. We assume that it is not so.
75 
76  tree_ = const_cast< BinSearchTree< Val, Cmp, Node >* >(tree);
77  node_ = const_cast< Node* >(current_node);
78 
79  if (add_to_iterator_list && tree_) {
80  next_iter_ = tree_->iterator_list_;
81  tree_->iterator_list_ = this;
82  }
83  }
84 
85  template < typename Val, class Cmp, class Node >
86  INLINE void BinSearchTreeIterator< Val, Cmp, Node >::detachFromTree_() {
87  if (tree_) {
88  BinSearchTreeIterator< Val, Cmp, Node >*iter, *prev_iter = 0;
89 
90  for (iter = tree_->iterator_list_; iter != this && iter;
91  prev_iter = iter, iter = iter->next_iter_) {}
92 
93  if (iter) {
94  if (prev_iter)
95  prev_iter->next_iter_ = next_iter_;
96  else
97  tree_->iterator_list_ = next_iter_;
98  }
99  }
100  }
101 
102  template < typename Val, class Cmp, class Node >
103  INLINE BinSearchTreeIterator< Val, Cmp, Node >::~BinSearchTreeIterator() {
104  GUM_DESTRUCTOR(BinSearchTreeIterator);
105 
106  // remove the iterator from its tree iterator's list
107  detachFromTree_();
108  }
109 
110  template < typename Val, class Cmp, class Node >
111  INLINE void BinSearchTreeIterator< Val, Cmp, Node >::clear() {
112  // remove the iterator from its tree iterator's list
113  detachFromTree_();
114 
115  // reset the iterator
116  node_ = 0;
117  next_node_ = 0;
118  prev_node_ = 0;
119  parent_ = 0;
120  left_child_ = 0;
121  right_child_ = 0;
122  tree_ = 0;
123  next_iter_ = 0;
124  }
125 
126  template < typename Val, class Cmp, class Node >
127  INLINE BinSearchTreeIterator< Val, Cmp, Node >&
128  BinSearchTreeIterator< Val, Cmp, Node >::operator=(
129  const BinSearchTreeIterator< Val, Cmp, Node >& from) {
130  // avoid self assignment
131  if (this != &from) {
132  GUM_OP_CPY(BinSearchTreeIterator);
133 
134  // if from and this belong to different trees, detach this from its
135  // current tree
136  if (from.tree_ != tree_) {
137  detachFromTree_();
138  tree_ = from.tree_;
139 
140  if (tree_) {
141  next_iter_ = tree_->iterator_list_;
142  tree_->iterator_list_ = this;
143  } else
144  next_iter_ = 0;
145  }
146 
147  // make the iterators point to the same element
148  node_ = from.node_;
149  next_node_ = from.next_node_;
150  prev_node_ = from.prev_node_;
151  parent_ = from.parent_;
152  left_child_ = from.left_child_;
153  right_child_ = from.right_child_;
154  }
155 
156  return *this;
157  }
158 
159  template < typename Val, class Cmp, class Node >
160  INLINE const Val& BinSearchTreeIterator< Val, Cmp, Node >::operator*() const {
161  if (node_) return node_->value();
162 
163  GUM_ERROR(UndefinedIteratorValue,
164  "the iterator does not point to a node of the binary tree");
165  }
166 
167  template < typename Val, class Cmp, class Node >
168  INLINE Node* BinSearchTree< Val, Cmp, Node >::minNode_(Node* node) const {
169  Node* prevNode = 0;
170 
171  for (; node; prevNode = node, node = node->leftChild()) {}
172 
173  return prevNode;
174  }
175 
176  template < typename Val, class Cmp, class Node >
177  INLINE Node* BinSearchTree< Val, Cmp, Node >::maxNode_(Node* node) const {
178  Node* prevNode = 0;
179 
180  for (; node; prevNode = node, node = node->rightChild()) {}
181 
182  return prevNode;
183  }
184 
185  template < typename Val, class Cmp, class Node >
186  INLINE Node* BinSearchTree< Val, Cmp, Node >::succNode_(Node* node) const {
187  if (!node) return 0;
188 
189  if (node->rightChild()) return minNode_(node->rightChild());
190 
191  Node* par = node->parent();
192 
193  while (par && (node->parentDir() == BinTreeDir::RIGHT_CHILD)) {
194  node = par;
195  par = par->parent();
196  }
197 
198  return par;
199  }
200 
201  template < typename Val, class Cmp, class Node >
202  INLINE Node* BinSearchTree< Val, Cmp, Node >::prevNode_(Node* node) const {
203  if (!node) return 0;
204 
205  if (node->leftChild()) return maxNode_(node->leftChild());
206 
207  Node* par = node->parent();
208 
209  while (par && (node->parentDir() == BinTreeDir::LEFT_CHILD)) {
210  node = par;
211  par = par->parent();
212  }
213 
214  return par;
215  }
216 
217  template < typename Val, class Cmp, class Node >
218  INLINE BinSearchTreeIterator< Val, Cmp, Node >&
219  BinSearchTreeIterator< Val, Cmp, Node >::operator++() {
220  // if there is a current node, use it to compute the next node, else use
221  // directly next_node_ (this case obtains when the iterator was pointing
222  // toward a node that has been deleted before we use operator++)
223  node_ = node_ ? tree_->succNode_(node_) : next_node_;
224 
225  if (!node_) {
226  next_node_ = 0;
227  prev_node_ = 0;
228  parent_ = 0;
229  left_child_ = 0;
230  right_child_ = 0;
231  }
232 
233  return *this;
234  }
235 
236  template < typename Val, class Cmp, class Node >
237  INLINE BinSearchTreeIterator< Val, Cmp, Node >&
238  BinSearchTreeIterator< Val, Cmp, Node >::operator--() {
239  // if there is a current node, use it to compute the preceding node, else
240  // use
241  // directly prev_node_ (this case obtains when the iterator was pointing
242  // toward a node that has been deleted before we use operator--)
243  node_ = node_ ? tree_->prevNode_(node_) : prev_node_;
244 
245  if (!node_) {
246  next_node_ = 0;
247  prev_node_ = 0;
248  parent_ = 0;
249  left_child_ = 0;
250  right_child_ = 0;
251  }
252 
253  return *this;
254  }
255 
256  template < typename Val, class Cmp, class Node >
257  INLINE bool BinSearchTreeIterator< Val, Cmp, Node >::operator==(
258  const BinSearchTreeIterator< Val, Cmp, Node >& from) const {
259  if (node_)
260  return (node_ == from.node_);
261  else
262  return ((node_ == from.node_) && (tree_ == from.tree_)
263  && (next_node_ == from.next_node_) && (prev_node_ == from.prev_node_)
264  && (parent_ == from.parent_) && (left_child_ == from.left_child_)
265  && (right_child_ == from.right_child_));
266  }
267 
268  template < typename Val, class Cmp, class Node >
269  INLINE bool BinSearchTreeIterator< Val, Cmp, Node >::operator!=(
270  const BinSearchTreeIterator< Val, Cmp, Node >& from) const {
271  if (node_)
272  return (node_ != from.node_);
273  else
274  return ((node_ != from.node_) || (tree_ != from.tree_)
275  || (next_node_ != from.next_node_) || (prev_node_ != from.prev_node_)
276  || (parent_ != from.parent_) || (left_child_ != from.left_child_)
277  || (right_child_ != from.right_child_));
278  }
279 
280  template < typename Val, class Cmp, class Node >
281  INLINE BinSearchTreeIterator< Val, Cmp, Node >&
282  BinSearchTreeIterator< Val, Cmp, Node >::up() {
283  // if there is a current node, use it to compute its parent node, else use
284  // directly parent_ (this case obtains when the iterator was pointing
285  // toward a node that has been deleted before we use operation up)
286  node_ = node_ ? node_->parent() : parent_;
287 
288  if (!node_) {
289  next_node_ = 0;
290  prev_node_ = 0;
291  parent_ = 0;
292  left_child_ = 0;
293  right_child_ = 0;
294  }
295 
296  return *this;
297  }
298 
299  template < typename Val, class Cmp, class Node >
300  INLINE BinSearchTreeIterator< Val, Cmp, Node >&
301  BinSearchTreeIterator< Val, Cmp, Node >::downLeft() {
302  // if there is a current node, use it to compute its left child, else use
303  // directly left_child_ (this case obtains when the iterator was pointing
304  // toward a node that has been deleted before we use operation downLeft)
305  node_ = node_ ? node_->leftChild() : left_child_;
306 
307  if (!node_) {
308  next_node_ = 0;
309  prev_node_ = 0;
310  parent_ = 0;
311  left_child_ = 0;
312  right_child_ = 0;
313  }
314 
315  return *this;
316  }
317 
318  template < typename Val, class Cmp, class Node >
319  INLINE BinSearchTreeIterator< Val, Cmp, Node >&
320  BinSearchTreeIterator< Val, Cmp, Node >::downRight() {
321  // if there is a current node, use it to compute its right child, else use
322  // directly right_child_ (this case obtains when the iterator was pointing
323  // toward a node that has been deleted before we use operation downRight)
324  node_ = node_ ? node_->rightChild() : right_child_;
325 
326  if (!node_) {
327  next_node_ = 0;
328  prev_node_ = 0;
329  parent_ = 0;
330  left_child_ = 0;
331  right_child_ = 0;
332  }
333 
334  return *this;
335  }
336 
337  // ===========================================================================
338  // ===========================================================================
339  // === GENERIC BINARY SEARCH TREE ===
340  // ===========================================================================
341  // ===========================================================================
342 
343  template < typename Val, class Cmp, class Node >
344  BinSearchTree< Val, Cmp, Node >::BinSearchTree(bool uniqueness_policy) :
345  root_(0), iterator_list_(0), uniqueness_policy_(uniqueness_policy),
346  nb_elements_(0) {
347  GUM_CONSTRUCTOR(BinSearchTree);
348  iter_end_.initialize_(this, 0, false);
349  }
350 
351  template < typename Val, class Cmp, class Node >
352  BinSearchTree< Val, Cmp, Node >::BinSearchTree(
353  const BinSearchTree< Val, Cmp, Node >& from) :
354  root_(0),
355  iterator_list_(0), uniqueness_policy_(from.uniqueness_policy_) {
356  // for debugging purposes
357  GUM_CONS_CPY(BinSearchTree);
358 
359  // copy the content of BinSearchTree "from"
360  root_ = copy_(from.root_);
361  nb_elements_ = from.nb_elements_;
362 
363  // initialize the end/rend iterator
364  iter_end_.initialize_(this, 0, false);
365  }
366 
367  template < typename Val, class Cmp, class Node >
368  INLINE void BinSearchTree< Val, Cmp, Node >::clear() {
369  // first we clear all the iterators, i.e., we detach them from the tree
370  for (iterator *iter = iterator_list_, *next_iter = 0; iter; iter = next_iter) {
371  next_iter = iter->next_iter_;
372  iter->clear();
373  }
374 
375  // now, delete the whole tree
376  deleteSubTree_(root_);
377  root_ = 0;
378  nb_elements_ = 0;
379 
380  // note that there is no need to redefined end/rend as they do not rely
381  // on the content of the tree
382  }
383 
384  template < typename Val, class Cmp, class Node >
385  BinSearchTree< Val, Cmp, Node >& BinSearchTree< Val, Cmp, Node >::operator=(
386  const BinSearchTree< Val, Cmp, Node >& from) {
387  // avoid self assignment
388  if (this != &from) {
389  // for debugging purposes
390  GUM_OP_CPY(BinSearchTree);
391 
392  // if the tree is not currently empty, remove it
393  clear();
394 
395  // copy binary tree "from"
396  uniqueness_policy_ = from.uniqueness_policy_;
397  root_ = copy_(from.root_); // note that we can copy from's tree structure
398  // as from and this have the same ordering cmp_
399  nb_elements_ = from.nb_elements_;
400 
401  // note that we do not need to update the end/rend iterator as, besides
402  // field tree_, no other field is related to the current tree (i.e., all
403  // _*node_ are set to 0
404  }
405 
406  return *this;
407  }
408 
409  template < typename Val, class Cmp, class Node >
410  BinSearchTree< Val, Cmp, Node >::~BinSearchTree() {
411  // for debugging purposes
412  GUM_DESTRUCTOR(BinSearchTree);
413 
414  // clear all the iterators and remove all nodes
415  clear();
416  }
417 
418  template < typename Val, class Cmp, class Node >
419  Node* BinSearchTree< Val, Cmp, Node >::copy_(Node* node,
420  Node* parent,
421  BinTreeDir dir) {
422  // if there is no node to copy, abort
423  if (!node) return 0;
424 
425  // create the copy of node
426  Node* new_node = new Node(*node);
427 
428  if (parent) parent->insertChild(*new_node, dir);
429 
430  // if necessary, create the left and right subgraphs
431  copy_(node->leftChild(), new_node, BinTreeDir::LEFT_CHILD);
432  copy_(node->rightChild(), new_node, BinTreeDir::RIGHT_CHILD);
433 
434  return new_node;
435  }
436 
437  template < typename Val, class Cmp, class Node >
438  void BinSearchTree< Val, Cmp, Node >::deleteSubTree_(Node* node) {
439  // if there is no node to remove, return
440  if (!node) return;
441 
442  // delete the left and right subgraphs
443  deleteSubTree_(node->leftChild());
444  deleteSubTree_(node->rightChild());
445 
446  // delete the node itself
447  delete node;
448  }
449 
450  template < typename Val, class Cmp, class Node >
451  INLINE Node* BinSearchTree< Val, Cmp, Node >::insert_(const Val& val) {
452  // if the tree is not empty, search the binary search tree to know
453  // where the node should be inserted
454  if (root_) {
455  Node* node = root_;
456 
457  while (true) {
458  if (cmp_(val, node->value()))
459  if (!node->leftChild()) {
460  // here we are on a leaf => insert the new node
461  ++nb_elements_;
462  return node->insertLeftChild(val);
463  } else {
464  node = node->leftChild();
465  }
466  else if (cmp_(node->value(), val) || !uniqueness_policy_)
467  if (!node->rightChild()) {
468  // here we are on a leaf => insert the new node
469  ++nb_elements_;
470  return node->insertRightChild(val);
471  } else {
472  node = node->rightChild();
473  }
474  else {
475  // here we found a node with the same key and the uniqueness policy
476  // is set. So we should raise an exception
477  GUM_ERROR(DuplicateElement,
478  "Val " << val << " already in the binary search tree");
479  }
480  }
481  }
482 
483  // here the tree is empty, just create a new node
484  root_ = new Node(val);
485  ++nb_elements_;
486  return root_;
487  }
488 
489  template < typename Val, class Cmp, class Node >
490  INLINE const Val& BinSearchTree< Val, Cmp, Node >::insert(const Val& val) {
491  return insert_(val)->value();
492  }
493 
494  template < typename Val, class Cmp, class Node >
495  INLINE const Val& BinSearchTree< Val, Cmp, Node >::rootValue() const {
496  if (root_ == 0) {
497  GUM_ERROR(NotFound, "no value in an empty Binary Search tree");
498  }
499 
500  return root_->value();
501  }
502 
503  template < typename Val, class Cmp, class Node >
504  INLINE const Val& BinSearchTree< Val, Cmp, Node >::minValue() const {
505  if (root_ == 0) {
506  GUM_ERROR(NotFound, "no minimal value in an empty Binary Search tree");
507  }
508 
509  return minNode_(root_)->value();
510  }
511 
512  template < typename Val, class Cmp, class Node >
513  INLINE const Val& BinSearchTree< Val, Cmp, Node >::maxValue() const {
514  if (root_ == 0) {
515  GUM_ERROR(NotFound, "no maximal value in an empty Binary Search tree");
516  }
517 
518  return maxNode_(root_)->value();
519  }
520 
521  template < typename Val, class Cmp, class Node >
522  INLINE Node* BinSearchTree< Val, Cmp, Node >::getNode_(const Val& val) const {
523  // if the tree is not empty, search the binary search tree to know
524  // where the node could be
525  if (root_) {
526  Node* node = root_;
527 
528  while (true) {
529  if (cmp_(val, node->value())) {
530  if (!node->leftChild())
531  return 0;
532  else
533  node = node->leftChild();
534  } else if (cmp_(node->value(), val)) {
535  if (!node->rightChild())
536  return 0;
537  else
538  node = node->rightChild();
539  } else
540  return node;
541  }
542  } else {
543  return 0;
544  }
545  }
546 
547  template < typename Val, class Cmp, class Node >
548  INLINE bool BinSearchTree< Val, Cmp, Node >::contains(const Val& val) const {
549  return (getNode_(val) != 0);
550  }
551 
552  template < typename Val, class Cmp, class Node >
553  INLINE Size BinSearchTree< Val, Cmp, Node >::size() const {
554  return nb_elements_;
555  }
556 
557  template < typename Val, class Cmp, class Node >
558  INLINE bool BinSearchTree< Val, Cmp, Node >::empty() const {
559  return (nb_elements_ == 0);
560  }
561 
562  template < typename Val, class Cmp, class Node >
563  std::string BinSearchTree< Val, Cmp, Node >::toString() const {
564  bool deja = false;
565  std::stringstream stream;
566  stream << "[";
567 
568  for (const_iterator iter = begin(); iter != end(); ++iter, deja = true) {
569  if (deja) stream << " , ";
570 
571  stream << *iter;
572  }
573 
574  stream << "]";
575 
576  return stream.str();
577  }
578 
579  template < typename Val, class Cmp, class Node >
580  INLINE bool BinSearchTree< Val, Cmp, Node >::uniquenessPolicy() const {
581  return uniqueness_policy_;
582  }
583 
584  template < typename Val, class Cmp, class Node >
585  INLINE void
586  BinSearchTree< Val, Cmp, Node >::setUniquenessPolicy(const bool new_policy) {
587  uniqueness_policy_ = new_policy;
588  }
589 
590  template < typename Val, class Cmp, class Node >
591  INLINE BinSearchTreeIterator< Val, Cmp, Node >
592  BinSearchTree< Val, Cmp, Node >::begin() {
593  BinSearchTreeIterator< Val, Cmp, Node > iter;
594  iter.initialize_(this, minNode_(root_), true);
595  return iter;
596  }
597 
598  template < typename Val, class Cmp, class Node >
599  INLINE BinSearchTreeIterator< Val, Cmp, Node >
600  BinSearchTree< Val, Cmp, Node >::begin() const {
601  BinSearchTreeIterator< Val, Cmp, Node > iter;
602  iter.initialize_(this, minNode_(root_), true);
603  return iter;
604  }
605 
606  template < typename Val, class Cmp, class Node >
607  INLINE BinSearchTreeIterator< Val, Cmp, Node >
608  BinSearchTree< Val, Cmp, Node >::rbegin() {
609  BinSearchTreeIterator< Val, Cmp, Node > iter;
610  iter.initialize_(this, maxNode_(root_), true);
611  return iter;
612  }
613 
614  template < typename Val, class Cmp, class Node >
615  INLINE BinSearchTreeIterator< Val, Cmp, Node >
616  BinSearchTree< Val, Cmp, Node >::rbegin() const {
617  BinSearchTreeIterator< Val, Cmp, Node > iter;
618  iter.initialize_(this, maxNode_(root_), true);
619  return iter;
620  }
621 
622  template < typename Val, class Cmp, class Node >
623  INLINE const BinSearchTreeIterator< Val, Cmp, Node >&
624  BinSearchTree< Val, Cmp, Node >::end() {
625  return iter_end_;
626  }
627 
628  template < typename Val, class Cmp, class Node >
629  INLINE const BinSearchTreeIterator< Val, Cmp, Node >&
630  BinSearchTree< Val, Cmp, Node >::end() const {
631  return iter_end_;
632  }
633 
634  template < typename Val, class Cmp, class Node >
635  INLINE const BinSearchTreeIterator< Val, Cmp, Node >&
636  BinSearchTree< Val, Cmp, Node >::rend() {
637  return iter_end_;
638  }
639 
640  template < typename Val, class Cmp, class Node >
641  INLINE const BinSearchTreeIterator< Val, Cmp, Node >&
642  BinSearchTree< Val, Cmp, Node >::rend() const {
643  return iter_end_;
644  }
645 
646  template < typename Val, class Cmp, class Node >
647  INLINE BinSearchTreeIterator< Val, Cmp, Node >
648  BinSearchTree< Val, Cmp, Node >::root() {
649  BinSearchTreeIterator< Val, Cmp, Node > iter;
650  iter.initialize_(this, root_, true);
651  return iter;
652  }
653 
654  template < typename Val, class Cmp, class Node >
655  INLINE BinSearchTreeIterator< Val, Cmp, Node >
656  BinSearchTree< Val, Cmp, Node >::root() const {
657  BinSearchTreeIterator< Val, Cmp, Node > iter;
658  iter.initialize_(this, root_, true);
659  return iter;
660  }
661 
662  template < typename Val, class Cmp, class Node >
663  void BinSearchTree< Val, Cmp, Node >::erase_(Node* node) {
664  if (!node) return;
665 
666  // update all the iterators pointing to node that they should point
667  // elsewhere
668  updateEraseIterators__(node);
669 
670  // update the number of elements contained in the tree
671  --nb_elements_;
672 
673  // now remove the node from the tree:
674 
675  // if the node has no children, then just remove it
676  if (!node->leftChild() && !node->rightChild()) {
677  // if the node was the only one in the tree, then the tree becomes empty
678  if (!node->parent()) root_ = 0;
679 
680  // note that, when node has a parent, there is no need to remove the
681  // link between node and this parent: this will be taken care of by
682  // node's destructor.
683  }
684  // if there is just a right child
685  else if (!node->leftChild()) {
686  // just relink the right child with the parent (if any)
687  if (!node->parent()) {
688  // in this case, no need to remove the link between "node" and its
689  // child:
690  // this will be taken care of by the destructor of "node"
691  root_ = node->rightChild();
692  } else {
693  Node * parent = node->parent(), *child = node->rightChild();
694  BinTreeDir dir = node->parentDir();
695  parent->eraseLink(dir);
696  node->eraseRightLink();
697  parent->insertChild(*child, dir);
698  }
699  }
700  // if there is just a left child
701  else if (!node->rightChild()) {
702  // just relink the left child with the parent (if any)
703  if (!node->parent()) {
704  // in this case, no need to remove the link between "node" and its
705  // child:
706  // this will be taken care of by the destructor of "node"
707  root_ = node->leftChild();
708  } else {
709  Node * parent = node->parent(), *child = node->leftChild();
710  BinTreeDir dir = node->parentDir();
711  parent->eraseLink(dir);
712  node->eraseLeftLink();
713  parent->insertChild(*child, dir);
714  }
715  }
716  // ok, here there are two children
717  else {
718  eraseWithTwoChildren__(node);
719  }
720 
721  // now we shall physically remove node from memory
722  delete node;
723  }
724 
725  template < typename Val, class Cmp, class Node >
726  INLINE void BinSearchTree< Val, Cmp, Node >::eraseWithTwoChildren__(Node* node) {
727  // the idea is to get the successor of "node" and substitute "node" by
728  // it. As "node" has two children, we are sure that the successor is one
729  // of node's descendants. Moreover, by its very definition, this
730  // successor has no left child. Hence, two cases can obtain:
731  // 1/ the successor is precisely node's right child. In this case, we just
732  // have to make node's left child be the left child of the successor,
733  // and node's parent be the successor's parent, and the tree is again
734  // a binary search tree.
735  // 2/ the successor is not node's right child. In this case, we know that
736  // the successor has a parent different from node and that the
737  // successor
738  // is a left child of this parent. We just need to put the right child
739  // of the successor (if any) as the left child of its parent, and to
740  // replace "node" by the successor.
741  Node* successor = succNode_(node);
742 
743  if (successor == node->rightChild()) { // proceed to case 1:
744  Node* left_child = node->leftChild();
745  node->eraseLeftLink();
746  node->eraseRightLink();
747  successor->insertLeftChild(*left_child);
748 
749  if (!node->parent()) {
750  // in this case, no need to remove the link between "node" and the
751  // successor: this will be taken care of by the destructor of "node"
752  root_ = successor;
753  } else {
754  // rechain node's parent with its successor
755  BinTreeDir par_dir = node->parentDir();
756  Node* parent = node->parent();
757  parent->eraseLink(par_dir);
758  parent->insertChild(*successor, par_dir);
759  }
760  } else { // proceed to case 2:
761  Node* parent = successor->parent();
762  parent->eraseLeftLink();
763 
764  if (successor->rightChild()) {
765  Node* succ_child = successor->rightChild();
766  successor->eraseRightLink();
767  parent->insertLeftChild(*succ_child);
768  }
769 
770  Node *left = node->leftChild(), *right = node->rightChild();
771  node->eraseLeftLink();
772  node->eraseRightLink();
773  successor->insertLeftChild(*left);
774  successor->insertRightChild(*right);
775 
776  if (!node->parent()) {
777  root_ = successor;
778  } else {
779  // rechain node's parent with its successor
780  BinTreeDir par_dir = node->parentDir();
781  Node* parent = node->parent();
782  parent->eraseLink(par_dir);
783  parent->insertChild(*successor, par_dir);
784  }
785  }
786  }
787 
788  template < typename Val, class Cmp, class Node >
789  INLINE void BinSearchTree< Val, Cmp, Node >::erase(const Val& val) {
790  Node* n = getNode_(val);
791 
792  if (n == nullptr)
793  GUM_ERROR(gum::NotFound, "Value \"" << val << "\" not found");
794 
795  erase_(n);
796  }
797 
798  template < typename Val, class Cmp, class Node >
799  INLINE void BinSearchTree< Val, Cmp, Node >::erase(const iterator& iter) {
800  erase_(iter.node_);
801  }
802 
803  template < typename Val, class Cmp, class Node >
804  void BinSearchTree< Val, Cmp, Node >::updateEraseIterators__(Node* node) {
805  for (iterator* iter = iterator_list_; iter; iter = iter->next_iter_) {
806  // if the iterator points toward the node to be deleted, make its node_
807  // field point to 0 and update accordingly its other fields
808  if (iter->node_ == node) {
809  iter->node_ = 0;
810  iter->next_node_ = succNode_(node);
811  iter->prev_node_ = prevNode_(node);
812  iter->parent_ = node->parent();
813  iter->left_child_ = node->leftChild();
814  iter->right_child_ = node->rightChild();
815  } else if (!iter->node_) {
816  if (iter->next_node_ == node) iter->next_node_ = succNode_(node);
817 
818  if (iter->prev_node_ == node) iter->prev_node_ = prevNode_(node);
819 
820  if (iter->parent_ == node) iter->parent_ = node->parent();
821 
822  if (iter->left_child_ == node) iter->left_child_ = node->leftChild();
823 
824  if (iter->right_child_ == node) iter->right_child_ = node->rightChild();
825  }
826  }
827  }
828 
829 } // namespace gum
830 
831 #endif // DOXYGEN_SHOULD_SKIP_THIS
aGrUM 0.20.2
Sun May 2 2021 12:36:00
© PHW&CG&others - 2021
DoXyGeN 1.8.13