// All of the methods you will need to implement (5 of them) will have the comment

// IMPLEMENT ME

// above them. Note that one of the methods to be filled in is inside the class
// definition. This is because you cannot return an inner class outside the scope of the
// defining class. Since findNode returns a Node (an inner class), its definition has to be
// inside the definition scope of the RedBlackTree class itself, so the Node class is in scope
// as well.


#ifndef RBTREE_CS197
#define RBTREE_CS197

#include <cassert>
#include <functional>
#include <utility>
#include <iostream>

using namespace std;

// Two types are templated here!
// K = key type
// V = value type
template<typename K, typename V, typename Compare = less<K> >
class RedBlackTree {
 public:
 // This is defining an enumeration type.
 // Enumerations are categorical variables, meaning
 // a variable of the enumeration type (in this case 'Color')
 // Can only receive the values 'BLACK' and 'RED'
 typedef enum Color { BLACK, RED };

 private:
 class Node {
 public:
   Node() {
     parent = left = right = NULL;
     color = RED;
   }
   Node(K key, V value) {
     parent = left = right = NULL;
     color = RED;
     this->key = key;
     this->value = value;
   }
   ~Node() {}

   string getColor() {
    if(color == BLACK) return "BLACK";
    else if(color==RED)return "RED";
    else return "I don't know man";
}

   Node *parent;
   Node *left;
   Node *right;
   K key;
   V value;
   Color color;
 };

 Node *root;
 Node *sentinel; // This is used as a "null" pointer. It should never be directly used except
                 // to indicate a boundary. However its color is black.

 // These are internal methods that are used to maintain
 // the correctness of the tree, and for convenience
 void rotateLeft(Node *x);
 void rotateRight(Node *x);
 void insertFixup(Node *z);
 void deleteFixup(Node *x);

 Node *subTreeMinimum(Node *n) {
   Node *current;
   current = n;
   while (current->left != sentinel) {
     current = current->left;
   }
   return current;
 }

 Node *subTreeMaximum(Node *n) {
   Node *current;
   current = n;
   while (current->right != sentinel) {
     current = current->right;
   }
   return current;
 }

 // IMPLEMENT ME
 Node *findNode(K key, Node *currentPosition) {

     if(key == currentPosition->key)
         return currentPosition;
     else if(key < currentPosition->key)
     {  //I was stuck on an error here for a long long time until I put the brackets in and fixed the error.
         if(currentPosition->left != sentinel)
            return findNode(key, currentPosition->left);
     }
         else if(key > currentPosition ->key)
         {
           if(currentPosition->right != sentinel)
            return findNode(key, currentPosition->right);
         }
         return NULL;
 }

 public:
 // Constructor and Destructor
 RedBlackTree();
 ~RedBlackTree();

 // methods -- Again, don't return a Node, the return type, if there is one,
 // is of type T. See comments near methods for description
 void insert(K key, V value);
 void remove(K key);
 pair<K,V> *get(K key);
 pair<K,V> *minimum();
 pair<K,V> *maximum();
 pair<K,V> *successor(K key);
 pair<K,V> *predecessor(K key);


};

// Constructor definition - the tree should start off empty, meaning that not
// even a root exists, yet this is still a valid state of the tree.
template <typename K, typename V, typename Compare >
RedBlackTree<K,V,Compare>::RedBlackTree() {
  sentinel = new Node();
  sentinel->color = BLACK;
  // This is so we never hit a null.
  // The color checks will terminate our loops.
  sentinel->left = sentinel;
  sentinel->right = sentinel;
  sentinel->parent = sentinel;
  root = sentinel;
}

// Deconstructor for the tree. Don't call delete on the key or value data since you
// don't know what it is. However, any remaining nodes in the tree need to be deallocated
// to avoid memory leaks.
template<typename K, typename V, typename Compare >
RedBlackTree<K,V,Compare>::~RedBlackTree() {
  delete sentinel;
}


// Inserts a new node into the tree.
template<typename K, typename V, typename Compare >
void RedBlackTree<K,V,Compare>::insert(K key, V value) {
  Node *z = new Node(key, value);
  Node *y = sentinel;
  Node *x = root;
  while (x != sentinel) {
    y = x;
    if (Compare()(z->key, x->key)) {
      x = x->left;
    } else {
      x = x->right;
    }
  }
  z->parent = y;
  if (y == sentinel) {
    root = z;
  } else {
    if (Compare()(z->key, y->key)) {
      y->left = z;
    } else {
      y->right = z;
    }
  }
  z->left = sentinel;
  z->right = sentinel;
  z->color = RED;
  insertFixup(z);
}

// Removes a node from the tree, if it (the node) exists.
template<typename K, typename V, typename Compare >
void RedBlackTree<K,V,Compare>::remove(K key) {
    /*
     //Tracer code for tree
cout<<"||"<<root->left->key<<"("<<root->left->getColor()<<")("<<root->left->parent->key<<")<-";
     cout<<"Root:"<<root->key<<"("<<root->getColor()<<"("<<root->parent->key<<")";

       cout<<"->"<<root->right->key<<"("<<root->right->getColor()<<")("<<root->right->parent->key<<")";
       cout<<"->"<<root->right->right->key<<"("<<root->right->right->getColor()<<")("<<root->right->right->parent->key<<")||"<<endl;
*/
  Node *x, *y;
  Node *z = findNode(key, root);

  if (z == sentinel) return;

  // Harder from here...
  if (z->left == sentinel || z->right == sentinel) {
    y = z;
  } else {
    pair<K,V> *result = successor(z->key);
    y = findNode(result->first, root);
    delete result; // Cleaning up
  }

  if (y->left != sentinel) {
    x = y->left;
  } else {
    x = y->right;
  }

  x->parent = y->parent;

  if (y->parent == sentinel) {
    root = x;
  } else {
    if (y == y->parent->left) {
      y->parent->left = x;
    } else {
      y->parent->right = x;
    }
  }

  if (y != z) {
    z->key = y->key;
    z->value = y->value;
  }

  if (y->color == BLACK) {
    deleteFixup(x);
  }

}

// Returns the key/value pair of the provided key if it exists.
// Otherwise returns null.
template<typename K, typename V, typename Compare >
pair<K,V> *RedBlackTree<K,V,Compare>::get(K key) {
  Node *found = findNode(key, root);
  if (found == sentinel) return NULL;
  else return new pair<K,V>(found->key, found->value);
}

// Returns the smallest item in the tree, or NULL if the tree is empty.
template<typename K, typename V, typename Compare >
pair<K,V> *RedBlackTree<K,V,Compare>::minimum() {
  if (root == sentinel) {
    return NULL;
  } else {
    Node *min = subTreeMinimum(root);
    return new pair<K,V>(min->key, min->value);
  }
}

// Returns the largest item in the tree, or NULL if the tree is empty.
template<typename K, typename V, typename Compare >
pair<K,V> *RedBlackTree<K,V,Compare>::maximum() {
  if (root == sentinel) {
    return NULL;
  } else {
    Node *max = subTreeMaximum(root);
    return new pair<K,V>(max->key, max->value);
  }
}

template<typename K, typename V, typename Compare >
void RedBlackTree<K,V,Compare>::insertFixup(Node *z) {
  Node *y;

  while (z->parent->color == RED) {
    if (z->parent == z->parent->parent->left) {
      y = z->parent->parent->right;
      if (y->color == RED) {
	z->parent->color = BLACK;
	y->color = BLACK;
	z->parent->parent->color = RED;
	z = z->parent->parent;
      } else {
	if (z == z->parent->right) {
	  z = z->parent;
	  rotateLeft(z);
	}
        //
	z->parent->color = BLACK;
	z->parent->parent->color = RED;
	rotateRight(z->parent->parent);
      }
    } else  {
      y = z->parent->parent->left;
      if (y->color == RED) {
	z->parent->color = BLACK;
	y->color = BLACK;
	z->parent->parent->color = RED;
	z = z->parent->parent;
      } else {
	if (z == z->parent->left) {
	  z = z->parent;
	  rotateRight(z);
	}
	z->parent->color = BLACK;
	z->parent->parent->color = RED;
	rotateLeft(z->parent->parent);
      }
    }
  }
  root->color = BLACK;



}

