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

#include "dictionary.h"

int const MAX = 100;

template <typename K, typename V>
class ArrayDictionary : public Dictionary<K, V>{
private:
	KeyValuePair<K, V> a[MAX];
	int n;
public:
	ArrayDictionary() : n(0) {}

	// O(log n)
	V* search(K const& key) {
		int left = 0, right = n - 1;
		// можем да проверим дали a[left].key > key или a[right].key < key
		while (left <= right) {
			int mid = (left + right) / 2;
			if (key == a[mid].key)
				return &a[mid].value;
			if (key < a[mid].key)
				right = mid - 1;
			else
				left = mid + 1;
		}
		// left > right
		return NULL;
	}

	// O(n)
	bool add(K const& key, V const& value) {
		if (n == MAX)
			return false;
		int i = 0;
		while (i < n && key > a[i].key)
			i++;
		// a[i-1].key < key <= a[i].key || i == 0 || i == n
		// key трябва да стои на позиция i
		// и да разместим останалите с една позиция надясно
		if (i < n && key == a[i].key)
			// вече го има!
			return false;
		// key < a[i].key || i == n
		for(int j = n - 1; j >= i; j--)
			a[j+1] = a[j];
		// j == i - 1
		a[i].key = key;
		a[i].value = value;
		n++;
		return true;
	}

	// O(n)
	bool remove(K const& key, V& value) {
		if (n == 0)
			return false;
		int i = 0;
		while (i < n && key > a[i].key)
			i++;
		// a[i-1].key < key <= a[i].key || i == 0 || i == n
		// key би трябвало да стои на позиция i
		// и да разместим останалите с една позиция наляво
		if (key < a[i].key)
			// въобще го няма
			return false;
		// key == a[i].key
		value = a[i].value;
		for(int j = i; j < n - 1; j++)
			a[j] = a[j+1];
		n--;
		return true;
	}

	LinkedList<K> keys() const {
		LinkedList<K> result;
		for(int i = 0; i < n; i++)
			result.toEnd(a[i].key);
		return result;
	}

};