#ifndef __PROJ_THREE_AVL_HPP
#define __PROJ_THREE_AVL_HPP

#include "runtimeexcept.hpp"
#include <string>
#include <vector>

class ElementNotFoundException : public RuntimeException
{
public:
	ElementNotFoundException(const std::string & err) : RuntimeException(err) {}
};

template<typename Key, typename Value>
class Node{
	public:
		Key key;
		Value value;
		Node<Key, Value>* left;
		Node<Key, Value>* right;
};

template<typename Key, typename Value>
class MyAVLTree{
private:
	Node<Key, Value>* avl;
	int total_size = 0;
	// fill in private member data here
	// If you need to declare private functions, do so here too.

public:
	MyAVLTree();

	// In general, a copy constructor and assignment operator
	// are good things to have.
	// For this quarter, I am not requiring these.
	//	MyAVLTree(const MyAVLTree & st);
	//	MyAVLTree & operator=(const MyAVLTree & st);


	// The destructor is, however, required.
	~MyAVLTree(){
		// TODO
	}

	// size() returns the number of distinct keys in the tree.
	size_t size() const noexcept;

	// isEmpty() returns true if and only if the tree has no values in it.
	bool isEmpty() const noexcept;

	// contains() returns true if and only if there
	//  is a (key, value) pair in the tree
	//	that has the given key as its key.
	bool contains(const Key & k) const;

	// find returns the value associated with the given key
	// If !contains(k), this will throw an ElementNotFoundException
	// There needs to be a version for const and non-const MyAVLTrees.
	Value & find(const Key & k);
	const Value & find(const Key & k) const;

	// Inserts the given key-value pair into
	// the tree and performs the AVL re-balance
	// operation, as described in lecture.
	// If the key already exists in the tree,
	// you may do as you please (no test cases in
	// the grading script will deal with this situation)
	void insert(const Key & k, const Value & v);

	// in general, a "remove" function would be here
	// It's a little trickier with an AVL tree
	// and I am not requiring it for this quarter's ICS 46.
	// You should still read about the remove operation
	// in your textbook.

	// The following three functions all return
	// the set of keys in the tree as a standard vector.
	// Each returns them in a different order.
	std::vector<Key> inOrder() const;
	std::vector<Key> preOrder() const;
	std::vector<Key> postOrder() const;
};


template<typename Key, typename Value>
MyAVLTree<Key,Value>::MyAVLTree(){
	avl = nullptr;									// Initialize AVL tree
}

template<typename Key, typename Value>
size_t MyAVLTree<Key, Value>::size() const noexcept{
	return total_size; // stub
}

template<typename Key, typename Value>
bool MyAVLTree<Key, Value>::isEmpty() const noexcept{
	if(avl == nullptr){
		return true;
	}
	return false;
}


template<typename Key, typename Value>
bool MyAVLTree<Key, Value>::contains(const Key &k) const{
	Node<Key, Value>* newNode = avl;
	do
	{
		if(newNode == nullptr)
		{
			return false;
		}
		else if(newNode->key == k)
		{
			return true;
		}
		else if(k < newNode->key)
		{
			newNode = newNode->left;

		}
		else
		{
			newNode = newNode->right;
		}
	}while(newNode != nullptr);

	return false;
}


template<typename Key, typename Value>
Value & MyAVLTree<Key, Value>::find(const Key & k){
	Value v;
	return v; // not only a stub, but a terrible idea.
}

template<typename Key, typename Value>
const Value & MyAVLTree<Key, Value>::find(const Key & k) const{

	Value v;
	return v; // not only a stub, but a terrible idea.
}

template<typename Key, typename Value>
void MyAVLTree<Key, Value>::insert(const Key & k, const Value & v){
	// Create new node with values
	Node<Key, Value>* newNode = new Node<Key, Value>;
	newNode->key = k;
	newNode->value = v;
	newNode->left = nullptr;
	newNode->right = nullptr;
	// Assign new node to AVL tree if the tree is empty
	if(avl == nullptr){
		avl = newNode;
		total_size++;
	}
	else{
		Node<Key, Value>* travelNode = avl;
		do{
			if(k == travelNode->key) //If the current key is correct
				break;
			else if(k > travelNode->key){
				if(travelNode->right == nullptr)
				{
					travelNode->right = newNode;
					total_size++;
				}
				else
				{
					travelNode = travelNode->right;
				}


			}
			else{
				if(travelNode->left == nullptr)
				{
					travelNode->left = newNode;
					total_size++;
				}
				else
				{
					travelNode = travelNode->left;
				}
			}

		}while(travelNode != nullptr);
	}
}



template<typename Key, typename Value>
std::vector<Key> MyAVLTree<Key, Value>::inOrder() const{
	std::vector<Key> foo;
	return foo;
}


template<typename Key, typename Value>
std::vector<Key> MyAVLTree<Key, Value>::preOrder() const{
	std::vector<Key> foo;
	return foo;
}


template<typename Key, typename Value>
std::vector<Key> MyAVLTree<Key, Value>::postOrder() const{
	std::vector<Key> foo;
	return foo;
}

#endif