GIMPACT/core/gim_hash_table.h

#ifndef GIM_HASH_TABLE_H_INCLUDED
#define GIM_HASH_TABLE_H_INCLUDED
/*! \file gim_trimesh_data.h
\author Francisco Leon Najera
*/
/*
-----------------------------------------------------------------------------
This source file is part of GIMPACT Library.

For the latest info, see http://gimpact.sourceforge.net/

Copyright (c) 2006 Francisco Leon Najera. C.C. 80087371.
email: projectileman@yahoo.com

 This library is free software; you can redistribute it and/or
 modify it under the terms of EITHER:
   (1) The GNU Lesser General Public License as published by the Free
       Software Foundation; either version 2.1 of the License, or (at
       your option) any later version. The text of the GNU Lesser
       General Public License is included with this library in the
       file GIMPACT-LICENSE-LGPL.TXT.
   (2) The BSD-style license that is included with this library in
       the file GIMPACT-LICENSE-BSD.TXT.
   (3) The zlib/libpng license that is included with this library in
       the file GIMPACT-LICENSE-ZLIB.TXT.

 This library is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the files
 GIMPACT-LICENSE-LGPL.TXT, GIMPACT-LICENSE-ZLIB.TXT and GIMPACT-LICENSE-BSD.TXT for more details.

-----------------------------------------------------------------------------
*/

#include "gim_radixsort.h"

#define GIM_INVALID_HASH 0xffffffff  //!< A very very high value
#define GIM_DEFAULT_HASH_TABLE_SIZE 380
#define GIM_DEFAULT_HASH_TABLE_NODE_SIZE 4
#define GIM_HASH_TABLE_GROW_FACTOR 2

#define GIM_MIN_RADIX_SORT_SIZE 860  //!< calibrated on a PIII

template <typename T>
struct GIM_HASH_TABLE_NODE
{
	GUINT m_key;
	T m_data;
	GIM_HASH_TABLE_NODE()
	{
	}

	GIM_HASH_TABLE_NODE(const GIM_HASH_TABLE_NODE& value)
	{
		m_key = value.m_key;
		m_data = value.m_data;
	}

	GIM_HASH_TABLE_NODE(GUINT key, const T& data)
	{
		m_key = key;
		m_data = data;
	}

	bool operator<(const GIM_HASH_TABLE_NODE<T>& other) const
	{
		///inverse order, further objects are first
		if (m_key < other.m_key) return true;
		return false;
	}

	bool operator>(const GIM_HASH_TABLE_NODE<T>& other) const
	{
		///inverse order, further objects are first
		if (m_key > other.m_key) return true;
		return false;
	}

	bool operator==(const GIM_HASH_TABLE_NODE<T>& other) const
	{
		///inverse order, further objects are first
		if (m_key == other.m_key) return true;
		return false;
	}
};

///Macro for getting the key
class GIM_HASH_NODE_GET_KEY
{
public:
	template <class T>
	inline GUINT operator()(const T& a)
	{
		return a.m_key;
	}
};

///Macro for comparing the key and the element
class GIM_HASH_NODE_CMP_KEY_MACRO
{
public:
	template <class T>
	inline int operator()(const T& a, GUINT key)
	{
		return ((int)(a.m_key - key));
	}
};

///Macro for comparing Hash nodes
class GIM_HASH_NODE_CMP_MACRO
{
public:
	template <class T>
	inline int operator()(const T& a, const T& b)
	{
		return ((int)(a.m_key - b.m_key));
	}
};

//! Sorting for hash table
/*!
switch automatically between quicksort and radixsort
*/
template <typename T>
void gim_sort_hash_node_array(T* array, GUINT array_count)
{
	if (array_count < GIM_MIN_RADIX_SORT_SIZE)
	{
		gim_heap_sort(array, array_count, GIM_HASH_NODE_CMP_MACRO());
	}
	else
	{
		memcopy_elements_func cmpfunc;
		gim_radix_sort(array, array_count, GIM_HASH_NODE_GET_KEY(), cmpfunc);
	}
}

// Note: assumes long is at least 32 bits.
#define GIM_NUM_PRIME 28

