{"id":290,"date":"2020-12-16T03:55:10","date_gmt":"2020-12-16T03:55:10","guid":{"rendered":"https:\/\/michaeljohnsteiner.com\/?p=290"},"modified":"2020-12-16T03:55:10","modified_gmt":"2020-12-16T03:55:10","slug":"bighashsetsa-cs","status":"publish","type":"post","link":"https:\/\/michaeljohnsteiner.com\/index.php\/2020\/12\/16\/bighashsetsa-cs\/","title":{"rendered":"BigHashsetSa.cs"},"content":{"rendered":"\n<p>Big Hash Set based on\u00a0<a href=\"https:\/\/michaeljohnsteiner.com\/index.php\/2020\/12\/14\/bigarray-cs\/\">BigArray.cs<\/a><\/p>\n\n\n\n<p>Uses a single array.<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"csharp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">using System;\nusing System.Collections;\nusing System.Collections.Generic;\nusing System.Diagnostics;\nusing System.Linq;\n[DebuggerDisplay(\"Count = {\" + nameof(Count) + \"}\")]\n[Serializable]\npublic class BigHashsetSa&lt;T> : MonitorActionFunc, IEnumerable\n{\n    public enum Method\n    {\n        Grow,\n        Compress\n    }\n    private volatile BigArray&lt;Bucket>        _buckets;\n    private          long                    _count;\n    private          Method                  _method;\n    internal         IBigEqualityComparer&lt;T> Comparer;\n    public BigHashsetSa(long size, Method method = Method.Grow) : this(size, new BigComparer&lt;T>(), method)\n    {\n    }\n    public BigHashsetSa(long size, IBigEqualityComparer&lt;T> comparer, Method method = Method.Grow)\n    {\n        if (comparer == null)\n            comparer = new BigComparer&lt;T>();\n        Comparer = comparer;\n        _buckets = new BigArray&lt;Bucket>(size);\n        Count    = 0;\n        _method  = method;\n    }\n    public long Count\n    {\n        get\n        {\n            return Lock(this, () =>\n            {\n                return _count;\n            });\n        }\n        private set\n        {\n            Lock(this, () =>\n            {\n                _count = value;\n            });\n        }\n    }\n    public long                       ElementCount         => GetElementCount();\n    public long                       NumberOfEmptyBuckets => GetNumberOfEmptyBuckets();\n    public (long mDepth, long index)  MaximumBucketDepth   => GetMaximumBucketDepth();\n    public float                      LoadRatio            => GetLoadRatio();\n    public KeyValuePair&lt;long, long>[] BucketDepthList      => GetBucketDepthList();\n    IEnumerator IEnumerable.GetEnumerator()\n    {\n        return GetEnumerator();\n    }\n    public void Clear()\n    {\n        _buckets.Clear();\n    }\n    public bool Add(T item)\n    {\n        return Lock(this, () =>\n        {\n            if (_method == Method.Grow)\n                EnsureSize();\n            var hashCode = Comparer.GetHashCode(item) &amp; long.MaxValue;\n            if (FindEntry(item, hashCode).APos != -1)\n                return false;\n            var pos = hashCode % _buckets.Length;\n            if (_buckets[pos] == null)\n                _buckets[pos] = new Bucket();\n            _buckets[pos].Add(item);\n            Count++;\n            return true;\n        });\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 (long APos, long BPos) FindEntry(T item, long hashCode)\n    {\n        if (Count == 0)\n            return (-1, -1);\n        if (hashCode == 0)\n        {\n            var a = 0;\n        }\n        var aPos = hashCode % _buckets.Length;\n        var bPos = 0;\n        if (_buckets[aPos] == null)\n        {\n            _buckets[aPos] = new Bucket();\n            return (-1, -1);\n        }\n        foreach (var i in _buckets[aPos].Values)\n        {\n            if (Comparer.Equals(i, item))\n                return (aPos, bPos);\n            bPos++;\n        }\n        return (-1, -1);\n    }\n    private void EnsureSize()\n    {\n        if (Count >= _buckets.Length)\n        {\n            var cArray = ToArray();\n            _buckets = new BigArray&lt;Bucket>(_buckets.Length + BigArray&lt;T>.Granularity);\n            foreach (var i in cArray)\n            {\n                var hashCode = Comparer.GetHashCode(i) &amp; long.MaxValue;\n                var pos      = hashCode % _buckets.Length;\n                if (_buckets[pos] == null)\n                    _buckets[pos] = new Bucket();\n                _buckets[pos].Add(i);\n            }\n        }\n    }\n    public bool Contains(T item)\n    {\n        return Lock(this, () =>\n        {\n            var hashCode = Comparer.GetHashCode(item) &amp; long.MaxValue;\n            return FindEntry(item, hashCode).APos != -1;\n        });\n    }\n    public IEnumerator&lt;T> GetEnumerator()\n    {\n        return Lock(this, () =>\n        {\n            return GetEnum();\n        });\n    }\n    public IEnumerator&lt;T> GetEnum()\n    {\n        for (var i = 0; i &lt; _buckets.Length; i++)\n            if (_buckets[i] != null)\n                for (var j = 0; j &lt; _buckets[i].Count; ++j)\n                    yield return _buckets[i].Values[j];\n    }\n    public long GetElementCount()\n    {\n        var count = 0;\n        for (var i = 0; i &lt; _buckets.Length; i++)\n            if (_buckets[i] != null)\n            {\n                var c = _buckets[i].Count;\n                count += c;\n            }\n        return count;\n    }\n    public long GetNumberOfEmptyBuckets()\n    {\n        var count = 0;\n        for (var i = 0; i &lt; _buckets.Length; i++)\n            if (_buckets[i] == null)\n                count++;\n        return count;\n    }\n    public long GetNumberOfFilledBuckets()\n    {\n        var count = 0;\n        for (var i = 0; i &lt; _buckets.Length; i++)\n            if (_buckets[i] != null)\n                count++;\n        return count;\n    }\n    public (long mDepth, long index) GetMaximumBucketDepth()\n    {\n        var max = 0;\n        var j   = 0;\n        for (var i = 0; i &lt; _buckets.Length; i++)\n            if (_buckets[i] != null)\n            {\n                var count = _buckets[i].Count;\n                if (count > max)\n                {\n                    max = count;\n                    j   = i;\n                }\n            }\n        return (max, j);\n    }\n    public KeyValuePair&lt;long, long>[] GetBucketDepthList()\n    {\n        var bdic = new Dictionary&lt;long, long>();\n        for (var i = 0; i &lt; _buckets.Length; i++)\n            if (_buckets[i] != null)\n            {\n                var count = _buckets[i].Count;\n                if (!bdic.ContainsKey(count))\n                {\n                    bdic.Add(count, 0);\n                    bdic[count]++;\n                }\n                else\n                {\n                    bdic[count]++;\n                }\n            }\n        return bdic.OrderByDescending(x => x.Value).ToArray();\n    }\n    public float GetLoadRatio()\n    {\n        var x = Count;\n        var y = _buckets.Length;\n        var r = x \/ (float) y;\n        return r;\n    }\n    internal class Bucket\n    {\n        public int Count;\n        public T[] Values;\n        public Bucket()\n        {\n            Values = new T[2];\n            Count  = 0;\n        }\n        public void Add(T item)\n        {\n            if (Count >= Values.Length)\n            {\n                var ta = new T[Values.Length + 1];\n                Array.Copy(Values, 0, ta, 0, Count);\n                Values = ta;\n            }\n            Values[Count++] = item;\n        }\n    }\n}<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Big Hash Set based on\u00a0BigArray.cs Uses a single array.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[2],"tags":[35,140,58,141],"_links":{"self":[{"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/posts\/290"}],"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=290"}],"version-history":[{"count":1,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/posts\/290\/revisions"}],"predecessor-version":[{"id":291,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/posts\/290\/revisions\/291"}],"wp:attachment":[{"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/media?parent=290"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/categories?post=290"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/tags?post=290"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}