Advanced Programming - Binary Search Tree
A simple Binary Search Tree implementation for the Advanced Programming 2019-2020 course @ SISSA.
Iterator.hpp
1 #ifndef ITERATOR_HPP
2 #define ITERATOR_HPP
3 
4 #include <iterator> /* For std::forward_iterator_tag */
5 
6 
7 namespace APbst {
8  template<typename KT, typename VT, typename cmp>
9  class bst;
10 }
11 
12 
13 namespace APutils {
14 
18  template <typename nodeT, typename T>
19  class __iterator {
21  nodeT* currentNode;
22  public:
23  /* Standard members of the class Iterator. You could also derive them directly from the class std::iterator,
24  * but since c++17 is deprecated our is the right way. */
30  using value_type = T; // T can be either pair or const pair
31  using reference = value_type&;
32  using pointer = value_type*;
33  using iterator_category = std::forward_iterator_tag;
34  using difference_type = std::ptrdiff_t;
35 
43  explicit __iterator(nodeT* n) noexcept : currentNode{n} {}
44 
45  /*
46  * @brief Operator of re-cast.
47  *
48  * For the cast at const_iterator.
49  */
50  //operator __iterator<nodeT, const T>() { return __iterator<nodeT, const T>{currentNode}; }
51 
60  reference operator*() const noexcept { return currentNode->data; }
61 
70  pointer operator->() const noexcept { return &(*(*this)); }
71 
77  __iterator& operator++() noexcept {
78  /* If we are a nullptr, we return ourselves.
79  */
80  if (!currentNode) { // equivalent to if (currentNode == nullptr)
81  return *this;
82  /* If we have a right child, we descend the tree always right until
83  * we only have a left child.
84  */
85  } else if (currentNode->right) {
86  currentNode = currentNode->right.get();
87  while (currentNode->left) {
88  currentNode = currentNode->left.get();
89  } // end while
90  /* We go up in the tree while we are the right child of our parent;
91  * when we are no more the right child and we are then the left child,
92  * we go up one last time to the parent.
93  */
94  } else {
95  nodeT* tmpNode = currentNode->parent;
96  while (tmpNode && currentNode == tmpNode->right.get()) {
97  currentNode = tmpNode;
98  tmpNode = currentNode->parent;
99  } // end while
100  currentNode = tmpNode;
101  } // end if
102  return *this;
103  } // end ++it
104 
110  __iterator operator++(int) noexcept {
111  /* The following line calls our 1-element constructor by giving an
112  * argument of type nodeT*. An almost equivalent statement would be
113  * __iterator tmpIterator{*this};
114  * that instead calls the copy constructor, since the argument is of
115  * type *(__iterator&) == __iterator. Is one better than the other? =)
116  */
117  __iterator tmpIterator{currentNode};
118  ++(*this);
119  return tmpIterator;
120  } // end it++
121 
129  friend inline bool operator==(const __iterator& a, const __iterator& b) { return a.currentNode == b.currentNode; }
130 
138  friend inline bool operator!=(const __iterator& a, const __iterator& b) { return !(a == b); }
139 
144  template<typename KT, typename VT, typename cmp>
145  friend class APbst::bst;
146 
152  template<class... Types>
153  void printNode(Types&&... args) {
154  return currentNode->printNode(std::forward<Types>(args)...);
155  }
156  };
157 
158 }
159 
160 
161 #endif // ITERATOR_HPP
T value_type
Type of the data stored by Node.
Definition: Iterator.hpp:30
Class that implements an iterator of a tree.
Definition: Iterator.hpp:19
__iterator(nodeT *n) noexcept
Constructor.
Definition: Iterator.hpp:43
nodeT * currentNode
Node referred to by the iterator.
Definition: Iterator.hpp:21
__iterator operator++(int) noexcept
Post-increment operator.
Definition: Iterator.hpp:110
friend bool operator==(const __iterator &a, const __iterator &b)
Equality operator.
Definition: Iterator.hpp:129
reference operator*() const noexcept
Dereference operator.
Definition: Iterator.hpp:60
pointer operator->() const noexcept
Arrow operator.
Definition: Iterator.hpp:70
friend bool operator!=(const __iterator &a, const __iterator &b)
Inequality operator.
Definition: Iterator.hpp:138
__iterator & operator++() noexcept
Pre-increment operator.
Definition: Iterator.hpp:77
Namespace that stands for "Advanced Programming Utils".
Definition: Iterator.hpp:13
Namespace for the Binary Search Tree.
Definition: BST.hpp:97
void printNode(Types &&... args)
Prints a tree Node.
Definition: Iterator.hpp:153
Class that implements a Binary Search Tree.
Definition: BST.hpp:116