static const GUINT gim_prime_list[GIM_NUM_PRIME] =
	{
		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};

inline GUINT gim_next_prime(GUINT number)
{
	//Find nearest upper prime
	GUINT result_ind = 0;
	gim_binary_search(gim_prime_list, 0, (GIM_NUM_PRIME - 2), number, result_ind);

	// inv: result_ind < 28
	return gim_prime_list[result_ind];
}

//! A compact hash table implementation
/*!
A memory aligned compact hash table that coud be treated as an array.
It could be a simple sorted array without the overhead of the hash key bucked, or could
be a formely hash table with an array of keys.
You can use switch_to_hashtable() and switch_to_sorted_array for saving space or increase speed.
</br>

<ul>
<li> if node_size = 0, then this container becomes a simple sorted array allocator. reserve_size is used for reserve memory in m_nodes.
When the array size reaches the size equivalent to 'min_hash_table_size', then it becomes a hash table by calling check_for_switching_to_hashtable.
<li> If node_size != 0, then this container becomes a hash table for ever
</ul>

*/
template <class T>
class gim_hash_table
{
protected:
	typedef GIM_HASH_TABLE_NODE<T> _node_type;

	//!The nodes
	//array< _node_type, SuperAllocator<_node_type> > m_nodes;
	gim_array<_node_type> m_nodes;
	//SuperBufferedArray< _node_type > m_nodes;
	bool m_sorted;

	///Hash table data management. The hash table has the indices to the corresponding m_nodes array
	GUINT* m_hash_table;  //!<
	GUINT m_table_size;   //!<
	GUINT m_node_size;    //!<
	GUINT m_min_hash_table_size;

	//! Returns the cell index
	inline GUINT _find_cell(GUINT hashkey)
	{
		_node_type* nodesptr = m_nodes.pointer();
		GUINT start_index = (hashkey % m_table_size) * m_node_size;
		GUINT end_index = start_index + m_node_size;

		while (start_index < end_index)
		{
			GUINT value = m_hash_table[start_index];
			if (value != GIM_INVALID_HASH)
			{
				if (nodesptr[value].m_key == hashkey) return start_index;
			}
			start_index++;
		}
		return GIM_INVALID_HASH;
	}

	//! Find the avaliable cell for the hashkey, and return an existing cell if it has the same hash key
	inline GUINT _find_avaliable_cell(GUINT hashkey)
	{
		_node_type* nodesptr = m_nodes.pointer();
		GUINT avaliable_index = GIM_INVALID_HASH;
		GUINT start_index = (hashkey % m_table_size) * m_node_size;
		GUINT end_index = start_index + m_node_size;

		while (start_index < end_index)
		{
			GUINT value = m_hash_table[start_index];
			if (value == GIM_INVALID_HASH)
			{
				if (avaliable_index == GIM_INVALID_HASH)
				{
					avaliable_index = start_index;
				}
			}
			else if (nodesptr[value].m_key == hashkey)
			{
				return start_index;
			}
			start_index++;
		}
		return avaliable_index;
	}

	//! reserves the memory for the hash table.
	/*!
    \pre hash table must be empty
    \post reserves the memory for the hash table, an initializes all elements to GIM_INVALID_HASH.
    */
	inline void _reserve_table_memory(GUINT newtablesize)
	{
		if (newtablesize == 0) return;
		if (m_node_size == 0) return;

		//Get a Prime size

		m_table_size = gim_next_prime(newtablesize);

		GUINT datasize = m_table_size * m_node_size;
		//Alloc the data buffer
		m_hash_table = (GUINT*)gim_alloc(datasize * sizeof(GUINT));
	}

	inline void _invalidate_keys()
	{
		GUINT datasize = m_table_size * m_node_size;
		for (GUINT i = 0; i < datasize; i++)
		{
			m_hash_table[i] = GIM_INVALID_HASH;  // invalidate keys
		}
	}

	//! Clear all memory for the hash table
	inline void _clear_table_memory()
	{
		if (m_hash_table == NULL) return;
		gim_free(m_hash_table);
		m_hash_table = NULL;
		m_table_size = 0;
	}

	//! Invalidates the keys (Assigning GIM_INVALID_HASH to all) Reorders the hash keys
	inline void _rehash()
	{
		_invalidate_keys();

		_node_type* nodesptr = m_nodes.pointer();
		for (GUINT i = 0; i < (GUINT)m_nodes.size(); i++)
		{
			GUINT nodekey = nodesptr[i].m_key;
			if (nodekey != GIM_INVALID_HASH)
			{
				//Search for the avaliable cell in buffer
				GUINT index = _find_avaliable_cell(nodekey);

				if (m_hash_table[index] != GIM_INVALID_HASH)
				{  //The new index is alreade used... discard this new incomming object, repeated key
					btAssert(m_hash_table[index] == nodekey);
					nodesptr[i].m_key = GIM_INVALID_HASH;
				}
				else
				{
					//;
					//Assign the value for alloc
					m_hash_table[index] = i;
				}
			}
		}
	}

	//! Resize hash table indices
	inline void _resize_table(GUINT newsize)
	{
		//Clear memory
		_clear_table_memory();
		//Alloc the data
		_reserve_table_memory(newsize);
		//Invalidate keys and rehash
		_rehash();
	}

	//! Destroy hash table memory
	inline void _destroy()
	{
		if (m_hash_table == NULL) return;
		_clear_table_memory();
	}

	//! Finds an avaliable hash table cell, and resizes the table if there isn't space
	inline GUINT _assign_hash_table_cell(GUINT hashkey)
	{
		GUINT cell_index = _find_avaliable_cell(hashkey);

		if (cell_index == GIM_INVALID_HASH)
		{
			//rehashing
			_resize_table(m_table_size + 1);
			GUINT cell_index = _find_avaliable_cell(hashkey);
			btAssert(cell_index != GIM_INVALID_HASH);
		}
		return cell_index;
	}

	//! erase by index in hash table
	inline bool _erase_by_index_hash_table(GUINT index)
	{
		if (index >= m_nodes.size()) return false;
		if (m_nodes[index].m_key != GIM_INVALID_HASH)
		{
			//Search for the avaliable cell in buffer
			GUINT cell_index = _find_cell(m_nodes[index].m_key);

			btAssert(cell_index != GIM_INVALID_HASH);
			btAssert(m_hash_table[cell_index] == index);

			m_hash_table[cell_index] = GIM_INVALID_HASH;
		}

		return this->_erase_unsorted(index);
	}

	//! erase by key in hash table
	inline bool _erase_hash_table(GUINT hashkey)
	{
		if (hashkey == GIM_INVALID_HASH) return false;

		//Search for the avaliable cell in buffer
		GUINT cell_index = _find_cell(hashkey);
		if (cell_index == GIM_INVALID_HASH) return false;

		GUINT index = m_hash_table[cell_index];
		m_hash_table[cell_index] = GIM_INVALID_HASH;

		return this->_erase_unsorted(index);
	}

	//! insert an element in hash table
	/*!
    If the element exists, this won't insert the element
    \return the index in the array of the existing element,or GIM_INVALID_HASH if the element has been inserted
    If so, the element has been inserted at the last position of the array.
    */
	inline GUINT _insert_hash_table(GUINT hashkey, const T& value)
	{
		if (hashkey == GIM_INVALID_HASH)
		{
			//Insert anyway
			_insert_unsorted(hashkey, value);
			return GIM_INVALID_HASH;
		}

		GUINT cell_index = _assign_hash_table_cell(hashkey);

		GUINT value_key = m_hash_table[cell_index];

		if (value_key != GIM_INVALID_HASH) return value_key;  // Not overrited

		m_hash_table[cell_index] = m_nodes.size();

		_insert_unsorted(hashkey, value);
		return GIM_INVALID_HASH;
	}

	//! insert an element in hash table.
	/*!
    If the element exists, this replaces the element.
    \return the index in the array of the existing element,or GIM_INVALID_HASH if the element has been inserted
    If so, the element has been inserted at the last position of the array.
    */
	inline GUINT _insert_hash_table_replace(GUINT hashkey, const T& value)
	{
		if (hashkey == GIM_INVALID_HASH)
		{
			//Insert anyway
			_insert_unsorted(hashkey, value);
			return GIM_INVALID_HASH;
		}

		GUINT cell_index = _assign_hash_table_cell(hashkey);

		GUINT value_key = m_hash_table[cell_index];

		if (value_key != GIM_INVALID_HASH)
		{  //replaces the existing
			m_nodes[value_key] = _node_type(hashkey, value);
			return value_key;  // index of the replaced element
		}

		m_hash_table[cell_index] = m_nodes.size();

		_insert_unsorted(hashkey, value);
		return GIM_INVALID_HASH;
	}

	///Sorted array data management. The hash table has the indices to the corresponding m_nodes array
	inline bool _erase_sorted(GUINT index)
	{
		if (index >= (GUINT)m_nodes.size()) return false;
		m_nodes.erase_sorted(index);
		if (m_nodes.size() < 2) m_sorted = false;
		return true;
	}

	//! faster, but unsorted
	inline bool _erase_unsorted(GUINT index)
	{
		if (index >= m_nodes.size()) return false;

		GUINT lastindex = m_nodes.size() - 1;
		if (index < lastindex && m_hash_table != 0)
		{
			GUINT hashkey = m_nodes[lastindex].m_key;
			if (hashkey != GIM_INVALID_HASH)
			{
				//update the new position of the last element
				GUINT cell_index = _find_cell(hashkey);
				btAssert(cell_index != GIM_INVALID_HASH);
				//new position of the last element which will be swaped
				m_hash_table[cell_index] = index;
			}
		}
		m_nodes.erase(index);
		m_sorted = false;
		return true;
	}

	//! Insert in position ordered
	/*!
    Also checks if it is needed to transform this container to a hash table, by calling check_for_switching_to_hashtable
    */
	inline void _insert_in_pos(GUINT hashkey, const T& value, GUINT pos)
	{
		m_nodes.insert(_node_type(hashkey, value), pos);
		this->check_for_switching_to_hashtable();
	}

	//! Insert an element in an ordered array
	inline GUINT _insert_sorted(GUINT hashkey, const T& value)
	{
		if (hashkey == GIM_INVALID_HASH || size() == 0)
		{
			m_nodes.push_back(_node_type(hashkey, value));
			return GIM_INVALID_HASH;
		}
		//Insert at last position
		//Sort element

		GUINT result_ind = 0;
		GUINT last_index = m_nodes.size() - 1;
		_node_type* ptr = m_nodes.pointer();

		bool found = gim_binary_search_ex(
			ptr, 0, last_index, result_ind, hashkey, GIM_HASH_NODE_CMP_KEY_MACRO());

		//Insert before found index
		if (found)
		{
			return result_ind;
		}
		else
		{
			_insert_in_pos(hashkey, value, result_ind);
		}
		return GIM_INVALID_HASH;
	}

	inline GUINT _insert_sorted_replace(GUINT hashkey, const T& value)
	{
		if (hashkey == GIM_INVALID_HASH || size() == 0)
		{
			m_nodes.push_back(_node_type(hashkey, value));
			return GIM_INVALID_HASH;
		}
		//Insert at last position
		//Sort element
		GUINT result_ind;
		GUINT last_index = m_nodes.size() - 1;
		_node_type* ptr = m_nodes.pointer();

		bool found = gim_binary_search_ex(
			ptr, 0, last_index, result_ind, hashkey, GIM_HASH_NODE_CMP_KEY_MACRO());

		//Insert before found index
		if (found)
		{
			m_nodes[result_ind] = _node_type(hashkey, value);
		}
		else
		{
			_insert_in_pos(hashkey, value, result_ind);
		}
		return result_ind;
	}

