#ifndef MAP_HEADER
#define MAP_HEADER

#include "Vector.h"

template <class Key, class T> class Map
{
public:
	struct Pair
	{
		Key first;
		T second;
	};

private:
	Vector<Pair> values;
	
public:
	class Iterator
	{
	typedef typename Vector<Pair>::Iterator VectorIterator;
	friend class Map;
	private:
		VectorIterator i;
		Iterator(VectorIterator iterator) : i(iterator) {}
	public:
		Iterator(const Iterator &iterator) : i(iterator.i) {}
		
		bool operator == (const Iterator &iterator) const {return this->i == iterator.i;}
		bool operator != (const Iterator &iterator) const {return this->i != iterator.i;}
		Iterator& operator ++ () {i++; return *this;}
		Iterator& operator ++ (int) {i++; return *this;}
		T& operator * () const {return (*i).second;}
		Pair* operator -> () const {return &(*i);}
	};
	
public:
	Iterator Begin() {return values.Begin();}
	Iterator End() {return values.End();}
	Iterator Find(Key key)
	{
		/*TODO: Binary Search*/
		for (Iterator i = Begin(); i != End(); i++)
			if (i->first == key) return i;	
			
		return End();
	}
	
	T& operator [] (Key key);
};

template<class Key, class T> T& Map<Key, T>::operator [] (Key key)
{
	Iterator iterator = Find(key);
	if (iterator != End()) return iterator->second;
	
	Pair pair;
	pair.first = key;
	values.PushBack(pair);	
	typename Vector<Pair>::SizeType i = values.GetSize() - 1;
	while (i > 0 && values[i].first < values[i - 1].first)
	{
		values.Swap(i, i - 1);
		i--;
	}
	
	return values[i].second;
}

#endif