#include "./tree-utils.h"
#include <vector>

// Exercise 1

template <class T>
bool isBST(Tree<T>* tree) {
	if (tree == nullptr) return true;
	return    (tree->left  == nullptr || tree->left->data < tree->data)
	       && (tree->right == nullptr || tree->data       < tree->right->data)
	       && isBST(tree->left) && isBST(tree->right);
}

void ex1() {
	Tree<int>* t = new Tree<int>(8, new Tree<int>(3, new Tree<int>(1), new Tree<int>(6, new Tree<int>(4), new Tree<int>(7))), new Tree<int>(10, nullptr, new Tree<int>(14, new Tree<int>(13))));
	std::cout << isBST(t) << std::endl;

	freeTree(t);
}

// Exercise 2

template <class T>
void recBuildBST(std::vector<T>& vec, int start, int end, Tree<T>*& parent) {
	int mid = start + (end - start) / 2;
	Tree<T>* current = new Tree<T>(vec[mid]);

	if (parent == nullptr)
		parent = current;

	if (current->data < parent->data)
		parent->left = current;
	else if (parent->data < current->data)
		parent->right = current;

	if (mid - start > 0)
		recBuildBST(vec, start, mid - 1, current);
	if (end - mid > 0)
		recBuildBST(vec, mid + 1, end, current);
}

template <class T>
Tree<T>* vecToBST(std::vector<T>& vec) {
	Tree<T>* result = nullptr;
	recBuildBST(vec, 0, vec.size() - 1, result);
	return result;
}

void ex2() {
	std::vector<int> v = { 1, 3, 4, 6, 7, 8, 10, 13, 14 };
	Tree<int>* t = vecToBST(v);
	printTree(t);

	freeTree(t);
}

// Exercise 3

template <class T>
void insertNodeInBST(Tree<T>*& tree, Tree<T>* node) {
	if (tree == nullptr) {
		tree = node;
		return;
	}
	
	insertNodeInBST((tree->data < node->data) ? tree->right : tree->left, node);
}

template <class T>
void removeInBST(Tree<T>*& tree, const T& elem) {
	Tree<T>** current = &tree;
	while (*current != nullptr && (*current)->data != elem) {
		current = ((*current)->data < elem) ? &((*current)->right) : &((*current)->left);
	}
	if (current == nullptr) return;

	Tree<T>* oldCurrent = *current;
	*current = (*current)->right;
	insertNodeInBST(*current, oldCurrent->left);
	delete oldCurrent;
}

void ex3() {
	Tree<int>* t = new Tree<int>(8, new Tree<int>(3, new Tree<int>(1), new Tree<int>(6, new Tree<int>(4), new Tree<int>(7))), new Tree<int>(10, nullptr, new Tree<int>(14, new Tree<int>(13))));
	removeInBST(t, 8);
	printTree(t);

	freeTree(t);
}

// Exercise 4

template <class T>
bool equal(Tree<T>* a, Tree<T>* b) {
	if ((a == nullptr) != (b == nullptr)) return false;
	else if (a == nullptr) return true;

	return a->data == b->data && equal(a->left, b->left) && equal(a->right, b->right);
}

void ex4() {
	Tree<int>* t1 = new Tree<int>(8, new Tree<int>(3, new Tree<int>(1), new Tree<int>(6, new Tree<int>(4), new Tree<int>(7))), new Tree<int>(10, nullptr, new Tree<int>(14, new Tree<int>(13))));
	Tree<int>* t2 = new Tree<int>(8, new Tree<int>(3, new Tree<int>(1), new Tree<int>(6, new Tree<int>(4), new Tree<int>(7))), new Tree<int>(10, nullptr, new Tree<int>(14, new Tree<int>(13))));
	std::cout << equal(t1, t2) << std::endl;

	freeTree(t1);
	freeTree(t2);
}

// Exercise 5

template <class T>
void rightRotation(Tree<T>*& tree) {
	Tree<T>* root = tree;
	Tree<T>* pivot = tree->left;

	tree = pivot;
	root->left = pivot->right;
	tree->right = root;
}

template <class T>
void leftRotation(Tree<T>*& tree) {
	Tree<T>* root = tree;
	Tree<T>* pivot = tree->right;

	tree = pivot;
	root->right = pivot->left;
	tree->left = root;
}

void ex5() {
	Tree<char>* t = new Tree<char>('Q', new Tree<char>('P', new Tree<char>('A'), new Tree<char>('B')), new Tree<char>('C'));
	printTree(t);
	rightRotation(t);
	printTree(t);
	leftRotation(t);
	leftRotation(t);
	printTree(t);
	rightRotation(t);
	printTree(t);

	freeTree(t);
}

// Exercise 6

template <class T>
T pred(Tree<T>* tree, const T& x) {
	if (tree->value > x) {
		if (tree->left == nullptr) return tree->value;
		pred(tree->left, x);
	}
	else {
		if (tree->right == nullptr) return tree->value;
		pred(tree->right, x);
	}
}

void ex6() {

}

// main

int main() {
	ex5();
}