#include <utility>
#include <iostream>

/**
 * B+Tree implementation. Note that the tree may not contain duplicate keys!
 *
 * Template parameters:
 * K: Key type.
 *   You may assume that keys can be compared with the < operator
 *   and are copy constructible and copy assignable.
 *   You may NOT use the == or the <= operator on keys, as these might be undefined for a key type!
 * V: Value type. You may assume that values are copy constructible and copy assignable.
 * NODE_SIZE: Number of key-value-pairs in leaves, number of keys in inner nodes.
 *    You may assume that S is >= 1
 *
 */
template<typename K, typename V, unsigned NODE_SIZE = 256>
class BPlusTree{
public:
	typedef K Key;
	typedef V Value;
	typedef BPlusTree<K,V,NODE_SIZE> ThisType;

	/**
	 * Copy assignment not allowed. This makes it easier for you!
	 */
	BPlusTree& operator=(const BPlusTree&other) = delete;


	/**
	 * Copy constructor. Make sure your class is correctly
	 * copy constructible!
	 */
	BPlusTree(const BPlusTree& other){
		//TODO implement
	}

	/**
	 *	Initializes an empty tree
	 */
	BPlusTree(){
		//TODO: implement
	}

	/**
	 *	Inserts a new key value pair <`key`,`value`> into the tree.
	 *	If the `key` already exists in the tree, then this operation
	 *	overwrites the old key value pair with the new one.
	 */
	void insert(Key key, Value value){
		//TODO: implement
	}

	/**
	 * Returns whether the `key` is contained in the tree.
	 */
	bool hasKey(Key key){
		//TODO: implement
		return false;
	}

	/**
	 * Finds the value associated to the `key`. If the `key`
	 * is not present in the tree, then a std::exception must
	 * be thrown.
	 */
	Value find(Key key){
		//TODO: implement
		return Value();
	}

	/**
	 * Splits this tree at `key`, that is, all keys which are
	 * less than `key` are moved into a new tree T which is
	 * returned by the method. This tree retains all keys
	 * which are greater than or equal `key`. Note that splitting
	 * a tree at a key which is not present in the tree must
	 * be possible.
	 *
	 * Make sure that the implementation has a worst case complexity
	 * of O(log n), i.e., simply copying all keys which are less
	 * than `key` will not suffice, as this will be O(n)!
	 *
	 * Example:
	 * This tree contains the keys (2,4,6,8)
	 * splitting it at key 5 results in two trees, one
	 * with keys (2,4) which is returned and
	 * one with (6,8) which is this tree.
	 */
	ThisType split(Key key){
		return ThisType(); //TODO implement!
	}


};
//--------- END OF IMPLEMENTATION ----------





//--------- TEST CODE ------------
typedef BPlusTree<int,int,16> Tree;
bool failed = false;

void fail(std::string message){
	failed = true;
	std::cerr << message << std::endl;
}

void exampleTest(){
	Tree tree;
	tree.insert(5,4);
	if(tree.find(5) != 4) fail("Wrong value for key 5");
}

void yourTests(){
	exampleTest();
	//TODO: Add own tests here!
	//Make sure your tests are reasonable!
	//Make sure your test cases test your implementation thoroughly
	//Especially, make sure to test corner cases!
}


int main(){
	try {
		yourTests();
	} catch (...) {
		std::cerr << "=============== EXCEPTION THROWN! Implementation is buggy! ===============" << std::endl;
	}
	if(failed){
		std::cerr << "=============== TESTS FAILED! Implementation is buggy! ===============" << std::endl;
	} else {
		std::cout << "=============== TESTS PASSED! ===============" << std::endl;
	}
}