//	VirtualDub - Video processing and capture application
//	System library component
//	Copyright (C) 1998-2010 Avery Lee, All Rights Reserved.
//
//	Beginning with 1.6.0, the VirtualDub system library is licensed
//	differently than the remainder of VirtualDub.  This particular file is
//	thus licensed as follows (the "zlib" license):
//
//	This software is provided 'as-is', without any express or implied
//	warranty.  In no event will the authors be held liable for any
//	damages arising from the use of this software.
//
//	Permission is granted to anyone to use this software for any purpose,
//	including commercial applications, and to alter it and redistribute it
//	freely, subject to the following restrictions:
//
//	1.	The origin of this software must not be misrepresented; you must
//		not claim that you wrote the original software. If you use this
//		software in a product, an acknowledgment in the product
//		documentation would be appreciated but is not required.
//	2.	Altered source versions must be plainly marked as such, and must
//		not be misrepresented as being the original software.
//	3.	This notice may not be removed or altered from any source
//		distribution.

#ifndef f_VD2_SYSTEM_VDSTL_HASHTABLE_H
#define f_VD2_SYSTEM_VDSTL_HASHTABLE_H

///////////////////////////////////////////////////////////////////////////////
//	vdhashtable_base_node
//
struct vdhashtable_base_node {
	vdhashtable_base_node *mpHashNext;
};

///////////////////////////////////////////////////////////////////////////////
//	vdhashtable_base
//
class vdhashtable_base {
public:
	typedef	size_t		size_type;
	typedef	ptrdiff_t	difference_type;

	vdhashtable_base();

	// size and capacity
	bool		empty() const { return mElementCount == 0; }
	size_type	size() const { return mElementCount; }
	size_type	max_size() const { return (size_type)-1 >> 1; }

	// bucket interface
	size_type			bucket_count() const;
	size_type			max_bucket_count() const;
	size_type			bucket_size(size_type n) const;

protected:
	static size_type compute_bucket_count(size_type n);

	size_type	mBucketCount;
	size_type	mElementCount;
	vdhashtable_base_node **mpBucketStart;
	vdhashtable_base_node **mpBucketEnd;

	static vdhashtable_base_node *const sEmptyBucket;
};

///////////////////////////////////////////////////////////////////////////

template<class T>
struct vdhashtable_node : public vdhashtable_base_node {
	T mData;

	vdhashtable_node() {}
	vdhashtable_node(vdhashtable_node<T> *next) : mData() {
		mpHashNext = next;
	}

	vdhashtable_node(vdhashtable_node<T> *next, const T& val) : mData(val) {
		mpHashNext = next;
	}
};

///////////////////////////////////////////////////////////////////////////

template<class T>
class vdhashtable_local_iterator {
public:
	typedef std::forward_iterator_tag iterator_category;
	typedef T value_type;
	typedef T* pointer;
	typedef T& reference;
	typedef size_t size_type;
	typedef ptrdiff_t difference_type;

	vdhashtable_local_iterator(vdhashtable_base_node *node);

	vdhashtable_local_iterator& operator++();
	vdhashtable_local_iterator operator++(int);

	T& operator*() const;
	T* operator->() const;

private:
	template<class U> friend bool operator==(const vdhashtable_local_iterator<U>& x, const vdhashtable_local_iterator<U>& y);
	template<class U> friend bool operator==(const vdhashtable_local_iterator<const U>& x, const vdhashtable_local_iterator<U>& y);
	template<class U> friend bool operator==(const vdhashtable_local_iterator<U>& x, const vdhashtable_local_iterator<const U>& y);
	template<class U> friend bool operator!=(const vdhashtable_local_iterator<U>& x, const vdhashtable_local_iterator<U>& y);
	template<class U> friend bool operator!=(const vdhashtable_local_iterator<const U>& x, const vdhashtable_local_iterator<U>& y);
	template<class U> friend bool operator!=(const vdhashtable_local_iterator<U>& x, const vdhashtable_local_iterator<const U>& y);

	vdhashtable_base_node *mpNode;
};

template<class T>
vdhashtable_local_iterator<T>::vdhashtable_local_iterator(vdhashtable_base_node *node)
	: mpNode(node)
{
}

