// returns true is Node's color is true or NULL

bool Node::isBlack() {
	return (this == NULL || this->black == true);
}

Node* Node::rightOnceLeftDownHelper(Node* x){
	if (x->right != NULL) return Min(x->right);
	Node* pt = x->parent;
	while (pt != NULL && x == pt->right){
		x = pt;
		pt = pt->parent;
	}
	return pt;
}


void Node::setColor(bool c) {
	black = c;
}

void Node::setLeft(Node* l) {
	left = l;
}

void Node::setRight(Node* r) {
	right = r;
}

void Node::setParent(Node* p) {
	parent = p;
}

void Node::setKey(string k) {
	key = k;
}

// removal method
Node* Node::RBRemove(Node* root, string key) {
	Node* node = search(root, key);
	Node* y = NULL;
	Node* x = NULL;
	Node* z = NULL;
	if (node->left != NULL && node->right != NULL) {
		y = rightOnceLeftDownHelper(node);
	}
	else{
		y = node;
	}

	if (y->getLeft() != NULL) {
		x = y->getLeft();
	}
	else {
		x = y->getRight();
	}
	if(x) x->parent = y->parent;
	if (y->getParent() == NULL) {
		root = x;
	}
	else {
		if (y == y->getParent()->getLeft())
			y->getParent()->left = x;
		else
			y->getParent()->right = x;
	}
	if (y != node) {
		node->key = y->getKey();
	}
	if (y->isBlack()) {
		delProcess(root, x, y->parent);
	}
	return root;
}

// rotation method (just a single rotation)

void Node::Rotate(Node* &root, bool recolor) {
	Node* x = this;
	Node* parent = x->parent;
	Node* gp = getGP(x);
	x->parent = gp; // x's parent points to grandparent
	if (gp != NULL) {
		if (r(gp) == parent) { // if p is right child of gp
			gp->right = x; // gp right points to x
		}
		else {
			gp->left = x; // gp left points to x
		}
	}
	else {
		root = x;
	}


	if (x == r(parent)) {
		Node* left = x->left;
		x->left = parent;
		parent->parent = x;
		parent->right = left;
		if (left != NULL) {
			left->parent = parent;
		}
	}
	else if (x == l(parent)){
		Node* right = x->right;
		x->right = parent;
		parent->parent = x;
		parent->left = right;
		if (right != NULL) {
			right->parent = parent;
		}
	}

	if (recolor) {
		bool xc = x->black;
		bool pc = NULL;
		if(parent->black) pc = parent->black;
		x->black = pc;
		parent->black = xc;
	}
}


// method where I fix up the tree after removal

bool isBlack(Node* n) {
	if (n == NULL || n->isBlack() == true) return true;
	else return false;
}

void delProcess(Node* &root, Node* x, Node* p) {
	if (!isBlack(x)) {
		x->setColor(true);
		return;
	}
	if (p == NULL) {
		return;
	}
	else {
		Node* w = NULL;
		if (x == p->getRight()) {
			w = p->getLeft();
		}
		else {
			w = p->getRight();
		}
		if (!isBlack(w)) { // handles the case where sibling node is red
			bool temp = isBlack(w);
			w->Rotate(root, true);
			delProcess(root, x, p, z);
		}
		else if (isBlack(w->getLeft()) && isBlack(w->getRight())) { // handles case where siblings left and right children are black (or NULL)
			w->setColor(false);
			x = p;
			p = p->getParent();
			delProcess(root, x, p, z);
		}

		else if (!isBlack(w->getDirect(w))) { // handles case where siblings direct child is red
				Node* direct = w->getDirect(w);
				direct->setColor(true);
				w->Rotate(root, true);
		}
		else { // the case where there is a zig-zag child is present and double rotation is required
				Node* zz = x == w->getRight() ? zz = w->getLeft() : zz = w->getRight();
				zz->Rotate(root, true);
				zz->Rotate(root, true);
				w->setColor(true);
		}
	}
}