/*
 * tree_dictionary.cpp
 *
 *  Created on: 23.01.2014
 *      Author: trifon
 */

#include "dictionary.h"
#include "avl_tree.cpp"

template <typename K, typename V>
class TreeDictionary : AVLTree<KeyValuePair<K, V> >,
						public Dictionary<K, V> {
private:
	void collectKeys(LinkedList<K>& keys,
			BinaryTreeIterator<AVLElement<
			KeyValuePair<K, V> > > it) const {
		if (!it)
			return;
		collectKeys(keys, ++it);
		keys.toEnd((*it).data.key);
		collectKeys(keys, it++);
	}

public:
	// O(log n)
	V* search(K const& key) {
		KeyValuePair<K, V> kvp(key);
		KeyValuePair<K, V>* result = AVLTree<KeyValuePair<K, V> >::search(kvp);
		if (!result)
			return NULL;
		return &result->value;
	}

	// O(log n)
	bool add(K const& key, V const& value) {
		KeyValuePair<K, V> kvp(key, value);
		return this->insert(kvp);
	}

	// O(log n)
	bool remove(K const& key, V& value) {
		KeyValuePair<K, V> kvp(key, value);
		return AVLTree<KeyValuePair<K, V> >::remove(kvp);
	}

	// O(n)
	LinkedList<K> keys() const {
		LinkedList<K> result;
		collectKeys(result, this->iterator());
		return result;
	}
};