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