#include <iostream>
#include <stdlib.h>
#include "time.h"

class Tree
{
public:
	class Node
	{
	public:
		int key;
		Node* L = nullptr;
		Node *R = nullptr;

		Node(int key);
	};
	void insert(int key);
	void printLeft();
	void printRight();
	void printSort(bool = true);
	Node* GetRoot() {return this->root;};
	Tree::Node* printLeft(Node*);
	Tree::Node* printRight(Node*);
	Node* root = nullptr;
private:

	void insert(int key, Node*& root);
	void printSort(bool, Node*);

};

Tree::Node::Node(int key)
{
	this->key = key;
}

void Tree::insert(int key)
{
	this->insert(key, this->root);
}

void Tree::insert(int key, Node*& root)
{
	if (root == nullptr)
	{
		root = new Node(key);
		return;
	}

	if (root->key == key)
	{
		insert(key, root->L);
	}

	if (root->key > key)
	{
		insert(key, root->L);
	}

	if (root->key < key)
	{
		insert(key, root->R);
	}
}

void Tree::printSort(bool asc)
{
	this->printSort(asc, this->root);
}

void Tree::printSort(bool asc, Node* root)
{
	if (root == nullptr)
	{
		return;
	}

	//pokud bool true, zavola se levy potomek
	printSort(asc, asc ? root->L : root->R);
	std::cout << root->key << " ";
	//pokud bool true, zavola se pravy potomek
	printSort(asc, asc ? root->R : root->L);
}

void Tree::printLeft()
{
    this->printLeft(this->root);
}

Tree::Node* Tree::printLeft(Node* root)
{
    if(root == nullptr)
        return 0;
    return root->L;
    //printLeft(root->L);   //pro opakování na využití rekurze

}

void Tree::printRight()
{
    this->printRight(this->root);
}

Tree::Node* Tree::printRight(Node* root)   //poze jednou
{
    if(root == nullptr)
        return 0;
    return root->R;

}
///////////////////////////////////
class Zasobnik
{
private:
	Tree::Node **zas;
	int index;
	int max;
public:
    Zasobnik(int);
    ~Zasobnik();
    void AddTop(Tree::Node*);
    Tree::Node* PickTop();
    bool IsEmpty();
    void DeleteTop();
};

Zasobnik::Zasobnik(int poc){
	max = poc;
	zas = new Tree::Node*[max];
    index = -1;
}

Zasobnik::~Zasobnik(void)
{
    for(int i = 0; i < this->index; i++)
    {
        delete  zas[i];
        this->index--;
    }
	delete [] zas;
}

void Zasobnik::AddTop(Tree::Node* h){
    if (index < max-1){
        index++;
        zas[this->index] = h;
    } else
        std::cout << "Zasobnik je plny!" << std::endl;
}

void Zasobnik::DeleteTop()
{
    if(index >= 0)
    {
        delete this->zas[this->index];
        index--;
    }
}

Tree::Node* Zasobnik::PickTop()
{
    if (index>=0){
        //std::cout << this->index << " " << this->zas[this->index]->key << std::endl;
        return this->zas[this->index];
    }
    else{
        std::cout << "Zasobnik je prazdny!" << std::endl;
    }
}

bool Zasobnik::IsEmpty(){
	if (index < 0)
        return true;
	else
        return false;
}

/////////////////////////////////////////////////////////////////////////////////////
class Iterator
{
private:
	Tree::Node* root;
	Zasobnik* z;
public:
    Iterator(Zasobnik*& z, Tree::Node* n);

    void Reset(Tree t);
    void Next(Tree t);
    bool IsEnd();
    int CurrentKey(Zasobnik* z);

};

Iterator::Iterator(Zasobnik*& z, Tree::Node* n)
{
    this->root = n;
    this->z = z;
}

void Iterator::Reset(Tree t)
{
    this->root = t.GetRoot();
    	//pokud je uzel nullptr jsme na konci = nasli jsme minumum
	while (this->root != nullptr)
	{
		//uzel do zasobniku
		this->z->AddTop(this->root);
		//posun na levy uzel
		this->root = this->root->L;
		if(this->root!=nullptr)
            std::cout<< "->" << this->root->key;
	}
}

void Iterator::Next(Tree t)
{
    if(this->root->R == nullptr){
        std::cout << "Neexistuje pravý podstrom" << std::endl;
        return;
    }
    //posun na pravý uzel od kořene
    this->root = this->root->R;
    std::cout << "->" << this->root->key;
    //posun na nejlevější uzel v pravém podstromu
 	while (this->root->L != nullptr)
	{
		//uzel do zasobniku
		this->z->AddTop(this->root);
		//posun na levy uzel
		this->root = this->root->L;
		if(this->root!=nullptr)
            std::cout<< "->" << this->root->key;
	}
}

bool Iterator::IsEnd()
{
    if(this->z->IsEmpty())
        return true;
    return false;
}

int Iterator::CurrentKey(Zasobnik* z)
{
    return z->PickTop()->key;
}
using namespace std;

int main()
{
    int random, root;
    srand(time(NULL));

	Tree tree;

	cout << "Tree generator: ";
    for(int i = 0; i<12;i++){
        random = rand()%100;
        tree.insert(random);
        cout << random << " ";
        if(i == 0)
            root = random;
    }

    cout << endl << "Sorted Tree: ";
    tree.printSort();
    cout << endl << endl;
    //cout << endl;

	//tree.printLeft();

    //cout << endl;

    //tree.printRight();
    Zasobnik* zasobnik = new Zasobnik(12);
	Iterator* i = new Iterator(zasobnik, tree.root);

    /*if(i->IsEnd())
        cout << "true" << endl;
    else
        cout << "false" <<endl;
    */
    cout << "Root: " << root << endl;
    cout << "Next: " << root;
    i->Next(tree);
    cout << endl;
    cout << "Reset: " << root;
    i->Reset(tree);
    cout << endl;
    cout << "CurrentKey: " << i->CurrentKey(zasobnik) << endl;

	system("pause");
	return 0;
}