template<typename K, typename V, typename Compare >
void RedBlackTree<K,V,Compare>::deleteFixup(Node *x) {
  Node *w;

  while (x != root && x->color == BLACK) {
    if (x = x->parent->left) {
      w = x->parent->right;
      if (w->color == RED) {
	w->color = BLACK;
	x->parent->color = RED;
	rotateLeft(x->parent);
	w = x->parent->right;
      }

      if (w->left->color == BLACK && w->right->color == BLACK) {
	w->color = RED;
	x = x->parent;
      } else {
	if (w->right->color == BLACK) {
	  w->color = RED;
	  rotateRight(w);
	  w = x->parent->right;
	}
	w->color = x->parent->color;
	x->parent->color = BLACK;
	w->right->color = BLACK;
	rotateLeft(x->parent);
	x = root;
      }
    } else {
      w = x->parent->left;
      if (w->color == RED) {
	w->color = BLACK;
	x->parent->color = RED;
	rotateRight(x->parent);
	w = x->parent->left;
      }

      if (w->right->color == BLACK && w->left->color == BLACK) {
	w->color = RED;
	x = x->parent;
      } else {
	if (w->left->color == BLACK) {
	  w->color = RED;
	  rotateLeft(w);
	  w = x->parent->left;
	}
	w->color = x->parent->color;
	x->parent->color = BLACK;
	w->left->color = BLACK;
	rotateRight(x->parent);
	x = root;
      }
    }
  }
  x->color = BLACK;

}

// IMPLEMENT ME
template<typename K, typename V, typename Compare >
pair<K,V> *RedBlackTree<K,V,Compare>::successor(K key) {
    Node *x = findNode(key, this->root);

    K k;
  if(x == NULL)return NULL;

    x = this->root;
     pair<K,V> *p = new pair<K,V>(x->key, x->value);

    while(x != sentinel)
    {
        if(Compare()(key, x->key))
        {
            if(Compare() (key, x->key) && ((x->key < p->first && p->first > key)|| (p->first <= key)))
                p = new pair<K,V>(x->key, x->value);
            x = x->left;
        }
        else
        {
            x = x->right;
        }
    }

     if(p->first > key) return p;
     else return new pair<K,V>;
}

// IMPLEMENT ME
template<typename K, typename V, typename Compare >
pair<K,V> *RedBlackTree<K,V,Compare>::predecessor(K key) {
  return NULL;
}

// IMPLEMENT ME
template<typename K, typename V, typename Compare >
void RedBlackTree<K,V,Compare>::rotateLeft(Node *x) {
   // cout<<"ROTATELEFT:"<<x->key<<endl;

          Node *me;
          Node *z;
       if (x->right == 0) return;

       me          = x; // me = x
       z           = me->right; //z = y
       z->parent = x->parent;
       me->right = z->left;
       me->parent = z;
       z->left   = me;

      // cout<<"z->parent("<<z->parent->key<<")";
        if(z->parent == sentinel) root = z;
        else x = z;
}


// IMPLEMENT ME
template<typename K, typename V, typename Compare >
void RedBlackTree<K,V,Compare>::rotateRight(Node *x) {
  //  cout<<"ROTATERIGHT"<<endl;
          Node *me;
          Node *z;
    if (x->left == 0) return;

       me          = x; // me = x
       z           = me->left; //z = y
       z->parent = x->parent;
       me->left = z->right;
       me->parent = z;
       z->right   = me;

      // cout<<"z->parent("<<z->parent->key<<")";
        if(z->parent == sentinel) root = z;
        else x = z;
}

#endif