RedBlackTree.cpp

#include "RedBlackTree.h"
#include <iostream>
#include <string>
#include <vector>

using std::cout;
using std::endl;
using std::string;

// public

RedBlackTree::RedBlackTree() {
	nil = new rbNode("NIL", "NIL", "NIL", 0, 0, "NIL", 0);
	nil->isRed = false;
	nil->left = nil;
	nil->right = nil;
	root = nil;
}

RedBlackTree::~RedBlackTree() {
	deleteAll(root);
	delete nil;
}

void RedBlackTree::printTree() {
	printTree(root);
	return;
}

void RedBlackTree::addDataNode(string in_commonName, string in_sciName, string in_phenophase, int in_elevation, int in_siteID, string in_date, int count) {
	rbNode *newNode = new rbNode (in_commonName, in_sciName, in_phenophase, in_elevation, in_siteID, in_date, count);
	newNode->left = nil;
	newNode->right = nil;

	rbNode *x = root;
	rbNode *y = NULL;

	if (root == nil) {
		root = newNode;
		newNode->parent = NULL;
		newNode->count++;
	} else {
		while (x != nil) {
			y = x;
			if (newNode->commonName.compare(x->commonName) < 0) {
				x = x->left;
			} else {
				x = x->right;
			}
		}

		if (y != nil && y != NULL) {
			if (newNode->commonName != y->commonName) {
				newNode->parent = y;
				newNode->count = 1;
				if (newNode->commonName.compare(y->commonName) < 0) {
					y->left = newNode;
				} else {
					y->right = newNode;
				}
				rbAddFixup(newNode);  // tree is already balanced if animal/plant has been added before
			} else {  // sighting of same animal/plant
				y->count++;
				y->phenophase.push_back(in_phenophase);
				y->elevation.push_back(in_elevation);
				y->siteID.push_back(in_siteID);
				y->date.push_back(in_date);
			}
		}
	}

	return;
}

void RedBlackTree::findDataNode(string commonName) {
	rbNode* x = searchRBTree(root, commonName);
	if (x == nil) {
		cout << "data not found" << endl;
	} else {
		cout << "data information: " << endl;
		printNode(x, true);
	}
	return;
}

void RedBlackTree::deleteDataNode(string commonName) {  // fix seg faults here
	rbNode *z = searchRBTree(root, commonName);
	if (z != nil) {
		rbNode *y = z;
		rbNode *x = nil;
		bool yOrigColor = y->isRed;
	
		if (z->left == nil) {
			x = z->right;
			rbTransplant(z, z->right);
		} else if (z->right == nil) {
			x = z->left;
			rbTransplant(z, z->right);
		} else {
			y = z->right;
			while (y->left != nil) {
				y = y->left;
			}
			yOrigColor = y->isRed;
			x = y->right;
			if (y->parent == z) {
				x->parent = y;
			} else {
				rbTransplant(y, y->right);
				y->right = z->right;
				y->right->parent = y;
			}
			rbTransplant(z,y);
			y->left = z->left;
			y->left->parent = y;
			y->isRed = z->isRed;
		}
		delete z;
		
		if (!yOrigColor) {
			rbDeleteFixup(x);
		}
	}
}

bool RedBlackTree::isValid() {
	if (rbValid(root) == 0) {
		return false;
	} else {
		cout << "Black height: " << rbValid(root) << endl;
		return true;
	}
}


// private

void RedBlackTree::deleteAll(rbNode *node) {
	if (node == nil) {
		return;
	} else {
		if (node->left != nil) {
			deleteAll(node->left);
		}
		if (node->right != nil) {
			deleteAll(node->right);
		}
		delete node;
	}
	return;
}

void RedBlackTree::printTree(rbNode *node) {
	cout << "print" << endl;
	if (node == nil) {
		cout << "no nodes in tree" << endl;
		return;
	} else {
		if (node->left != nil) {
			printTree(node->left);
		}
		printNode(node, false);
		if (node->right != nil) {
			printTree(node->right);
		}
		return;
	}
}

void RedBlackTree::printNode(rbNode *node, bool lookUp) {
	cout << "Common name: " << node->commonName << endl;
	cout << "Scientific name: " << node->sciName << endl;
	cout << "Number of records: " << node->count << endl;
	cout << "Site ID(s): ";
	for (unsigned int i = 0; i < (node->siteID).size()-1; i++) {
		cout << node->siteID[i]<<",";
	} cout << node->siteID[node->siteID.size()-1] << endl;

	if(lookUp){//only an option when the user has searched for a specimen by common name (not when printing entire tree)
        	std::string input = "blah";
        	while(input != "y" && input != "n"){//loop until user provides valid input
            		cout<<"Would you like more information on a site ID? (y)es or (n)o" <<endl;
            		std::getline(std::cin, input);
        	}

        	if(input =="y"){
            		std::string ID = " ";

            		while(ID.compare(" ") == 0){
                		cout<<"What is the site ID?"<<endl;
                		getline(std::cin, ID);
            		}

            		bool found = false;//indicates whether at least one with the same index has been found
            		for(unsigned int i=0; i < (node->siteID).size(); i++){
               			if(std::to_string(node->siteID[i]).compare(ID)== 0){//change to string to more easily handle invalid user input(e.g. string instead of int)
                    			if(!found){//first instance in vector
                        			cout<<"Site ID:" << node->siteID[i]<<endl;
                        			cout<<"Elevation:" <<node->elevation[i]<<endl;
                        			cout<<"----------"<<endl;
                        			found = true;
                    			}
                    			if(node->date[i].length() ==8){
                        			cout<<node->date[i].substr(0,2)<<"/"<<node->date[i].substr(2,2)<<"/"<<node->date[i].substr(4,4)<< ": " <<node->phenophase[i]<<endl;
                    			}else{
                        			cout<<node->date[i].substr(0,2)<<"/"<<node->date[i].substr(2,1)<<"/"<<node->date[i].substr(3,4)<<": " <<node->phenophase[i]<<endl;
                    			}

                		}
            		}
            		if(!found){
                		cout<<"Sorry, that ID could not be found" <<endl;
            		}

            	}
        }
}

