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

#include "dictionary.h"

template <typename K, typename V>
struct Pair {
	K key;
	V value;
};

template <typename K=int, typename V=int>
class ListDictionary : public Dictionary<K, V>
{
private:
	LinkedList<Pair<K, V> > d;

public:
	void print() const {
		d.print();
	}

	V* search(K const& key) const {
		LinkedListIterator<Pair<K,V> > it = d.iteratorBegin();
		while (it && (*it).key < key)
			++it;
		if (!it || (*it).key > key)
			return NULL;
		return &(*it).value;
	}

	bool add(K const& key, V const& value)
	{
		LinkedListIterator<Pair<K, V> > it = d.iteratorBegin(),
										itp = it++;
		Pair<K, V> p = { key, value };
		if (!itp)
		{
			d.toEnd(p);
			return true;
		}
		if ((*itp).key == key)
			return false;
		if ((*itp).key > key)
		{
			d.insertBefore(p, itp);
			return true;
		}
		while (it && (*it).key < key)
			itp = it++;
		// !it || (*it).key >= key
		if (it && (*it).key == key)
			return false;
		d.insertAfter(p, itp);
		return true;
	}

	bool remove(K const& key) {
		LinkedListIterator<Pair<K, V> > it = d.iteratorBegin(),
										itp = it++;
		if (!itp || (*itp).key > key)
			return false;

		Pair<K, V> temp;
		if ((*itp).key == key)
		{
			d.deleteAt(temp, itp);
			return true;
		}
		while (it && (*it).key < key)
			itp = it++;
		// !it || (*it).key >= key
		if (!it || (*it).key > key)
			return false;
		d.deleteAfter(temp, itp);
		return true;
	}

	LinkedList<K> keys() const {
		LinkedList<K> k;
		for(LinkedListIterator<Pair <K, V> > it = d.iteratorBegin();
			it; ++it)
			k.toEnd((*it).key);
		return k;
	}

	LinkedList<V> values() const {
		LinkedList<V> v;
		for(LinkedListIterator<Pair <K, V> > it = d.iteratorBegin();
			it; ++it)
			v.toEnd((*it).value);
		return v;
	}


};

template <typename K, typename V>
ostream& operator<<(ostream& os, Pair<K, V> const& p)
{
	return os << "(" << p.key << ", " << p.value << ")";
}