/*
 * Key needs to have equality, comparison (just less than)
 * Key has to be able to be printed
 * Value just gets retrieved and printed, and a default constructor
 */
#include<iostream>
template<class keytype, class valuetype>
class kv_rbtree {
	struct node {
		keytype key;
		valuetype value;
		node *left = nullptr, *right = nullptr;
	};
	node *root = nullptr;
	public:
	valuetype& operator[](const keytype& key){ // Iterative, so O(log(n)) time and O(1) memory
		if(!root){
			root = new node;
			root->key = key;
			return root->value;
		}
		// do we care if the root has the key
		// or do we want something more general?
		node *place = root;
		while(true){
			if(place->key == key)
				return place->value; // c++ will handle the reference
											// Should we go right or left?
			node **next_place = &(place->right);
			if(key < place->key)
				next_place = &(place->left);
			if(!*next_place){
				*next_place = new node;
				(*next_place)->key = key;
				return (*next_place)->value;
			}
			place = *next_place;
		}
	}

	void print_inorder(){ // Recursive, so O(log(n) time and O(log(n)) memory
		print_inorder_r(root);
	}
	void print_inorder_r(node *place){
		if(!place)
			return;
		print_inorder_r(place->left);
		std::cout << " (" << place->key << ", " << place->value << ") "; // Avoid cout in header files
		print_inorder_r(place->right);
	}

	bool contains(const keytype &key){
		node *place = root;
		while(true){
			if(!place)
				return false;
			if(place->key == key)
				return true;
			if(key < place->key)
				place = place->left;
			else
				place = place->right;
		}
	}

};