natalie_code/program3/AVLCommands.cpp

// written by Rob Gysel

#include "AVLCommands.h"

#include <cassert>
#include <iostream>
#include <string>
#include <queue>

#include "json.hpp"


BSTNode::BSTNode(int key) :
	key_(key),
	parent_(std::weak_ptr<BSTNode>()),
	left_(nullptr),
	right_(nullptr),
	height_(1) {} // add a height_

BSTNode::BSTNode(int key, std::weak_ptr<BSTNode> parent) :
	key_(key),
	parent_(parent),
	left_(nullptr),
	right_(nullptr),
	height_(1) {}

bool BSTNode::IsLeaf() const {
	return left_ == nullptr && right_ == nullptr;
}

bool BSTNode::HasLeftChild() const {
	return left_ != nullptr;
}

bool BSTNode::HasRightChild() const {
	return right_ != nullptr;
}

void BSTNode::DeleteChild(std::shared_ptr<BSTNode> v) {
	if (left_ == v) {
		left_ = nullptr;
	} else if (right_ == v) {
		right_ = nullptr;
	} else {
		std::cerr << "BSTNode::DeleteChild Error: non-child passed as argument\n";
		exit(EXIT_FAILURE);
	}
}

void BSTNode::ReplaceChild(std::shared_ptr<BSTNode> v, std::shared_ptr<BSTNode> u) {
	if (left_ == u || right_ == u) {
		std::cerr << "BSTNode::ReplaceChild Error: child passed as replacement\n";
	}
	if (left_ == v) {
		left_ = u;
		u->parent_ = v->parent_;
	} else if (right_ == v) {
		right_ = u;
		u->parent_ = v->parent_;
	} else {
		std::cerr << "BSTNode::ReplaceChild Error: non-child passed as argument\n";
		exit(EXIT_FAILURE);
	}
}

AVLCommands::AVLCommands() : root_(nullptr), size_(0) {} // add height here?

// searches through the node keys to get the parent of specified key
int AVLCommands::getParent(int key) {
	int parent = 0;
	if (root_ == nullptr) {
		return -1;
	}
	std::shared_ptr<BSTNode> currentNode = root_, lastNode = nullptr;
	while (currentNode->key_ != key) {
		lastNode = currentNode;
		currentNode = (key < currentNode->key_) ?
			currentNode->left_ : currentNode->right_;
	}
	parent = lastNode -> key_;
	return parent;
}


int AVLCommands::getLeft(int key) {
	if (root_ == nullptr) {
		return -1;
	}
	std::shared_ptr<BSTNode> currentNode = root_;
	while (currentNode->key_ != key) {
		currentNode = (key < currentNode->key_) ?
			currentNode->left_ : currentNode->right_;
	}
	currentNode = currentNode->left_;
	return currentNode->key_;
}

int AVLCommands::getRight(int key) {
	if (root_ == nullptr) {
		return -1;
	}
	std::shared_ptr<BSTNode> currentNode = root_;
	while (currentNode->key_ != key) {
		currentNode = (key < currentNode->key_) ?
			currentNode->left_ : currentNode->right_;
	}
	currentNode = currentNode->right_;
	return currentNode->key_;
}

int AVLCommands::max(int a, int b) {
	return (a > b)? a : b;
}

int AVLCommands::height(std::shared_ptr<BSTNode> currentNode) {
	if (currentNode == nullptr)
      return 0;
  return currentNode->height_;
}

int AVLCommands::getBalance(std::shared_ptr<BSTNode> currentNode) {
	if (currentNode == nullptr)
      return 0;
  return height(currentNode->left_) - height(currentNode->right_);
}

std::shared_ptr<BSTNode> AVLCommands::rightRotate(std::shared_ptr<BSTNode> currentNode){
	std::shared_ptr<BSTNode> x = currentNode->left_;
  std::shared_ptr<BSTNode> T2 = x->right_;

  // Perform rotation
  x->right_ = currentNode;
  currentNode->left_ = T2;

  // Update heights
  currentNode->height_ = max(height(currentNode->left_), height(currentNode->right_))+1;
  x->height_ = max(height(x->left_), height(x->right_))+1;

  // Return new root
  return x;
}

std::shared_ptr<BSTNode> AVLCommands::leftRotate(std::shared_ptr<BSTNode> currentNode){
	std::shared_ptr<BSTNode> y = currentNode->right_;
  std::shared_ptr<BSTNode> T2 = y->left_;

  // Perform rotation
  y->left_ = currentNode;
  currentNode->right_ = T2;

  //  Update heights
  currentNode->height_ = max(height(currentNode->left_), height(currentNode->right_))+1;
  y->height_ = max(height(y->left_), height(y->right_))+1;

  // Return new root
  return y;
}

void AVLCommands::Insert(int key) {
	// BST insertion
	if (root_ == nullptr) {
		root_ = std::make_shared<BSTNode>(key);
		size_++;
		return;
	}
	std::shared_ptr<BSTNode> currentNode = root_, lastNode = nullptr;
	while (currentNode != nullptr) {
		lastNode = currentNode;
		currentNode = (key < currentNode->key_) ?
			currentNode->left_ : currentNode->right_;
	}
	if (key < lastNode->key_) {
		lastNode->left_ = std::make_shared<BSTNode>(key, lastNode);
	} else {
		lastNode->right_ = std::make_shared<BSTNode>(key, lastNode);
	}
	size_++;

	// Update hight of this ancestor's node... need to check if this should be currNode or lastNode
	lastNode->height_ = 1 + max(height(lastNode->left_), height(lastNode->right_));

	// Update balance factor of this ancestor's node
	int lastNodeBalance = getBalance(lastNode);

	// Check if unbalanced
	// Left Left Case
  if (lastNodeBalance > 1 && key < lastNode->left_->key_)
      rightRotate(lastNode);

  // Right Right Case
  if (lastNodeBalance < -1 && key > lastNode->right_->key_)
      leftRotate(lastNode);

  // Left Right Case
  if (lastNodeBalance > 1 && key > lastNode->left_->key_) {
      lastNode->left_ =  leftRotate(lastNode->left_);
      rightRotate(lastNode);
  }

  // Right Left Case
  if (lastNodeBalance < -1 && key < lastNode->right_->key_) {
      lastNode->right_ = rightRotate(lastNode->right_);
      leftRotate(lastNode);
  }
}

bool AVLCommands::Delete(int key) {
	// base BST delete
	std::shared_ptr<BSTNode> currentNode = root_;
	while (currentNode != nullptr) {
		if (currentNode->key_ == key) {
			if (currentNode->IsLeaf()) {
				DeleteLeaf(currentNode);
			} else if (currentNode->left_ == nullptr) {
				assert(currentNode->right_ != nullptr);
				std::shared_ptr<BSTNode> parent = currentNode->parent_.lock();
				parent->ReplaceChild(currentNode, currentNode->right_);
				size_--; assert(size_ >= 0);
			} else if (currentNode->right_ == nullptr) {
				assert(currentNode->left_ != nullptr);
				std::shared_ptr<BSTNode> parent = currentNode->parent_.lock();
				parent->ReplaceChild(currentNode, currentNode->left_);
				size_--; assert(size_ >= 0);
			} else {
				currentNode->key_ = DeleteMin(currentNode);
			}
		}
		currentNode = (key < currentNode->key_) ?
			currentNode->left_ : currentNode->right_;
	}

	// update height of current node
	currentNode->height_ = 1 + max(height(currentNode->left_), height(currentNode->right_));

	// Update balance factor of this ancestor's node
	int currentNodeBalance = getBalance(currentNode);

	// Check if unbalanced
	// Left Left Case
  if (currentNodeBalance > 1 && getBalance(currentNode->left_) >= 0)
      rightRotate(currentNode);

  // Right Right Case
  if (currentNodeBalance < -1 && getBalance(currentNode->right_) <= 0)
      leftRotate(currentNode);

  // Left Right Case
  if (currentNodeBalance > 1 && getBalance(currentNode->left_) < 0) {
      currentNode->left_ =  leftRotate(currentNode->left_);
      rightRotate(currentNode);
  }

  // Right Left Case
  if (currentNodeBalance < -1 && getBalance(currentNode->right_) > 0) {
      currentNode->right_ = rightRotate(currentNode->right_);
      leftRotate(currentNode);
  }
	return false;
}

int AVLCommands::DeleteMin() {
	return DeleteMin(root_);
}


void AVLCommands::DeleteLeaf(std::shared_ptr<BSTNode> currentNode) {
	std::shared_ptr<BSTNode> parent = currentNode->parent_.lock();
	if (parent == nullptr) {
		// Delete root
		root_ = nullptr;
		size_--; assert(size_ == 0);
	} else {
		if (parent->right_ == currentNode) {
			parent->right_ = nullptr;
		} else if (parent->left_ == currentNode) {
			parent->left_ = nullptr;
		} else {
			std::cerr << "BST::DeleteLeaf Error: inconsistent state\n";
		}
		size_--; assert(size_ >= 0);
	}
}

int AVLCommands::DeleteMin(std::shared_ptr<BSTNode> currentNode) {
	std::shared_ptr<BSTNode> lastNode = nullptr;
	while (currentNode != nullptr) {
		lastNode = currentNode;
		currentNode = currentNode->left_;
	}
	int result = lastNode->key_;
	std::shared_ptr<BSTNode> parent = lastNode->parent_.lock();
	if (parent == nullptr) {
		// lastNode is root
		if (lastNode->right_ != nullptr) {
			root_ = lastNode->right_;
			lastNode->right_->parent_.reset();
		} else {
			root_ = nullptr;
		}
	} else {
		// lastNode under the root
		if (lastNode->right_ != nullptr) {
			parent->left_ = lastNode->right_;
			lastNode->right_->parent_ = parent;
		} else {
			parent->left_ = nullptr;
		}
  }
	size_--; assert(size_ >= 0);
	return result;
}

size_t AVLCommands::size() const {
	return size_;
}

bool AVLCommands::empty() const {
	return size_ == 0;
}

bool AVLCommands::Find(int key) const {
	std::shared_ptr<BSTNode> currentNode = root_;
	while (currentNode != nullptr) {
		if (currentNode->key_ == key) {
			return true;
		}
		currentNode = (key < currentNode->key_) ?
			currentNode->left_ : currentNode->right_;
	}
	return false;
}

std::string AVLCommands::JSON() const {
	nlohmann::json result;
	std::queue< std::shared_ptr<BSTNode> > nodes;
	if (root_ != nullptr) {
		result["root"] = root_->key_;
		nodes.push(root_);
		while (!nodes.empty()) {
			auto v = nodes.front();
			nodes.pop();
			std::string key = std::to_string(v->key_);
			if (v->left_ != nullptr) {
				result[key]["left"] = v->left_->key_;
				nodes.push(v->left_);
			}
			if (v->right_ != nullptr) {
				result[key]["right"] = v->right_->key_;
				nodes.push(v->right_);
			}
			if (v->parent_.lock() != nullptr) {
				result[key]["parent"] = v->parent_.lock()->key_;
			} else {
				result[key]["root"] = true;
			}
		}
	}
	result["size"] = size_;
	return result.dump(2) + "\n";
}