template<class T>
vdhashtable_local_iterator<T>& vdhashtable_local_iterator<T>::operator++() {
	mpNode = mpNode->mpHashNext;
	return *this;
}

template<class T>
vdhashtable_local_iterator<T> vdhashtable_local_iterator<T>::operator++(int) {
	vdhashtable_local_iterator prev(*this);
	mpNode = mpNode->mpHashNext;
	return prev;
}

template<class T>
T& vdhashtable_local_iterator<T>::operator*() const {
	return static_cast<vdhashtable_node<T> *>(mpNode)->mData;
}

template<class T>
T* vdhashtable_local_iterator<T>::operator->() const {
	return &static_cast<vdhashtable_node<T> *>(mpNode)->mData;
}

template<class T>
bool operator==(const vdhashtable_local_iterator<T>& x, const vdhashtable_local_iterator<T>& y) {
	return x.mpNode == y.mpNode;
}

template<class T>
bool operator==(const vdhashtable_local_iterator<const T>& x, const vdhashtable_local_iterator<T>& y) {
	return x.mpNode == y.mpNode;
}

template<class T>
bool operator==(const vdhashtable_local_iterator<T>& x, const vdhashtable_local_iterator<const T>& y) {
	return x.mpNode == y.mpNode;
}

template<class T>
bool operator!=(const vdhashtable_local_iterator<T>& x, const vdhashtable_local_iterator<T>& y) {
	return x.mpNode != y.mpNode;
}

template<class T>
bool operator!=(const vdhashtable_local_iterator<const T>& x, const vdhashtable_local_iterator<T>& y) {
	return x.mpNode != y.mpNode;
}

template<class T>
bool operator!=(const vdhashtable_local_iterator<T>& x, const vdhashtable_local_iterator<const T>& y) {
	return x.mpNode != y.mpNode;
}

///////////////////////////////////////////////////////////////////////////

template<class T> struct vdhashtable_iterator_nonconst {
	typedef T result;
};

template<class T> struct vdhashtable_iterator_nonconst<const T> {
	typedef T result;
};

template<class T>
class vdhashtable_iterator {
	typedef typename vdhashtable_iterator_nonconst<T>::result T_NonConst;
public:
	typedef std::forward_iterator_tag iterator_category;
	typedef T value_type;
	typedef T* pointer;
	typedef T& reference;
	typedef size_t size_type;
	typedef ptrdiff_t difference_type;

	vdhashtable_iterator();
	vdhashtable_iterator(vdhashtable_base_node *node, vdhashtable_base_node **bucket, vdhashtable_base_node **bucketEnd);
	vdhashtable_iterator(const vdhashtable_iterator<T_NonConst>& src);

	vdhashtable_iterator& operator++();
	vdhashtable_iterator operator++(int);

	T& operator*() const;
	T* operator->() const;

private:
	friend class vdhashtable_iterator<const T>;
	template<class U> friend bool operator==(const vdhashtable_iterator<U>& x, const vdhashtable_iterator<U>& y);
	template<class U> friend bool operator==(const vdhashtable_iterator<const U>& x, const vdhashtable_iterator<U>& y);
	template<class U> friend bool operator==(const vdhashtable_iterator<U>& x, const vdhashtable_iterator<const U>& y);
	template<class U> friend bool operator!=(const vdhashtable_iterator<U>& x, const vdhashtable_iterator<U>& y);
	template<class U> friend bool operator!=(const vdhashtable_iterator<const U>& x, const vdhashtable_iterator<U>& y);
	template<class U> friend bool operator!=(const vdhashtable_iterator<U>& x, const vdhashtable_iterator<const U>& y);

	vdhashtable_base_node *mpNode;
	vdhashtable_base_node **mpBucket;
	vdhashtable_base_node **mpBucketEnd;
};

template<class T>
vdhashtable_iterator<T>::vdhashtable_iterator()
	: mpNode(NULL)
	, mpBucket(NULL)
	, mpBucketEnd(NULL)
{
}

template<class T>
vdhashtable_iterator<T>::vdhashtable_iterator(vdhashtable_base_node *node, vdhashtable_base_node **bucket, vdhashtable_base_node **bucketEnd)
	: mpNode(node)
	, mpBucket(bucket)
	, mpBucketEnd(bucketEnd)
{
}