rbNode* RedBlackTree::searchRBTree(rbNode *node, std::string in_commonName) {
	if (node == nil) {
		return nil;
	} else if (node->commonName == in_commonName) {
		return node;
	} else {
		if (in_commonName.compare(node->commonName) < 0) {
			return searchRBTree(node->left, in_commonName);
		} else {
			return searchRBTree(node->right, in_commonName);
		}
	}
}

void RedBlackTree::rbAddFixup(rbNode *node) {
	rbNode *uncle = NULL;
	node->left = nil;
	node->right = nil;

	while (node != root && node->parent->isRed) {
			cout << "check" << endl;

		if (node->parent->parent->left == node->parent) {
			uncle = node->parent->parent->right;
			if (uncle->isRed) {
				node->parent->isRed = false;
				uncle->isRed = false;
				node->parent->parent->isRed = true;
				node = node->parent->parent;
			} else {
				if (node->parent->right == node) {
					node = node->parent;
					cout << "working before rotate left" << endl;
					leftRotate(node);
				}
				node->parent->isRed = false;
				node->parent->parent->isRed = true;
				cout << "working before rotate right" << endl;
				rightRotate(node->parent->parent);
			}
		} else {
			uncle = node->parent->parent->left;
			if (uncle->isRed) {
				node->parent->isRed = false;
				uncle->isRed = false;
				node->parent->parent->isRed = true;
				node = node->parent->parent;
			} else {
				if (node->parent->left == node) {
					node = node->parent;
					cout << "working before rotate right 2" << endl;
					rightRotate(node);
				}
				node->parent->isRed = false;
				node->parent->parent->isRed = true;
				cout << "working before left rotate 2" << endl;
				leftRotate(node->parent->parent);
			}
		}
	}
	root->isRed = false;
}

void RedBlackTree::rbDeleteFixup(rbNode *node) {
	rbNode *w = nil;
	while (node != root && node->isRed == false) {
		if (node->parent->left == node) {
			w = node->parent->right;
			if (w->isRed) {
				w->isRed = false;
				node->parent->isRed = true;
				leftRotate(node->parent);
				w = node->parent->right;
			}

			if (!w->left->isRed && !w->right->isRed) {
				w->isRed = true;
				node = node->parent;
			} else {
				if (!w->right->isRed) {
					w->left->isRed = false;
					w->isRed = true;
					rightRotate(w);
					w = node->parent->right;
				}
				w->isRed = node->parent->isRed;
				node->parent->isRed = false;
				w->right->isRed = false;
				leftRotate(node->parent);
				node = root;
			}
		}

		else {
			w = node->parent->right;
			if (w->isRed) {
				w->isRed = false;
				node->parent->isRed = true;
				rightRotate(node->parent);
				w = node->parent->left;
			}

			if (!w->left->isRed && !w->right->isRed) {
				w->isRed = true;
				node = node->parent;
			} else {
				if (!w->left->isRed) {
					w->right->isRed = false;
					w->isRed = true;
					leftRotate(w);
					w = node->parent->left;
				}
				w->isRed = node->parent->isRed;
				node->parent->isRed = false;
				w->left->isRed = false;
				rightRotate(node->parent);
				node = root;
			}
		}
	}
	node->isRed = false;
	return;
}

void RedBlackTree::rbTransplant(rbNode *u, rbNode *v) {
	if (u->parent == nil) {
		root = v;
	} else if (u->parent->left == u) {
		u->parent->left = v;
	} else {
		u->parent->right = v;
	}
	v->parent = u->parent;
	return;
}

void RedBlackTree::leftRotate(rbNode *x) {
	rbNode *y = x->right;
	x->right = y->left;
	if (y->left != nil) {
		y->left->parent = x;
	}
	y->parent = x->parent;
	if (x->parent == nil) {
		root = y;
	} else {
		if (x->parent->left == x) {
			x->parent->left = y;
		} else {
			x->parent->right = y;
		}
	}
	y->left = x;
	x->parent = y;
	return;
}

void RedBlackTree::rightRotate(rbNode *x) {
	rbNode *y = x->left;
	x->left = y->right;
	if (y->right != nil) {
		y->right->parent = x;
	}
	y->parent = x->parent;
	if (x->parent == nil) {
		root = y;
	} else {
		if (x->parent->left == x) {
			x->parent->left = y;
		} else {
			x->parent->right = y;
		}
	}
	y->right = x;
	x->parent = y;
}

int RedBlackTree::rbValid(rbNode *node) {
	int lh = 0;
	int rh = 0;
	// If we are at a nil node just return 1
    	if (node == nil)
        	return 1; 

    	else {
        	rbNode * ln = node->left;
        	rbNode * rn = node->right;

        	// consecutive red links 
        	if (node->isRed)
        	{
            		if(ln->isRed || rn->isRed)
            		{
                	cout << "red violation\n";
                	return 0;
            		}
        	}

        	lh = rbValid(ln);
        	rh = rbValid(rn);

        	// black height mismatch 
        	if (lh != 0 && rh != 0 && lh != rh)
        	{
            		cout << "Black height violation\n";
            		return 0;
        	}

        	if (lh != 0 && rh != 0)
        	{
                	return node->isRed ? lh : lh + 1;
        	}
        	else
        	{
            		return 0;
        	}
	}
}