Skip to content

Instantly share code, notes, and snippets.

@mjs3339
Created July 27, 2021 10:24
Show Gist options
  • Save mjs3339/cd0d44aff740ce7908df40436f3580ad to your computer and use it in GitHub Desktop.
Save mjs3339/cd0d44aff740ce7908df40436f3580ad to your computer and use it in GitHub Desktop.
Internal Mini HashSet version 15
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
[DebuggerDisplay("Count = {" + nameof(Count) + "}")]
[Serializable]
public class MSet15<T>
{
private int[] _hashBuckets;
internal IEqualityComparer<T> Comparer;
internal int Position;
internal Slot[] Slots;
public bool SlowGrowth;
public MSet15() : this(101, EqualityComparer<T>.Default)
{
}
public MSet15(int size) : this(size, EqualityComparer<T>.Default)
{
}
public MSet15(IEqualityComparer<T> comparer) : this(31, comparer)
{
}
public MSet15(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 MSet15(IEnumerable<T> collection, IEqualityComparer<T> comparer)
{
if (comparer == null)
comparer = EqualityComparer<T>.Default;
var enumerable = collection as T[] ?? collection.ToArray();
var size = enumerable.Length;
Comparer = comparer;
_hashBuckets = new int[size];
Slots = new Slot[size];
Count = 0;
Position = -1;
foreach (var i in enumerable)
Add(i);
}
public int Count
{
get;
private set;
}
public IEnumerator<T> GetEnumerator()
{
for (var i = 0; i < Count; i++)
if (Slots[i].HashCode > 0)
yield return Slots[i].Value;
}
public bool Add(T item)
{
var hashCode = Comparer.GetHashCode(item) & int.MaxValue;
if (FindEntry(item, hashCode) != -1)
return true;
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;
}
public void AddRange(IEnumerable<T> collection)
{
foreach (var i in collection)
Add(i);
}
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;
}
public bool Contains(T item)
{
return FindEntry(item, Comparer.GetHashCode(item) & int.MaxValue) != -1;
}
public T[] ToArray()
{
var newArray = new T[Count];
using (var en = GetEnumerator())
{
var ptr = 0;
while (en.MoveNext())
{
var value = en.Current;
if (value == null)
break;
newArray[ptr++] = value;
}
return newArray;
}
}
private void Resize()
{
var newSize = !SlowGrowth ? _hashBuckets.Length + _hashBuckets.Length / 4 * 3 : _hashBuckets.Length + 1;
var newSlots = new Slot[newSize];
var newHashBuckets = new int[newSize];
var newCount = 0;
var en = GetEnumerator();
while (en.MoveNext())
{
var item = en.Current;
var hashCode = Comparer.GetHashCode(item) & int.MaxValue;
var hashPos = hashCode % newHashBuckets.Length;
newSlots[newCount].Next = newHashBuckets[hashPos] - 1;
newSlots[newCount].Value = item;
newSlots[newCount].HashCode = hashCode;
newHashBuckets[hashPos] = newCount + 1;
++newCount;
}
Slots = newSlots;
_hashBuckets = newHashBuckets;
Count = newCount;
}
public 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);
}
internal struct Slot
{
public int HashCode;
public int Next;
public T Value;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment