__hash.h

A Set of Simple C++ Hash Templates

#ifndef THE__HASH_WHICH_SHOULD_BE_DERIVED_BY_ALL_HASH_TEMPLATES_H__20070524
#define THE__HASH_WHICH_SHOULD_BE_DERIVED_BY_ALL_HASH_TEMPLATES_H__20070524

#include <assert.h>

#include <vector>

#ifndef HASHREFERENCEPREATTRIBUTES
#define HASHREFERENCEPREATTRIBUTES
#endif
#ifndef HASHREFERENCEPOSTATTRIBUTES
#define HASHREFERENCEPOSTATTRIBUTES
#endif

/** \class __hash
	\brief The root class of all hash tables used by the astdlib.

	Do not derive directly from this class. Derive from its children.\n
	Your hash table class should:\n
	1. Implement GetHashReference().\n
	2. \em Optional Define macros HASHREFERENCEPREATTRIBUTES and HASHREFERENCEPOSTATTRIBUTES. Doing this might optimize performance with whatever compiler you are using, but such things can be dangerous, so be very careful when using them.

*/

template <typename T>
class __hash {
protected:
	//!Constructor
	__hash(int nBucketArraySize) : m_buckets(nBucketArraySize), m_nCount(0) {}
	virtual ~__hash() {}
#ifdef DEBUG_AHASH
#define CHECK_NEXT_AND_PREV()
#else
#define CHECK_NEXT_AND_PREV() assert(CheckNextAndPrev())
#endif
public:
	//!Creats a text report on the number of collisions in the table
	#ifndef _MSC_VER
		void ReportCollisions(_Log *pLog, bool bSuppressZeroCollisions = TRUE, bool bSuppressElements = TRUE) const {
			bucket_array_unit nMaxCollisions = 0, nTotalCollisions = 0;
			int nNonEmptyElements = 0;
			char c[100];
			for (bucket_array_unit nIndex = 0; nIndex < m_buckets.size(); nIndex++)
				if (!m_buckets[nIndex].empty()) {
					nNonEmptyElements++;
					bucket_array_unit nCollisions = m_buckets[nIndex].size() - 1;
					nTotalCollisions += nCollisions;
					if (nCollisions > nMaxCollisions) nMaxCollisions = nCollisions;
					if (!bSuppressElements)
						if (nCollisions != 0 || !bSuppressZeroCollisions) {
							sprintf(c, "%d: %d collisions", (int)nIndex, (int)nCollisions);
							pLog->LogLine(c);
						}
				}
			pLog->LogLine("==========");
			sprintf(c, "Total collisions:\t%d", (int)nTotalCollisions);
			pLog->LogLine(c);
			sprintf(c, "Maximum collisions:\t%d", (int)nMaxCollisions);
			pLog->LogLine(c);
			sprintf(c, "Average collisions:\t%f", double(nTotalCollisions)/nNonEmptyElements);
			pLog->LogLine(c);
		}
	#endif

	/**
	 *  \brief Adds an element to the table
	 * @param t The data to add to the table
	 * @return A reference to the newly created element
	 */
	T &Add(const T &t);
	/**
	 *  \brief Is the table empty?
	 * @return TRUE if there are no elements in the table, FALSE otherwise
	 */
	bool empty() const {
		return m_nCount == 0;
	}
	/**
	 *  \brief Gets the number of elements in the table
	 		\note This is not the size of the bucket array, but how many elements of T have been added.
	 * @return The size of the table.
	 */
	unsigned int size() const {
		return m_nCount;
	}
	//!Removes all elements from the hash table
	/**The bucket array's size is not changed*/
	void clear();

protected:
	class elementlist;//I don't know why the hell I had to put this here, but the friend declaration didn't work if I didn't
	//!A single element for a doubley-linked list, including next and previous pointers
	class listelement {
	friend class elementlist;
	public:
		listelement() : m_pPrev(NULL), m_pNext(NULL) {}
		//!Copy constructor
		listelement(const listelement &le);

		/**
		 *   \brief Constructor which inserts itself into a list
		 * @param pPrev The previous element or NULL if this is to be the head element
		 * @param pNext The next element or NULL if this is to be the tail element
		 * @param element The data to store
		 */
		listelement(listelement *pPrev, listelement *pNext, const T &element);
		~listelement() {
			//assert(CheckNextAndPrev());
			delete m_pNext;
		}

		//!A pointer to the next element or NULL if this is the last element
		listelement *next() {CHECK_NEXT_AND_PREV();return m_pNext;}
		//!A pointer to the next element or NULL if this is the last element
		const listelement *next() const {CHECK_NEXT_AND_PREV();return m_pNext;}
		//!A pointer to the previous element or NULL if this is the first element
		listelement *prev() {CHECK_NEXT_AND_PREV();return m_pPrev;}
		//!A pointer to the previous element or NULL if this is the first element
		const listelement *prev() const {CHECK_NEXT_AND_PREV();return m_pPrev;}
		
		//!Dereference operator
		T &operator *() {
			CHECK_NEXT_AND_PREV();
			return m_element;
		}
		//!Dereference operator
		const T &operator *() const {
			CHECK_NEXT_AND_PREV();
			return m_element;
		}
		//!Confirms that pointers to the adjacent elements are correct and that the proper pointers in those elements point to this.
		bool CheckNextAndPrev() const {
			bool bNextGood = m_pNext == NULL || m_pNext->m_pPrev == this;
			bool bPrevGood = m_pPrev == NULL || m_pPrev->m_pNext == this;
			return bNextGood && bPrevGood;
		}

	protected:
		//!Removes itself from the list and ensures continuity in the list
		/**It is the responsiblity of the owner to destroy this instance, of course*/
		listelement *Remove() {
			listelement *pOriginalNext = m_pNext;
			if (m_pNext != NULL) {
				assert(m_pNext->m_pPrev == this);
				m_pNext->m_pPrev = m_pPrev;
				m_pNext = NULL;
			}
			if (m_pPrev != NULL) {
				assert(m_pPrev->m_pNext == this);
				m_pPrev->m_pNext = pOriginalNext;
				m_pPrev = NULL;
			}
			return pOriginalNext;
		}
	public:
		T m_element;//!<The data we are storing
	private:
		listelement *m_pPrev, //!<Pointer to the previous element or NULL if this is the head element
							*m_pNext;//!<Pointer to the next element or NULL if this is the tail element
	};//class listelement

	//!A light-weight doubley-linked list
	class elementlist {
	public:
		elementlist() : m_plist(NULL), m_ptail(NULL) {
			#ifdef DEBUG_AHASH
				m_nSize = 0;
				assert(SizeCorrect());
			#endif
		}
		//!Copy constructor
		elementlist(const elementlist &el) : m_plist(NULL), m_ptail(NULL) {
			#ifdef DEBUG_AHASH
				m_nSize = 0;
			#endif
			Copy(el);
		}
		//!Constructor that takes a T
		/**m_plist and m_ptail are also duly assigned*/
		elementlist(const T &t);
		~elementlist() {
			Destroy();
		}
		//!Assignment operator.
		elementlist *operator=(const elementlist &el) {
			Copy(el);
			return this;
		}

		//!Gets the first element of the list
		listelement *head() {
			#ifdef DEBUG_AHASH
				assert(m_plist == NULL || m_plist->CheckNextAndPrev());assert(BothNULLorNonNULL());assert(SizeCorrect());
			#endif
			return m_plist;
		}
		//!Gets the first element of the list
		const listelement *head() const {
			#ifdef DEBUG_AHASH
				assert(m_plist == NULL || m_plist->CheckNextAndPrev());assert(BothNULLorNonNULL());assert(SizeCorrect());
			#endif
			return m_plist;
		}
		//!Gets the last element of the list
		T &back() {
			#ifdef DEBUG_AHASH
				assert(m_ptail != NULL && m_plist != NULL);assert(m_plist->CheckNextAndPrev());assert(SizeCorrect());
			#endif
			return m_ptail->m_element;
		}
		//!Gets the last element of the list
		const T &back() const {
			#ifdef DEBUG_AHASH
				assert(m_ptail != NULL && m_plist != NULL);assert(m_plist->CheckNextAndPrev());assert(SizeCorrect());
			#endif
			return m_ptail->m_element;
		}
		
		//!Erases an element from the list
		/**The list pointers are also duly change to keep m_plist and m_ptail valid and preserve the continuity of the list.*/
		void erase(listelement *le) {
			#ifdef DEBUG_AHASH
				assert(m_nSize > 0);
				assert(SizeCorrect());
				m_nSize--;
			#endif
			assert(le != NULL);
			assert(m_plist != NULL && m_ptail != NULL);
			if (le == m_plist) {
				assert((m_plist->next() == NULL) == (m_plist == m_ptail));
				m_plist = m_plist->next();
				if (m_plist == NULL)
					m_ptail = NULL;
			}
			else
				if (le == m_ptail) {
					m_ptail = m_ptail->prev();
				}
			le->Remove();
			delete le;
			assert(m_plist == NULL || m_plist->m_pPrev == NULL);
			#ifdef DEBUG_AHASH
				assert(BothNULLorNonNULL());
				assert(SizeCorrect());
			#endif
				//assert(false);
			//}
		}
		
