//
// 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; } }
}
}
}