Last active
April 9, 2019 21:54
-
-
Save mjs3339/cc4d35543fd3c054f97fe78ccc4d26ad to your computer and use it in GitHub Desktop.
C# TinySet Class Base Hash
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
internal IEqualityComparer<T> Comparer; | |
public int Position; | |
public int Resizes; | |
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; | |
Resizes = 0; | |
} | |
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; | |
Resizes = 0; | |
} | |
public void Clear() | |
{ | |
var size = Slots.Length; | |
_hashBuckets = new int[size]; | |
Slots = new Slot[size]; | |
Count = 0; | |
Position = -1; | |
Resizes = 0; | |
} | |
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) | |
Resize(); | |
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; | |
} | |
private void Resize() | |
{ | |
Resizes++; | |
var log = Math.Log(_hashBuckets.Length); | |
var inv = 1.0 / log * 2; | |
var newSize = _hashBuckets.Length * (1.0 + inv); | |
SetSizeAndOrForceNewHashCodes((int) newSize); | |
} | |
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 != -1) | |
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; | |
} | |
} | |
internal class HashSetDebugView<T> | |
{ | |
private readonly HashSet<T> _set; | |
public HashSetDebugView(HashSet<T> set) | |
{ | |
if (set == null) | |
throw new ArgumentNullException(nameof(set)); | |
_set = set; | |
} | |
[DebuggerBrowsable(DebuggerBrowsableState.RootHidden)] | |
public T[] Items => _set.ToArray(); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment