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

namespace System.Collections {
	public class Dictionary<TKey, TValue> {
		private struct Element {
			public TValue _value;
			public TKey _key;
			public int _first;
			public int _hash, _next;
		}

		private int _version;

		private Element[] _items;

		private int _peakCount, _freeCount, _freeFirst;

		public Dictionary() {
		}

		public Dictionary( int capacity ) {
			Initialize( capacity );
		}

		public bool Add( TKey key, TValue value ) {
			return Insert( key, value, false );
		}

		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 ContainsKey( TKey key ) { return FindKey( key ) >= 0; }
		public bool ContainsValue( TValue value ) { return FindValue( value ) >= 0; }

		private int FindValue( TValue value ) {
			var index = 0;

			while( index < _peakCount ) {
				if( _items[index]._hash >= 0 && _items[index]._value == value )
					return index;

				++index;
			}

			return -1;
		}

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

		public TValue this[TKey key] {
			get {
				var index = FindKey( key );

				if( index >= 0 )
					return _items[index]._value;

				return default( TValue );
			}
			set {
				Insert( key, value, true );
			}
		}

		public bool TryGetValue( TKey key, TValue& value ) {
			var index = FindKey( key );

			if( index >= 0 ) {
				value = _items[index]._value;
				return true;
			}

			return false;
		}

		private int FindKey( TKey key ) {
			int previous;
			return FindKey( key, previous );
		}

		private int FindKey( TKey key, int& previous ) {
			previous = -1;

			if( _items != null ) {
				var hash = key.GetHashCode() & 0x7FFFFFFF;

				for( var i = _items[hash % _items.Length]._first; i >= 0; previous = i, i = _items[i]._next )
					if( ( uint ) _items[i]._hash == hash && _items[i]._key == key )
						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( TKey key, TValue value, bool replace ) {
			int freeIndex;

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

			var keyHash = ( int ) key.GetHashCode() & 0x7FFFFFFF;
			var index = keyHash % _items.Length;

			if( !replace && ContainsKey( key ) )
				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]._key = key;
			_items[freeIndex]._hash = keyHash;
			_items[freeIndex]._next = _items[index]._first;
			_items[freeIndex]._value = value;
			_items[index]._first = freeIndex;
			CommonCollectionOperations.UpdateVersion( &_version );

			return true;
		}

		public bool Remove( TKey key ) {
			if( _items != null ) {
				int previous;
				var i = FindKey( key, previous );

				if( i >= 0 ) {
					if( previous < 0 ) _items[( key.GetHashCode() & 0x7FFFFFFF ) % _items.Length]._first = _items[i]._next;
					else _items[previous]._next = _items[i]._next;

					_items[i]._hash = -1;
					_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]._hash % prime;
				items[j]._next = items[index]._first;
				items[index]._first = j;
			}

			_items = items;
		}

		public Enumerator GetEnumerator() {
			return new Enumerator( this );
		}

		[EnumeratorAttribute]
		public struct Enumerator {
			private readonly declaringtype _parent;
			private readonly int _version;
			private int _index;
			private KeyValuePair<TKey, TValue> _current;

			internal Enumerator( declaringtype parent ) {
				_current = default( KeyValuePair<TKey, TValue> );
				_version = parent._version;
				_parent = parent;
				_index = 0;
			}

			public bool MoveNext() {
				if( _version != _parent._version ) {
					Assert.Fail( "Collection was modified since last iteration." );
					return false;
				}

				while( _index < _parent._peakCount ) {
					if( _parent._items[_index]._hash >= 0 ) {
						_current.Key = _parent._items[_index]._key;
						_current.Value = _parent._items[_index]._value;
						++_index;
						return true;
					}

					++_index;
				}

				_index = _parent._peakCount + 1;
				_current = default( KeyValuePair<TKey, TValue> );
				return false;
			}

			public KeyValuePair<TKey, TValue> Current { get { return _current; } }
		}
	}
}