ahashps.h

A Set of Simple C++ Hash Templates

#ifndef THE_A_HASH_TEMPLATE_THAT_RETURNS_POINTERS_AND_ONLY_TAKES_ONE_TYPE_WHICH_IS_BOTH_THE_STORAGE_AND_THE_REFERENCE_TYPE_IN_THE_GET_RATHER_THAN_REFERENCES_20061219_H__
#define THE_A_HASH_TEMPLATE_THAT_RETURNS_POINTERS_AND_ONLY_TAKES_ONE_TYPE_WHICH_IS_BOTH_THE_STORAGE_AND_THE_REFERENCE_TYPE_IN_THE_GET_RATHER_THAN_REFERENCES_20061219_H__

#include "__hash.h"

/**
	\brief Hash table with a key that is all of an element's data.

	To setup this class:
	1. You derive your hash class from this class.
	2. T must also have comparison operator.
	3. Follow the requirements for __hash<T>.
*/

template <typename T>
class _HashPS : public __hash<T> {
protected:
	_HashPS(int nBucketSize = 0);

public:
	typedef typename __hash<T>::hashelementlist hashelementlist;//!<Getting the parent
	typedef typename __hash<T>::hasherator 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>::const_hasherator const_hasherator;//!<Getting the parent
	typedef typename __hash<T>::phashelementlist phashelementlist;//!<Getting the parent

private:
	listelement *SeekIterator(phashelementlist &plist, const T&);

protected:
	/*
	 *  \brief Gets the list in which the sought element is to be found.
	 * @param  ref An instance of T which has the member used to create the key.
	 * @return The index for m_buckets of the element that has the list.
	 */
	//virtual bucket_array_unit HASHREFERENCEPREATTRIBUTES GetHashReference(const T &ref) const HASHREFERENCEPOSTATTRIBUTES=0;

public:
	/**
	 *  \brief Erase the contents of the table
	 
	 		This will not deallocate the bucket array, but just remove all of its elements.
	 */
	void erase(const T &t);
	//!Similar to Get(KEY_TYPE) but returns a pointer
	/**\return The pointer to an element if found, or NULL otherwise*/
	const T *Find(const T &ref) const;
	//!Has an element been added?
	/**\return TRUE if the specified element was found, or FALSE otherwise*/
	bool IsAdded(const T &ref) const {
		return Find(ref) != NULL;
	}
};

//!Constructor taking the initial size of the bucket array
template <typename T>
_HashPS<T>::_HashPS(int nBucketSize) : __hash<T>(nBucketSize) {
}

template <typename T>
const T *_HashPS<T>::Find(const T &ref) const {
	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 (ref == pElement->m_element) return &pElement->m_element;
	return NULL;
}

/**
 * \brief Erases an element from the table
 * @param r 
 */
template <typename T>
void _HashPS<T>::erase(const T &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 reference to the element.
 	\return The iterator to the element, or plist->end() if none was found
 */
template <typename T>
typename _HashPS<T>::listelement *_HashPS<T>::SeekIterator(phashelementlist &plist, const T &ref) {
	bucket_array &buckets = __hash<T>::m_buckets;
	assert(!buckets.empty());
	bucket_array_unit nIndex = GetHashReference(ref);
	assert(nIndex < buckets.size());
	plist = &buckets[nIndex];
	for(listelement *p = plist->head(); p != NULL; p = p->next()) {
		#ifdef DEBUG_AHASH
			assert(buckets[nIndex].BothNULLorNonNULL());
		#endif
		if (CompareReferences(p->m_element, ref)) {
			return p;
		}
	}
	return NULL;
}

#endif