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

namespace System.Collections {
	public class HashSet<TValue> {
		private int _version;

		private Element[] _items;

		private int _peakCount, _freeCount, _freeFirst;

		public HashSet() {
		}

		public HashSet( int 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 = 0; i < _items.Length; ++i )
				_items[i]._first = -1;

			_freeFirst = -1;
			_peakCount = 0;
			_freeCount = 0;
			CommonCollectionOperations.UpdateVersion( &_version );
		}

		public bool Contains( TValue value ) { return FindValue( value ) >= 0; }

		private int FindValue( TValue value ) {
			int previous;
			return FindValue( value, previous );
		}

		private int FindValue( TValue value, int& previous ) {
			previous = -1;

			if( _items != null ) {
				var hash = value.GetHashCode();

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

			return -1;
		}

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

			_items = new[prime] Element;
			for( var i = 0; i < prime; ++i )
				_items[i]._first = -1;

			_freeFirst = -1;
		}

		private bool Insert( TValue value ) {
			int freeIndex;

			if( _items == null )
				Initialize( 3 );

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

			if( Contains( value ) ) return false;

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

				freeIndex = _peakCount;
				++_peakCount;
			}

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

			return true;
		}

		public bool Remove( TValue value ) {
			if( _items != null ) {
				int previous;
				var i = FindValue( value, previous );

				if( i >= 0 ) {
					if( previous < 0 ) _items[value.GetHashCode() % _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 = 0; i < prime; ++i )
				items[i]._first = -1;

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

			_items = items;
		}

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

		public struct Element {
			public TValue _value;
			public int _first;
			public int _next;
			public uint _hash;
		}

		public yield<TValue> GetEnumerator() {
			if( _items == null ) yield break;

			var version = _version;

			for( var i = 0; i < _items.Length; ++i ) {
				if( _items[i]._first == -1 ) continue;

				var current = _items[i]._first;
				while( current != -1 ) {
					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 int _version;

		private Element[] _items;

		private int _peakCount, _freeCount, _freeFirst;

		public HashSet() {
		}

		public HashSet( int 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 = 0; i < _items.Length; ++i )
				_items[i]._first = -1;

			_freeFirst = -1;
			_peakCount = 0;
			_freeCount = 0;
			CommonCollectionOperations.UpdateVersion( &_version );
		}

		public bool Contains( TValue value ) { return FindValue( value ) >= 0; }

		private int FindValue( TValue value ) {
			int previous;
			return FindValue( value, previous );
		}

		private int FindValue( TValue value, int& previous ) {
			previous = -1;

			if( _items != null ) {
				var hash = THash.GetHashCode( value );

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

			return -1;
		}

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

			_items = new[prime] Element;
			for( var i = 0; i < prime; ++i )
				_items[i]._first = -1;

			_freeFirst = -1;
		}

		private bool Insert( TValue value ) {
			int freeIndex;

			if( _items == null )
				Initialize( 3 );

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

			if( Contains( value ) ) 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]._value = value;
			_items[index]._first = freeIndex;
			CommonCollectionOperations.UpdateVersion( &_version );

			return true;
		}

		public bool Remove( TValue value ) {
			if( _items != null ) {
				int previous;
				var i = FindValue( value, previous );

				if( i >= 0 ) {
					if( previous < 0 ) _items[THash.GetHashCode( value ) % _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 = 0; i < prime; ++i )
				items[i]._first = -1;

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

			_items = items;
		}

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

		public struct Element {
			public TValue _value;
			public int _first;
			public int _next;
		}

		public yield<TValue> GetEnumerator() {
			if( _items == null ) yield break;

			var version = _version;

			for( var i = 0; i < _peakCount; ++i ) {
				if( _items[i]._first == -1 ) continue;

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

					CommonCollectionOperations.VersionCheck( version == _version );

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