// NOtes:
// might want to use horner scheme for string or string-like hashing, for that
// the hash must get the size of the table, and we have to provide security
// measures against wrong rehashing when resizing the table.
// also look at brent-hashing to improve open addressing schemes


#include <iostream>
#include <cassert>
#include <vector>
#include <algorithm>
#include <stdexcept>
#include <cstring>
#include <unordered_map>

#include "boost/mpl/if.hpp"
#include "boost/utility/enable_if.hpp"

#undef DEBUG
namespace iwear
{
// ######################################################################
// helper stuff
// ######################################################################
template<class T, size_t N>
constexpr size_t array_size( T(& )[N] )
{
	return N;
}

// replace usages of this macro by use of a constexpr function as soon as we have them
#define asize(x) (sizeof(x) / sizeof(x[0]))
/*
 * This class aims to be a quite versatile hashtable, where you can control
 * various parameters of its behaviour via template parameters.
 */

/**
 * These enums control basic behaviours of the hashing functions built in. If
 * you need something else for the trivial types, you need to roll your own
 * structure that does this.
 * @note You can create specializations for various other hashing classes
 * yourself, and specify them at the same point where you instantiate them
 * otherwise. To do that, simply specialize for other numerical values, like
 * hash<T,(hashclass)3> and use that type wherever you want.
 */
enum class hashclass : int
{
	identity, ///< If possible, use the value as the result of the hash, to suppress possible errors we static_cast to size_type
	trivial,  ///< Use a trivial hashing, like multiplication with a large prime
	fnv       ///< Use a hashing scheme similar to fnv (but not quite exactly)
};

/**
 * This is a value metafunction that takes an integer as input and outputs the
 * same value of the type hashclass. Whenever the input could be something
 * convertible to int, this is a wrapper for the case you don't like casts. You
 * can use it like make_hashclass<5>::value instead of (hash_class)5
 */
template<int hc>
struct make_hashclass
{
    static const hashclass value = (hashclass)hc;
};

/**
 * This class is for the actual hashing. The user is supposed to specialize it
 * for his own types in order to get the hashing behaviour he wants. It might
 * be possible though, that for some reasons another hashing is needed for the
 * same datatype. To compensate for this we allow for specifying the type of
 * the hash struct later in the hash_table_impl so that a user can use its own
 * there.
 * @note per default a trivial hashing is used, which is often a good balance
 * between speed and degradation effects.
 * @note We will always use this type without explicitly specifying its
 * namespace. Therefore it could be possible that sometimes something from your
 * namespace is picked up, be aware of that.
 * @warning Various hashes have different degradation properties, like
 * avalanche effects and similar. Consider carefully what you chose here, and
 * in that consideration, think about who controls the data. If you control the
 * data you can usually be much more lax with the requirements as you can make
 * sure that no strange clustering effects can occur.
 */
template<class T, hashclass HC >
struct hash
{
    typedef size_t size_type;
    typedef T item_type;
private:
    /**
     * If you get a compile error here saying that this is private, you need to
     * specialize your own version of hash for your item_type with this
     * function not being private. This generic version is just to communicate
     * a defined interface.
     */
    size_type operator()( const item_type& i );
    size_type operator()( item_type* i );
};

namespace __detail
{

template<class size_type, int N>
struct roundup
{
	static size_type roundup_recurse( size_type v )
	{
		v = roundup<size_type,N/2>::roundup_recurse(v);
		v |= v >> N;
		return v;
    }
};

template<class size_type>
struct roundup<size_type,1>
{
	static size_type roundup_recurse( size_type v )
	{
		v |= v >> 1;
		return v;
	}
};

template<class size_type>
size_type roundup2( size_type v )
{
	v--;
	v = roundup<size_type,sizeof(v)>::roundup_recurse(v);
	v++;
	return v;
}

} // namespace __detail

#if 0  // old shit ;)
/**
 * This class controls how the sizes of the hashtable are selected, as well as
 * how the hash value is actually transformed into an index.
 * @param binary decides whether the hashtable uses power of two sizes only,
 * and then the operator& to determine indices or whether a predefined list of
 * primes is used with the operator%.
 */
template<bool binary >
struct hash_selection
{
    typedef size_t size_type;

    /**
     * With this we control whether the hashtable will automatically resize
     * when it detects after an insert that it is now too small, or whether the
     * user is responsible for calling the corresponding check function.
     * @note that in no case a check for the size is done, when the slot in the
     * hashtable that was found wasn't already occupied.
     */
    static const bool auto_resize;
    /**
     * required helper function that will determine the type of the pointer
     * being used. You can write your own variant, that will use e.g.
     * boost::offset_ptr so all pointers that are permanently stored in memory
     * are of such a type which means you can store things in shared memory or
     * in a memory mapped file you will be able to relocate.
     */
    template<class T>
    struct add_pointer
    {
	typedef T* type;
    };

    /**
     * The default metafunction for creating the slot item type assumes that we
     * are using a singly linked list for our hashtable.
     */
    template<class T>
    struct slot_item
    {
	typedef typename add_pointer<T>::type type;
    };

    /**
     * Transforms the hash into an actual index.
     * @param hash is the hash as gathered from the hash structure
     * @param size is the current size of the hashtable in number of slots
     */

    static size_type index( size_type hash, size_type size );

    /**
     * @returns true if a resize of the hashtable is recommended, making the
     * hashtable actually bigger. If a shrink is possible, this does not mean a
     * resize is recommended, so this function returns false.
     */
    static bool need_resize( size_type size, size_type filled );

    /**
      Do a resize so the size vs filled ratio is optimized in case too much
     * slots are filled. If there are already enough free slots, no change is
     * made.
     * @returns true iff an actual resize was made.
     */
    static bool resize( size_type size, size_type filled );

    /**
     * Shrinks a hashtable to the least minimum necessary for a proper
     * fillratio of the table. This might be significantly slower as the
     * recommended size used in resize() so that you should only ever call this
     * if you think the hashtable will not be filled in the future.
     */
    static bool shrink( size_type size, size_type filled );
};

template<>
struct hash_selection<false>
{
    template<class R>
    struct add_pointer
    {
	typedef R* type;
    };

    template<class R>
    struct slot_item
    {
	typedef typename add_pointer<R>::type type;
    };

    typedef size_t size_type;
    static size_type index( size_type hash, size_type size )
    {
#ifdef DEBUG
	std::cerr << "hash = " << hash << ", size = " << size << "\n";
#endif
	return hash % size;
    }
};
#endif

// ######################################################################
// hash collision resolvers
// ######################################################################

// all of them should get a _templ variant that gets the NEXT parameter, and
// one without, then we can use an mpl list of all of them that we chain
// together with the NEXT ones.
/**
 * Tries to resolve collisions by linear probing, that is if slot[hash % mask]
 * is occupied, the algorithm will use a loop for(i=1 to maxsteps) try
 * slot[(hash+(i*stepsize) % mask] as the next slot.
 * @tparam NEXT the type that is being used next to resolve collisions
 * @tparam stepsize the amount to add in each iteration
 * @tparam maxsteps the maximum number of iterations this resolver will try
 * until giving up and passing work to the next one
 */
template<
class NEXT,
size_t stepsize,
size_t maxsteps
>
struct resolver_linear_probing
{
	// DRAFT!!!
	template<class ITEM_TYPE, class TABLE_TYPE, class INSERTER, class SLOT_SELECTOR>
	bool operator()( size_t hsum, size_t mask, ITEM_TYPE& it, TABLE_TYPE& table )
	{
		for( size_t i = 1; i <= maxsteps; ++i )
		{
			size_t hvalue = hsum + stepsize * i;
			size_t idx = SLOT_SELECTOR()(hvalue,mask);
			if( ! INSERTER::occupied(idx,table) )
			{
				return INSERTER::insert(it,idx,table);
			}
		}
	}
};

template<
class NEXT,
class polytype,
size_t maxsteps,
	   // XXX Check if this technique shouldnt be use everywhere else where some float would be a nice idea
size_t c1_n,
size_t c2_n,
size_t c1_d = 1,
size_t c2_d = 1
>
struct resolver_quadratic_probing
{
	// DRAFT!!!
	template<class ITEM_TYPE, class TABLE_TYPE, class INSERTER, class SLOT_SELECTOR>
	bool operator()( size_t hsum, size_t mask, ITEM_TYPE& it, TABLE_TYPE& table )
	{
		polytype c1 = c1_n / c1_d;
		polytype c2 = c2_n / c2_d;
		for( size_t i = 1; i <= maxsteps; ++i )
		{
			size_t hvalue = hsum + c1 * i + c2 * i * i;
			size_t idx = SLOT_SELECTOR()(hvalue,mask);
			if( ! INSERTER::occupied(idx,table) )
			{
				return INSERTER::insert(it,idx,table);
			}
		}
	}
};

template<
class NEXT,
class OTHERHASH,
size_t maxsteps
>
struct resolver_double_hashing
{
	// DRAFT!!!
	template<class ITEM_TYPE, class TABLE_TYPE, class INSERTER, class SLOT_SELECTOR>
	bool operator()( size_t hsum, size_t mask, ITEM_TYPE& it, TABLE_TYPE& table )
	{
		OTHERHASH hasher;
		size_t extrahash = hasher(it);
		for( size_t i = 1; i <= maxsteps; ++i )
		{
			size_t hvalue = hsum + i * extrahash;
			size_t idx = SLOT_SELECTOR()(hvalue,mask);
			if( ! INSERTER::occupied(idx,table) )
			{
				return INSERTER::insert(it,idx,table);
			}
		}
	}
};

template<
class NEXT,
class OTHERHASH
>
struct resolver_second_hashing
{
	// DRAFT!!!
	template<class ITEM_TYPE, class TABLE_TYPE, class INSERTER, class SLOT_SELECTOR>
	bool operator()( size_t hsum, size_t mask, ITEM_TYPE& it, TABLE_TYPE& table )
	{
		OTHERHASH hasher;
		size_t hvalue = hasher(it);
		size_t idx = SLOT_SELECTOR()(hvalue,mask);
		if( ! INSERTER::occupied(idx,table) )
		{
			return INSERTER::insert(it,idx,table);
		}
	}
};

struct slot_selector_modulo
{
	static size_t mask_from_length( size_t len )
	{
		return len;
	}

	size_t hash_to_index( size_t hsum, size_t mask ) const
	{
#ifdef DEBUG
		std::cerr << "slot_selector_modulo::hash_to_index(" << hsum << " % " << mask << " == " << (hsum % mask) << "\n";
#endif
		return hsum % mask;
	}
};

struct slot_selector_power2
{
	static size_t mask_from_length( size_t len )
	{
		return len - 1;
	}

	size_t hash_to_index( size_t hsum, size_t mask ) const 
	{
#ifdef DEBUG
		std::cerr << "slot_selector_power2::hash_to_index(" << hsum << " & " << mask << " == " << (hsum & mask) << "\n";
#endif
		// assert( mask+1 is power of 2 );
		return hsum & mask;
	}
};

struct slot_selector_power2_xorfolded
{
	static size_t mask_from_length( size_t len )
	{
		return len - 1;
	}

	size_t operator()( size_t hsum, size_t mask ) const 
	{
#ifdef DEBUG
		std::cerr << "slot_selector_power2()(" << hsum << " & " << mask << " == " << (hsum & mask) << "\n";
#endif
//		 XXX We need to xor fold the bits that would be masked off into the resulting slot!
		// assert( mask+1 is power of 2 );
		return hsum & mask;
	}
};

// ############################################# # # # # # # # # # # # # # # # # # # # # # # # #
//
// for the factor 1.1
size_t primetable11[] =
{
	2,				3,				5,				7,				11,				13,				
	17,				19,				23,				29,				31,				37,				
	41,				43,				53,				59,				67,				73,				
	83,				89,				97,				107,			127,			139,			
	157,			167,			191,			211,			223,			251,			
	269,			293,			331,			359,			389,			431,			
	479,			521,			569,			631,			691,			757,			
	827,			911,			1009,			1103,			1213,			1327,			
	1459,			1607,			1777,			1949,			2137,			2347,			
	2591,			2843,			3137,			3449,			3779,			4157,			
	4583,			5039,			5527,			6079,			6689,			7369,			
	8089,			8923,			9787,			10771,			11863,			13033,			
	14327,			15761,			17333,			19069,			20981,			23071,			
	25391,			27917,			30703,			33773,			37159,			40867,			
	44953,			49451,			54401,			59833,			65827,			72421,			
	79631,			87613,			96353,			105997,			116593,			128257,			
	141073,			155191,			170701,			187763,			206543,			227189,			
	249911,			274909,			302399,			332641,			365903,			402487,			
	442721,			487007,			535697,			589273,			648191,			713021,			
	784307,			862739,			949019,			1043921,		1148311,		1263133,		
	1389439,		1528399,		1681241,		1849349,		2034283,		2237743,		
	2461477,		2707651,		2978399,		3276241,		3603857,		3964229,		
	4360649,		4796749,		5276387,		5804023,		6384439,		7022867,		
	7725161,		8497681,		9347441,		10282177,		11310413,		12441439,		
	13685579,		15054157,		16559561,		18215501,		20037053,		22040771,		
	24244837,		26669317,		29336243,		32269877,		35496869,		39046541,		
	42951203,		47246359,		51970957,		57168043,		62884859,		69173333,		
	76090681,		83699761,		92069729,		101276699,		111404369,		122544787,		
	134799271,		148279217,		163107157,		179417839,		197359663,		217095589,		
	238805207,		262685693,		288954269,		317849681,		349634651,		384598153,		
	423057949,		465363781,		511900133,		563090189,		619399213,		681339121,		
	749473051,		824420407,		906862427,		997548689,		1097303609,		1207033967,		
	1327737391,		1460511163,		1606562357,		1767218597,		1943940541,		2138334589,		
	2352168083UL,	2587384981UL,	2846123519UL,	3130735931UL,	3443809657UL,	3788190661UL,		
	4167009773UL,		
};

// for the factor 1.5
constexpr size_t primetable15[] = 
{
	2,				5,				7,				11,				17,				29,				
	41,				59,				89,				137,			199,			307,			
	449,			673,			1009,			1511,			2267,			3391,			
	5087,			7639,			11443,			17167,			25741,			38611,			
	57917,			86923,			130337,			195469,			293201,			439799,			
	659689,			989533,			1484291,		2226431,		3339643,		5009471,		
	7514231,		11271319,		16906949,		25360441,		38040619,		57060931,		
	85591417,		128387137,		192580621,		288870937,		433306427,		649959679,		
	974939417,		1462409083,		2193613607UL,	3290420401UL
};

template<
int grow_load_pm,
int perfect_load_pm,
int shrink_load_pm
>
struct resize_base
{
// XXX one day take some time and think about whether we can safely do all this
// with integer only maths. Or even provide a template parameter for this.
	static constexpr float shrink_load = shrink_load_pm / 1000.0f;
	static constexpr float perfect_load = perfect_load_pm / 1000.0f;
	static constexpr float grow_load = grow_load_pm / 1000.0f;

	/**
	 */
//	__attribute__((noinline))
	static bool need_grow( size_t elements, size_t slots )
	{
		// XXX A later design could sacrifice a few bytes to store the actual
		// values in elements for grow and shrink barriers, so that a check
		// against those only needs to compare against them. Of course in case
		// of a real resize event those values will need to be recalculated.
		// Since this is a speed vs space trade-off we will provide template
		// parameters for that with proper defaults.

		// calculate actual load factor
		double lfactor = double(elements)/slots;
#ifdef DEBUG
		std::cerr << "need_grow load factor " << lfactor << "\n";
		std::cerr << "load factor at which to start growing " << grow_load << "\n";
		std::cerr << "returning " << ( lfactor >= grow_load ) << "\n";
#endif
		if( lfactor >= grow_load )
		{
			return true;
		}
		else
		{
			return false;
		}
	}

	static bool need_shrink( size_t elements, size_t slots )
	{
		// calculate actual load factor
		// XXX Check whether the compiler can properly inline and elide this
		// calculation in the case need_resize() will be called.
		double lfactor = double(elements)/slots;
#ifdef DEBUG
		std::cerr << "need_shrink load factor " << lfactor << "\n";
		std::cerr << "load factor at which to start shrinking " << shrink_load << "\n";
		std::cerr << "returning " << ( lfactor < shrink_load ) << "\n";
#endif
		if( lfactor < shrink_load )
		{
			return true;
		}
		else
		{
			return false;
		}
	}

	static bool need_resize( size_t elements, size_t slots )
	{
		return need_grow(elements,slots) || need_shrink(elements,slots);
	}

};

template<
int grow_load_pm,
int perfect_load_pm,
int shrink_load_pm,
const size_t* prime_table_start,
size_t prime_table_size
>
struct resize_primetable_template
	: resize_base<grow_load_pm,perfect_load_pm, shrink_load_pm>
{
	typedef resize_base<grow_load_pm,perfect_load_pm, shrink_load_pm> base_type;

	typedef slot_selector_modulo slot_selector;

	static size_t max_size( )
	{
		return prime_table_start[prime_table_size-1];
	}
	/**
	 * The optimal size will be calculated in the way that from the desired
	 * load factor (per default 0.8*elements) on we will take the next bigger
	 * prime from our table. The table was generated using a start number (89)
	 * and multiplying this by 1.5 and then choosing the next prime (and so on,
	 * taking the previous result and not the prime as input for multiplication
	 * by 1.5 so that you can easier determine the numbers).
	 * @note the optimal_size function is potentially expensive and should only
	 * be called in the case a resize needs to be done. Determining whether a
	 * resize is needed should be done purely on the current sizes load factor.
	 */
	static size_t optimal_size( size_t elements )
	{
		// First of all we calculate the number of slots for the desired
		// perfect load factor.
		size_t min_slots = elements / base_type::perfect_load;
		// then search in the provided primetable for a proper prime number.
		const size_t* i = std::lower_bound(prime_table_start, prime_table_start + prime_table_size , min_slots);
		if( i == (prime_table_start+prime_table_size) )
		{
			// XXX refine to a more suited exception type one day
			throw std::runtime_error("Exceeded built in primetable while generating optimal_size");
		}
		return *i;
	}

	static bool need_resize( size_t elements, size_t slots )
	{
		return (base_type::need_grow(elements,slots) || base_type::need_shrink(elements,slots))
			// actually ask for shrink only if the amount of elements is really
			// bigger than the smallest size we would ever have.
			&& prime_table_start[0] < elements;
	}


};

template<
int grow_load_pm = 800,
int perfect_load_pm = 700,
int shrink_load_pm = 300
>
struct resize_primetable_15
	: resize_primetable_template<grow_load_pm,perfect_load_pm, shrink_load_pm,primetable15,array_size(primetable15)>
{
	template<class ht>
	struct mangle
	{
		typedef typename ht::template set_slot_resizer<resize_primetable_15>::type type;
	};
};


// XXX A good default load factor depends on the collision resolution used
template<
int grow_load_pm = 800,
int perfect_load_pm = 700,
int shrink_load_pm = 300
>
struct resize_power2
	: resize_base<grow_load_pm, perfect_load_pm, shrink_load_pm>
{
	typedef resize_base<grow_load_pm, perfect_load_pm, shrink_load_pm> base_type;

	typedef slot_selector_power2 slot_selector;

	template<class ht>
	struct mangle
	{
		typedef typename ht::template set_slot_resizer<resize_power2>::type type;
	};

	static size_t max_size( )
	{
		return static_cast<size_t>(-1);
	}
	/**
	 * 
	 */
	static size_t optimal_size( size_t elements )
	{
		// the optimal size is given a certain load factor the next power of
		// two after the amount of slots needed to achieve this load factor.
		size_t min_slots = elements / base_type::perfect_load;
		// Now find the next power of two...
		size_t s = __detail::roundup2(min_slots);
		return s;
	}
};

struct raw_pointer
{
	template<class T>
	struct pointer
	{
		typedef T* type;
	};
};



// generic anchor hierarchy, to be used by all possible containers that might
// want to use them.

template<class T, class PTR_SELECTOR >
struct anchor_single
{
	typedef T item_type;
	typedef typename PTR_SELECTOR::template pointer<item_type>::type pointer_type;
	typedef decltype(*pointer_type()) reference_type;

	static const bool empty = false;
protected:
	pointer_type next;
public:
	anchor_single( )
		: next(0) // not really necessary but gcc warns otherwise
	{
#ifdef DEBUG
		next = reinterpret_cast<pointer_type>(~0UL);
#endif
	}

	const pointer_type get_next() const { return next; }
	pointer_type get_next() { return next; }
	void set_next( pointer_type ptr ) { next = ptr; }

	template<class AA>
	void to_dot( std::ostream& out ) const
	{
		if( next )
		{
			out << "node_" << this << " -> node_" << next << ";\n";
			AA aa;
			aa(next)->anchor.template to_dot<AA>(out);
		}
	}
};

template<class T, class PTR_SELECTOR>
struct anchor_double : public anchor_single<T,PTR_SELECTOR>
{
    typedef anchor_single<T,PTR_SELECTOR> base_type;
    typedef typename base_type::item_type item_type;
    typedef typename base_type::pointer_type pointer_type;
    typedef typename base_type::reference_type reference_type;
protected:
    pointer_type prev;
public:
    const pointer_type get_prev() const { return prev; }
    void set_prev( pointer_type ptr ) { prev = ptr; }
};

template<class T, class PTR_SELECTOR>
struct anchor_btree : protected anchor_double<T,PTR_SELECTOR>
{
    typedef anchor_double<T,PTR_SELECTOR> base_type;
    typedef typename base_type::item_type item_type;
    typedef typename base_type::pointer_type pointer_type;
    typedef typename base_type::reference_type reference_type;

    const pointer_type get_left() const { return base_type::prev; }
    const pointer_type get_right() const { return base_type::next; }

    void set_left( pointer_type ptr ) { base_type::set_prev(ptr); }
    void set_right( pointer_type ptr ) { base_type::set_next(ptr); }

    base_type& get_base() { return *this; } 
    const base_type& get_base() const { return *this; } 
};

namespace avl
{
    enum class skew
    {
	none,
	left,
	right
    };
}

/* need to be adapted to new PTR_SELECTOR non-template variant
template<class T, template<class> class PTR>
struct anchor_avltree : public anchor_btree<T,PTR>
{
    avl::skew sk;
    avl::skew get_skew() const { return sk; }
    void set_skew( avl::skew _sk ) { sk = _sk; }
};

template<class T, template<class> class PTR>
struct anchor_compressed_avltree : public anchor_btree<T,PTR>
{
    typedef anchor_btree<T,PTR> base_type;
    typedef typename base_type::item_type item_type;
    typedef typename base_type::pointer_type pointer_type;
    typedef typename base_type::reference_type reference_type;

    // XXX its likely a good idea to have this as a free utility function somewhere
    static ptrdiff_t get_pointer_bits( const void* ptr, ptrdiff_t mask )
    {
	const char* t = reinterpret_cast<const char*>(ptr);
	const char* null = 0;
	ptrdiff_t d = t - null;
	return (d&mask);
    }
    // abuse boost::mpl::print to emit a warning when sizeof(base) != sizeof(*this)
	avl::skew get_skew() const
	{
		// for efficiency reasons, if possible we only use the left pointer
		if( sizeof(*this) >= 4 )
		{
			// pointer points always to a multiple of 4, meaning that the lower
			// two bits are reserved for us. Useful compilers will eliminate
			// this if.
			return static_cast<avl::skew>( get_pointer_bits(get_left(), 0x3u));
		}
		else
		{
			const ptrdiff_t mask = 0x1u;
			assert( sizeof(*this) >= 2 ); // it cannot be lower, we consist of two distinct objects, that is pointers
			if( get_pointer_bits(get_left(),mask) ) // lowest bit of left is set
			{
				assert( !get_pointer_bits(get_right() & mask) ); // both bits are never set by us, so this must be a bug somewhere
				return avl::skew::left;
			}
			else if( get_pointer_bits(get_right(),mask) ) // lowest bit of left is set
			{
				assert( !get_pointer_bits(get_left() & mask) ); // both bits are never set by us, so this must be a bug somewhere
				return avl::skew::right;
			}
			// no bit is set, skew is none
			return avl::skew::none;
		}
	}

    void set_skew( avl::skew _sk );

    // XXX its likely a good idea to have this as a free utility function somewhere
	template<class U>
	U* get_masked_pointer( const void* ptr, ptrdiff_t mask )
	{
		U* ret;
		const char* t = reinterpret_cast<const char*>(ptr);
		const char* null = 0;
		ptrdiff_t d = t - null;
		d &= ~mask; // mask "off" the bits
		ret = static_cast<U*>(null + d);
		return ret;
	}

    const pointer_type get_left() const 
    {
	if( sizeof(*this) >= 4 )
	{
	    return get_masked_pointer<const pointer_type>(base_type::get_left(),0x3u);
	}
	else
	{
	    return get_masked_pointer<const pointer_type>(base_type::get_left(),0x1u);
	}
    }

    const pointer_type get_right() const 
    { 
	if( sizeof(*this) >= 4 )
	{ // in this case, the right pointer is not used for special bits
	    return base_type::get_right();
	}
	else
	{ // in this case, its the lowest bit, mask it off
	    return get_masked_pointer<const pointer_type>(base_type::get_right(),0x1u);
	}
    }

    void set_left( pointer_type ptr )
    {
	// XXX We should make this function act upon the actual skew and
	// sizeof(*this) and maybe change the skew only if affected by the
	// pointer or so.
	avl::skew s = get_skew();
	base_type::set_left(ptr);
	set_skew(s);
    }

    void set_right( pointer_type ptr )
    {
	avl::skew s = get_skew();
	base_type::set_right(ptr);
	set_skew(s);
    }
};
*/

enum class occupancy : unsigned char
{
	free,
	deleted,
	occupied
};

template<bool>
struct anchor_occupancy_storage;

template<>
struct anchor_occupancy_storage<true>
{
	occupancy occupied;
};

template<>
struct anchor_occupancy_storage<false>
{
};

template<bool>
struct anchor_hash_storage;

template<>
struct anchor_hash_storage<true>
{
	size_t hash;

	static const bool store_hash = true;
};

template<>
struct anchor_hash_storage<false>
{
	static const bool store_hash = false;
};

template<class anchor_type, bool empty>
struct anchor_storage;

template<class anchor_type>
struct anchor_storage<anchor_type,false>
{
	anchor_type anchor;
};

template<class anchor_type>
struct anchor_storage<anchor_type,true>
{
};

template< class anchor_type, bool store_hash, bool store_occupancy>
struct anchor_member_mixer :
	anchor_storage<anchor_type, anchor_type::empty>,
	anchor_occupancy_storage<store_occupancy>,
	anchor_hash_storage<store_hash>

{
};

template<class ANCHOR_ACCESSOR>
struct single_inserter_template
{
	typedef ANCHOR_ACCESSOR anchor_accessor;

	template<class AA>
	struct rebind
	{
		typedef single_inserter_template<AA> other;
	};

	// XXX choose per template parameter whether to put things at the beginning
	// or the end of the list
	template<
		class IT,
		class SZ,
		class SLA
		>
	static bool insert( IT* i, SZ idx, SLA** sa )
	{
		SLA*& slot = sa[idx];
#ifdef DEBUG
		std::cerr << "Chosen slot = " << (void*)slot << "\n";
#endif
		anchor_accessor aa;
		aa(i)->anchor.set_next(0);
		// XXX if is_occupied(slot) for others
		if( slot )
		{
			IT* next = slot;
			while( aa(next)->anchor.get_next() )
			{
#ifdef DEBUG
				std::cerr << "Accessing slot/item " << (void*)slot << " and next being ";
#endif
				next = aa(next)->anchor.get_next();
#ifdef DEBUG
				std::cerr << (void*)next << "\n";
#endif
			}
			assert( next != NULL );
			// next now contains the last item in the list
			// XXX singly linked list collision resolution
			aa(next)->anchor.set_next(i);
		}
		else // its free, just set it
		{
			slot = i;
		}
		return true;
	}

	template<
		class IT,
		class SZ,
		class SLA
		>
	static bool remove( IT* it, SZ idx, SLA** sa )
	{
//		std::cout << "remove(" << it << "," << idx << "," << sa << ")\n";
		SLA*& slot = sa[idx];
//		std::cout << "slot = " << slot << "\n";
		
		anchor_accessor aa;
		if( slot == it )
		{
			// If it is directly sitting at the slot remove it there.
			slot = aa(it)->anchor.get_next();
#ifdef DEBUG
			aa(it)->anchor.set_next( reinterpret_cast<IT*>(~0UL) );
#endif
			return true;
		}
		else if( slot )
		{
			// It is not the first in the slot but there is something
			IT* next = slot;
			while( aa(next)->anchor.get_next() )
			{
				IT* prev = next;
				next = aa(next)->anchor.get_next();
				if( next == it )
				{
					aa(prev)->anchor.set_next( aa(next)->anchor.get_next() );
#ifdef DEBUG
					aa(next)->anchor.set_next( reinterpret_cast<IT*>(~0UL) );
#endif
					return true;
				}
			}

		}
		return false;
	}

};

template<class ANCHOR_ACCESSOR>
struct double_inserter_template
{
	typedef ANCHOR_ACCESSOR anchor_accessor;

	template<class AA>
	struct rebind
	{
		typedef double_inserter_template<AA> other;
	};

		template<
		class IT,
		class SZ,
		class SLA
		>
	static bool insert( IT* i, SZ idx, SLA** sa )
	{
		SLA*& slot = sa[idx];
#ifdef DEBUG
		std::cerr << "Chosen slot = " << (void*)slot << "\n";
#endif
		anchor_accessor aa;
		// XXX if is_occupied(slot) for others
		if( slot )
		{
			IT* next = slot;
			while( aa(next)->anchor.get_next() )
			{
#ifdef DEBUG
				std::cerr << "Accessing slot/item " << (void*)slot << " and next being ";
#endif
				next = aa(next)->anchor.get_next();
#ifdef DEBUG
				std::cerr << (void*)next << "\n";
#endif
			}
			// next now contains the last item in the list
			// XXX singly linked list collision resolution
			aa(next)->anchor.set_next(i);
			aa(i)->anchor.set_next(0);
			aa(i)->anchor.set_prev(next);
//			++elem_size;
		}
		else // its free, just set it
		{
			slot = i;
			aa(i)->anchor.set_next(0);
			aa(i)->anchor.set_prev(0);
//			++elem_size;
		}
		return true;
	}
	template<
		class IT,
		class SZ,
		class SLA
		>
	static bool remove( IT* it, SZ idx, SLA** sa )
	{
		assert(false);
	}
};

struct double_inserter
{
	template<class AA>
	struct rebind
	{
		typedef double_inserter_template<AA> other;
	};
};

struct single_inserter
{
	template<class AA>
	struct rebind
	{
		typedef single_inserter_template<AA> other;
	};
};


struct resolution_single_linked_list
{
	template<class T, class PTR_SELECTOR>
	struct anchor_member_type
	{
		typedef anchor_single<T,PTR_SELECTOR> type;
	};
	typedef single_inserter inserter;

	template<class SIZE_TYPE, class ITEM_TYPE>
	SIZE_TYPE reselect( SIZE_TYPE idx, ITEM_TYPE**, SIZE_TYPE )
	{
		return idx;
	}


	template<class ht>
	struct mangle
	{
		typedef typename ht::template set_collision_resolution<resolution_single_linked_list>::type type;
	};
};

struct resolution_double_linked_list
{
	template<class T, class PTR_SELECTOR>
	struct anchor_member_type
	{
		typedef anchor_double<T,PTR_SELECTOR> type;
	};
	typedef double_inserter inserter;

	template<class SIZE_TYPE, class ITEM_TYPE>
	SIZE_TYPE reselect( SIZE_TYPE idx, ITEM_TYPE**, SIZE_TYPE )
	{
		return idx;
	}

	template<class ht>
	struct mangle
	{
		typedef typename ht::template set_collision_resolution<resolution_double_linked_list>::type type;
	};
};


/**
 * This is a metafunction that provides the proper type for an anchor, given
 * certain parameters.
 * @tparam COLLISION_RESOLUTION is the metafunction that provides the way
 * collisions are resolved. Depending on that the anchor may contain pointers
 * (e.g. for linked list resolves) or also simply nothing.
 * @tparam PTR_SELECTOR is the selector metafunction that transforms types into
 * pointers to that type. We use it everywhere so that we can use special
 * pointer types (shared pointers, relative pointers etc.)
 * @tparam store_occupancy tells us whether we should provide storage for
 * whether this item is occupied or not. This makes only sense if you want to
 * use an open addressing hashtable, as such the collision resolution should be
 * chosen in an appropriate way.
 * XXX Make this not a parameter but depending on a member of the collision resolution.
 * @tparam store_hash tells us whether the hash value is ever stored or not. If
 * it is stored, then it will be in a member of type size_t.
 */
template<
class T,
class COLLISION_RESOLUTION = resolution_single_linked_list ,
class PTR_SELECTOR = raw_pointer,
bool store_hash = false,
bool store_occupancy = false
>
struct anchor_member_chooser
{
	typedef 
		anchor_member_mixer<
		typename COLLISION_RESOLUTION::template anchor_member_type<T,PTR_SELECTOR>::type,
		store_hash,
		store_occupancy>
		type;

	template<bool sh>
	struct set_store_hash
	{
		typedef 
			anchor_member_mixer<
			typename COLLISION_RESOLUTION::template anchor_member_type<T,PTR_SELECTOR>::type,
			sh,
			store_occupancy>
			type;
	};
};

// ############################################# # # # # # # # # # # # # # # # # # # # # # # # #
// 
// We do not want the user to manually chose (however he of course can do so)
// the necessary anchor for his hash table, but we want to provide a
// metafunction that can do so. Therefore we create here something that
// collects all the properties for the future hashtable that will not depend on
// the type of data being stored. Within that embedded will be a metafunction
// that chooses the anchor type.
// Those marked with * influence the anchor type
//
// Not all of these things may be combined
//*- collision resolution scheme
//   - single linked list
//   - double linked list
//   - jumping (various weird kinds)
//   - rehashing (various ways, including one with alternative hashers)
//   - cookoo hashing
// - allocator storage
//   - whether to store the allocator passed to the ctor in a member variable or not
// - comparator storage
//   - whether to store the comparator passed to the ctor in a member variable or not
//*- data storage
//   - in the table (OA like), item will be copied (precludes linked list et al collision resolution)
//   - as pointers, items will be "linked" into the datastructure
//*- pointer type
//   - default is a raw pointer
//   - metafunction that will lead to a pointer type when fed with T
//*- store hash
//   - storing the hash (without the upper bit) set might be necessary in case
//     the hashing is so expensive that its worth it
// - ownership
//   - data structure owns data (on destruction, all items are destroyed)
//   - the user owns the data. On destruction, items will not be touched at all
// - size and access
//   - size is always multiple of 2, access to slots is done by masking of bits
//   - size is an arbitrary number (likely prime). slots will be chosen by
//     taking the remainder of division modulo the size
// - table storage
//   - default is std::vector
//   - a metafunction or template can be provided that will determine the type
//     of the underlying table storage.
// - the size_type
//   - type that is used to store various underlying values
// - automatic resize on insert/remove.
//   - enable per template
//   - disable per template
//   - have a runtime changeable flag with templated default
// - duplicate entries
//   - allow/disallow per template parameter
// - compare hash
//   - if store hash is enabled, before comparing the elements themselves, the hash is compared
// - allocator and storage
//   - an allocator must be specified which can be stored optionally, have a param that tells us
// - same for a comparator
// - also for the hasher we might want to store it (or not)
// The result must be in the hash_config passed to the hash_table_impl
// ############################################# # # # # # # # # # # # # # # # # # # # # # # # #
// For the following things, we need to have T available in some way.
// - hashing
//   - user provides a functor or metafunction or whatever that can hash T into
//     an integer
//   - We provide means for hashing standard datastructures and arbitrary byte
//     buffers in three categories, among the user could chose for his datatypes too.
//       - identity. Do not hash things, useful for those cases where the key
//         is known to be distributed properly
//       - trivial is a very simple way to determine the hash
//       - fnv uses a bit more complex hashing, similar to fnv
// - anchor access
//   - the user provides a mean for accessing the appropriate anchor for this
//     hashtable when having a T* at hand
//   - for OA-like hashtables that store copies in the table itself, the anchor
//     shall provide a way to mark items as occupied, free or deleted. Each
//     element *must* be default constructible and *must* be initially marked
//     as free. Failure to do so will lead to undefined behaviour
// The result must be in the hash_accessor passed to the hash_table_impl
namespace collision_resolution
{

/**
 * This shall resolve collisions by putting things in a singly linked list.
 * We gonna need functionality for specifying the type of the anchor and a
 * function to resolve things in case of a collision. Lets start with simple
 * ones and adapt the interface for every of them.
 */
#if 0
template<
class T,
class POINTER_TYPE,
class ANCHOR_ACCESSOR
>
struct resolve_single_linked
{
	typedef T item_type;
	typedef POINTER_TYPE<item_type>::type pointer_type;
	typedef anchor_single<T,POINTER_TYPE> anchor_type;
	typedef ANCHOR_ACCESSOR<anchor_type> anchor_accessor;

	/**
	 * @param colliding is the element at the slot where the collision has been detected.
	 * @param added is the element that shall be added to the hashtable. After
	 * returning, this element is a successful member of the hashtable.
	 */
	static void resolve( T* colliding, T* added )
	{
		T* nx = colliding;
		T* tmp;
		while(tmp = anchor_accessor::get(nx).get_next())
		{
			nx = tmp;
		}
		anchor_accessor::get(nx).set_next(added);
		anchor_accessor::get(added).set_next(0);
	}

	struct iterator
	{
		pointer_type* slot_position;
		pointer_type item;
		iterator& operator++(int);
		iterator& operator++();
	};
};
#endif

}

#if 0
template<
class T,
template<class,class> class COLLISION_RESOLUTION,
template<class,class> class DATA_ACCESS,
template<class> class POINTER_TYPE
      >
struct hash_intrusion_config // weird name but for OA style we don't have any anchor...
{
	/**
	 * Just define the type of the object that shall be stored
	 */
	typedef T item_type;

	/**
	 * Metafunction that transforms any item type into the pointer type
	 * We leave this as a metafunction and do not directly use a pointer type
	 * since maybe at other places we need pointers too but have some different
	 * item type. Just be flexible.
	 */
	template<class IT>
	struct pointer_type
	{
		typedef typename POINTER_TYPE<IT>::type type;
	};

	/**
	 * This should somehow resemble the slot type. It will depend on the actual
	 * planned collision resolution and also on where to store what, usually
	 * its though either the element itself or a pointer to it.
	 */
	template<class IT>
	struct slot_type
	{
	};

	/*
	 * anchor type depends on collision resolution. If its single/double linked
	 * list then we have anchors, if its some re-hashing or OA we just have
	 * nothing. Ideally the anchor would not eixst then giving us compile time
	 * errors.
	 */
	typedef typename COLLISION_RESOLUTION<T,
			STORE_HASH,
			POINTER_TYPE
			>::anchor_type anchor_type;
};
#endif

template<
class T0,
class T1,
class T2,
class T3,
class T4,
class T5
      >
struct hash_config
{
};

// Here we wrap the storage type that the user wants us to use in a hashtable 
template<class T>
struct storage_wrapper
{
};

template<class A>
struct anchor_accessor_single
{
    typedef typename A::item_type item_type;
    A* operator()( item_type* i )
    {
	// XXX This all is total mockup, we really need a way to
	// flexibly accessing the proper member (possible via member
	// pointers). This interface must be suitable for the
	// generated item types from UDTs.
	return &(i->anchor); // XXX make this a refernece
    }
};

#if 0
template<class T>
struct hash_anchor_oa
{
    /**
     * To mark this element as occupied/free/deleted
     */
    unsigned char status;
};

template<class T>
struct hash_item_double
{
    typedef T item_type;
    hash_anchor_double<T> anchor;
    T item;
};

/**
 * There is no real anchor for OA based items. Either we have just a plain
 * pointer to them or they are already fully in the table.
 */
template<class T>
struct hash_item_oa
{
    typedef T item_type;
};

template<class T>
struct hash_item_single
{
    typedef T item_type;
    hash_anchor_single<T> anchor;
    T item;
};

/**
 * For open addressing based hashtables there is the possibility of using this
 * only as collision resolution, and just store the pointers in there, or to
 * store the whole object in there. This is the variant of the item thats just
 * for the pointers.
 */
template<class T>
struct hash_item_oa_pointer
{
    typedef T item_type;
    item_type* item;
};

template<class T>
struct hash_item_oa_item
{
    typedef T item_type;
    item_type item;
};
#endif
/**
 * This class controls how the single items that are being stored in the table
 * are accessed.
 * If there is no special accessor that uses anchors embedded in the usertype,
 * then this will generate nodes containing the users type in them and all
 * inserts will be copies instead of "hanging" the node into the table.
 */
template<class T>
struct hash_accessor
{
    typedef typename T::item_type item_type;

};

template<class T>
struct default_accessor
{
	typedef decltype(T::anchor) anchor_type;
	/*
	struct anchor_type
	{
		static const bool store_hash = true;
	};
	*/

	anchor_type* operator()( T& t )
	{ 
		return &(t.anchor);
	}
	anchor_type* operator()( T* t )
	{ 
		return &(t->anchor);
	}
};

template<bool store_per_instance, class H>
struct hasher_storage_base;

template<class H>
struct hasher_storage_base<true,H>
{
	H hasher_instance;
};

template<class H>
struct hasher_storage_base<false,H>
{
	static H hasher_instance;
};

template<class H>
H hasher_storage_base<false,H>::hasher_instance;

template<bool store_per_instance, class H>
struct allocator_storage_base;

template<class H>
struct allocator_storage_base<true,H>
{
	H allocator_instance;
};

template<class H>
struct allocator_storage_base<false,H>
{
	static H allocator_instance;
};

template<class H>
H allocator_storage_base<false,H>::allocator_instance;

template<
class T,
class ATYPE,
ATYPE T::* AMEMBER
>
struct anchor_member_accessor
{
	typedef ATYPE anchor_type;
	ATYPE* operator()( T& t ) { return &( t.*AMEMBER); }
	ATYPE* operator()( T* t ) { return &( t->*AMEMBER); }
};

struct item_compare
{
	template<class T0, class T1>
	bool operator()( const T0& l, const T1& r ) const
	{
		return l == r;
	}
};

template< class T , class K , K T::* M >
struct member_compare
{
	template<class R>
	bool operator()( const T& l, const R& r ) const
	{
		return l.*M == r;
	}

	bool operator()( const T& l, const T& r ) const
	{
		return l.*M == r.*M;
	}

};
struct auto_size_always
{
	bool auto_size( ) const { return true; }
};

struct auto_size_never
{
	bool auto_size( ) const { return false; }
};

struct empty_base_owns
{
};

struct empty_base_size
{
};


enum class storage_levels
{
	storage_level_auto_size,
	storage_level_owns_items
};

struct auto_size_bool_storage
{
	bool a_size;

	template<int>
	void store( bool b )
	{
		a_size = b;
	}

	template<int>
	bool load( void ) const
	{
		return a_size;
	}
};

struct owns_items_bool_storage
{
	bool o_items;

	template<storage_levels>
	void store( bool b )
	{
		o_items = b;
	}

	template<storage_levels>
	bool load( void ) const
	{
		return o_items;
	}
};
/**
 * important: This must always go at least once through rebind to make the
 * mpl::if_c call so the use_bitset_storage parameter is reflected correctly.
 */
template<bool def = true, bool use_bitset_storage = true, class T = void >
struct auto_size_runtime
	: public boost::mpl::if_c<use_bitset_storage,empty_base_size,auto_size_bool_storage>::type
{
	auto_size_runtime( )
	{
		set_auto_size(def);
	}

	static const storage_levels storage_level = storage_levels::storage_level_auto_size;

	static const bool needs_bitset_storage = use_bitset_storage;

	void set_auto_size( bool en = true)
	{
		static_cast<T*>(this)->template store<storage_level>(en);
	}

	bool auto_size( ) const
	{
		return static_cast<const T*>(this)->template load<storage_level>();
	}

	template<class U>
	struct rebind
	{
		typedef auto_size_runtime<def,use_bitset_storage,
			typename boost::mpl::if_c<use_bitset_storage, U, auto_size_bool_storage>::type > other;
	};
};

template<bool def = true, bool use_bitset_storage = true, class T = void >
struct owns_items_runtime
	: public boost::mpl::if_c<use_bitset_storage,empty_base_owns,owns_items_bool_storage>::type
{
	owns_items_runtime( )
	{
		set_owns_items(def);
	}

	static const storage_levels storage_level = storage_levels::storage_level_owns_items;

	static const bool needs_bitset_storage = use_bitset_storage;

	void set_owns_items( bool en = true)
	{
		static_cast<T*>(this)->template store<storage_level>(en);
	}

	bool owns_items( ) const
	{
		return static_cast<const T*>(this)->template load<storage_level>();
	}

	template<class U>
	struct rebind
	{
		typedef owns_items_runtime<def,use_bitset_storage,
			typename boost::mpl::if_c<use_bitset_storage, U, owns_items_bool_storage>::type > other;
	};
};



template<class T0, class T1>
struct policy_bool_storage :
	T0::template rebind<policy_bool_storage<T0,T1> >::other,
	T1::template rebind<policy_bool_storage<T0,T1> >::other
{
	bool b0 : 1;
	bool b1 : 1;

	template<storage_levels N>
	void store( bool b )
	{
		switch(N)
		{
			case storage_levels::storage_level_auto_size:
				b0 = b;
				break;
			case storage_levels::storage_level_owns_items:
				b1 = b;
				break;
			// intentionally no default case, anything else here is UB
		}
	}

	template<storage_levels N>
	bool load( void ) const
	{
		switch(N)
		{
			case storage_levels::storage_level_auto_size:
				return b0;
			case storage_levels::storage_level_owns_items:
				return b1;
		}
	}
};

struct three_bytes_test
{
	char c0;
	char c1;
	char c2;
};
#if 0
// planned final class interface something like:
hash_table_impl<T,ACCESSOR,HASHER,
	store_hasher<true>,
	equal_comparator<COMPARE>,
	size_type<int>,
	auto_size<auto_size_runtime<false> >,

#endif

template<bool STORE_MASK, class SIZE_TYPE, class SLOT_RESIZER>
struct mask_storage_base;

template<class SIZE_TYPE, class SLOT_RESIZER>
struct mask_storage_base<true,SIZE_TYPE,SLOT_RESIZER>
{
	typedef SLOT_RESIZER slot_resizer;
	typedef typename slot_resizer::slot_selector hash_slot_selector;
	typedef SIZE_TYPE size_type;

	size_type h_mask;

	void reset_mask( size_t len )
	{
		h_mask = hash_slot_selector::mask_from_length(len);
//		std::cerr << "Setting h_mask to " << h_mask << " from len " << len << "\n";
	}

	size_type hash_mask( size_t /*len*/ ) const
	{
		return h_mask;
	}
};

template<class SIZE_TYPE, class SLOT_RESIZER>
struct mask_storage_base<false,SIZE_TYPE,SLOT_RESIZER>
{
	typedef SLOT_RESIZER slot_resizer;
	typedef typename slot_resizer::slot_selector hash_slot_selector;
	typedef SIZE_TYPE size_type;

	void reset_mask( size_t /*len*/ )
	{
	}

	size_type hash_mask( size_t len ) const
	{
		return hash_slot_selector::mask_from_length(len);
	}
};

/**
 */
template<class T
, class SIZE_TYPE// = size_t
, class HASHER// = void//int//default_hasher<T>
, bool STORE_HASHER// = true
, bool COMPARE_HASH// = false
, bool STORE_MASK//   = true
, class SLOT_RESIZER// = iwear::resize_primetable_15<>
, class ANCHOR_ACCESSOR// = dummy_accessor
, class COMPARE// = void
, class COLLISION_RESOLUTION// = iwear::resolution_single_linked_list
, class AUTOSIZE// = iwear::auto_size_runtime<true,true>
, class OWNAGE// = iwear::owns_items_runtime<true,true>
    >
class hash_table_impl :
	protected hasher_storage_base<STORE_HASHER,HASHER>,
	protected mask_storage_base<STORE_MASK,SIZE_TYPE,SLOT_RESIZER>,
//	protected allocator_storage_base<STORE_ALLOCATOR,ALLOCATOR>
	// XXX MPL check for whether we do not better derive from empty base
	public policy_bool_storage<AUTOSIZE, OWNAGE>
	// XXX later check how many size_type members we have at most and at least.
	// If this differs much, and they are also shattered around then it could
	// make sense to do something like the policy_bool_storage for size_type so
	// that alignment issues due to derivation do not play any role.
{
public:
	typedef hash_table_impl<T,SIZE_TYPE,HASHER,STORE_HASHER,COMPARE_HASH,STORE_MASK,SLOT_RESIZER,ANCHOR_ACCESSOR,COMPARE,COLLISION_RESOLUTION,AUTOSIZE,OWNAGE> this_type;


	typedef mask_storage_base<STORE_MASK,SIZE_TYPE,SLOT_RESIZER> mask_storage;

	typedef policy_bool_storage<AUTOSIZE, OWNAGE> pbstorage;
    /**
     * This is the selector type that will give us many mayn informations about
     * other types.
     */
//    typedef S hash_selector;

    /**
     * This is the type of the items or "nodes" that the user will put into our
     * hashtable. Depending on the selector, our array will contain those items
     * explicitly, or pointers to them, that then will either resemble singly
     * linked or doubly linked lists.
     */
    typedef T item_type;

	typedef SIZE_TYPE size_type;
	typedef item_type* slot_item_type;
//	typedef std::vector<slot_item_type> table_type;
	typedef slot_item_type* table_type;
	typedef slot_item_type* table_iterator;

	typedef SLOT_RESIZER slot_resizer;
	typedef typename slot_resizer::slot_selector hash_slot_selector;
	typedef ANCHOR_ACCESSOR anchor_accessor;
	typedef typename anchor_accessor::anchor_type anchor_type;
	static_assert( COMPARE_HASH ? anchor_type::store_hash : true, "When COMPARE_HASH is set, STORE_HASHER must be set too");

	typedef COMPARE compare;

//	typedef INSERTER inserter;
//	typedef typename INSERTER::template rebind<ANCHOR_ACCESSOR>::other inserter;

	typedef COLLISION_RESOLUTION collision_resolver;
	typedef typename collision_resolver::inserter::template rebind<anchor_accessor>::other inserter;

	struct iterator
	{
		table_iterator table;
		table_iterator table_end;
		item_type* item;
		iterator( table_iterator t, table_iterator end ) :
			table(t),
			table_end(end),
			item(nullptr)
		{
			if( table != table_end )
			{
				item = *table;
			}
			while(!item && table != table_end )
			{
				++table;
				item = *table;
			}
		}

		void _dump( std::ostream& out ) const
		{
			out << "it[" << table << "," << table_end << "," << item << "]\n";
		}

		void advance( )
		{
//			std::cout << "advance on " << (void*)table << "\n";
//			std::cout << "item = " << item << "\n";
//			std::cout << "item->anchor.next = " << item->anchor.anchor.get_next() << "\n";
			anchor_accessor aa;
			item = aa(item)->anchor.get_next();
//			item = item->anchor.anchor.get_next();
			
//			std::cout << "item = " << item << "\n";
//			std::cout << "table = " << table << "\n";
//			if( table ) { std::cout << "*table = " << *table << "\n"; }
//			std::cout << "table_end = " << table_end << "\n";
			if( item == nullptr )
			{
				while( table != table_end )
				{
//					std::cout << "table = " << table << "\n";
//					if( table ) { std::cout << "*table = " << *table << "\n"; }
//					std::cout << "table_end = " << table_end << "\n";

					++table;
					if( table != table_end && *table )
					{
						item = *table;
						break;
					}
				}
			}
//			std::cout << "table = " << table << "\n";
//			if( table ) { std::cout << "*table = " << *table << "\n"; }
//			std::cout << "table_end = " << table_end << "\n";
//			std::cout << "item = " << item << "\n";
		}

		iterator& operator++( )
		{
			advance();
			return *this;
		}

		item_type& operator*()
		{
//			std::cout << "item = " << item << "\n";
			
			return *item;
		}

		bool operator!=( const iterator& other ) const
		{
//			std::cerr << (void*)table << " != " << (void*)other.table << "\n";
			if( table != other.table )
			{
				return true;
			}
//			std::cerr << (void*)item << " != " << (void*)other.item << "\n";
			if( item != other.item )
			{
				return true;
			}
			return false;
		}
	};
//    typedef typename hash_selector::size_type size_type;
//    typedef K key_type;
//    typedef typename hash_selector::template slot_item<item_type>::type slot_item_type;
//    typedef typename hash_selector::template add_pointer<slot_item_type>::type table_type;

    /**
     * We are a nullary metafunction returning ourselves. Who knows what this
     * is good for...
     */
    typedef hash_table_impl type;
//    typedef V<slot_item_type> sequence_type;
//    typedef IT iterator;
//    typedef IT const_iterator;
 /*   template<class T,...>
    struct 
    {
	typedef hash_table_impl<T,...> type;
    } helper_type;
    */
private:
	table_type data;

	/**
	 * Amount of elements actually contained within the hashtable.
	 */
	size_type elem_size;

	/**
	 * The length of the slots array/vector.
	 */
	size_type h_length;

	void set_slots_size( size_type h_l )
	{
//		std::cerr << "Set slot size to " << h_l << "\n";
		h_length = h_l;
		this->reset_mask(h_l);
	}
protected:
public:
	hash_table_impl( size_type i_s ) :
		elem_size(0)
	{
		set_slots_size(slot_resizer::optimal_size(i_s));
		data = new slot_item_type[h_length];
		// XXX This fill is redundant if the slot item type is a UDT. It makes
		// only sense if it is a pointer type.
		std::fill_n( data, h_length, slot_item_type());
#ifdef DEBUG
		std::cerr << "i_s = " << i_s << ", h_length " << h_length << ", h_mask = " << this->hash_mask(table_size()) << "\n";
#endif
	}

	/* currently broken, recreate as soon as the above ctor is stable and we
	 * can provide useful defaults here.
	 * XXX Make sure empty hashtables work well with no dynamic storage
	 * allocated. (especially iterators etc. will have to work properly)
	hash_table_impl( ) :
		data(0),
		elem_size(0),
		h_mask(0)
	{
	}
	*/

	~hash_table_impl( )
	{
		// XXX allocation and deallocation should be routed through a policy so
		// we can use policies that allocate in e.g. memory mapped files using
		// relative pointers.
		clear();
		delete[] data;
	}

	hash_table_impl( const hash_table_impl& ) = delete;
	hash_table_impl& operator=( const hash_table_impl& ) = delete;

	iterator begin( )
	{
		return iterator(&data[0],&data[0] + table_size());
	}

	iterator end( ) 
	{
		return iterator(&data[0] + table_size() ,&data[0] + table_size());
	}
    // insert variant that allows duplicates and uses single linked lists for
    // collision resolution.
    /**
     * @returns true if the insert was successfully, the item should be removed
     * from the structure prior to deletion, as removing will likely need
     * access to the item. If false is returned, this means that the item has
     * not been inserted. In this case the user is always responsible for
     * handling this item, e.g. delete it.
     */
//    IWEAR_WARN_UNUSED_RESULT
	bool insert( item_type* i )
	{
		// XXX note: a shrink on insert doesn't really make sense. If the table
		// is bigger then it is because someone has removed something without
		// having the table shrink, or its being constructed to hold many
		// elements.
		if( maybe_grow() )
		{
#ifdef DEBUG
			std::cerr << "Hashtable changed its size\n";
#endif
		}
		return insert_direct( i );
	}

	/*private*/
	bool insert_direct( item_type* i )
	{
#ifdef DEBUG
//		std::cerr << "sizeof(pbstorage) " << sizeof(pbstorage) << "\n";
#endif
#ifdef DEBUG
		std::cerr << "Inserting " << i << "\n";
#endif

		static_assert( sizeof(this->hasher_instance(i)) != 0, "We need to be able to call hasher_instance(i), if we are not, then most likely the hasher is wrong");
		// generate hash
		size_type hvalue = this->hasher_instance(i);
#ifdef DEBUG
		std::cerr << "hvalue = " << hvalue << "\n";
#endif
		// generate slot position
		hash_slot_selector selector;
		size_type idx = selector.hash_to_index(hvalue,this->hash_mask(table_size()));
#ifdef DEBUG
		std::cerr << "idx = " << idx << ", data is " << (void*)data  << "\n";
#endif

		// ask the reselector if the slot has to be reselected, this could be
		// the case if:
		// - we are doing open addressing (or first step open addressing) only
		//   (chaining will always return the same slot)

		collision_resolver cr;
		// the resolver will possibly select a new slot used to insert things,
		// for chaining resolution this is a no-op that should be optimized
		// away.
		idx = cr.reselect(idx,&data[0],table_size());

		// get the slot at hands...
		// although the table_type might be some relative pointer thingie, we
		// use a plain pointer here since this is for internal purposes only
		// and any compatible pointer should have conversions to/from us

		bool ret = inserter::insert(i,idx,&data[0]);
		if( ret )
		{
			reset_size( elem_size + 1 );
		}
		// XXX check whether duplicates are allowed
		// do collision prevention
		// set slot and/or do list linking, if not already done by
		// collision prevention
		return false;
	}

	void reset_size( size_type sz )
	{
		elem_size = sz;
	}

	void resize_slots( size_t nslots )
	{
#ifdef DEBUG
		std::cerr << "resize_slots(" << nslots << ")\n";
#endif
		assert( nslots >= size() );
		// XXX Invent some smart pointer like things to make this all exception
		// safe.

		// Save a bunch of useful old values
		table_type odata = data;
		size_type olen = h_length;
		size_type omask = this->hash_mask(h_length);
#ifdef DEBUG
		size_type oelem = elem_size;
#endif

		// now set the new wanted values
		set_slots_size(nslots);
		data = new slot_item_type[h_length];
		std::fill_n( data, h_length, slot_item_type());

		// Since for inserting we pretend to be an empty hashtable currently we
		// set our size to 0
		reset_size(0);

#ifdef DEBUG
#ifdef DEBUG
		std::cerr << "re-inserting " << oelem << " elements \n";
#endif
#endif
		for( size_t i = 0; i < olen; ++i )
		{
			slot_item_type it = odata[i];
			while(it)
			{
#ifdef DEBUG
				std::cerr << "re-inserting item chain starting at " << (void*)it << "\n";
#endif
				// do an erase() on the old data (needs to be kept in sync with
				// erase()
				size_type hvalue = this->hasher_instance(it);
				hash_slot_selector selector;
				size_type idx = selector.hash_to_index(hvalue,omask);
				inserter::remove(it,idx,&odata[0]);

				// this will insert into the new storage, not checking and/or
				// triggering any resizes.
				insert_direct(it);
				it = odata[i];
			}
		}
#ifdef DEBUG
		assert( oelem == elem_size );
#endif
		// data has been transferred, dispose of the slots storage
		delete[] odata;
	}

	// XXX when we have a "never resize" or "never shrink" policy, make this
	// function not remove the internal storage table. Otherwise pretend that
	// "shrink to fit" was called.
	/**
	 */
	bool clear ( )
	{
#ifdef DEBUG
		std::cerr << "Clearing hashtable of " << size() << " elements \n";
#endif
		for( size_t i = 0; i < h_length; ++i )
		{
			slot_item_type it = data[i];
			while(it)
			{
//				std::cout << "i = " << i << "\n";
//				std::cout << "it = " << it << "\n";
				
				
				// do an erase() on the old data (needs to be kept in sync with
				// erase()
//				static_assert( sizeof(this->hasher_instance(it)) != 0, "We need to be able to call hasher_instance(i), if we are not, then most likely the hasher is wrong");
				size_type hvalue = this->hasher_instance(it);
				hash_slot_selector hs;
				size_type idx = hs.hash_to_index(hvalue,this->hash_mask(this->table_size()));
//				std::cout << "idx = " << idx << "\n";
//				std::cout << "hvalue = " << hvalue << "\n";
//				std::cout << "it->i = " << it->i << "\n";

				assert( i == idx );
				

				inserter::remove(it,idx,&data[0]);
				if( this->owns_items() )
				{
					delete it;
				}
				it = data[i];
			}
		}
		return true;
	}


	void _reset( )
	{
		for( size_t i = 0; i < h_length; ++i )
		{
			data[i] = nullptr;
		}
		h_length=0;
	}

	void to_dot( std::ostream& out )  const
	{
		out << "digraph hashtable {\n";
		out << "node [ shape=\"box\" ];\n";
		for( size_t i = 0; i < h_length; ++i )
		{
			out << "bucket_" << i << " [ label=\"" << i << "\" ];\n";
			if( data[i] )
			{
				out << "bucket_" << i << " -> node_" << data[i] << ";\n";
				anchor_accessor aa;
				aa(data[i])->anchor.template to_dot<anchor_accessor>(out);

				hash_slot_selector selector;
				size_type hvalue = this->hasher_instance(data[i]);
				size_type idx = selector.hash_to_index(hvalue,this->hash_mask(table_size()));
				assert(idx == i );
			}

		}
		out << "};\n";
	}

	/**
	 * @returns true if a table resize has been done
	 */
	bool shrink_to_fit( )
	{
		// XXX unimplemented
		return false;
	}

	bool empty( ) const
	{
		return elem_size == 0;
	}

	size_type max_size( ) const
	{
		return slot_resizer::max_size();
	}
	/**
	 * @param num is the number of elements to prepare the hashtable for being
	 * stored. If this is bigger than what the current size of the hashtable is
	 * optimal for, then a resize will be triggered.
	 * @returns true if the size of the hashtable was actually changed.
	 */
	bool reserve( size_t num )
	{
		size_type sz = slot_resizer::optimal_size(num);
		if( sz > table_size() )
		{
			resize_slots( sz );
			return true;
		}
		return false;
	}

    /**
     * Checks if the table needs to be resized according to our
     * resize policy and returns true if it was done, false
     * otherwise.
     */
	/*private*/
//	__attribute__((noinline))
	bool maybe_grow( void )
	{
		// XXX split auto resize policy into "auto grow" and "auto shrink".
		// Some people might never want the table to shrink automatically but
		// to grow. We will then also have to make the actual calculations for
		// grow/shrink depending on those values as they are now are done
		// together.

		// check if we do auto size at all
		if( this->auto_size() )
		{
#ifdef DEBUG
			std::cerr << "auto_resize check\n";
#endif
			if( __builtin_expect(slot_resizer::need_grow( size(), table_size() ),0) )
			{
#ifdef DEBUG
				std::cerr << "auto resize triggered\n";
#endif
				resize_slots( slot_resizer::optimal_size(size()) );
			}
		}
		return false;
	}

	bool maybe_shrink( void )
	{
		// check if we do auto size at all
		if( this->auto_size() )
		{
#ifdef DEBUG
			std::cerr << "auto_resize check\n";
#endif
			if( slot_resizer::need_shrink( size(), table_size() ) )
			{
#ifdef DEBUG
				std::cerr << "auto resize triggered\n";
#endif
				resize_slots( slot_resizer::optimal_size(size()) );
			}
		}
		return false;
	}
	/*
	iterator erase( iterator i )
	{
		iterator tmp(i);
		++tmp;
		erase(&*i);
		return tmp;
	}
*/

	bool erase( item_type* it )
	{
		// XXX Make sure that for elements caching their hash values we reset
		// the hash value to "unstored"
		size_type hvalue = hasher_instance(it);
		size_type idx = hash_slot_selector()(hvalue,this->hash_mask(table_size()));
		bool ret = inserter::remove(it,idx,&data[0]);

		if( ret )
		{
			maybe_shrink();
		}

		return ret;
	}

    /**
     *
     */
    item_type* find( ) { return const_cast<item_type*>(const_cast<const type*>(this)->find()); }

    /**
     * Find something.
     * @param k is the key to search in the hashtable for. There must exist an
     * operator() in the hash template parameter that takes such a type, and
     * also this must be comparable via operator== to the item_type.
	 * XXX Think about whether it makes sense to return an iterator instead.
	 * Most of the cases we don't want anything besides the item, and for
	 * iterating any position is as good as the one from find, since after all
	 * we cannot expect to know anything about where things went.
     */
	template<class K>
	const item_type* find( const K& k ) const
	{
		// XXX Try to figure out if we do the exact same sequence of operations
		// for find/insert too, and if yes lets have a look if we can put it
		// into one single function, so that we only have one place to maintain
		// it.
		size_type hvalue = this->hasher_instance(k);
#ifdef DEBUG
		std::cerr << "Trying to find a K \"" << k << "\" with hash " << hvalue << "\n";
#endif

		hash_slot_selector selector;
		size_type idx = selector.hash_to_index(hvalue,this->hash_mask(table_size()));
#ifdef DEBUG
		std::cerr << "First trying at index idx = " << idx << ", data is " << (void*)data  << "\n";
#endif

		slot_item_type* slot = data + idx;
#ifdef DEBUG
		std::cerr << "Chosen slot = " << (void*)slot << "\n";
#endif
		if( *slot )
		{
			anchor_accessor aa;
			item_type* next = *slot;
			while( next && !compare()(*next,k) )
			{
				next = aa(next)->anchor.get_next();
			}
#ifdef DEBUG
			std::cerr << "Returning element at " << (void*)next << "\n";
#endif
			return next;
		}
		else
		{
#ifdef DEBUG
			std::cerr << "Chosen slot is empty\n";
#endif
			return 0;
		}
	}


    /**
     * Returns the amount of occupied elements.
     */
	size_type size() const { return elem_size; }

	size_type table_size() const
	{
		return h_length;
	}
};

// below come some convenience wrapper templates that behave more or less like the stdlib alternatives.
/*
   template<class T, class HT<T> = hash_table_impl >
hash_set
{
public:
    typedef size_t size_type;
    typedef T item_type;
    typedef typename HT::accesor_type accessor_type;
private:
protected:
public:
    bool insert( item_type& );
    bool insert( item_type* );
    bool erase( item_type& );
    bool erase( item_type* );
    iterator find( item_type* );
    iterator find( item_type& );
    iterator find( key_type& );
    iterator find( size_type );
    void reserve( size_type );
    size_type capacity( void ) const;
    bool resize( size_type );

    const_iterator begin( void ) const;
    iterator begin( void );
    const_iterator end( void ) const;
    iterator end( void );

};

template<class T, class HT<...> = hash_table_impl >
hash_map
{
};
*/

template<bool sh> 
struct store_hasher
{
	template<class ht>
	struct mangle
	{
		typedef typename ht::template set_store_hasher<sh>::type type;
	};
};

template<class HASHER>
struct hasher
{
	template<class ht>
	struct mangle
	{
		typedef typename ht::template set_hasher< HASHER >::type type;
	};
};

template<class T>
struct default_hasher
{
	uint64_t operator()( const T& t ) const
	{
		return std::hash<T>()(t);
	}
};


struct mangle_noop
{
	template<class T>
	struct mangle
	{
		typedef T type;
	};
};

template<class T
, class SIZE_TYPE = uint32_t
, class HASHER = default_hasher<T>
, bool STORE_HASHER = true
, bool COMPARE_HASH = false
, bool STORE_MASK   = true
, class SLOT_RESIZER = iwear::resize_primetable_15<>
, class ANCHOR_ACCESSOR = iwear::default_accessor<T>
, class COMPARE = iwear::item_compare
, class COLLISION_RESOLUTION = iwear::resolution_single_linked_list
, class AUTOSIZE = iwear::auto_size_runtime<true,true>
, class OWNAGE = iwear::owns_items_runtime<true,true>
    >
struct hashtable_parameter_collector
{
	typedef hashtable_parameter_collector<T,SIZE_TYPE,HASHER,STORE_HASHER,COMPARE_HASH,STORE_MASK,SLOT_RESIZER,ANCHOR_ACCESSOR,COMPARE,COLLISION_RESOLUTION,AUTOSIZE,OWNAGE> this_type;

	template<class n_T>
	struct set_item_type
	{
		typedef hashtable_parameter_collector<n_T,SIZE_TYPE,HASHER,STORE_HASHER,COMPARE_HASH,STORE_MASK,SLOT_RESIZER,ANCHOR_ACCESSOR,COMPARE,COLLISION_RESOLUTION,AUTOSIZE,OWNAGE> type;
	};

	template<bool n_STORE_HASHER>
	struct set_store_hasher
	{
		typedef hashtable_parameter_collector<T,SIZE_TYPE,HASHER,n_STORE_HASHER,COMPARE_HASH,STORE_MASK,SLOT_RESIZER,ANCHOR_ACCESSOR,COMPARE,COLLISION_RESOLUTION,AUTOSIZE,OWNAGE> type;
	};

	template<class n_SLOT_RESIZER>
	struct set_slot_resizer
	{
		typedef hashtable_parameter_collector<T,SIZE_TYPE,HASHER,STORE_HASHER,COMPARE_HASH,STORE_MASK,n_SLOT_RESIZER,ANCHOR_ACCESSOR,COMPARE,COLLISION_RESOLUTION,AUTOSIZE,OWNAGE> type;
	};

	template<class n_HASHER>
	struct set_hasher
	{
//		static_assert(sizeof(n_HASHER) == 0, "Just to print this thing");
		typedef hashtable_parameter_collector<T,SIZE_TYPE,n_HASHER,STORE_HASHER,COMPARE_HASH,STORE_MASK,SLOT_RESIZER,ANCHOR_ACCESSOR,COMPARE,COLLISION_RESOLUTION,AUTOSIZE,OWNAGE> type;
	};

