Small Hash Set Class (Minimal)<\/p>\n\n\n\n
Updated: July-23,2021<\/p>\n\n\n\n
using System;\nusing System.Collections.Generic;\nusing System.Diagnostics;\nusing System.Linq;\n\n[DebuggerDisplay(\"Count = {\" + nameof(Count) + \"}\")]\n[Serializable]\npublic class MSet15<T>\n{\n private int[] _hashBuckets;\n internal IEqualityComparer<T> Comparer;\n internal int Position;\n internal Slot[] Slots;\n public bool SlowGrowth;\n public MSet15() : this(101, EqualityComparer<T>.Default)\n {\n }\n public MSet15(int size) : this(size, EqualityComparer<T>.Default)\n {\n }\n public MSet15(IEqualityComparer<T> comparer) : this(31, comparer)\n {\n }\n public MSet15(int size, IEqualityComparer<T> comparer)\n {\n if (comparer == null)\n comparer = EqualityComparer<T>.Default;\n Comparer = comparer;\n _hashBuckets = new int[size];\n Slots = new Slot[size];\n Count = 0;\n Position = -1;\n }\n public MSet15(IEnumerable<T> collection, IEqualityComparer<T> comparer)\n {\n if (comparer == null)\n comparer = EqualityComparer<T>.Default;\n var enumerable = collection as T[] ?? collection.ToArray();\n var size = enumerable.Length;\n Comparer = comparer;\n _hashBuckets = new int[size];\n Slots = new Slot[size];\n Count = 0;\n Position = -1;\n foreach (var i in enumerable)\n Add(i);\n }\n public int Count\n {\n get;\n private set;\n }\n public IEnumerator<T> GetEnumerator()\n {\n for (var i = 0; i < Count; i++)\n if (Slots[i].HashCode > 0)\n yield return Slots[i].Value;\n }\n public bool Add(T item)\n {\n var hashCode = Comparer.GetHashCode(item) & int.MaxValue;\n if (FindEntry(item, hashCode) != -1)\n return true;\n if (Count >= Slots.Length)\n Resize();\n var hashPos = hashCode % _hashBuckets.Length;\n Slots[Count].Next = _hashBuckets[hashPos] - 1;\n Slots[Count].Value = item;\n Slots[Count].HashCode = hashCode;\n _hashBuckets[hashPos] = Count + 1;\n Position = Count;\n ++Count;\n return false;\n }\n\n public void AddRange(IEnumerable<T> collection)\n {\n foreach (var i in collection)\n Add(i);\n }\n public bool Remove(T item)\n {\n if (Count != 0)\n {\n var hashCode = Comparer.GetHashCode(item) & int.MaxValue;\n var iPos = hashCode % _hashBuckets.Length;\n var tPos = -1;\n for (var sPos = _hashBuckets[iPos] - 1; sPos >= 0; sPos = Slots[sPos].Next)\n {\n if (Slots[sPos].HashCode == hashCode && Comparer.Equals(Slots[sPos].Value, item))\n {\n if (tPos < 0)\n _hashBuckets[iPos] = Slots[sPos].Next + 1;\n else\n Slots[tPos].Next = Slots[sPos].Next;\n Slots[sPos].HashCode = -1;\n Slots[sPos].Value = default;\n Slots[sPos].Next = 0;\n --Count;\n return true;\n }\n tPos = sPos;\n }\n }\n return false;\n }\n public bool Contains(T item)\n {\n return FindEntry(item, Comparer.GetHashCode(item) & int.MaxValue) != -1;\n }\n public T[] ToArray()\n {\n var newArray = new T[Count];\n using (var en = GetEnumerator())\n {\n var ptr = 0;\n while (en.MoveNext())\n {\n var value = en.Current;\n if (value == null)\n break;\n newArray[ptr++] = value;\n }\n return newArray;\n }\n }\n private void Resize()\n {\n var newSize = !SlowGrowth ? _hashBuckets.Length + _hashBuckets.Length \/ 4 * 3 : _hashBuckets.Length + 1;\n var newSlots = new Slot[newSize];\n var newHashBuckets = new int[newSize];\n var newCount = 0;\n var en = GetEnumerator();\n while (en.MoveNext())\n {\n var item = en.Current;\n var hashCode = Comparer.GetHashCode(item) & int.MaxValue;\n var hashPos = hashCode % newHashBuckets.Length;\n newSlots[newCount].Next = newHashBuckets[hashPos] - 1;\n newSlots[newCount].Value = item;\n newSlots[newCount].HashCode = hashCode;\n newHashBuckets[hashPos] = newCount + 1;\n ++newCount;\n }\n Slots = newSlots;\n _hashBuckets = newHashBuckets;\n Count = newCount;\n }\n public int FindEntry(T item, int hashCode)\n {\n for (var position = _hashBuckets[hashCode % _hashBuckets.Length] - 1; position >= 0; position = Slots[position].Next)\n if (Slots[position].HashCode == hashCode && Comparer.Equals(Slots[position].Value, item))\n {\n Position = position;\n return position;\n }\n return -1;\n }\n public int FindEntry(T item)\n {\n return FindEntry(item, Comparer.GetHashCode(item) & int.MaxValue);\n }\n internal struct Slot\n {\n public int HashCode;\n public int Next;\n public T Value;\n }\n}<\/pre>\n","protected":false},"excerpt":{"rendered":"Small Hash Set Class (Minimal) Updated: July-23,2021<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[2],"tags":[58,57],"_links":{"self":[{"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/posts\/154"}],"collection":[{"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/comments?post=154"}],"version-history":[{"count":2,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/posts\/154\/revisions"}],"predecessor-version":[{"id":506,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/posts\/154\/revisions\/506"}],"wp:attachment":[{"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/media?parent=154"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/categories?post=154"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/tags?post=154"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}