#include "pch.h"
#include <iostream>
#include <stack>

using namespace std;

template<typename T>
class Tree {
public:
	class node {
	public:
		node* left;
		node* right;
		node* parent;
		T key;
		node(node* parent, T key) {
			this->parent = parent;
			this->key = key;
		}
	};
public:
	node* root;

	Tree() {
		root = NULL;
	}

	void push(T key, node* parent) {
		if (parent->key < key) {
			if (parent->right == NULL) {
				parent->right = new node(parent, key);
			}
			else {
				push(key, parent->right);
			}
		}
		else {
			if (parent->left == NULL) {
				parent->left = new node(parent, key);
			}
			else {
				push(key, parent->left);
			}
		}
	}

	void push(T key) {
		if (root == NULL) {
			root = new node(NULL, key);
		}
		else {
			push(key, root);
		}
	}

	void print() {
		print(root);
	}

	void print(node* parent) {
		if (parent->left != NULL) {
			print(parent->left);
		}

		cout << "{" << parent->key << "} ";

		if (parent->right != NULL) {
			print(parent->right);
		}
	}

	static node* findl(node* parent) {
		node* n = parent;

		while (n->left != NULL) {
			n = n->left;
		}

		return n;
	}

	static node* findr(node* parent) {
		node* n = parent;

		while (n->right != NULL) {
			n = n->right;
		}

		return n;
	}

	class iterator {
	public:
		node* current;
		stack<node*> s;

		iterator(node* n) {
			current = n;
		}

		void findn() {
			if (current->right != NULL) {
				s.push(current);
				current = Tree::findl(current->right);
			}
			else {
				node* parent = current->parent;

				if (!s.empty()) {

					node* top = s.top();
					while (top == parent) {
						parent = top->parent;
						s.pop();
						if (s.empty())
							break;
						top = s.top();
					}
				}
				current = parent;
			}
		}

		bool operator !=(iterator other) {
			return current != other.current;
		}
		iterator operator++() {
			findn();
			return *this;
		}

		iterator operator++(int) {
			findn();
			return *this;
		}

		T operator *() {
			return current->key;
		}




	};

	iterator begin() {
		return iterator(findl(root));
	}

	iterator end() {
		return iterator(NULL);
	}

	iterator end1() {
		return iterator(findr(root));
	}


	class riterator {
	public:
		node* current;
		stack<node*> s;

		riterator(node* n) {
			current = n;
		}

		void findn1() {
			if (current->left != NULL) {
				s.push(current);
				current = Tree::findr(current->left);
			}
			else {
				node* parent = current->parent;

				if (!s.empty()) {

					node* top = s.top();
					while (top == parent) {
						parent = top->parent;
						s.pop();
						if (s.empty())
							break;
						top = s.top();
					}
				}
				current = parent;
			}
		}
		bool operator !=(riterator other) {
			return current != other.current;
		}

		riterator operator++() {
			findn1();
			return *this;
		}

		riterator operator ++(int) {
			findn1();
			return *this;
		}

		T operator *() {
			return current->key;
		}

	};

	riterator begin1() {
		return riterator(findr(root));
	}


};


int main()
{

	Tree <int> t;

	t.push(7);
	t.push(200);
	t.push(4);
	t.push(1);
	t.push(435);
	t.push(28);
	t.push(3);
	cout << "print: " << endl;
	t.print();
	cout << endl;
	cout << "iterator ++: " << endl;
	Tree<int>::iterator i = t.begin();

	for (Tree<int>::iterator i = t.begin(); i != t.end(); i++) {
		cout << "{" << *i << "} ";
	}

	cout <<endl<< "riterator ++: " << endl;

	Tree<int>::riterator j = t.begin1();
	for (Tree<int>::riterator j = t.begin1(); j != NULL; j++) {
		cout << "{" << *j << "} ";
	}
	return 0;
}

/*
           5
          / \
		 0   7
		  \   \
		   3   9
		  /     \
		 2		10
*/