//
// Created by Eugeny Grishul
//
// See license at http://bamelg.com/license.txt
//

namespace System.Collections {
	public class HashSet<TValue> {
		private struct Element {
			public TValue _value;
			public uint _first;
			public uint _next;
			public uint _hash;
		}

		private uint _version;

		private Element[] _items;

		private uint _peakCount, _freeCount, _freeFirst;

		public HashSet() {
			Initialize( 3 );
		}

		public HashSet( uint capacity ) {
			Initialize( capacity );
		}

		public HashSet( thistype value ) {
			_items = new[value._items.Length] Element;
			_peakCount = value._peakCount;
			_freeCount = value._freeCount;
			_freeFirst = value._freeFirst;

			CommonCollectionOperations.Copy<Element>( &_items[0], &value._items[0], _items.Length );
		}

		public bool Add( TValue value ) {
			return Insert( value );
		}

		public void AddRange( TValue[] items ) { foreach( var item in items ) Add( item ); }
		public void AddRange( List<TValue> items ) { foreach( var item in items ) Add( item ); }

		public void Clear() {
			if( _peakCount == 0 ) return;

			CommonCollectionOperations.Clear<Element>( &_items[0], _peakCount );
			for( var i = 0U; i < _items.Length; ++i )
				_items[i]._first = uint.MaxValue;

			_freeFirst = uint.MaxValue;
			_peakCount = 0;
			_freeCount = 0;
			CommonCollectionOperations.UpdateVersion( &_version );
		}

		public bool Contains( TValue value ) { return FindValue( value ) != uint.MaxValue; }

		private uint FindValue( TValue value ) {
			uint previous;
			var hash = value.GetHashCode();
			return FindValue( value, hash, previous );
		}

		private uint FindValue( TValue value, uint hash, uint& previous ) {
			previous = uint.MaxValue;

			for( var i = _items[hash % _items.Length]._first; i != uint.MaxValue; previous = i, i = _items[i]._next )
				if( _items[i]._value.GetHashCode() == hash && _items[i]._value == value )
					return i;

			return uint.MaxValue;
		}

		private void Initialize( uint capacity ) {
			var prime = PrimeNumber.GetClosestPrime( capacity );

			_items = new[prime] Element;
			for( var i = 0U; i < prime; ++i )
				_items[i]._first = uint.MaxValue;

			_freeFirst = uint.MaxValue;
		}

		private bool Insert( TValue value ) {
			uint freeIndex;

			var hash = value.GetHashCode();
			var index = hash % _items.Length;

			uint previous;
			if( FindValue( value, hash, previous ) != uint.MaxValue ) return false;

			if( _freeCount > 0 ) {
				freeIndex = _freeFirst;
				_freeFirst = _items[freeIndex]._next;
				--_freeCount;
			}
			else {
				if( _peakCount == _items.Length ) {
					Resize();
					index = hash % _items.Length;
				}

				freeIndex = _peakCount;
				++_peakCount;
			}

			_items[freeIndex]._next = _items[index]._first;
			_items[freeIndex]._hash = hash;
			_items[freeIndex]._value = value;
			_items[index]._first = freeIndex;
			CommonCollectionOperations.UpdateVersion( &_version );

			return true;
		}

		public bool Remove( TValue value ) {
			uint previous;
			var hash = value.GetHashCode();
			var i = FindValue( value, hash, previous );

			if( i != uint.MaxValue ) {
				if( previous == uint.MaxValue ) _items[hash % _items.Length]._first = _items[i]._next;
				else _items[previous]._next = _items[i]._next;

				_items[i]._next = _freeFirst;
				_items[i]._value = default( TValue );

				_freeFirst = i;
				++_freeCount;
				CommonCollectionOperations.UpdateVersion( &_version );

				return true;
			}

			return false;
		}

		private void Resize() {
			var prime = PrimeNumber.GetClosestPrime( _peakCount * 2 );

			var items = new[prime] Element;
			CommonCollectionOperations.Copy<Element>( &items[0], &_items[0], _peakCount );
			for( var i = 0U; i < prime; ++i )
				items[i]._first = uint.MaxValue;

			for( var j = 0U; j < _peakCount; ++j ) {
				var index = items[j]._value.GetHashCode() % prime;
				items[j]._next = items[index]._first;
				items[index]._first = j;
			}

			_items = items;
		}

		public uint Count { get { return _peakCount - _freeCount; } }

		public yield<TValue> GetEnumerator() {
			if( _peakCount == 0 ) yield break;

			var version = _version;

			for( var i = 0U; i < _items.Length; ++i ) {
				if( _items[i]._first == uint.MaxValue ) continue;

				var current = _items[i]._first;
				while( current != uint.MaxValue ) {
					yield return _items[current]._value;

					if( _version != version ) {
						Assert.Fail( "Collection was modified since last iteration." );
						yield break;
					}

					current = _items[current]._next;
				}
			}
		}
	}

