Untitled

#pragma once
#include <sstream>
#include <exception>
#include <memory>
namespace cs251 {

// Custom exception classes
class duplicate_key : public std::runtime_error {
	public: duplicate_key() : std::runtime_error("Duplicate key!") {} };
class nonexistent_key : public std::runtime_error {
	public: nonexistent_key() : std::runtime_error("Key does not exist!") {} };
class empty_tree : public std::runtime_error {
	public: empty_tree() : std::runtime_error("Tree is empty!") {} };

template <typename K, typename V>
class splay_tree {
public:
	struct splay_tree_node {
		// Pointer to the left child
		std::shared_ptr<splay_tree_node> m_left {};
		// Pointer to the right child
		std::shared_ptr<splay_tree_node> m_right {};
		// Weak pointer to the parent
		std::weak_ptr<splay_tree_node> m_parent {};

		// The key of this element
		K m_key {};
		// Pointer to the value of this element
		std::unique_ptr<V> m_value {};
	};

	// Return a pointer to the root of the tree
	std::shared_ptr<splay_tree_node> get_root() const;

	// Default constructor - create an empty splay tree
	splay_tree();

	// Insert the key/value pair into the tree, if the key doesn't already exist
	// Throw duplicate_key if the key already exists
	void insert(const K& key, std::unique_ptr<V> value);
	// Return a const reference to the value associated with the given key
	// Throw nonexistent_key if the key is not in the splay tree
	const std::unique_ptr<V>& peek(const K& key);
	// Remove and return the key-value pair associated with the given key
	// Throw nonexistent_key if the key is not in the splay tree
	std::unique_ptr<V> extract(const K& key);

	// Return the minimum key in the splay tree, and splay the node
	// Throw empty_tree if the tree is empty
	K minimum_key();
	// Return the maximum key in the splay tree, and splay the node
	// Throw empty_tree if the tree is empty
	K maximum_key();

	// Return the current number of elements in the splay tree
	bool empty() const;
	// Return whether the splay tree is currently empty
	size_t size() const;

private:
	// Pointer to the root node of the splay tree
	std::shared_ptr<splay_tree_node> m_root {};