		//!Ensures that m_plist and m_ptail are both NULL or neither are NULL
		bool BothNULLorNonNULL() const {
			bool bListNULL = m_plist == NULL;
			bool bTailNULL = m_ptail == NULL;
			bool bSuccess = bListNULL == bTailNULL;
			return bSuccess;
		}

		//!Adds an element to the tail
		listelement *push_back(const T &element);
		//!Finds out if the list is empty
		bool empty() const {
			#ifdef DEBUG_AHASH
				assert(m_plist == NULL || m_plist->CheckNextAndPrev());assert(BothNULLorNonNULL());assert(SizeCorrect());
			#endif
			return m_plist == NULL;
		}
		//!Empties the list
		void clear();
		//!Gets the number of elements in the list
		/** \note currently the time-complexity of this method is O(n)*/
		size_t size() const;
	private:
		//!See HASHTEMPLATE::elementlist::Destroy
		void Destroy();
		//!See HASHTEMPLATE::elementlist::Copy
		void Copy(const elementlist &el);
		#ifdef DEBUG_AHASH
			//!DEBUG only: confirms that the size of the list according to m_nSize is correct
			bool SizeCorrect() const {
				return size() == m_nSize;
			}
		#endif

		listelement *m_plist,//!<Pointer to the first list element or NULL if the list is empty
							*m_ptail;//!<Pointer to the last list element or NULL if the list is empty
		#ifdef DEBUG_AHASH
			size_t m_nSize;//!<Currently only used for debugging. Keeps track of the number of elements in the list
		#endif
	};//class elementlist

	typedef elementlist hashelementlist;//!<The type for a list of elements

	typedef hashelementlist * phashelementlist;//!<A pointer to a list which is an element of the pointer table

protected:
	typedef std::vector<hashelementlist>													bucket_array;//!<The type array that will be the table
	typedef typename std::vector<hashelementlist>::size_type			bucket_array_unit;//!<The units used to index table elements

protected:
	bucket_array m_buckets;//!<The table containing the lists of elements
	unsigned int m_nCount;//!<The number of elements in the table

public:
	//!Sets the size of the bucket array
	/**You must only call this once, unless you call Delete() first. The bucket array cannot be resized once the size has been set.*/
	void SetBucketSize(bucket_array_unit nNewSize) {
		assert(empty());
		m_buckets.resize(nNewSize);
	}
	/**
	 *  \brief Gets the size of the bucket array, as set in SetBucketSize()
	 * @return The size of the table.
	 	\note This does not return the number of elements in the table
	 */
	bucket_array_unit GetBucketSize() const {
		return __hash<T>::m_buckets.size();
	}
	//!Takes an array and adds the elements to this hash table
	void TakeArray(const std::vector<T> &array);
	/**
	 * \brief Gets an array of the table's contents

	 	Call this if you want the data to be an array.
	 * @param array The array to add to. It will first be cleared
	 * @return The size of the array.
	 */
	bucket_array_unit GetArray(std::vector<T> &array) const;

	//!Useful for getting the statistics for a table in debug mode
	/**Currently all it does it report how many T elements each element of the hash array has. Use this to test for colisions.
		\param array An array of the number of T elements in each element of the hash array. The index for each element in this array correspond to that in the hash array. The data in each element of array is the number of T elements.
		\return The size of array
	*/
	bucket_array_unit GetBucketStats(std::vector<size_t> &array) const {
		array.clear();
		bucket_array &table = __hash<T>::m_buckets;
		for (bucket_array_unit nTableIndex = 0; nTableIndex < table.size(); nTableIndex++) {
			const hashelementlist &the_list = table[nTableIndex];
			bucket_array_unit nThisListSize = the_list.size();
			if (nThisListSize >= array.size()) array.resize(nThisListSize + 1);
			array[nThisListSize]++;
		}
		return array.size();
	}

	/**
		\class __hash::hasherator
		\brief Iterator for __hash*/
	class hasherator {
	public:
		//!Simple constructor
		/**You can't use this hasherator using this, unless it gets assigned by another one, which was constructed with another constructor*/
		hasherator() {
			#ifndef NDEBUG
				m_pbuckets = NULL;
				m_pListElement = NULL;
			#endif
		}
		/**
		 * \brief Constructor
		 * @param buckets The bucket array.
		 */
		hasherator(bucket_array &buckets);
	
		/**
		 *   \brief Pre-increment operator
		 * @return The hash iterator after incrementing
		 */
		hasherator &operator++();
		/**
		 *   \brief Dereferences the member of the hash table pointed to by the iterator
		 * @return A reference to the member of the hash table.
		 */
		T &operator *() {