
#ifndef PandaWave_XPTRSET
#define PandaWave_XPTRSET


#include <XConfig.h>
#include <XDynArray.h>


template <class T> class XGPtrSet {
	public:
			XGPtrSet() { fHashArray = NULL; }
			XGPtrSet( T *item ) { fHashArray = NULL; Add(item); }
			XGPtrSet( const XGPtrSet<T> &copy ) { fHashArray = NULL; fArray = copy.fArray; }
			~XGPtrSet() { delete [] fHashArray; }
			
			void RebuildHash() const
			{
				int len = fArray.Length();
				if (len >= 8)
				{
					int hlen = len * 2;
					fHashShift = 3;
					while ((1 << fHashShift) < hlen)
					{
						++fHashShift;
					}
					delete [] fHashArray;
					hlen = 1 << fHashShift;
					fHashArray = new int[hlen];
					if (fHashArray)
					{
						memset( fHashArray, 0xff, hlen * sizeof(int) );
						unsigned hmask = hlen - 1;
						for (int i = 0; i < len; ++i)
						{
							unsigned h = (unsigned)(fArray[i]);
							unsigned hstep = (h ^ (h >> (fHashShift-1)) ^ (h >> (2*(fHashShift-1)))) | 1;
							h = (h ^ (h >> fHashShift) ^ (h >> (2*fHashShift)) ^ (h >> (3 * fHashShift)));
							for (;;)
							{
								h = (h + hstep) & hmask;
								int index = fHashArray[h];
								if (index == -1)
								{
									fHashArray[h] = i;
									break;
								}
							}
						}
					}
				}
				else
				{
					delete [] fHashArray;
					fHashArray = NULL;
				}
			}
			
			inline bool HasMember( T *item ) const
				{
					if (!fHashArray)
					{
						int len = fArray.Length();
						if (len < 8)
						{
							for (int i = 0; i < len; ++i) {
								if (fArray[i] == item) return true;
							}
							return false;
						}
						else
						{
							RebuildHash();
						}
					}
					unsigned hmask = (1 << fHashShift) - 1;
					unsigned h = (unsigned)item;
					unsigned hstep = (h ^ (h >> (fHashShift-1)) ^ (h >> (2*(fHashShift-1)))) | 1;
					h = (h ^ (h >> fHashShift) ^ (h >> (2*fHashShift)) ^ (h >> (3 * fHashShift)));
					for (;;)
					{
						h = (h + hstep) & hmask;
						int index = fHashArray[h];
						if (index == -1) return false;
						T *ptr = fArray[index];
						if (ptr == item) return true;
					}
				}
				
			void Add( T *item )
				{
					if (!HasMember(item)) fArray += item;
					if (fHashArray)
					{
						if (fArray.Length() > (1 << fHashShift) - (1 << (fHashShift - 2)))
						{
							delete [] fHashArray;
							fHashArray = NULL;
						}
						else
						{
							unsigned hmask = (1 << fHashShift) - 1;
							unsigned h = (unsigned)item;
							unsigned hstep = (h ^ (h >> (fHashShift-1)) ^ (h >> (2*(fHashShift-1)))) | 1;
							h = (h ^ (h >> fHashShift) ^ (h >> (2*fHashShift)) ^ (h >> (3 * fHashShift)));
							for (;;)
							{
								h = (h + hstep) & hmask;
								int index = fHashArray[h];
								if (index == -1)
								{
									fHashArray[h] = fArray.Length() - 1;
									break;
								}
							}
						}
					}
				}
				
			void Remove( T *item )
				{
					int len = fArray.Length();
					for (int i = 0; i < len; ++i) {
						if (fArray[i] == item) {
							fArray.Delete(i);
							break;
						}
					}
					
					delete [] fHashArray;
					fHashArray = NULL;
				}
			
			void Empty()
				{
					fArray.DeleteAll();
					delete [] fHashArray;
					fHashArray = NULL;
				}
			
			int Size() const
				{ return fArray.Length(); }
			
			T *operator[]( int i ) const
				{ return fArray[i]; }
			
			XGPtrSet<T> &operator +=( T *item )
				{ this->Add(item); return *this; }
	
			
			XGPtrSet<T> &operator -=( T *item )
				{ this->Remove(item); return *this; }
			
			XGPtrSet<T> &operator =( const XGPtrSet &in )
				{ fArray = in.fArray; delete [] fHashArray; fHashArray = NULL; return *this; }
			
			XGPtrSet<T> &operator =( T *item )
				{ this->Empty(); this->Add(item); return *this; }
			
			XGPtrSet<T> &operator |= ( const XGPtrSet<T> &other )
				{
					int otherlen = other.fArray.Length();
					for (int i = 0; i < otherlen; ++i) {
						T *item = other[i];
						Add( item );
					}
					
					return *this;
				}
			
			XGPtrSet<T> &operator &= ( const XGPtrSet<T> &other )
				{
					*this = *this & other;
					return *this;
				}
			
			XGPtrSet<T> &operator -= ( const XGPtrSet<T> &other )
				{
					*this = *this - other;
					return *this;
				}
			
			XGPtrSet<T> &operator ^= ( const XGPtrSet<T> &other )
				{
					*this = *this ^ other;
					return *this;
				}
			
			XGPtrSet<T> operator | ( const XGPtrSet<T> &other ) const
				{
					XGPtrSet<T> temp = *this;
					temp |= other;
					return temp;
				}
			
			XGPtrSet<T> operator ^ ( const XGPtrSet<T> &other ) const
				{
					XGPtrSet<T> temp;
					int i;
					
					for (i = 0; i < this->fArray.Length(); ++i) {
						if (!other.HasMember( this->fArray[i] )) {
							temp += this->fArray[i];
						}
					}
					
					for (i = 0; i < other.fArray.Length(); ++i) {
						if (!this->HasMember( other.fArray[i] )) {
							temp += other.fArray[i];
						}
					}
					
					return temp;
				}
			
			XGPtrSet<T> operator & ( const XGPtrSet<T> &other ) const
				{
					XGPtrSet<T> temp;
					int otherlen = other.fArray.Length();
					int mylen = fArray.Length();
					if (mylen < otherlen)
					{
						for (int i = 0; i < mylen; ++i)
						{
							if (other.HasMember( fArray[i] )) temp.Add( fArray[i] );
						}
					}
					else
					{
						for (int i = 0; i < mylen; ++i)
						{
							if (this->HasMember( other.fArray[i] )) temp.Add( other.fArray[i] );
						}
					}
					
					return temp;
				}
			
			XGPtrSet<T> operator - ( const XGPtrSet<T> &other ) const
				{
					XGPtrSet<T> temp;
					int len = fArray.Length();
					for (int i = 0; i < len; ++i)
					{
						if (!other.HasMember( fArray[i] ))
						{
							temp.Add( fArray[i] );
						}
					}
					
					return temp;
				}
				
	private:
			XGPDynArray<T> fArray;
			mutable int fHashShift;
			mutable int *fHashArray;
};


#endif

