ahashp.h

A Set of Simple C++ Hash Templates

#ifndef THE_A_HASH_TEMPLATE_THAT_RETURNS_POITNERS_IN_THE_GET_RATHER_THAN_REFERENCES_20061219_H__
#define THE_A_HASH_TEMPLATE_THAT_RETURNS_POITNERS_IN_THE_GET_RATHER_THAN_REFERENCES_20061219_H__

#include "__hash.h"

#ifndef COMPAREREFERENCESPREATTRIBUTES 
#define COMPAREREFERENCESPREATTRIBUTES 
#endif
#ifndef COMPAREREFERENCESPOSTATTRIBUTES
#define COMPAREREFERENCESPOSTATTRIBUTES
#endif

/**
	\brief Hash table that doesn't need NULL elements
	
	Similar to _Hash< T, KEY_TYPE > but does not need the elements to have a "NULL" member to indicate a NULL set from Get() calls.\n
	To setup this class:\n
	1. You derive your hash class from this class.\n
	2. Implement GetHashReference() and CompareReferences().\n
	3. Follow the requirements for __hash<T>.\n
	4. \em Optional Define macros COMPAREREFERENCESPREATTRIBUTES and COMPAREREFERENCESPOSTATTRIBUTES. 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, typename KEY_TYPE = const char *>
class _HashP : public __hash<T> {
protected:
	_HashP(int nBucketSize = 0);

public:
	typedef typename __hash<T>::hasherator hasherator;//!<Getting the parent
	typedef typename __hash<T>::const_hasherator const_hasherator;//!<Getting the parent
	typedef typename __hash<T>::bucket_array_unit bucket_array_unit;//!<Getting the parent
private:
	typedef typename __hash<T>::elementlist elementlist;//!<Getting the parent
	typedef typename __hash<T>::bucket_array bucket_array;//!<Getting the parent
	typedef typename __hash<T>::listelement listelement;//!<Getting the parent
	typedef typename __hash<T>::hashelementlist hashelementlist;//!<Getting the parent
	typedef typename __hash<T>::phashelementlist phashelementlist;//!<Getting the parent

private:
	/**
	 *  \brief Gets the bucket in which the sought element is to be found.

		This should essentially do the same thing as __hash< T >::GetHashReference(const T &) except that it works on a different type.
	 * @param ref The reference data used to locate the element.
	 * @return The index for m_buckets of the element that has the list. This reference should be >= 0 and \< GetBucketSize().
	 	\note <b>Do not neglect to include the HASHREFERENCEPREATTRIBUTES and HASHREFERENCEPOSTATTRIBUTES parts.</b> If you do, you probably won't get a compile or linker error, but your program could behave unpredictably.
	 */
	virtual bucket_array_unit HASHREFERENCEPREATTRIBUTES GetHashReference(KEY_TYPE ref) const HASHREFERENCEPOSTATTRIBUTES=0;
	/**
	 *  \brief Compares a T type against an KEY_TYPE type.
	 
	 	The implementation should be a simple comparison operation between the key in ref1 and the key that is ref2.
	 * @param ref1 A type T reference
	 * @param ref2 A type KEY_TYPE reference
	 * @return TRUE if ref1 contains ref2 or FALSE otherwise
	 	\note <b>Do not neglect to include the COMPAREREFERENCESPREATTRIBUTES and COMPAREREFERENCESPOSTATTRIBUTES parts.</b> If you do, you probably won't get a compile or linker error, but your program could behave unpredictably.
	 */
	virtual bool COMPAREREFERENCESPREATTRIBUTES CompareReferences(const T &ref1, KEY_TYPE ref2) const COMPAREREFERENCESPOSTATTRIBUTES =0;

