// © Copyright 1997. Joseph Bergin. All rights reserved.

#ifndef HASHTABLE_H
#define HASHTABLE_H

#include <fstream.h>
#include <list.h>
#include <vector.h>
#include <function.h>
#include <algo.h>

#define ht_debug 1

template <class T, class HASHER, class EQUAL>
class hash_table
{public:
	typedef T key_type;
	typedef list<key_type >::iterator iterator;
	typedef list<key_type >::const_iterator const_iterator;
	
	typedef HASHER hash_type;
	typedef EQUAL equal_type;
	
	hash_table()
	:	maxbuckets(1), 
		halfbuckets(0),
		currentbuckets(0), 
		index(), 
		buckets(), 
		compare(EQUAL()),
		hasher(HASHER())
	{	index.push_back(buckets.end());
	#if ht_debug
		dumpfile.open ("hash.dump");
	#endif
	}
	
	long size()const{ return buckets.size();}
	bool empty()const{return buckets.empty();}
	iterator begin(){return buckets.begin();}
	iterator end(){return buckets.end();}
	const_iterator begin()const{return buckets.begin();}
	const_iterator end() const{return buckets.end();}

protected:	

	iterator insertit(key_type t, unsigned long i) // insert t in bucket i
	{	unsigned long next = i+1;	
		iterator where = buckets.insert(index[next], t);
		while(index[i] == index[next])
			index[i--] = where;
		return where;
	}
	
public:

	iterator insert(key_type t)
	{	expand();
		unsigned long b = hash(t);
		unsigned long w = b+1;
		iterator where = buckets.insert(index[w], t);
		// Inserts "before" the beginning of the next bucket--
		// i.e. at the end of bucket b.  
		while(index[b] == index[w]) // Adjust for empty buckets.  
			index[b--] = where;
		return where;
	}

/*	iterator insert(key_type t)
	{	expand();
		iterator where = insertit(t, hash(t));
	#if ht_debug
		dump();
	#endif
		return where;
	}
*/	
/*	int erase(key_type t)
	{	int result = 0;
		unsigned long where = hash(t);
		pair<iterator, bool> loc = find(t);
		while(loc.second)
		{	while(index[where] == loc.first)
				++index[where--];
			buckets.erase(loc.first);
			result++;
			loc = find(t);
		}
	#if ht_debug
		dump();
	#endif
		return result;
	}
*/
int erase(key_type t)
{	int result = 0;
	unsigned long where = hash(t);
	pair<iterator, bool> loc = find(t);
	while(loc.second)
	{	int i = where;
		while(index[i] == loc.first)
			++index[i--];
		buckets.erase(loc.first);
		result++;
		loc = find(t);
	}
	#if ht_debug
		dump();
	#endif
	return result;
}
	
	hash_type hash_function(){return hasher;}
	equal_type comparer(){return compare;}
	
	// The next two function must be the same except for the returned iterator type. 
	pair<iterator, bool> find(const key_type& t) 
	{	if(buckets.size() > 0)
		{	unsigned long bucket = hash(t);
			iterator where = 
				::find_if(index[bucket], index[bucket+1], bind1st(compare,t) );
			if(where != index[bucket+1]) 
				return pair<iterator, bool>(where, true);
		}
		return pair<iterator, bool>(index[currentbuckets], false);
	}
	
	pair<const_iterator, bool> find(const key_type& t) const
	{	if(buckets.size() > 0)
		{	unsigned long bucket = hash(t);
			const_iterator where = 
				::find_if(index[bucket], index[bucket+1], bind1st(compare,t) );
			if(where != index[bucket+1]) 
				return pair<const_iterator, bool>(where, true);
		}
		return pair<const_iterator, bool>(index[currentbuckets], false);
	}

	#if ht_debug
	ofstream dumpfile;
	
	void dump()
	{	dumpfile << "CB: "<<currentbuckets<<"  MB: "<<maxbuckets<<endl;
		for(int i = 0; i < currentbuckets; ++i)
		{	for(iterator j = index[i]; j != index[i+1]; ++j)
				dumpfile << *j << ' ';
			dumpfile << endl;
		}
		dumpfile <<"--> ";
		for(iterator i = buckets.begin(); i!= buckets.end(); ++i)
			dumpfile << *i<<' ';
			dumpfile << endl;
	}
	#endif
	
private:
	unsigned long maxbuckets;
	unsigned long halfbuckets; //(always half of maxbuckets)
	unsigned long currentbuckets;
	
//	typedef allocator<T> allocT;
//	typedef allocator<iterator > allocListIter;
	
	vector<iterator > index;
	list<T> buckets;
//	vector<iterator, allocListIter > index;
//	list<T, allocT> buckets;
	hash_type hasher; 
	equal_type compare;
	
	unsigned long hash(const key_type& t) const
	{	unsigned long result = hasher(t);
		result %= maxbuckets;
		if (result >= currentbuckets) result -= halfbuckets;
	#if ht_debug
		dumpfile <<"< "<<t<<" hash "<<result<<'>'<<endl;
	#endif
		return result;
	}
	
	void expand()
	{	currentbuckets++;	
		index.push_back(buckets.end());
		if(currentbuckets > maxbuckets){ halfbuckets = maxbuckets; maxbuckets <<= 1;}
		unsigned long buddy = currentbuckets -1 - halfbuckets;
	#if ht_debug
		dumpfile << "buddy = "<< buddy<<endl;
	#endif
		for(iterator start = index[buddy]; start != index[buddy+1];)
		{	iterator next = start;
		  	++next;
			if(hash(*start) != buddy) // must move this item
		  	{		  		if(next == index[currentbuckets-1]) // can just adjust pointers
		  		{	--index[currentbuckets-1];
		  			unsigned long adjust = currentbuckets-2;
		  			while(index[adjust] == next)
		  				--index[adjust--];
		  			return;
		  		}
		  		else // must actually move it
		  		{	unsigned long k = buddy;
	  				while(start == index[k])
	  					++index[k--];
					buckets.splice(index[currentbuckets-1], buckets, start);
					iterator temp = index[currentbuckets-1];
					k = currentbuckets - 1;
					while(index[k] == temp)
						--index[k--];
		  		}
		  		start = next;
		 	}
		 	else ++start;
		 }
	}
};

#endif