	/// 'THash' must provide static 'GetHashCode' method with fast and simple retrieval like:
	/// struct StringHash { [ForceInline] public static uint GetHashCode( string key ) { return key.Hash; } }
	/// Since 'HashSet<TValue, THash>' contains no key/hash 'GetHashCode' must return precomputed or computationally lightweight hash ( like "public static uint GetHashCode( void* key ) { return ( uint ) key; }" )
	public class HashSet<TValue, THash> {
		private struct Element {
			public TValue _value;
			public uint _first;
			public uint _next;
		}

		private uint _version;

		private Element[] _items;

		private uint _peakCount, _freeCount, _freeFirst;

		public HashSet() {
			Initialize( 3 );
		}

		public HashSet( uint capacity ) {
			Initialize( capacity );
		}

		public HashSet( thistype value ) {
			_items = new[value._items.Length] Element;
			_peakCount = value._peakCount;
			_freeCount = value._freeCount;
			_freeFirst = value._freeFirst;

			CommonCollectionOperations.Copy<Element>( &_items[0], &value._items[0], _items.Length );
		}

		public bool Add( TValue value ) {
			return Insert( value );
		}

		public void AddRange( TValue[] items ) { foreach( var item in items ) Add( item ); }
		public void AddRange( List<TValue> items ) { foreach( var item in items ) Add( item ); }

		public void Clear() {
			if( _peakCount == 0 ) return;

			CommonCollectionOperations.Clear<Element>( &_items[0], _peakCount );
			for( var i = 0U; i < _items.Length; ++i )
				_items[i]._first = uint.MaxValue;

			_freeFirst = uint.MaxValue;
			_peakCount = 0;
			_freeCount = 0;
			CommonCollectionOperations.UpdateVersion( &_version );
		}

		public bool Contains( TValue value ) { return FindValue( value ) != uint.MaxValue; }

		private uint FindValue( TValue value ) {
			uint previous;
			var hash = THash.GetHashCode( value );
			return FindValue( value, hash, previous );
		}

		private uint FindValue( TValue value, uint hash, uint& previous ) {
			previous = uint.MaxValue;

			for( var i = _items[hash % _items.Length]._first; i != uint.MaxValue; previous = i, i = _items[i]._next )
				if( THash.GetHashCode( _items[i]._value ) == hash && _items[i]._value == value )
					return i;

			return uint.MaxValue;
		}

		private void Initialize( uint capacity ) {
			var prime = PrimeNumber.GetClosestPrime( capacity );

			_items = new[prime] Element;
			for( var i = 0U; i < prime; ++i )
				_items[i]._first = uint.MaxValue;

			_freeFirst = uint.MaxValue;
		}

		private bool Insert( TValue value ) {
			var hash = THash.GetHashCode( value );
			var index = hash % _items.Length;

			uint previous;
			if( FindValue( value, hash, previous ) != uint.MaxValue ) return false;

			uint freeIndex;
			if( _freeCount > 0 ) {
				freeIndex = _freeFirst;
				_freeFirst = _items[freeIndex]._next;
				--_freeCount;
			}
			else {
				if( _peakCount == _items.Length ) {
					Resize();
					index = hash % _items.Length;
				}

				freeIndex = _peakCount;
				++_peakCount;
			}

			_items[freeIndex]._next = _items[index]._first;
			_items[freeIndex]._value = value;
			_items[index]._first = freeIndex;
			CommonCollectionOperations.UpdateVersion( &_version );

			return true;
		}

		public bool Remove( TValue value ) {
			uint previous;
			var hash = THash.GetHashCode( value );
			var i = FindValue( value, hash, previous );

			if( i != uint.MaxValue ) {
				if( previous == uint.MaxValue ) _items[hash % _items.Length]._first = _items[i]._next;
				else _items[previous]._next = _items[i]._next;

				_items[i]._next = _freeFirst;
				_items[i]._value = default( TValue );

				_freeFirst = i;
				++_freeCount;
				CommonCollectionOperations.UpdateVersion( &_version );

				return true;
			}

			return false;
		}

		private void Resize() {
			var prime = PrimeNumber.GetClosestPrime( _peakCount * 2 );

			var items = new[prime] Element;
			CommonCollectionOperations.Copy<Element>( &items[0], &_items[0], _peakCount );
			for( var i = 0U; i < prime; ++i )
				items[i]._first = uint.MaxValue;

			for( var j = 0U; j < _peakCount; ++j ) {
				var index = THash.GetHashCode( items[j]._value ) % prime;
				items[j]._next = items[index]._first;
				items[index]._first = j;
			}

			_items = items;
		}

		public uint Count { get { return _peakCount - _freeCount; } }

		public yield<TValue> GetEnumerator() {
			if( _peakCount == 0 ) yield break;

			var version = _version;

			for( var i = 0U; i < _peakCount; ++i ) {
				if( _items[i]._first == uint.MaxValue ) continue;

				var current = _items[i]._first;
				while( current != uint.MaxValue ) {
					yield return _items[current]._value;

					CommonCollectionOperations.VersionCheck( version == _version );

					current = _items[current]._next;
				}
			}
		}
	}
}