	//! Fast insertion in m_nodes array
	inline GUINT _insert_unsorted(GUINT hashkey, const T& value)
	{
		m_nodes.push_back(_node_type(hashkey, value));
		m_sorted = false;
		return GIM_INVALID_HASH;
	}

public:
	/*!
        <li> if node_size = 0, then this container becomes a simple sorted array allocator. reserve_size is used for reserve memory in m_nodes.
        When the array size reaches the size equivalent to 'min_hash_table_size', then it becomes a hash table by calling check_for_switching_to_hashtable.
        <li> If node_size != 0, then this container becomes a hash table for ever
        </ul>
    */
	gim_hash_table(GUINT reserve_size = GIM_DEFAULT_HASH_TABLE_SIZE,
				   GUINT node_size = GIM_DEFAULT_HASH_TABLE_NODE_SIZE,
				   GUINT min_hash_table_size = GIM_INVALID_HASH)
	{
		m_hash_table = NULL;
		m_table_size = 0;
		m_sorted = false;
		m_node_size = node_size;
		m_min_hash_table_size = min_hash_table_size;

		if (m_node_size != 0)
		{
			if (reserve_size != 0)
			{
				m_nodes.reserve(reserve_size);
				_reserve_table_memory(reserve_size);
				_invalidate_keys();
			}
			else
			{
				m_nodes.reserve(GIM_DEFAULT_HASH_TABLE_SIZE);
				_reserve_table_memory(GIM_DEFAULT_HASH_TABLE_SIZE);
				_invalidate_keys();
			}
		}
		else if (reserve_size != 0)
		{
			m_nodes.reserve(reserve_size);
		}
	}

	~gim_hash_table()
	{
		_destroy();
	}

	inline bool is_hash_table()
	{
		if (m_hash_table) return true;
		return false;
	}

	inline bool is_sorted()
	{
		if (size() < 2) return true;
		return m_sorted;
	}

	bool sort()
	{
		if (is_sorted()) return true;
		if (m_nodes.size() < 2) return false;

		_node_type* ptr = m_nodes.pointer();
		GUINT siz = m_nodes.size();
		gim_sort_hash_node_array(ptr, siz);
		m_sorted = true;

		if (m_hash_table)
		{
			_rehash();
		}
		return true;
	}

	bool switch_to_hashtable()
	{
		if (m_hash_table) return false;
		if (m_node_size == 0) m_node_size = GIM_DEFAULT_HASH_TABLE_NODE_SIZE;
		if (m_nodes.size() < GIM_DEFAULT_HASH_TABLE_SIZE)
		{
			_resize_table(GIM_DEFAULT_HASH_TABLE_SIZE);
		}
		else
		{
			_resize_table(m_nodes.size() + 1);
		}

		return true;
	}

	bool switch_to_sorted_array()
	{
		if (m_hash_table == NULL) return true;
		_clear_table_memory();
		return sort();
	}

	//!If the container reaches the
	bool check_for_switching_to_hashtable()
	{
		if (this->m_hash_table) return true;

		if (!(m_nodes.size() < m_min_hash_table_size))
		{
			if (m_node_size == 0)
			{
				m_node_size = GIM_DEFAULT_HASH_TABLE_NODE_SIZE;
			}

			_resize_table(m_nodes.size() + 1);
			return true;
		}
		return false;
	}

	inline void set_sorted(bool value)
	{
		m_sorted = value;
	}

	//! Retrieves the amount of keys.
	inline GUINT size() const
	{
		return m_nodes.size();
	}

	//! Retrieves the hash key.
	inline GUINT get_key(GUINT index) const
	{
		return m_nodes[index].m_key;
	}

	//! Retrieves the value by index
	/*!
    */
	inline T* get_value_by_index(GUINT index)
	{
		return &m_nodes[index].m_data;
	}

	inline const T& operator[](GUINT index) const
	{
		return m_nodes[index].m_data;
	}

	inline T& operator[](GUINT index)
	{
		return m_nodes[index].m_data;
	}

