Skip to content

Instantly share code, notes, and snippets.

@rusdevops

rusdevops/iterator.hpp

Last active May 7, 2018 06:09
Show Gist options
  • Save rusdevops/ecaa2352849632c7b1be4643cfcc3493 to your computer and use it in GitHub Desktop.
Save rusdevops/ecaa2352849632c7b1be4643cfcc3493 to your computer and use it in GitHub Desktop.
Download ZIP
BSTree 🌳
Raw
iterator.hpp
#include <node.hpp>
namespace BSTree {
template<typename T>
class iterator;
template <typename T>
class pre_iterator;
template <typename T>
class post_iterator;
template<typename T>
class iterator {
using pointer = T *;
using reference = T &;
using value_type = T;
public:
iterator(const iterator &);
~iterator();
iterator& operator=(const iterator &);
virtual iterator& operator++();
virtual reference operator*() const;
virtual iterator operator++(int);
value_type operator*() const;
pointer operator->() const;
reference operator*() const;
iterator operator++(int);
friend bool operator==(const iterator&, const iterator&);
friend bool operator!=(const iterator&, const iterator&);
friend void swap(iterator& lhs, iterator& rhs);
private:
Node* ptr;
};
template <typename T>
class pre_iterator : iterator<T> {
protected:
pre_iterator();
pre_iterator(Node* ptr);
// ...
};
template <typename T>
class post_iterator : iterator<T> {
protected:
post_iterator();
post_iterator(Node* ptr);
// ...
};
}
Raw
main.cpp
int main() {
using BSTree::Tree;
Tree<int> tree = {5, 3, 4, 2, 7, 9, 6, 8};
auto it = tree.begin();
auto end = tree.end();
for (; it != end; ++it ) {
std::cout << *it << ' ';
}
std::cout << std::endl;
auto rit = tree.rbegin();
auto rend = tree.rend();
for(; rit != rend; ++rit) {
std::cout << *it << ' ';
}
std::cout << std::endl;
}
Raw
node.hpp
namespace BSTree {
template <typename T>
struct Node {
T data;
Node * left;
Node * right;
Node * parent;
};
}
Raw
tree.hpp
#include <hode.hpp>
#include <iterator.hpp>
namespace BSTree {
template <typename T>
class Tree {
public:
using iterator = pre_order::iterator;
using reverse_iterator = post_order::iterator;
Tree(std::initializer_list<T>);
auto push_back(const T&) -> void;
auto begin() -> iterator;
auto end() -> iterator;
auto rbegin() -> reverse_iterator;
auto rend() -> reverse_iterator;
private:
Node<T>* root;
};
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment