A Small HashSet Class
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
[DebuggerTypeProxy(typeof(HashSetDebugView<>))]
[DebuggerDisplay("Count = {" + nameof(Count) + "}")]
[Serializable]
public class TinySet<T>
{
private int[] _hashBuckets;
private SizeHelper<T> _newSize = new SizeHelper<T>();
internal IEqualityComparer<T> Comparer;
public int Position;
internal Slot[] Slots;
public TinySet() : this(101, EqualityComparer<T>.Default)
{
}
public TinySet(int size) : this(size, EqualityComparer<T>.Default)
{
}
public TinySet(IEqualityComparer<T> comparer) : this(101, comparer)
{
}
public TinySet(int size, IEqualityComparer<T> comparer)
{
if (comparer == null)
comparer = EqualityComparer<T>.Default;
Comparer = comparer;
_hashBuckets = new int[size];
Slots = new Slot[size];
Count = 0;
Position = -1;
}
public TinySet(IEnumerable<T> collection, IEqualityComparer<T> comparer)
{
if (comparer == null)
comparer = EqualityComparer<T>.Default;
Comparer = comparer;
if (!(collection is ICollection<T> coll))
return;
var size = coll.Count;
_hashBuckets = new int[size];
Slots = new Slot[size];
UnionWith(coll);
}
public int Count
{
get;
private set;
}
public T[] ToArray()
{
var newArray = new T[Count];
var copied = 0;
for (var i = 0; i < Count && copied < Count; i++)
if (Slots[i].HashCode > 0)
newArray[copied++] = Slots[i].Value;
return newArray;
}
public void Create(int size, IEqualityComparer<T> comparer)
{
if (comparer == null)
comparer = EqualityComparer<T>.Default;
Comparer = comparer;
_hashBuckets = new int[size];
Slots = new Slot[size];
Count = 0;
Position = -1;
}
public void Clear()
{
var size = Slots.Length;
_hashBuckets = new int[size];
Slots = new Slot[size];
Count = 0;
Position = -1;
}
public bool Add(T item)
{
return Insert(item, true);
}
public bool Contains(T item)
{
return Insert(item, false);
}
internal bool Insert(T item, bool add)
{
var hashCode = Comparer.GetHashCode(item) & int.MaxValue;
if (FindEntry(item, hashCode) != -1)
return true;
if (add)
{
if (Count >= Slots.Length)
SetSizeAndOrForceNewHashCodes(_newSize.GetNewSize(_hashBuckets.Length));
var hashPos = hashCode % _hashBuckets.Length;
Slots[Count].Next = _hashBuckets[hashPos] - 1;
Slots[Count].Value = item;
Slots[Count].HashCode = hashCode;
_hashBuckets[hashPos] = Count + 1;
Position = Count;
++Count;
}
return false;
}
public void ForceNewHashCodes()
{
SetSizeAndOrForceNewHashCodes();
}
private void SetSizeAndOrForceNewHashCodes(int Size = 0)
{
if (Count == 0) return;
var newSize = Size == 0 ? Count : Size;
var newSlots = new Slot[newSize];
var newHashBuckets = new int[newSize];
if (Slots != null)
Array.Copy(Slots, 0, newSlots, 0, Count);
for (var i = 0; i < newSize; ++i)
if (newSlots[i].HashCode > 0 && newSlots[i].Value != null)
newSlots[i].HashCode = Comparer.GetHashCode(newSlots[i].Value) & int.MaxValue;
for (var i = 0; i < newSize; ++i)
{
var pos = newSlots[i].HashCode % newSize;
newSlots[i].Next = newHashBuckets[pos] - 1;
newHashBuckets[pos] = i + 1;
}
Slots = newSlots;
_hashBuckets = newHashBuckets;
}
public void TrimExcess()
{
var newHashBuckets = new int[Count];
var newSlots = new Slot[Count];
Array.Copy(Slots, newSlots, Count);
for (var i = 0; i < Count; i++)
{
var pos = newSlots[i].HashCode % Count;
newSlots[i].Next = newHashBuckets[pos] - 1;
newHashBuckets[pos] = i + 1;
}
_hashBuckets = newHashBuckets;
Slots = newSlots;
}
public bool Remove(T item)
{
if (Count != 0)
{
var hashCode = Comparer.GetHashCode(item) & int.MaxValue;
var iPos = hashCode % _hashBuckets.Length;
var tPos = -1;
for (var sPos = _hashBuckets[iPos] - 1; sPos >= 0; sPos = Slots[sPos].Next)
{
if (Slots[sPos].HashCode == hashCode && Comparer.Equals(Slots[sPos].Value, item))
{
if (tPos < 0)
_hashBuckets[iPos] = Slots[sPos].Next + 1;
else
Slots[tPos].Next = Slots[sPos].Next;
Slots[sPos].HashCode = -1;
Slots[sPos].Value = default;
Slots[sPos].Next = 0;
--Count;
return true;
}
tPos = sPos;
}
}
return false;
}
private int FindEntry(T item, int hashCode)
{
for (var position = _hashBuckets[hashCode % _hashBuckets.Length] - 1; position >= 0; position = Slots[position].Next)
if (Slots[position].HashCode == hashCode && Comparer.Equals(Slots[position].Value, item))
{
Position = position;
return position;
}
return -1;
}
public int FindEntry(T item)
{
return FindEntry(item, Comparer.GetHashCode(item) & int.MaxValue);
}
public void ExceptWith(IEnumerable<T> other)
{
if (other == null)
throw new Exception("The other set must not be null.");
if (Count == 0)
return;
if (Equals(other, this))
Clear();
else
foreach (var obj in other)
Remove(obj);
}
public void UnionWith(IEnumerable<T> other)
{
if (other == null)
throw new Exception("The other set must not be null.");
foreach (var obj in other)
Add(obj);
}
public bool Overlaps(IEnumerable<T> other)
{
if (other == null)
throw new Exception("The other set must not be null.");
return Count != 0 && other.Any(Contains);
}
public bool ContainsAllElements(IEnumerable<T> other)
{
return other.All(Contains);
}
public int RemoveWhere(Predicate<T> pred)
{
if (pred == null)
throw new Exception("The Predicate cannot be null.");
var matches = 0;
for (var i = 0; i < Count; ++i)
if (Slots[i].HashCode >= 0)
{
var obj = Slots[i].Value;
if (pred(obj) && Remove(obj))
++matches;
}
return matches;
}
internal struct Slot
{
public int HashCode;
public int Next;
public T Value;
}
}