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

#include <iostream>
using namespace std;

#include "dictionary.h"


// O(n)
template <typename T, typename I>
I member(T const& x, List<T, I> const& l) {
	I it = l.begin();
	while (it && *it != x)
		++it;
	return it;
}

template <typename K, typename V>
class ListDictionary : LinkedList<KeyValuePair<K, V> >,
						public Dictionary<K, V>
{
public:
	typedef LinkedListIterator<KeyValuePair<K, V> > I;

	// O(n)
	V* search(K const& key) {
		I it = member(KeyValuePair<K, V>(key), *this);
		if (!it)
			return NULL;
		return &(*it).value;
	}

	// O(1)
	// O(n), ако има проверка за повторение
	bool add(K const& key, V const& value) {
		this->toEnd(KeyValuePair<K,V>(key,value));
		// хубаво е да направим проверка за повторение на ключа
		return true;
	}

	// O(n)
	bool remove(K const& key, V& value) {
		I it = member(KeyValuePair<K, V>(key), *this);
		if (!it)
			return false;
		KeyValuePair<K, V> kvp;
		this->deleteAt(kvp, it);
		value = kvp.value;
		return true;
	}

	// O(n)
	LinkedList<K> keys() const {
		LinkedList<K> result;
		for(I it = this->begin(); it; ++it)
			result.toEnd((*it).key);
		return result;
	}
};