#ifndef __AST_HASHTABLE_H
#define __AST_HASHTABLE_H
#include <assert.h>
#include <stdlib.h>
//#include <ext/hash_map>
#include <map>
#include <sstream>
#include <math.h>
#include <string.h>
#include "AST/AST"
#include "AST/Symbol"
#include "FFIs/Allocators"

namespace AST {

struct hashstr {
	unsigned long operator()(const char* str) const {
	        unsigned long hash = 5381;
	        int c;
		while ((c = *str++))
			hash = ((hash << 5) + hash) ^ c; /* hash * 33 ^ c */
		return hash;
	}
};
struct eqstr {
	bool operator()(const char* s1, const char* s2) const {
		return strcmp(s1, s2) == 0;
	}
};
struct ltstr {
	bool operator()(const char* s1, const char* s2) const {
		return strcmp(s1, s2) < 0;
	}
};

////typedef std::unordered_map<const char*, AST::NodeT, __gnu_cxx::hash<const char*>, eqstr, gc_allocator<std::pair<const char*, AST::NodeT> > > RawHashtable;
////typedef __gnu_cxx::hash_map<const char*, AST::NodeT, __gnu_cxx::hash<const char*>, eqstr, gc_allocator<std::pair<const char*, AST::NodeT> > > RawHashtable;
//typedef std::map<const char*, AST::NodeT, ltstr, gc_allocator<std::pair<const char*, AST::NodeT> > > RawHashtable;
//// has no allocator: typedef khmap_t<const char*, AST::NodeT, khashf_t, khasheq_t, gc_allocator<std::pair<const char*, AST::NodeT> > > RawHashtable;
/*
static AST::NodeT listFromHashtable(Hashtable::const_iterator iter, Hashtable::const_iterator endIter) {
	if(iter == endIter)
		return(NULL);
	else {
		++iter;
		return(AST::makeCons(AST::symbolFromStr(iter->first), listFromHashtable(iter, endIter)));
	}
}
*/
typedef enum {
	HS_FREE,
	HS_OCCUPIED,
	HS_FREE_AGAIN,
} HashtableEntryState;
template<typename K, typename V>
struct HashtableEntry {
	HashtableEntryState state;
	K first; // key. Idiotic name because of interface compability.
	V second; // value. Idiotic name because of interface compability.
};
/* Key Value Hasher Comparator */
template<typename K, typename V, typename H, typename C>
class RawHashtable : public AST::Node {
private:
	HashtableEntry<K,V>* entries; /* or std::vector, for that matter */
	int capacity;
	int count;
	inline unsigned int hash(const K& k) const {
		return (unsigned int) H()(k);
	}
	inline struct HashtableEntry<K,V>* findEntry(const K& key) const {
		if(capacity == 0)
			return(NULL);
		int index = hash(key) % capacity;
		struct HashtableEntry<K,V>* entry = &entries[index];
		if(entry->state == HS_FREE)
			return(NULL);
		if(entry->state != HS_OCCUPIED || !C()(entry->first, key)) {
			int c;
			for(c = 0; c < capacity; ++c) {
				++index;
				if(index >= capacity)
					index = 0;
				entry = &entries[index];
				if(entry->state == HS_FREE)
					return(NULL);
				if(C()(entry->first, key))
					break;
			}
		}
		bool B_matches = C()(entry->first, key);
		return(B_matches ? entry : NULL);
	}
	void growTo(int count) {
		if(count > this->capacity) {
			HashtableEntry<K,V>* oldEntries = this->entries;
			int oldCapacity = this->capacity;
			capacity = 1 << ((int)log2(count) + 1); // FIXME use primes or something
			this->entries = new (UseGC) HashtableEntry<K,V>[capacity]; // and zeroed out
			for(int i = 0; i < capacity; ++i) {
				this->entries[i].state = HS_FREE;
			}
			this->capacity = capacity;
			for(int i = 0; i < oldCapacity; ++i) {
				struct HashtableEntry<K,V>* entry = &oldEntries[i];
				if(entry->state == HS_OCCUPIED)
					put(entry->first, entry->second);
			}
		}
	}
	struct HashtableEntry<K,V>* actualPut(const K& key, const V& value) {
		struct HashtableEntry<K,V>* entry = findEntry(key);
		if(!entry) {
			growTo(count + 1);
			int index = hash(key) % capacity;
			entry = &entries[index];
			if(entry->state == HS_OCCUPIED) {
				int c;
				for(c = 0; c < capacity; ++c) {
					++index;
					if(index >= capacity)
						index = 0;
					entry = &entries[index];
					if(entry->state != HS_OCCUPIED)
						break;
				}
				if(c == capacity) {
					/* oops. completely full. This shouldn't happen */
					abort();
				}
			}
			assert(entry->state != HS_OCCUPIED);
			++count;
		}
		entry->state = HS_OCCUPIED;
		entry->first = key;
		entry->second = value;
		// = HashtableEntry<K, V>(key, value);
		return(entry);
	}
public:
	void clear(void) {
		entries = NULL;
		capacity = 0;
		count = 0;
	}
	RawHashtable(void) {
		clear();
	}
	size_t size(void) const {
		return(count);
	}
	class const_iterator {
	private:
		HashtableEntry<K,V>* entry;
		int remainder;
	public:
		const_iterator(HashtableEntry<K,V>* entry, int remainder) :
			entry(entry),
			remainder(remainder)
		{
		}
		inline void operator++(void) {
			assert(remainder > 0);
			for(++entry, --remainder; remainder > 0 && entry->state != HS_OCCUPIED; ++entry, --remainder)
				;
		}
		inline std::pair<K, V> operator*(void) const {
			return(std::pair<K, V>(entry->first, entry->second));
		}
		inline HashtableEntry<K,V>* operator->(void) const {
			return(entry);
		}
		inline bool operator==(const const_iterator& b) const {
			if(this == &b)
				return(true);
			else if(entry == b.entry)
				return(true);
			else
				return(false);
		}
		inline bool operator!=(const const_iterator& b) const {
			return(!operator==(b));
		}
	};
	inline const_iterator begin(void) const {
		int i;
		for(i = 0; i < capacity && entries[i].state != HS_OCCUPIED; ++i)
			;
		return(const_iterator(&entries[i], capacity - i));
	}
	inline const_iterator end(void) const {
		return(const_iterator(&entries[capacity], 0));
	}
	inline const_iterator find(const K& key) const {
		struct HashtableEntry<K,V>* entry = findEntry(key);
		if(entry) {
			return(const_iterator(entry, capacity - (entry - entries)));
		} else 
			return(end());
	}
	inline void put(const K& key, const V& value) {
		(void) actualPut(key, value);
	}
	inline bool empty() const {
		return(count == 0);
	}
	inline bool containsKeyP(const K& key) const {
		return(findEntry(key) != NULL);
	}
	inline V get(const K& key) const {
		struct HashtableEntry<K,V>* entry = findEntry(key);
		assert(entry);
		return entry->second;
	}
	inline V& operator[](const K& key) {
		struct HashtableEntry<K,V>* entry = findEntry(key);
		if(!entry) {
			V value = 0;
			entry = actualPut(key, value);
		}
		return entry->second;
	}
	inline const V& operator[](const K& key) const {
		return(get(key));
	}
	inline void removeByKey(const K& key) {
		struct HashtableEntry<K,V>* entry = findEntry(key);
		if(entry)
			entry->state = HS_FREE_AGAIN;
		//  TODO shrink
	}
	virtual std::string toString(void) const {
		std::stringstream sst;
		for(const_iterator iter = begin(); iter != end(); ++iter) {
			sst << '[' << iter->first << ", " << str(iter->second) << "] ";
		}
		return(sst.str());
	}
};
typedef RawHashtable<const char*, AST::NodeT, hashstr, eqstr> Hashtable;

#ifdef CX11
class Hashtable : public RawHashtable, public AST::Node {
public:
};
#endif

};
#endif /* ndef __AST_HASHTABLE_H */