#ifndef HashTable_H
#define HashTable_H

#include<cstring>


template<class Key, class Value>
class HashTable {
	struct TableEntry {
		Key k;
		Value v;
		bool used;
	};
	class HTIterator {
		size_t entries_left;
		struct TableEntry *table;
		public:
		HTIterator(TableEntry *t, size_t el) {
			table = t;
			entries_left = el;
			while(!table[entries_left-1].used && entries_left > 0)
				entries_left--;
		}
		HTIterator operator++(){
			if(entries_left == 0)
				return *this;
			entries_left--;
			if(!entries_left)
				return *this;
			while(!table[entries_left-1].used){

				entries_left--;
				if(!entries_left)
					return *this;
			}
			return *this;
		}
		bool operator!=(const HTIterator& other){
			return other.entries_left != entries_left;
		}	
		Key& operator*(){
			return table[entries_left-1].k;
		}
	};
	struct TableEntry *table;
	size_t capacity = 10;
	size_t items = 0;
	public:
	HashTable(){
		table = (struct TableEntry*)malloc(sizeof(struct TableEntry) * 10);
		memset(table, 0, (sizeof(struct TableEntry) * 10));
	}
	HashTable(size_t initial_capacity): capacity(initial_capacity) {
		table = (struct TableEntry*)malloc(sizeof(struct TableEntry) * capacity);
		memset(table, 0, (sizeof(struct TableEntry) * capacity));
	}

	size_t get_items(){
		return items;
	}

	HTIterator begin(){
		return HTIterator(table, capacity); 
	}

	HTIterator end(){
		return HTIterator(table, 0);
	}

	bool contains(Key k){
		size_t hv = data_hash(k) % capacity;
		// Retreive an existing entry from the table
		while(table[hv].used){
			if(table[hv].k == k)
				return true;
			hv++;
			if(hv >= capacity)
				hv -= capacity;
			// TODO What if the table is actually all the way full?
		}
		return false;
	}

	Value& operator[] (Key k){
		size_t hv = data_hash(k) % capacity;
		// Retreive an existing entry from the table
		while(table[hv].used){
			if(table[hv].k == k)
				return table[hv].v;
			hv++;
			if(hv >= capacity)
				hv -= capacity;
			// TODO What if the table is actually all the way full?
			// Answer:  It's not.  We resize it when it's half full
		}

		// If we're here, then we didn't find anything
		// The user wants to add it!
		// See how full the table is
		if(items > capacity/2){
			// Resize the table
			size_t new_capacity = capacity*2;
			struct TableEntry *new_table = (struct TableEntry*)malloc(sizeof(struct TableEntry) * new_capacity);
			memset(new_table, 0, (sizeof(struct TableEntry) * new_capacity));

			for(size_t i = 0; i < capacity; i++){ // each item in the old table
				if(!table[i].used)
					continue;
				//Find the spot for a key an existing entry from the table
				//The next few lines insert a new value v at position k
				Key k = table[i].k; // The one from the old table
				Value v = table[i].v; // The one from the old table, again
				size_t hv = data_hash(k) % new_capacity;
				while(new_table[hv].used){
					hv++;
					if(hv >= new_capacity)
						hv -= new_capacity;
				}
				new_table[hv] = table[i];
			}
			free(table);
			table = new_table;
			capacity = new_capacity;
		}

		// Add a new entry to the table (as in, we didn't find it)
		table[hv].k = k;
		table[hv].used = true;
		items++;
		return table[hv].v;
	}

	void chain_fixer(Key k, size_t pos){
		size_t hv = data_hash(k) % capacity; // Should we have saved this?
		ssize_t replacement = -1;
		size_t rsearch_pos = pos + 1;
		for(; table[rsearch_pos].used; rsearch_pos++){
			if(hv == data_hash(table[rsearch_pos].k) % capacity) { // If this goes in the same place as what we're deleting
				replacement = rsearch_pos;
			}
		}
		if(replacement != -1){
			table[pos] = table[replacement];
			table[replacement].used = false;
		}
	}

	void remove(Key k){
		size_t hv = data_hash(k) % capacity;
		// Retreive an existing entry from the table
		while(table[hv].used){
			if(table[hv].k == k) {
				table[hv].used = false;
				// Maybe we should call the destructor?
				chain_fixer(k, hv);
				items--;
				break;
			}
			hv++;
			if(hv >= capacity)
				hv -= capacity;
		}
	}

	void debug_info(){
		for(int i = 0; i < capacity; i++) {
			if(table[i].used)
				cout << i << ": " << table[i].k << endl;
			else
				cout << i << ": " << "unused\n";
		}
	}

	~HashTable(){
		free(table);
	}
	// Expected use:  our_hash_table[key] = value
	// Like this:  our_hash_table["fish"] = 400;
};
#endif