Untitled

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.
	if(m_size == 1){
		if(m_root -> m_key != key) throw nonexistent_key();
		std::unique_ptr<V> extracted_value = std::move(m_root -> m_value);
		m_root = nullptr;
		m_size--;
		return extracted_value;
	}
	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);
				}
			}
		}
	}
	std::unique_ptr<V> extracted_value = std::move(current->m_value);
	// m_root = current;

	// Remove the node
	/*
	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;
	}
	*/


	std::shared_ptr<splay_tree_node> x = current;

	auto successor = x;
	if(successor -> m_right){
		successor = successor -> m_right;
		while (successor->m_left) {
			successor = successor->m_left;
		}
	}
	else{
		successor = nullptr;
	}


	if(successor){
		// std :: cout << "Successor Key: " << successor -> m_key << std :: endl;
        successor->m_left = x->m_left;
        if(x -> m_left) x->m_left->m_parent = successor;
        if (x->m_right != successor){
			successor -> m_parent.lock() -> m_left = successor -> m_right;
			if(successor -> m_right) successor -> m_right -> m_parent = successor -> m_parent;
			successor->m_right = x->m_right;
			if(x -> m_right) x->m_right->m_parent = successor;
		}
		successor -> m_parent.reset();
		m_root = successor;
	}
	else{
		m_root = x->m_left;
        if (m_root) m_root->m_parent.reset();
	}

	m_size--;
	return extracted_value;
}