template<class T>
vdhashtable_iterator<T>::vdhashtable_iterator(const vdhashtable_iterator<T_NonConst>& src)
	: mpNode(src.mpNode)
	, mpBucket(src.mpBucket)
	, mpBucketEnd(src.mpBucketEnd)
{
}

template<class T>
vdhashtable_iterator<T>& vdhashtable_iterator<T>::operator++() {
	mpNode = mpNode->mpHashNext;

	while(!mpNode && ++mpBucket != mpBucketEnd)
		mpNode = static_cast<vdhashtable_node<T> *>(*mpBucket);

	return *this;
}

template<class T>
vdhashtable_iterator<T> vdhashtable_iterator<T>::operator++(int) {
	vdhashtable_iterator prev(*this);
	mpNode = mpNode->mpHashNext;
	return prev;
}

template<class T>
T& vdhashtable_iterator<T>::operator*() const {
	return static_cast<vdhashtable_node<T> *>(mpNode)->mData;
}

template<class T>
T* vdhashtable_iterator<T>::operator->() const {
	return &static_cast<vdhashtable_node<T> *>(mpNode)->mData;
}

template<class T>
bool operator==(const vdhashtable_iterator<T>& x, const vdhashtable_iterator<T>& y) {
	return x.mpNode == y.mpNode;
}

template<class T>
bool operator==(const vdhashtable_iterator<const T>& x, const vdhashtable_iterator<T>& y) {
	return x.mpNode == y.mpNode;
}

template<class T>
bool operator==(const vdhashtable_iterator<T>& x, const vdhashtable_iterator<const T>& y) {
	return x.mpNode == y.mpNode;
}

template<class T>
bool operator!=(const vdhashtable_iterator<T>& x, const vdhashtable_iterator<T>& y) {
	return x.mpNode != y.mpNode;
}

template<class T>
bool operator!=(const vdhashtable_iterator<const T>& x, const vdhashtable_iterator<T>& y) {
	return x.mpNode != y.mpNode;
}

template<class T>
bool operator!=(const vdhashtable_iterator<T>& x, const vdhashtable_iterator<const T>& y) {
	return x.mpNode != y.mpNode;
}

///////////////////////////////////////////////////////////////////////////

template<class T>
class vdhashtable : public vdhashtable_base {
public:
	typedef T value_type;
	typedef vdhashtable_node<value_type> node_type;
	typedef value_type *pointer;
	typedef const value_type *const_pointer;
	typedef value_type& reference;
	typedef const value_type& const_reference;
	typedef vdhashtable_iterator<value_type> iterator;
	typedef vdhashtable_iterator<const value_type> const_iterator;
	typedef vdhashtable_local_iterator<value_type> local_iterator;
	typedef vdhashtable_local_iterator<const value_type> const_local_iterator;

	// iterators
	iterator			begin();
	const_iterator		begin() const;
	iterator			end();
	const_iterator		end() const;
};

// iterators
template<class T>
typename vdhashtable<T>::iterator vdhashtable<T>::begin() {
	vdhashtable_base_node **bucket = mpBucketStart;
	vdhashtable_base_node *p = NULL;

	while(bucket != mpBucketEnd) {
		p = *bucket;
		if (p)
			break;

		++bucket;
	}

	return iterator(static_cast<node_type *>(p), bucket, mpBucketEnd);
}

template<class T>
typename vdhashtable<T>::const_iterator vdhashtable<T>::begin() const {
	vdhashtable_base_node **bucket = mpBucketStart;
	vdhashtable_base_node *p = NULL;

	while(bucket != mpBucketEnd) {
		p = *bucket;
		if (p)
			break;

		++bucket;
	}

	return const_iterator(static_cast<node_type *>(p), bucket, mpBucketEnd);
}

template<class T>
typename vdhashtable<T>::iterator vdhashtable<T>::end() {
	return iterator(NULL, NULL, NULL);
}

template<class T>
typename vdhashtable<T>::const_iterator vdhashtable<T>::end() const {
	return const_iterator(NULL, NULL, NULL);
}

#endif	// f_VD2_SYSTEM_VDSTL_HASHTABLE_H