	// TODO: Add any additional methods or variables here
    size_t m_size = 0;
    void left_rotate(std::shared_ptr<splay_tree_node>& x);
    void right_rotate(std::shared_ptr<splay_tree_node>& x);
};

template <typename K, typename V>
std::shared_ptr<typename splay_tree<K,V>::splay_tree_node> splay_tree<K,V>::get_root() const {
	return m_root;
}

template <typename K, typename V>
splay_tree<K,V>::splay_tree() {
	// TODO: Remove the following line and add your implementation here.
	throw std::logic_error("splay_tree::" + std::string(__FUNCTION__) + "() not implemented");
}

template <typename K, typename V>
void splay_tree<K,V>::insert(const K& key, std::unique_ptr<V> value) {
	// TODO: Remove the following line and add your implementation here.
	if (!m_root) {
		m_root = std::make_shared<splay_tree_node>();
		m_root->m_key = key;
		m_root->m_value = std::move(value);
		m_size++;
		return;
	}

	std::shared_ptr<splay_tree_node> current = m_root;
	std::shared_ptr<splay_tree_node> parent;

	while (current) {
		parent = current;
		if (key < current->m_key)
			current = current->m_left;
		else if (key > current->m_key)
			current = current->m_right;
		else
			throw duplicate_key();
	}

	current = std::make_shared<splay_tree_node>();
	current->m_key = key;
	current->m_value = std::move(value);
	current->m_parent = parent;

	if (key < parent->m_key)
		parent->m_left = current;
	else
		parent->m_right = current;

	m_size++;
	// Splay the newly inserted node to the root
	while (current->m_parent.lock()) {
		std::shared_ptr<splay_tree_node> parent = current->m_parent.lock();
		std::shared_ptr<splay_tree_node> grandparent = parent->m_parent.lock();

		if (!grandparent) {
			// Zig case
			if (current == parent->m_left)
				right_rotate(parent);
			else
				left_rotate(parent);
		} else {
			if (parent == grandparent->m_left) {
				if (current == parent->m_left) {
					// Zig-Zig case
					right_rotate(grandparent);
					right_rotate(parent);
				} else {
					// Zig-Zag case
					left_rotate(parent);
					right_rotate(grandparent);
				}
			} else {
				if (current == parent->m_right) {
					// Zig-Zig case
					left_rotate(grandparent);
					left_rotate(parent);
				} else {
					// Zig-Zag case
					right_rotate(parent);
					left_rotate(grandparent);
				}
			}
		}
	}
	m_root = current;
}

template <typename K, typename V>
const std::unique_ptr<V>& splay_tree<K,V>::peek(const K& key) {
	// TODO: Remove the following line and add your implementation here.
	std::shared_ptr<splay_tree_node> current = m_root;
	while (current) {
		if (key == current->m_key)
			break;
		else if (key < current->m_key)
			current = current->m_left;
		else
			current = current->m_right;
	}
	if (!current)
		throw nonexistent_key();

	// Splay the found node to the root
	while (current->m_parent.lock()) {
		std::shared_ptr<splay_tree_node> parent = current->m_parent.lock();
		std::shared_ptr<splay_tree_node> grandparent = parent->m_parent.lock();

		if (!grandparent) {
			// Zig case
			if (current == parent->m_left)
				right_rotate(parent);
			else
				left_rotate(parent);
		} else {
			if (parent == grandparent->m_left) {
				if (current == parent->m_left) {
					// Zig-Zig case
					right_rotate(grandparent);
					right_rotate(parent);
				} else {
					// Zig-Zag case
					left_rotate(parent);
					right_rotate(grandparent);
				}
			} else {
				if (current == parent->m_right) {
					// Zig-Zig case
					left_rotate(grandparent);
					left_rotate(parent);
				} else {
					// Zig-Zag case
					right_rotate(parent);
					left_rotate(grandparent);
				}
			}
		}
	}
	m_root = current;
	return current->m_value;
}

template <typename K, typename V>
std::unique_ptr<V> splay_tree<K,V>::extract(const K& key) {
	// TODO: Remove the following line and add your implementation here.
	std::shared_ptr<splay_tree_node> current = m_root;
	while (current) {
		if (key == current->m_key)
			break;
		else if (key < current->m_key)
			current = current->m_left;
		else
			current = current->m_right;
	}
	if (!current)
		throw nonexistent_key();

	// Splay the found node to the root
	while (current->m_parent.lock()) {
		std::shared_ptr<splay_tree_node> parent = current->m_parent.lock();
		std::shared_ptr<splay_tree_node> grandparent = parent->m_parent.lock();

		if (!grandparent) {
			// Zig case
			if (current == parent->m_left)
				right_rotate(parent);
			else
				left_rotate(parent);
		} else {
			if (parent == grandparent->m_left) {
				if (current == parent->m_left) {
					// Zig-Zig case
					right_rotate(grandparent);
					right_rotate(parent);
				} else {
					// Zig-Zag case
					left_rotate(parent);
					right_rotate(grandparent);
				}
			} else {
				if (current == parent->m_right) {
					// Zig-Zig case
					left_rotate(grandparent);
					left_rotate(parent);
				} else {
					// Zig-Zag case
					right_rotate(parent);
					left_rotate(grandparent);
				}
			}
		}
	}
	m_root = current;

	// Remove the node
	std::unique_ptr<V> extracted_value = std::move(current->m_value);
	if (current->m_left)
		current->m_left->m_parent = current->m_parent;
	if (current->m_right)
		current->m_right->m_parent = current->m_parent;
	if (current->m_parent.lock()) {
		if (current == current->m_parent.lock()->m_left)
			current->m_parent.lock()->m_left = nullptr;
		else
			current->m_parent.lock()->m_right = nullptr;
	}
	m_size--;
	return extracted_value;
}

template <typename K, typename V>
K splay_tree<K,V>::minimum_key() {
	// TODO: Remove the following line and add your implementation here.
	if (empty())
		throw empty_tree();

	std::shared_ptr<splay_tree_node> current = m_root;
	while (current->m_left)
		current = current->m_left;

	peek(current->m_key);
	return current->m_key;
}

template <typename K, typename V>
K splay_tree<K,V>::maximum_key() {
	// TODO: Remove the following line and add your implementation here.
	if (empty())
		throw empty_tree();

	std::shared_ptr<splay_tree_node> current = m_root;
	while (current->m_right)
		current = current->m_right;

	peek(current->m_key);
	return current->m_key;
}

template <typename K, typename V>
bool splay_tree<K,V>::empty() const {
	// TODO: Remove the following line and add your implementation here.
	return !m_root;
}

template <typename K, typename V>
size_t splay_tree<K,V>::size() const {
	// TODO: Remove the following line and add your implementation here.
	return m_size;
}
    template <typename K, typename V>
void splay_tree<K,V>::left_rotate(std::shared_ptr<splay_tree_node>& x) {
	// TODO: Add your implementation here.
	td::shared_ptr<splay_tree_node> y = x->m_right;
	if (!y) return;

	x->m_right = y->m_left;
	if (y->m_left)
		y->m_left->m_parent = x;
	y->m_parent = x->m_parent;
	if (!x->m_parent.lock())
		m_root = y;
	else if (x == x->m_parent.lock()->m_left)
		x->m_parent.lock()->m_left = y;
	else
		x->m_parent.lock()->m_right = y;
	y->m_left = x;
	x->m_parent = y;
}
    template <typename K, typename V>
void splay_tree<K,V>::right_rotate(std::shared_ptr<splay_tree_node>& x) {
	// TODO: Add your implementation here.
	std::shared_ptr<splay_tree_node> y = x->m_left;
	if (!y) return;

	x->m_left = y->m_right;
	if (y->m_right)
		y->m_right->m_parent = x;
	y->m_parent = x->m_parent;
	if (!x->m_parent.lock())
		m_root = y;
	else if (x == x->m_parent.lock()->m_right)
		x->m_parent.lock()->m_right = y;
	else
		x->m_parent.lock()->m_left = y;
	y->m_right = x;
	x->m_parent = y;
}

}