	//! Finds the index of the element with the key
	/*!
    \return the index in the array of the existing element,or GIM_INVALID_HASH if the element has been inserted
    If so, the element has been inserted at the last position of the array.
    */
	inline GUINT find(GUINT hashkey)
	{
		if (m_hash_table)
		{
			GUINT cell_index = _find_cell(hashkey);
			if (cell_index == GIM_INVALID_HASH) return GIM_INVALID_HASH;
			return m_hash_table[cell_index];
		}
		GUINT last_index = m_nodes.size();
		if (last_index < 2)
		{
			if (last_index == 0) return GIM_INVALID_HASH;
			if (m_nodes[0].m_key == hashkey) return 0;
			return GIM_INVALID_HASH;
		}
		else if (m_sorted)
		{
			//Binary search
			GUINT result_ind = 0;
			last_index--;
			_node_type* ptr = m_nodes.pointer();

			bool found = gim_binary_search_ex(ptr, 0, last_index, result_ind, hashkey, GIM_HASH_NODE_CMP_KEY_MACRO());

			if (found) return result_ind;
		}
		return GIM_INVALID_HASH;
	}

	//! Retrieves the value associated with the index
	/*!
    \return the found element, or null
    */
	inline T* get_value(GUINT hashkey)
	{
		GUINT index = find(hashkey);
		if (index == GIM_INVALID_HASH) return NULL;
		return &m_nodes[index].m_data;
	}

	/*!
    */
	inline bool erase_by_index(GUINT index)
	{
		if (index > m_nodes.size()) return false;

		if (m_hash_table == NULL)
		{
			if (is_sorted())
			{
				return this->_erase_sorted(index);
			}
			else
			{
				return this->_erase_unsorted(index);
			}
		}
		else
		{
			return this->_erase_by_index_hash_table(index);
		}
		return false;
	}

	inline bool erase_by_index_unsorted(GUINT index)
	{
		if (index > m_nodes.size()) return false;

		if (m_hash_table == NULL)
		{
			return this->_erase_unsorted(index);
		}
		else
		{
			return this->_erase_by_index_hash_table(index);
		}
		return false;
	}

	/*!

    */
	inline bool erase_by_key(GUINT hashkey)
	{
		if (size() == 0) return false;

		if (m_hash_table)
		{
			return this->_erase_hash_table(hashkey);
		}
		//Binary search

		if (is_sorted() == false) return false;

		GUINT result_ind = find(hashkey);
		if (result_ind != GIM_INVALID_HASH)
		{
			return this->_erase_sorted(result_ind);
		}
		return false;
	}

	void clear()
	{
		m_nodes.clear();

		if (m_hash_table == NULL) return;
		GUINT datasize = m_table_size * m_node_size;
		//Initialize the hashkeys.
		GUINT i;
		for (i = 0; i < datasize; i++)
		{
			m_hash_table[i] = GIM_INVALID_HASH;  // invalidate keys
		}
		m_sorted = false;
	}

	//! Insert an element into the hash
	/*!
    \return If GIM_INVALID_HASH, the object has been inserted succesfully. Else it returns the position
    of the existing element.
    */
	inline GUINT insert(GUINT hashkey, const T& element)
	{
		if (m_hash_table)
		{
			return this->_insert_hash_table(hashkey, element);
		}
		if (this->is_sorted())
		{
			return this->_insert_sorted(hashkey, element);
		}
		return this->_insert_unsorted(hashkey, element);
	}

	//! Insert an element into the hash, and could overrite an existing object with the same hash.
	/*!
    \return If GIM_INVALID_HASH, the object has been inserted succesfully. Else it returns the position
    of the replaced element.
    */
	inline GUINT insert_override(GUINT hashkey, const T& element)
	{
		if (m_hash_table)
		{
			return this->_insert_hash_table_replace(hashkey, element);
		}
		if (this->is_sorted())
		{
			return this->_insert_sorted_replace(hashkey, element);
		}
		this->_insert_unsorted(hashkey, element);
		return m_nodes.size();
	}

	//! Insert an element into the hash,But if this container is a sorted array, this inserts it unsorted
	/*!
    */
	inline GUINT insert_unsorted(GUINT hashkey, const T& element)
	{
		if (m_hash_table)
		{
			return this->_insert_hash_table(hashkey, element);
		}
		return this->_insert_unsorted(hashkey, element);
	}
};

#endif  // GIM_CONTAINERS_H_INCLUDED