public:
	void erase(KEY_TYPE r);
	//!Adds a member if its key isn't already there, and assigns the new one if it is.
	T &Set(const T &t);
	/**
	 *  \brief A const version of Get(KEY_TYPE)
	 */
	const T *Get(KEY_TYPE ref) const {
		const T *pElement = Find(ref);
		return pElement;
	}
	/**
	 *  \brief Get an element from the table
	 * @param ref The key used to find the element
	 * @return A pointer to the element sought, or NULL if not found.
	 */
	T *Get(KEY_TYPE ref);
	//!Identical Get(KEY_TYPE)
	/**\return The pointer to an element if found, or NULL otherwise*/
	const T *Find(KEY_TYPE ref) const;
	//!Has an element been added?
	/**\return TRUE if the specified element was found, or FALSE otherwise*/
	bool IsAdded(KEY_TYPE ref) const {
		return Find(ref) != NULL;
	}

	#ifdef HASH_BENCHMARK
		void ReportGetCollisions(_Log *pLog) const {
			char c[100];
			sprintf(c, "%d collisions / %d get calls = %f", m_nGetCollisionCount, m_nGetCallCount, double(m_nGetCollisionCount)/m_nGetCallCount);
			pLog->LogLine(c);
		}
	private:
		int m_nGetCallCount, m_nGetCollisionCount;
	#endif
		
	
private:
	listelement *SeekIterator(phashelementlist &plist, KEY_TYPE);
};


//!Constructor taking the initial size of the hash lookup table
template <typename T, typename KEY_TYPE>
_HashP<T, KEY_TYPE>::_HashP(int nBucketSize) : __hash<T>(nBucketSize) {
	#ifdef HASH_BENCHMARK
		m_nGetCollisionCount = 0;
		m_nGetCallCount = 0;
	#endif
}

template <typename T, typename KEY_TYPE>
T &_HashP<T, KEY_TYPE>::Set(const T &def) {
	T *p = Get(def);
	if (p == NULL) return Add(def);
	*p = def;
	return *p;
}

template <typename T, typename KEY_TYPE>
const T *_HashP<T, KEY_TYPE>::Find(KEY_TYPE ref) const {
	#ifdef HASH_BENCHMARK
		int *pCollisionCount = const_cast<int*>(&m_nGetCollisionCount);
		(*pCollisionCount)++;
	#endif
	const bucket_array &buckets = __hash<T>::m_buckets;
	assert(!buckets.empty());
	bucket_array_unit nIndex = GetHashReference(ref);
	assert(nIndex < buckets.size());
	for(const listelement *pElement = buckets[nIndex].head(); pElement != NULL; pElement = pElement->next()) {
		if (CompareReferences(pElement->m_element, ref)) return &pElement->m_element;
		#ifdef HASH_BENCHMARK
			int *pCollisionCount = const_cast<int*>(&m_nGetCollisionCount);
			(*pCollisionCount)++;
		#endif
	}
	return NULL;
}

template <typename T, typename KEY_TYPE>
T *_HashP<T, KEY_TYPE>::Get(KEY_TYPE ref) {
	#ifdef HASH_BENCHMARK
		m_nGetCallCount++;
	#endif
	bucket_array &buckets = __hash<T>::m_buckets;
	assert(!buckets.empty());
	bucket_array_unit nIndex = GetHashReference(ref);
	for(listelement *pElement = buckets[nIndex].head(); pElement != NULL; pElement = pElement->next()) {
		if (CompareReferences(pElement->m_element, ref)) return &pElement->m_element;
		#ifdef HASH_BENCHMARK
			m_nGetCollisionCount++;
		#endif
	}
	return NULL;
}

/**
 * \brief Erases an element from the table
 * @param r A key of the element to erase
 */
template <typename T, typename KEY_TYPE>
void _HashP<T, KEY_TYPE>::erase(KEY_TYPE r) {
	phashelementlist plist;
	listelement *le = SeekIterator(plist, r);
	assert(le != NULL);
	plist->erase(le);
	__hash<T>::m_nCount--;
}

/**
 * \brief Searches for an iterator to an element
 * @param plist The list in which the element was found
 	\param ref A key to the element.
 	\return The iterator to the element, or plist->end() if none was found
 */
template <typename T, typename KEY_TYPE>
typename _HashP<T, KEY_TYPE>::listelement *_HashP<T, KEY_TYPE>::SeekIterator(phashelementlist &plist, KEY_TYPE ref) {
	bucket_array &table = __hash<T>::m_buckets;
	assert(!table.empty());
	bucket_array_unit nIndex = GetHashReference(ref);
	assert(nIndex < table.size());
	plist = &table[nIndex];
	for(listelement *p = plist->head(); p != NULL; p = p->next()) {
		#ifdef DEBUG_AHASH
			assert(table[nIndex].BothNULLorNonNULL());
		#endif
		if (CompareReferences(p->m_element, ref)) {
			return p;
		}
	}
	return NULL;
}

#endif