	template<class>
	struct get_hashtable_type
	{
		typedef iwear::hash_table_impl<T,SIZE_TYPE,HASHER,STORE_HASHER,COMPARE_HASH,STORE_MASK,SLOT_RESIZER,ANCHOR_ACCESSOR,COMPARE,COLLISION_RESOLUTION,AUTOSIZE,OWNAGE> hashtable_type;
	};

	template<class n_COLLISION_RESOLUTION>
	struct set_collision_resolution
	{
		typedef hashtable_parameter_collector<T,SIZE_TYPE,HASHER,STORE_HASHER,COMPARE_HASH,STORE_MASK,SLOT_RESIZER,ANCHOR_ACCESSOR,COMPARE,n_COLLISION_RESOLUTION,AUTOSIZE,OWNAGE> type;
	};
};

template<class T
,class MANGLE00 = mangle_noop
,class MANGLE01 = mangle_noop
,class MANGLE02 = mangle_noop
,class MANGLE03 = mangle_noop
,class MANGLE04 = mangle_noop
,class MANGLE05 = mangle_noop
,class MANGLE06 = mangle_noop
,class MANGLE07 = mangle_noop
,class MANGLE08 = mangle_noop
,class MANGLE09 = mangle_noop
,class MANGLE10 = mangle_noop
,class MANGLE11 = mangle_noop
,class MANGLE12 = mangle_noop
,class MANGLE13 = mangle_noop
,class MANGLE14 = mangle_noop
>
struct gen_hashtable
{
	typedef hashtable_parameter_collector<T> raw;
	typedef typename MANGLE00::template mangle<raw>::type mangled00;
	typedef typename MANGLE01::template mangle<mangled00>::type mangled01;
	typedef typename MANGLE02::template mangle<mangled01>::type mangled02;
	typedef typename MANGLE03::template mangle<mangled02>::type mangled03;
	typedef typename MANGLE04::template mangle<mangled03>::type mangled04;
	typedef mangled04 type;

	template<class>
	struct get_hashtable_type
	{
		typedef typename type::template get_hashtable_type<T>::hashtable_type hashtable_type;
	};
};

template<class T ,class... MANGLE >
struct hashtable :
	gen_hashtable<T ,MANGLE... >::template get_hashtable_type<T>::hashtable_type
{
	typedef typename 
		gen_hashtable<T ,MANGLE... >::template get_hashtable_type<T>::hashtable_type base_type;

	template<class... Tx>
	hashtable( Tx&&... tx ) :
		base_type( std::forward<Tx>(tx)... )
	{
	}
};



} // namespace iwear

/*
 * Future improvements
 * - make the load ratios optionally configurable at runtime.
 */
// vim: tabstop=4 shiftwidth=4 noexpandtab