aGrUM  0.13.2
binSearchTree.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 GUM_BIN_SEARCH_TREE_H
29 #define GUM_BIN_SEARCH_TREE_H
30 
31 #include <agrum/agrum.h>
32 
33 #include <agrum/core/binTreeNode.h>
34 
35 namespace gum {
36 
37 #ifndef DOXYGEN_SHOULD_SKIP_THIS
38  // classes provided/used by this header
39  template < typename Val, class Cmp, class Node >
40  class BinSearchTree;
41 
42  template < typename Val, class Cmp, class Node >
43  class BinSearchTreeIterator;
44 #endif // DOXYGEN_SHOULD_SKIP_THIS
45 
46  // ===========================================================================
47  // === GENERIC BINARY SEARCH TREE ===
48  // ===========================================================================
49 
62  template < typename Val,
63  class Cmp = std::less< Val >,
64  class Node = BinTreeNode< Val > >
65  class BinSearchTree {
66  public:
72 
73  // ============================================================================
75  // ============================================================================
77 
86  explicit BinSearchTree(bool uniqueness_policy = false);
87 
93 
97  virtual ~BinSearchTree();
98 
100  // ============================================================================
102  // ============================================================================
104 
112 
114  // ============================================================================
116  // ============================================================================
118 
123  iterator begin();
125  const_iterator begin() const;
127 
133  iterator rbegin();
135  const_iterator rbegin() const;
137 
142  const iterator& end();
144  const const_iterator& end() const;
146 
152  const iterator& rend();
154  const const_iterator& rend() const;
156 
161  iterator root();
163  const_iterator root() const;
165 
167  // ============================================================================
169  // ============================================================================
171 
177  const Val& rootValue() const;
178 
186  const Val& minValue() const;
187 
195  const Val& maxValue() const;
196 
210  const Val& insert(const Val& val);
211 
217  void erase(const Val& val);
218 
227  void erase(const iterator& iter);
228 
234  bool contains(const Val& val) const;
235 
239  void clear();
240 
245  Size size() const;
246 
251  bool empty() const;
252 
258  virtual const std::string toString() const;
259 
261  // ============================================================================
263  // ============================================================================
265 
270  bool uniquenessPolicy() const;
271 
287  void setUniquenessPolicy(const bool new_policy);
288 
290 
291  protected:
293  Node* _root;
294 
296  Cmp _cmp;
297 
299  mutable iterator* _iterator_list;
300 
303  mutable bool _uniqueness_policy;
304 
307 
316  iterator _iter_end;
317 
320  friend class BinSearchTreeIterator< Val, Cmp, Node >;
322 
334  Node* _copy(Node* root_from,
335  Node* parent = 0,
337 
344  Node* _minNode(Node* node) const;
345 
352  Node* _maxNode(Node* node) const;
353 
359  Node* _succNode(Node* node) const;
360 
366  Node* _prevNode(Node* node) const;
367 
374  Node* _getNode(const Val& val) const;
375 
377 
386  void _deleteSubTree(Node* node);
387 
392  virtual void _erase(Node* node);
393 
394  private:
401  void __eraseWithTwoChildren(Node* node);
402 
403  protected:
420  virtual Node* _insert(const Val& val);
421 
422  private:
427  void __updateEraseIterators(Node* node);
428  };
429 
430  // ===========================================================================
431  // === GENERIC BINARY SEARCH TREE ITERATORS ===
432  // ===========================================================================
433 
445  template < typename Val, class Cmp, class Node >
447  public:
448  // ============================================================================
450  // ============================================================================
452 
457 
464 
467 
469  // ============================================================================
471  // ============================================================================
473 
481 
488  const Val& operator*() const;
489 
511 
532 
540  bool operator!=(const BinSearchTreeIterator< Val, Cmp, Node >& from) const;
541 
549  bool operator==(const BinSearchTreeIterator< Val, Cmp, Node >& from) const;
550 
552  // ############################################################################
554  // ############################################################################
556 
562 
569 
576 
580  void clear();
581 
583 
584  protected:
586  Node* _node;
587 
589  Node* _next_node;
590 
593  Node* _prev_node;
594 
596  Node* _parent;
597 
599  Node* _left_child;
600 
603 
606 
609 
610  private:
613  friend class BinSearchTree< Val, Cmp, Node >;
615 
628  void _initialize(const BinSearchTree< Val, Cmp, Node >* tree,
629  const Node* current_node,
630  bool add_to_iterator_list);
631 
636  void _detachFromTree();
637  };
638 
639 } /* namespace gum */
640 
641 
642 extern template class gum::BinSearchTree< int >;
643 
644 
645 // always include the template implementations
647 
648 #endif // GUM_BIN_SEARCH_TREE_H
Node * _prevNode(Node *node) const
Returns the previous node according to weak ordering Cmp.
iterator _iter_end
Pseudo static iterator.
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
A generic binary search tree.
Definition: binSearchTree.h:65
const Val & minValue() const
Returns the value of the leftmost node with the minimal key in the tree.
Cmp _cmp
The comparison function.
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.
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.
gum is the global namespace for all aGrUM entities
Definition: agrum.h:25
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.
bool _uniqueness_policy
The uniqueness property: whether the same value can appear multiple times.
const Val & rootValue() const
Returns the value of the root of the tree.
Basic binary tree.
Node * _getNode(const Val &val) const
Returns the node containing a given value.
BinSearchTreeIterator< Val, Cmp, Node > const_iterator
Alias for gum::BinSearchTree iterators.
Definition: binSearchTree.h:70
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.
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).
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.
Formula operator*(const Formula &a, const Formula &b)
Definition: formula_inl.h:469
BinSearchTree(bool uniqueness_policy=false)
Basic constructor: returns an empty binary search tree.
bool operator==(const TiXmlString &a, const TiXmlString &b)
Definition: tinystr.h:243
Node * _node
The current node pointed to by the iterator.
A Generic binary search tree.
iterator * _iterator_list
The list of iterators pointing to the binary search tree.
virtual Node * _insert(const Val &val)
Creates a copy of the value, insert it in the gum::BinSearchTree and returns the copy value...
BinSearchTreeIterator< Val, Cmp, Node > iterator
Alias for gum::BinSearchTree iterators.
Definition: binSearchTree.h:69
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.
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.
Size _nb_elements
The number of elements stored 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...
bool operator!=(const TiXmlString &a, const TiXmlString &b)
Definition: tinystr.h:251
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.
virtual void _erase(Node *node)
Erase the node passed in argument.
iterator begin()
Begin iterator.
Node * _root
The root node of the tree.
void __eraseWithTwoChildren(Node *node)
Erase a node with two children.