#include "BinarySearchTree.h"
#include <stdlib.h>

//----------------- private -------------------

struct Node* root = NULL;

struct Node* _min(struct Node* n) {
  struct Node* min = n;
  while (min->leftChild != NULL) {
    min = min->leftChild;
  }
  return min;
}

struct Node* _max(struct Node* n) {
  struct Node* max = n;
  while (max->rightChild  != NULL) {
    max = max->rightChild;
  }
  return max;
}

struct Node* _search(struct Node* n, KeyType key) {
  if (n == NULL) {
    return NULL;
  } else if (key == n->key) {
    return n;
  } else {
    if (key < n->key) {
      return _search(n->leftChild, key);
    } else { 
      //key > n->key
      return _search(n->rightChild, key);
    }
  }
}

//------------------- public ----------------------

struct Node* min() {
  return _min(root);
}

struct Node* max() {
  return _max(root);
}

struct Node* search(KeyType key) {
  return _search(root, key);
}

int insert(KeyType key) {
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
  newNode->key = key;
  newNode->leftChild = NULL;
  newNode->rightChild = NULL;

  if (root == NULL) {
    //The tree is empty. The new node will become the root.
    newNode->parent = NULL;
    root = newNode;
    return 0;
  }
  
  struct Node* parentOfNewNode = root;
  while (parentOfNewNode != NULL) {
    if (key == parentOfNewNode->key) {
      //The key allready exists in the tree. 
      //We can not insert it again.
      return -1;
    } else if (key < parentOfNewNode->key) {
      if ( parentOfNewNode->leftChild == NULL) {
	//Insert the new node here.
	parentOfNewNode->leftChild = newNode;
	newNode->parent = parentOfNewNode;
	return 0;
      } else {
	parentOfNewNode = parentOfNewNode->leftChild;
      }
    } else {
      //key > parentofNewNode->key
      if ( parentOfNewNode->rightChild == NULL) {
	//Insert the new node here.
	parentOfNewNode->rightChild = newNode;
	newNode->parent = parentOfNewNode;
	return 0;
      } else {
	parentOfNewNode = parentOfNewNode->rightChild;
      }
    }
  }
}


int remove(KeyType key) {
  struct Node* nodeToRemove = _search(root, key);
  if (nodeToRemove == NULL) {
    //There was no node with the specified key. Can not remove.
    return -1;
  }

  struct Node* parent = nodeToRemove->parent;
  struct Node* leftChild = nodeToRemove->leftChild;
  struct Node* rightChild = nodeToRemove->rightChild;
  bool isLeftChild = parent->leftChild == nodeToRemove;

  if (leftChild == NULL && rightChild == NULL) {
    //The node has no children.

    if (isLeftChild) {
      parent->leftChild = NULL;
    } else {
      parent->rightChild = NULL;
    }
    return 0;

  } else if (leftChild == NULL || rightChild == NULL) {
    //The node has one child.

    if (leftChild != NULL) {
      //The node has a left child. Let the parent point to the left child instead of 
      //the node that shall be removed.
      if (isLeftChild) {
	parent->leftChild = leftChild;
	leftChild->parent = parent;
      } else {
	parent->rightChild = leftChild;
	leftChild->parent = parent;
      }
    } else {
      //The node has a right child. Let the parent point to the left child instead of 
      //the node that shall be removed.
      if (isLeftChild) {
	parent->leftChild = rightChild;
	rightChild->parent = parent;
      } else {
	parent->rightChild = rightChild;
	rightChild->parent = parent;
      }
    }
    return 0;

  } else {
    //The node has two children. Copy the lowest value from the right subtree
    //to the node that shall be removed and remove the lowest node in
    //the right subtree instead.

    struct Node* lowestInRightSubtree = _min(nodeToRemove->rightChild);
    KeyType tmp = lowestInRightSubtree->key;
    remove(lowestInRightSubtree->key);
    nodeToRemove->key = tmp;
    return 0;

  }
}

//------------------------------------------

struct Node* cursor;

void beforeFirst() {
  cursor = min();
}

struct Node* next() {
  struct Node* next;
  if (cursor->rightChild != NULL) {
    next = cursor->rightChild;
    next = _min(next);
  } else {
    next = cursor->parent;
    struct Node* ch = cursor;
    while (next != NULL && ch == next->rightChild) {
      ch = next;
      next = next->parent;
    }
  }
  struct Node* current = cursor;
  cursor = next;
  return current;
}



bool hasNext() {
  return cursor != NULL;
}