// Copyright (C) 2002 Michael Anthony <mike at unlikely dot org>
// Permission to copy, use, modify, sell and distribute this software is
// granted provided this copyright notice appears in all copies.  This
// software is provided "as is" without express or implied warranty, and
// with no claim as to its suitability for any purpose.

#ifndef OHASH_H
#define OHASH_H

#include "nset.h"
#include <hash_map>
#include <stdexcept>

template<typename K, typename D, typename H = hash<K> >
class ohash_iterator;
template<typename K, typename D, typename H = hash<K> >
class ohash_const_iterator;
template<typename K, typename D, typename H = hash<K> >
class ohash_iter_base;

class ohash_full; // exception

// A hash, somewhat, a la STL hash_map, but which uses open addressing
// (you can retrieve elements using an integer index; K/D pairs are
// stored in one big array, not an array of lists).
//
// Since resizing the hash is likely to invalidate the values' indexes,
// resizing is not performed automatically.  Instead, an exception of
// type ohash_full will be thrown when an insert is attempted on a full
// hash.  Note that inserts for an existing key on a full hash will, as
// you might expect, succeed.  If you wish to grow the hash, simply
// call h.resize (h.capacity () + 1).  The hash will grow by a
// substantially greater amount than 1, in fact.  Note, also, that it's
// a good idea to resize well before size == capacity.
template<typename K, typename D, typename H = hash<K> >
class ohash
{
public:
	typedef K key_type;
	typedef D data_type;
	typedef pair<const K,D> value_type;
	typedef H hasher;
	typedef ohash_iterator<K,D,H> iterator;
	typedef ohash_const_iterator<K,D,H> const_iterator;

	static const size_t npos = -1;

	ohash (size_t = 0);
	ohash (const ohash&, size_t = 0);
	~ohash ();
	iterator begin ();
	iterator end ();
	const_iterator begin () const;
	const_iterator end () const;
	size_t size () const;
	bool empty () const;
	void resize (size_t);
	ohash& operator= (const ohash&);
	void swap (ohash&);
	pair<iterator, bool> insert (const value_type&);
	template <typename T>
	void insert (T begin, T end);
	void clear ();
	const_iterator find (const key_type&) const;
	iterator find (const key_type&);
	size_t count (const key_type&) const;
	data_type& operator[] (const key_type&);

	size_t index (const key_type&) const;
		// Return the index of a key or npos if it's not in the hash.
	bool active (size_t) const;
		// Return true iff something is stored at the index given.
	const value_type& slot (size_t) const;
	value_type& slot (size_t);
		// Return the K/D pair stored at the index given.
		// Precondition: something must be stored there.
	size_t capacity () const;
		// Return the number of values the hash can store before being
		// resized.

private:
	friend ohash_iter_base<K,D,H>;

	size_t hash2 (const key_type &k) const;
	const pair<K,D>* get (const key_type&) const;
	pair<pair<K,D>*, bool> put (const key_type&);

	size_t m_size;
	nset<> m_active;
	pair<K,D> *m_data;
	hasher m_hash;
};


class ohash_full : public exception
{
public:
	ohash_full () : exception () {}
	const char* what () const { return "ohash full"; }
};


template<typename K, typename D, typename H>
class ohash_iter_base
{
public:
	pair<K,D>* value () const;
	size_t index () const;
	void next ();
	void prev ();
	int cmp (const ohash_iter_base&) const;

private:
	friend ohash<K,D,H>;

	const ohash<K,D,H> *m_ohash;
	nset<>::const_iterator m_it;
};


template<typename K, typename D, typename H>
class ohash_const_iterator : private ohash_iter_base<K,D,H>
{
public:
	typedef K key_type;
	typedef D data_type;
	typedef pair<const K, D> value_type;

	size_t index () const;
	const value_type& operator* () const;
	const value_type* operator-> () const;
	ohash_const_iterator<K,D,H> operator++ (int);
	ohash_const_iterator<K,D,H>& operator++ ();
	ohash_const_iterator<K,D,H> operator-- (int);
	ohash_const_iterator<K,D,H>& operator-- ();
	bool operator== (const ohash_const_iterator&) const;
	bool operator!= (const ohash_const_iterator&) const;
	bool operator< (const ohash_const_iterator&) const;
	bool operator<= (const ohash_const_iterator&) const;
	bool operator> (const ohash_const_iterator&) const;
	bool operator>= (const ohash_const_iterator&) const;

private:
	friend ohash<K,D,H>;
	friend ohash_iterator<K,D,H>;
};


template<typename K, typename D, typename H>
class ohash_iterator : public ohash_const_iterator<K,D,H>
{
public:
	typedef pair<const K, D> value_type;

	value_type& operator* () const;
	value_type* operator-> () const;
	ohash_iterator<K,D,H> operator++ (int);
	ohash_iterator<K,D,H>& operator++ ();
	ohash_iterator<K,D,H> operator-- (int);
	ohash_iterator<K,D,H>& operator-- ();

private:
	friend ohash<K,D,H>;
};


template<typename K, typename D, typename H>
ohash<K,D,H>::iterator
ohash<K,D,H>::begin ()
{
	iterator it;
	it.m_ohash = this;
	it.m_it = m_active.begin ();
	return it;
}

template<typename K, typename D, typename H>
ohash<K,D,H>::iterator
ohash<K,D,H>::end ()
{
	iterator it;
	it.m_ohash = this;
	it.m_it = m_active.end ();
	return it;
}

template<typename K, typename D, typename H>
ohash<K,D,H>::const_iterator
ohash<K,D,H>::begin () const
{
	const_iterator it;
	it.m_ohash = this;
	it.m_it = m_active.begin ();
	return it;
}

template<typename K, typename D, typename H>
ohash<K,D,H>::const_iterator
ohash<K,D,H>::end () const
{
	const_iterator it;
	it.m_ohash = this;
	it.m_it = m_active.end ();
	return it;
}

template<typename K, typename D, typename H>
size_t
ohash<K,D,H>::size () const
{
	return m_active.size ();
}

template<typename K, typename D, typename H>
size_t
ohash<K,D,H>::capacity () const
{
	return m_size;
}

template<typename K, typename D, typename H>
bool
ohash<K,D,H>::empty () const
{
	return m_active.empty ();
}

template<typename K, typename D, typename H>
void
ohash<K,D,H>::resize (size_t n)
{
	if (n > m_size)
	{
		ohash<K,D,H> o (n);
		o.insert (this->begin (), this->end ());
		this->swap (o);
	}
}

inline size_t hash_size (size_t min)
{
	static const int N = 28;
	static const size_t primes[N] =
	{
		53ul,         97ul,         193ul,       389ul,       769ul,
		1543ul,       3079ul,       6151ul,      12289ul,     24593ul,
		49157ul,      98317ul,      196613ul,    393241ul,    786433ul,
		1572869ul,    3145739ul,    6291469ul,   12582917ul,  25165843ul,
		50331653ul,   100663319ul,  201326611ul, 402653189ul, 805306457ul, 
		1610612741ul, 3221225473ul, 4294967291ul
	};
	int i = 0;
	while (primes[i] < min) ++i;
	return primes[i];
}

template<typename K, typename D, typename H>
ohash<K,D,H>::ohash (size_t n = 0) :
	m_size (hash_size (n)),
	m_active (m_size),
	m_data (new pair<K,D> [m_size])
{
}

template<typename K, typename D, typename H>
ohash<K,D,H>::ohash (const ohash &o, size_t n) :
	m_size (hash_size (max (n, o.size ()))),
	m_active (m_size),
	m_data (new pair<K,D> [m_size])
{
	this->insert (o.begin (), o.end ());
}

template<typename K, typename D, typename H>
ohash<K,D,H>::~ohash ()
{
	delete [] m_data;
}

template<typename K, typename D, typename H>
ohash<K,D,H>&
ohash<K,D,H>::operator= (const ohash &o)
{
	ohash<K,D,H> n (o);
	this->swap (n);
	return *this;
}

template<typename K, typename D, typename H>
void
ohash<K,D,H>::swap (ohash &o)
{
	::swap (o.m_size, m_size);
	::swap (o.m_active, m_active);
	::swap (o.m_data, m_data);
	::swap (o.m_hash, m_hash);
}

template<typename K, typename D, typename H>
pair<ohash<K,D,H>::iterator, bool>
ohash<K,D,H>::insert (const value_type &v)
{
	pair<pair<K,D>*, bool> r = this->put (v.first);
	r.first->second = v.second;
	iterator it;
	it.m_ohash = this;
	assert (m_active.count (r.first - m_data));
	it.m_it = m_active.find (r.first - m_data);
	return pair<iterator, bool> (it, r.second);
}

template<typename K, typename D, typename H>
template <typename T>
void
ohash<K,D,H>::insert (T begin, T end)
{
	while (begin != end)
	{
		this->insert (*begin);
		++begin;
	}
}


template<typename K, typename D, typename H>
ohash<K,D,H>::const_iterator
ohash<K,D,H>::find (const key_type &k) const
{
	return const_cast<ohash<K,D,H>*> (this)->find (k);
}

template<typename K, typename D, typename H>
ohash<K,D,H>::iterator
ohash<K,D,H>::find (const key_type &k)
{
	const pair<K,D> *r = this->get (k);
	iterator it;
	it.m_ohash = this;
	if (r)
	{
		assert (m_active.count (r - m_data));
		it.m_it = m_active.find (r - m_data);
	}
	else
	{
		it.m_it = m_active.end ();
	}
	return it;
}

template<typename K, typename D, typename H>
size_t
ohash<K,D,H>::count (const key_type &k) const
{
	const pair<K,D> *r = this->get (k);
	return r ? 1 : 0;
}

template<typename K, typename D, typename H>
ohash<K,D,H>::data_type&
ohash<K,D,H>::operator[] (const key_type &k)
{
	pair<pair<K,D>*, bool> r = this->put (k);
	return r.first->second;
}

template<typename K, typename D, typename H>
const ohash<K,D,H>::value_type&
ohash<K,D,H>::slot (size_t x) const
{
	assert (this->active (x));
	return m_data[x];
}

template<typename K, typename D, typename H>
ohash<K,D,H>::value_type&
ohash<K,D,H>::slot (size_t x)
{
	assert (this->active (x));
	return reinterpret_cast<pair<const K,D>&> (m_data[x]);
}

template<typename K, typename D, typename H>
bool
ohash<K,D,H>::active (size_t x) const
{
	return m_active.count (x);
}

template<typename K, typename D, typename H>
size_t
ohash<K,D,H>::index (const key_type &k) const
{
	const pair<K,D> *r = this->get (k);
	if (r)
	{
		assert (m_active.count (r - m_data));
		return r - m_data;
	}
	else
	{
		return ohash<K,D,H>::npos;
	}
}

template<typename K, typename D, typename H>
size_t
ohash<K,D,H>::hash2 (const K &k) const
{
	size_t x = 0;
	size_t sz = sizeof(k);
	const unsigned char *b = reinterpret_cast<const unsigned char*> (&k);

	while (sz)
	{
		x += *b;
		++b;
		--sz;
	}

	return 1 + (x % (m_size - 1));
}

template<typename K, typename D, typename H>
const pair<K,D>*
ohash<K,D,H>::get (const key_type &k) const
{
	size_t h1 = m_hash (k);
	size_t h2 = this->hash2 (k);
	size_t n;
	const pair<K,D> *r = 0;

	for (n = 0; n < m_size; ++n)
	{
		size_t i = (h1 + (n * h2)) % m_size;
		if (m_active.count (i) == 1)
		{
			if (m_data[i].first == k)
			{
				r = m_data + i;
				break;
			}
		}
		else
		{
			break;
		}
	}

	return r;
}

template<typename K, typename D, typename H>
pair<pair<K,D>*, bool>
ohash<K,D,H>::put (const key_type &k)
{
	size_t h1 = m_hash (k);
	size_t h2 = this->hash2 (k);
	size_t n;
	pair<pair<K,D>*, bool> r (0, true);

	for (n = 0; n < m_size; ++n)
	{
		size_t i = (h1 + (n * h2)) % m_size;
		if (m_active.count (i) == 1)
		{
			if (m_data[i].first == k)
			{
				r.first = m_data + i;
				r.second = false;
				break;
			}
		}
		else
		{
			m_active.insert (i);
			m_data[i].first = k;
			r.first = m_data + i;
			r.second = true;
			m_active.insert (i);
			break;
		}
	}

	if (n == m_size)
	{
		throw ohash_full ();
	}

	assert (r.first);

	return r;
}


template<typename K, typename D, typename H>
size_t
ohash_iter_base<K,D,H>::index () const
{
	return *m_it;
}

template<typename K, typename D, typename H>
pair<K,D>*
ohash_iter_base<K,D,H>::value () const
{
	return const_cast<pair<K,D>*> (m_ohash->m_data + *m_it);
}

template<typename K, typename D, typename H>
void
ohash_iter_base<K,D,H>::next ()
{
	++m_it;
}

template<typename K, typename D, typename H>
void
ohash_iter_base<K,D,H>::prev ()
{
	--m_it;
}

template<typename K, typename D, typename H>
int
ohash_iter_base<K,D,H>::cmp (const ohash_iter_base &o) const
{
	return m_it == o.m_it ? 0 : m_it > o.m_it ? 1 : -1;
}


template<typename K, typename D, typename H>
size_t
ohash_const_iterator<K,D,H>::index () const
{
	return this->ohash_iter_base<K,D,H>::index ();
}

template<typename K, typename D, typename H>
const ohash_const_iterator<K,D,H>::value_type&
ohash_const_iterator<K,D,H>::operator* () const
{
	return reinterpret_cast<value_type&> (
		*this->ohash_iter_base<K,D,H>::value ());
}

template<typename K, typename D, typename H>
const ohash_const_iterator<K,D,H>::value_type*
ohash_const_iterator<K,D,H>::operator-> () const
{
	return reinterpret_cast<value_type*> (
		this->ohash_iter_base<K,D,H>::value ());
}

template<typename K, typename D, typename H>
ohash_const_iterator<K,D,H>
ohash_const_iterator<K,D,H>::operator++ (int)
{
	ohash_const_iterator<K,D,H> o (*this);
	this->operator++ ();
	return o;
}

template<typename K, typename D, typename H>
ohash_const_iterator<K,D,H>&
ohash_const_iterator<K,D,H>::operator++ ()
{
	this->ohash_iter_base<K,D,H>::next ();
	return *this;
}

template<typename K, typename D, typename H>
ohash_const_iterator<K,D,H>
ohash_const_iterator<K,D,H>::operator-- (int)
{
	ohash_const_iterator<K,D,H> o (*this);
	this->operator-- ();
	return o;
}

template<typename K, typename D, typename H>
ohash_const_iterator<K,D,H>&
ohash_const_iterator<K,D,H>::operator-- ()
{
	this->ohash_iter_base<K,D,H>::prev ();
	return *this;
}

template<typename K, typename D, typename H>
bool
ohash_const_iterator<K,D,H>::operator== (
	const ohash_const_iterator<K,D,H> &o) const
{
	return this->ohash_iter_base<K,D,H>::cmp (o) == 0;
}

template<typename K, typename D, typename H>
bool
ohash_const_iterator<K,D,H>::operator!= (
	const ohash_const_iterator &o) const
{
	return this->ohash_iter_base<K,D,H>::cmp (o) != 0;
}
  
template<typename K, typename D, typename H>
bool
ohash_const_iterator<K,D,H>::operator< (
	const ohash_const_iterator &o) const
{
	return this->ohash_iter_base<K,D,H>::cmp (o) == -1;
}

template<typename K, typename D, typename H>
bool
ohash_const_iterator<K,D,H>::operator<= (
	const ohash_const_iterator &o) const
{
	return this->ohash_iter_base<K,D,H>::cmp (o) < 1;
}

template<typename K, typename D, typename H>
bool
ohash_const_iterator<K,D,H>::operator> (
	const ohash_const_iterator &o) const
{
	return this->ohash_iter_base<K,D,H>::cmp (o) == 1;
}

template<typename K, typename D, typename H>
bool
ohash_const_iterator<K,D,H>::operator>= (
	const ohash_const_iterator &o) const
{
	return this->ohash_iter_base<K,D,H>::cmp (o) > -1;
}


template<typename K, typename D, typename H>
ohash_iterator<K,D,H>::value_type&
ohash_iterator<K,D,H>::operator* () const
{
	return reinterpret_cast<value_type&> (
		*this->ohash_iter_base<K,D,H>::value ());
}

template<typename K, typename D, typename H>
ohash_iterator<K,D,H>::value_type*
ohash_iterator<K,D,H>::operator-> () const
{
	return reinterpret_cast<value_type*> (
		this->ohash_iter_base<K,D,H>::value ());
}

template<typename K, typename D, typename H>
ohash_iterator<K,D,H>::ohash_iterator<K,D,H>
ohash_iterator<K,D,H>::operator++ (int)
{
	ohash_const_iterator<K,D,H> o (*this);
	this->operator++ ();
	return o;
}

template<typename K, typename D, typename H>
ohash_iterator<K,D,H>&
ohash_iterator<K,D,H>::operator++ ()
{
	this->ohash_iter_base<K,D,H>::next ();
	return *this;
}

template<typename K, typename D, typename H>
ohash_iterator<K,D,H>
ohash_iterator<K,D,H>::operator-- (int)
{
	ohash_const_iterator<K,D,H> o (*this);
	this->operator-- ();
	return o;
}

template<typename K, typename D, typename H>
ohash_iterator<K,D,H>&
ohash_iterator<K,D,H>::operator-- ()
{
	this->ohash_iter_base<K,D,H>::prev ();
	return *this;
}

#endif