__hash.h

A Set of Simple C++ Hash Templates

			return m_pListElement->m_element;
		}
		/**
		 *   \brief See operator *()
		 */
		T *operator ->() {
			return &(operator*());
		}
		/**
		 *   \brief Compares 2 iterators. 
		 * @param p The 2nd iterator
		 * @return TRUE if the iterators are equal or both have m_bEnd set, FALSE otherwise.
		 */
		bool operator ==(const hasherator &p) const {
			return m_pListElement == p.m_pListElement;
		}
		/**
		 *   \brief Is this the past-the-end iterator.
		 			Call this member after you have incremented the iterator and want to know if you have reached the end of the hash table.
		 * @return TRUE if this iterator points past the end of the hash table, FALSE otherwise.
		 */
		inline bool IsEnd() const {return m_pListElement == NULL;}
	protected:
		bucket_array *m_pbuckets;//!<Points to the pointer array in the hash table.
		
		bucket_array_unit m_nBucketIndex;//!<Index of the pointer array that this iterator is currently pointing to.
		listelement *m_pListElement;//!<pointer to the list element the iterator is pointing to
	};
	
	//!A iterator pointing to a constant hash
	class const_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*/
		const_hasherator() {
			#ifndef NDEBUG
				m_pbuckets = NULL;
				m_pListElement = NULL;
			#endif
		}
		/**
		 * \brief Constructor
		 * @param buckets The bucket array
		 */
		const_hasherator(const bucket_array &buckets);
	
		/**
		 *   \brief Pre-increment operator
		 * @return The hash iterator before incrementing
		 */
		const_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.
		 */
		const T &operator *() const {
			assert(m_pListElement != NULL);
			return m_pListElement->m_element;
		}
		/**
		 *   \brief See operator *()
		 */
		const T *operator ->() const {
			return &(operator*());
		}
		/**
		 *   \brief Compares 2 iterators. 
		 * @param iter The 2nd iterator
		 * @return TRUE if the iterators are equal or both have m_bEnd set, FALSE otherwise.
		 */
		bool operator ==(const const_hasherator &iter) const {
			return m_pListElement == iter.m_pListElement;
		}
		/**
		 *   \brief Is the the past-the-end iterator.
		 			Call this member after you have incremented the iterator and want to know if you have reached the end of the hash table.
		 * @return TRUE if this iterator points past the end of the hash table, FALSE otherwise.
		 */
		bool IsEnd() const {return m_pListElement == NULL;}
	protected:
		//bool m_bEnd;//!<TRUE if this iterator points past-the-end of the hash table, FALSE otherwise
		//typedef const bucket_array * cbucket_array_ptr;
		const bucket_array *m_pbuckets;//!<Points to the pointer array in the hash table.
		bucket_array_unit m_nBucketIndex;//!<Index of the pointer array that this iterator is currently pointing to.
		const listelement *m_pListElement;//!<pointer to the list element the iterator is pointing to
		//const hashelementlist *m_plist;//!<The STL list that this iterator is pointing to.
	};

	/**
	 *  \brief Gets the first reference in the hash table
	 * @return Iterator to the first member of the hash table
	 */
	hasherator begin() {
		hasherator iter(__hash<T>::m_buckets);
		return iter;
	}
	/**
	 *  \brief Gets the first reference in the hash table
	 * @return An iterator to the first member of a constant hash table.
	 */
	const_hasherator begin() const {
		const_hasherator iter(__hash<T>::m_buckets);
		return iter;
	}

	/*!
		\fn __hash::Delete
		\brief Removes all elements from the table and clears the bucket array
	*/
	void Delete() {
		m_buckets.clear();
		m_nCount = 0;
	}

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

			This should call your hashing function.
	 * @param  ref An instance of T which has the member used to reference.
	 * @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 will behave unpredictably.
	 */
	virtual bucket_array_unit HASHREFERENCEPREATTRIBUTES GetHashReference(const T &ref) const HASHREFERENCEPOSTATTRIBUTES =0;

};

template <typename T>
T &__hash<T>::Add(const T &def) {
	assert(m_buckets.size() > 0);
	bucket_array_unit nIndex = GetHashReference(def);
	assert(nIndex < m_buckets.size());
	hashelementlist &alist = m_buckets[nIndex];
	alist.push_back(def);
	m_nCount++;
	return alist.back();
}

template <typename T>
void __hash<T>::clear() {
	bucket_array_unit nSize = m_buckets.size();
	for (bucket_array_unit nIndex = 0; nIndex < nSize; nIndex++) {
		m_buckets[nIndex].clear();
	}
	m_nCount = 0;
}

/*!
    \fn __hash<T>::TakeArray(const std::vector<T> &array)
    \brief Method that takes an array and incorporates it into the hash

    Any current elements in the hash are cleared. The bucket array does not change.
 */
template <typename T>
void __hash<T>::TakeArray(const std::vector<T> &array) {
	clear();
	bucket_array_unit nSize = array.size();
	SetBucketSize(nSize);
	for (bucket_array_unit nIndex = 0; nIndex < nSize; nIndex++)
		Add(array[nIndex]);
}

//!Takes the contents and put thems into an array.
template <typename T>
typename __hash<T>::bucket_array_unit __hash<T>::GetArray(std::vector<T> &array) const {
	array.clear();
	const bucket_array &table = __hash<T>::m_buckets;
	bucket_array_unit nSize = table.size();
	for (bucket_array_unit nTableIndex = 0; nTableIndex < nSize; nTableIndex++) {
		for(const listelement *pElement = table[nTableIndex].head(); pElement != NULL; pElement = pElement->next())
			array.push_back(pElement->m_element);
	}
	return array.size();
}


template <typename T>
__hash<T>::listelement::listelement(const listelement &le) : m_element(le.m_element) {
	if (le.m_pNext == NULL) m_pNext = NULL;
	else {
		m_pNext = new listelement(*le.m_pNext);
		m_pNext->m_pPrev = this;
	}
	if (le.m_pPrev == NULL) m_pPrev = NULL;//if not, our m_pPrev will be set by the previous instance
}

template <typename T>
__hash<T>::listelement::listelement(listelement *pPrev, listelement *pNext, const T &element) : m_element(element), m_pPrev(pPrev), m_pNext(pNext) {
	if (m_pPrev != NULL) {
		assert(m_pPrev->m_pNext == pNext);
		m_pPrev->m_pNext = this;
	}
	if (m_pNext != NULL) {
		assert(m_pNext->m_pPrev == pPrev);
		m_pNext->m_pPrev = this;
	}
	CHECK_NEXT_AND_PREV();
}

template <typename T>
__hash<T>::elementlist::elementlist(const T &t) {
	#ifdef DEBUG_AHASH
		m_nSize = 1;
	#endif
	m_plist = new listelement(NULL, NULL, t);
	assert(m_plist->m_pPrev == NULL);
	m_ptail = m_plist;
	#ifdef DEBUG_AHASH
		assert(SizeCorrect());
		assert(m_plist->CheckNextAndPrev());
	#endif
}

template <typename T>
typename __hash<T>::listelement *__hash<T>::elementlist::push_back(const T &element) {
	#ifdef DEBUG_AHASH
		assert(m_plist == NULL || m_plist->CheckNextAndPrev());
		m_nSize++;
	#endif
	listelement *pNew = new listelement(m_ptail, NULL, element);
	if (m_plist == NULL) {
		assert(m_ptail == NULL);
		m_plist = pNew;
	}
	else assert(m_ptail != NULL);
	m_ptail = pNew;
	assert(m_ptail->next() == NULL);
	#ifdef DEBUG_AHASH
		assert(SizeCorrect());
		assert(m_plist == NULL || m_plist->CheckNextAndPrev());
	#endif
	return pNew;
}

template <typename T>
void __hash<T>::elementlist::clear() {
	#ifdef DEBUG_AHASH
		assert(m_plist == NULL || m_plist->CheckNextAndPrev());assert(BothNULLorNonNULL());assert(SizeCorrect());
	#endif
	if (m_plist != NULL) {delete m_plist; m_plist = NULL;m_ptail = NULL;
		#ifdef DEBUG_AHASH
			m_nSize = 0;
		#endif
	}
	#ifdef DEBUG_AHASH
		assert(SizeCorrect());
	#endif
}

template <typename T>
size_t __hash<T>::elementlist::size() const {
	size_t nSize = 0;
	const listelement *le = m_plist;
	if (le != NULL) {
		assert(le->prev() == NULL);
	}
	for (const listelement *p = le; p != NULL; p = p->next()) {
		nSize++;
		assert((p->next() == NULL) == (p == m_ptail));
	}
	return nSize;
}

template <typename T>
void __hash<T>::elementlist::Destroy() {
	#ifdef DEBUG_AHASH
		assert(BothNULLorNonNULL());
		assert(m_plist == NULL || m_plist->CheckNextAndPrev());
		assert(SizeCorrect());
	#endif
	for (listelement *pCurrent = m_ptail; pCurrent != NULL;) {
		listelement *pCurrentActual = pCurrent;
		pCurrent = pCurrent->m_pPrev;
		if (pCurrent != NULL)
			pCurrent->m_pNext = NULL;
		delete pCurrentActual;
	}
	#ifdef DEBUG_AHASH
		m_nSize = 0;
	#endif
	m_plist = NULL;
	m_ptail = NULL;
}

template <typename T>
void __hash<T>::elementlist::Copy(const elementlist &el) {
	Destroy();
	if (el.m_plist == NULL) {
		m_plist = NULL;
		assert(el.m_ptail == NULL);
		m_ptail = NULL;
		#ifdef DEBUG_AHASH
			m_nSize = 0;
		#endif
	}
	else {
		m_plist = new listelement(*el.m_plist);
		assert(m_plist->m_pPrev == NULL);
		#ifdef DEBUG_AHASH
			m_nSize = 1;
		#endif
		for (m_ptail = m_plist; m_ptail->next() != NULL; m_ptail = m_ptail->next()) {
			#ifdef DEBUG_AHASH
				m_nSize++;
			#endif
		}
	}
}

template <typename T>
__hash<T>::hasherator::hasherator(bucket_array &buckets) : m_pbuckets(&buckets), m_pListElement(NULL) {
	bucket_array_unit nSize = m_pbuckets->size();
	for (m_nBucketIndex = 0; m_nBucketIndex < nSize; m_nBucketIndex++) {
		elementlist &list = m_pbuckets->at(m_nBucketIndex);
		if (!list.empty()) {
			m_pListElement = list.head();
			break;
		}
	}
}

template <typename T>
typename __hash<T>::hasherator &__hash<T>::hasherator::operator++() {//pre-increment
	if (m_pListElement != NULL) {
		assert(m_pbuckets != NULL);
		if ((m_pListElement = m_pListElement->next()) == NULL) {
			bucket_array_unit nSize = m_pbuckets->size();
			while (++m_nBucketIndex < nSize) {
				bucket_array &table = *m_pbuckets;
				if (!table.at(m_nBucketIndex).empty()) {
					elementlist &the_list = table[m_nBucketIndex];
					m_pListElement = the_list.head();
					break;
				}
			}
		}
	}
	return *this;
}

template <typename T>
__hash<T>::const_hasherator::const_hasherator(const bucket_array &buckets) : m_pbuckets(&buckets), m_pListElement(NULL) {
	bucket_array_unit nSize = m_pbuckets->size();
	for (m_nBucketIndex = 0; m_nBucketIndex < nSize; m_nBucketIndex++) {
		const elementlist &list = m_pbuckets->at(m_nBucketIndex);
		if (!list.empty()) {
			m_pListElement = list.head();
			break;
		}
	}
}

template <typename T>
typename __hash<T>::const_hasherator &__hash<T>::const_hasherator::operator++() {//pre-increment
	if (m_pListElement != NULL) {
		assert(m_pbuckets != NULL);
		if ((m_pListElement = m_pListElement->next()) == NULL) {
			bucket_array_unit nSize = m_pbuckets->size();
			while (++m_nBucketIndex < nSize) {
				const bucket_array &table = *m_pbuckets;
				if (!table.at(m_nBucketIndex).empty()) {
					const elementlist &the_list = table[m_nBucketIndex];
					m_pListElement = the_list.head();
					break;
				}
			}
		}
	}
	return *this;
}

#endif