Segmented

SegmentedArray.cs

Segmented Array Class

I wrote this array class while investigating the error curve in Prime Number Theorem. I wanted to avoid using blocking while using parallel invoke, while using as little memory as possible.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
public struct SegmentedArray<T>
{
    private readonly IntA<T>[] _array;
    private readonly int       _size;
    public SegmentedArray(int length, int size)
    {
        _array = new IntA<T>[16];
        _size  = size;
    }
    public void Add(T item, int index, long range, long total)
    {
        if (!_array[index].Allocated)
            _array[index] = new IntA<T>(_size);
        var density = (float)_array[index].Count / range;
        var ssic    = total                      * density;
        _array[index].Add(item, (int)ssic);
    }
    public T[] ToArray()
    {
        var totalCount = 0;
        for (var i = 0; i < 16; ++i)
            if (_array[i].Allocated)
                totalCount += _array[i].Count;
        var ta  = new T[totalCount];
        var ptr = 0;
        for (var i = 0; i < 16; ++i)
            if (_array[i].Allocated)
            {
                var it = _array[i].ToArray();
                _array[i].Zero();
                for (var j = 0; j < it.Length; ++j)
                    ta[ptr++] = it[j];
            }
        return ta;
    }
    [DebuggerDisplay("Count = {Count}")]
    internal struct IntA<T> : IEnumerable<T>
    {
        internal T[]  _array;
        internal bool Allocated;
        public IntA(int cap)
        {
            Count     = 0;
            _array    = new T[cap];
            Allocated = true;
        }
        public int Count
        {
            get;
            private set;
        }
        public T this[int index]
        {
            get
            {
                if (index > _array.Length)
                    throw new Exception("Error: Index out of range.");
                return _array[index];
            }
            set
            {
                if (index > _array.Length)
                    throw new Exception("Error: Index out of range.");
                _array[index] = value;
            }
        }
        IEnumerator<T> IEnumerable<T>.GetEnumerator()
        {
            return GetEnumerator();
        }
        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
        public void Add(T item, int suggestedSize)
        {
            if (Count >= _array.Length)
                Array.Resize(ref _array, suggestedSize);
            _array[Count] = item;
            Count++;
        }
        public T[] ToArray()
        {
            var newtArray = new T[Count];
            Array.Copy(_array, 0, newtArray, 0, Count);
            return newtArray;
        }
        public void Clean()
        {
            var newtArray = new T[Count];
            Array.Copy(_array, 0, newtArray, 0, Count);
            _array = newtArray;
        }
        public void Clear()
        {
            Array.Clear(_array, 0, Count);
            Count = 0;
        }
        public void Zero()
        {
            _array = Array.Empty<T>();
            Count  = 0;
        }
        public IEnumerator<T> GetEnumerator()
        {
            return GetEnum();
        }
        public IEnumerator<T> GetEnum()
        {
            for (var i = 0; i < Count; i++)
                yield return _array[i];
        }
    }
}

SegmentedHashSet.cs

Segmented Hashset Class

Useful for input or output buffer for use in parallel invoke operations where unique values are needed.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
public class SegmentedHashSet<T> : IEnumerable<T>
{
    private readonly IntHs<T>[] _array;
    private readonly int        _size;
    private          int        _length;
    public SegmentedHashSet(int length, int size)
    {
        _array = new IntHs<T>[4096];
        for (var i = 0; i < length; ++i)
            _array[i] = new IntHs<T>(size);
        _length = length;
        _size   = size;
    }
    public IEnumerator<T> GetEnumerator()
    {
        throw new NotImplementedException();
    }
    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
    public void Add(T item, int index)
    {
        if (index >= _length)
            for (var i = _length; i <= index; ++i)
            {
                _array[i] = new IntHs<T>(_size);
                _length++;
            }
        if (!ContainedInArray(item))
            _array[index].Add(item);
    }
    private bool ContainedInArray(T item)
    {
        for (var i = 0; i < _length; ++i)
            if (_array[i].Contains(item))
                return true;
        return false;
    }
    public T[] CombineToArray()
    {
        var totalCount = 0;
        for (var i = 0; i < _length; ++i)
            totalCount += _array[i].Count;
        var ta  = new T[totalCount];
        var ptr = 0;
        for (var i = 0; i < _length; ++i)
        {
            var it = _array[i].ToArray();
            _array[i].Zero();
            for (var j = 0; j < it.Length; ++j)
                ta[ptr++] = it[j];
        }
        return ta;
    }
    [DebuggerDisplay("Count = {Count}")]
    internal class IntHs<T> : IEnumerable
    {
        private  Bucket[]             _buckets;
        internal IEqualityComparer<T> Comparer;
        public IntHs(int size) : this(size, null)
        {
        }
        public IntHs(int size, IEqualityComparer<T> comparer)
        {
            if (comparer == null)
                comparer = EqualityComparer<T>.Default;
            Comparer = comparer;
            _buckets = new Bucket[size];
            Count    = 0;
        }
        public int Count
        {
            get;
            private set;
        }
        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
        public void Zero()
        {
            _buckets = null;
            Count    = 0;
        }
        public bool Add(T item)
        {
            if (Count >= _buckets.Length)
                EnsureSize();
            var hashCode = Comparer.GetHashCode(item) & int.MaxValue;
            var apos     = FindEntry(item, hashCode).APos;
            if (apos != -1)
                return false;
            var pos = hashCode % _buckets.Length;
            if (_buckets[pos] == null)
                _buckets[pos] = new Bucket();
            _buckets[pos].Add(item);
            Count++;
            return true;
        }
        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 (int APos, int BPos) FindEntry(T item, int hashCode)
        {
            if (Count == 0)
                return (-1, -1);
            var aPos = hashCode % _buckets.Length;
            var bPos = 0;
            if (_buckets[aPos] == null)
            {
                _buckets[aPos] = new Bucket();
                return (-1, -1);
            }
            foreach (var i in _buckets[aPos].Values)
            {
                if (Equals(i, item))
                    return (aPos, bPos);
                bPos++;
            }
            return (-1, -1);
        }
        private void EnsureSize()
        {
            var cArray = ToArray();
            _buckets = new Bucket[_buckets.Length + _buckets.Length / 4 * 3];
            foreach (var i in cArray)
            {
                var hashCode = Comparer.GetHashCode(i) & int.MaxValue;
                var pos      = hashCode % _buckets.Length;
                if (_buckets[pos] == null)
                    _buckets[pos] = new Bucket();
                _buckets[pos].Add(i);
            }
        }
        public bool Contains(T item)
        {
            var hashCode = Comparer.GetHashCode(item) & int.MaxValue;
            return FindEntry(item, hashCode).APos != -1;
        }
        public IEnumerator<T> GetEnumerator()
        {
            return GetEnum();
        }
        public IEnumerator<T> GetEnum()
        {
            for (var i = 0; i < _buckets.Length; i++)
                if (_buckets[i] != null)
                    for (var j = 0; j < _buckets[i].Count; ++j)
                        yield return _buckets[i].Values[j];
        }
        internal class Bucket
        {
            public int Count;
            public T[] Values;
            public Bucket()
            {
                Values = new T[1];
                Count  = 0;
            }
            public void Add(T item)
            {
                if (Count >= Values.Length)
                    Array.Resize(ref Values, Values.Length + 1);
                Values[Count++] = item;
            }
        }
    }
}

MiniSet.cs

A Small Segmented Set Class

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
/// <summary>
/// Date: 10/03/20 **MJS**
/// Customer set using indexed hash buckets.
/// Possible uses less memory then standard hashset, with very similar search performance.
/// </summary>
/// <typeparam name="T"></typeparam>
[DebuggerDisplay("Count = {" + nameof(Count) + "}")]
[Serializable]
public class MiniSet<T> : IEnumerable<T>
{
    private  Bucket[]             _buckets;
    private  SizeHelper<T>        _newSize = new SizeHelper<T>();
    internal IEqualityComparer<T> Comparer;
    public   int                  Count;
    public   int                  ReSizes;
    public MiniSet(int size) : this(size, EqualityComparer<T>.Default)
    {
    }
    public MiniSet(int size, IEqualityComparer<T> comparer)
    {
        if (comparer == null)
            comparer = EqualityComparer<T>.Default;
        Comparer = comparer;
        _buckets = new Bucket[size];
        Count    = 0;
        ReSizes  = 0;
    }

    public MiniSet(IEnumerable<T> collection, IEqualityComparer<T> comparer)
    {
        if (comparer == null)
            comparer = EqualityComparer<T>.Default;
        Comparer = comparer;
        if (!(collection is ICollection<T> coll))
            return;
        Count    = coll.Count;
        _buckets = new Bucket[Count];
        UnionWith(coll);
    }
    public int                     ElementCount         => GetElementCount();
    public int                     NumberOfEmptyBuckets => GetNumberOfEmptyBuckets();
    public (int mDepth, int index) MaximumBucketDepth   => GetMaximumBucketDepth();
    public float                   LoadRatio            => GetLoadRatio();
    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
    public void Clear()
    {
        _buckets.Clear();
    }
    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 Add(T item)
    {
        EnsureSize();
        var hashCode = Comparer.GetHashCode(item) & int.MaxValue;
        if (FindEntry(item, hashCode).APos != -1)
            return false;
        var pos = hashCode % _buckets.Length;
        if (_buckets[pos] == null)
            _buckets[pos] = new Bucket();
        _buckets[pos].Add(item);
        Count++;
        return true;
    }

    public int AddRange(IEnumerable<T> items)
    {
        return items.Sum(i => !Add(i) ? 0 : 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 (int APos, int BPos) FindEntry(T item, int hashCode)
    {
        if (Count == 0)
            return (-1, -1);
        var aPos = hashCode % _buckets.Length;
        var bPos = 0;
        if (_buckets[aPos] == null)
            _buckets[aPos] = new Bucket();
        foreach (var i in _buckets[aPos].Values)
        {
            if (Comparer.Equals(i, item))
                return (aPos, bPos);
            bPos++;
        }
        return (-1, -1);
    }
    private void EnsureSize()
    {
        if (Count >= _buckets.Length)
        {
            ReSizes++;
            var cArray = ToArray();
            _buckets = new Bucket[_newSize.GetNewSize(_buckets.Length)];
            foreach (var i in cArray)
            {
                var hashCode = Comparer.GetHashCode(i) & int.MaxValue;
                var pos      = hashCode % _buckets.Length;
                if (_buckets[pos] == null)
                    _buckets[pos] = new Bucket();
                _buckets[pos].Add(i);
            }
        }
    }
    public bool Contains(T item)
    {
        var hashCode = Comparer.GetHashCode(item) & int.MaxValue;
        return FindEntry(item, hashCode).APos != -1;
    }
    public IEnumerator<T> GetEnumerator()
    {
        for (var i = 0; i < _buckets.Length; i++)
            if (_buckets[i] != null)
                for (var j = 0; j < _buckets[i].Count; ++j)
                    yield return _buckets[i].Values[j];
    }
    public int GetElementCount()
    {
        var count = 0;
        for (var i = 0; i < _buckets.Length; i++)
            if (_buckets[i] != null)
            {
                var c = _buckets[i].Count;
                count += c;
            }
        return count;
    }
    public int GetNumberOfEmptyBuckets()
    {
        var count = 0;
        for (var i = 0; i < _buckets.Length; i++)
            if (_buckets[i] == null)
                count++;
        return count;
    }
    public int GetNumberOfFilledBuckets()
    {
        var count = 0;
        for (var i = 0; i < _buckets.Length; i++)
            if (_buckets[i] != null)
                count++;
        return count;
    }
    public (int mDepth, int index) GetMaximumBucketDepth()
    {
        var max = 0;
        var j   = 0;
        for (var i = 0; i < _buckets.Length; i++)
            if (_buckets[i] != null)
            {
                var count = _buckets[i].Count;
                if (count > max)
                {
                    max = count;
                    j   = i;
                }
            }
        return (max, j);
    }
    public KeyValuePair<int, int>[] BucketDepthList => GetBucketDepthList();
    public KeyValuePair<int, int>[] GetBucketDepthList()
    {
        var bdic = new Dictionary<int, int>();
        for (var i = 0; i < _buckets.Length; i++)
            if (_buckets[i] != null)
            {
                var count = _buckets[i].Count;
                if (!bdic.ContainsKey(count))
                {
                    bdic.Add(count, 0);
                    bdic[count]++;
                }
                else
                {
                    bdic[count]++;
                }
            }
        return bdic.OrderByDescending(x=>x.Value).ToArray();
    }
    public float GetLoadRatio()
    {
        var x = Count;
        var y = _buckets.Length;
        var r = x / (float) y;
        return r;
    }
    internal class Bucket
    {
        public int Count;
        public T[] Values;
        public Bucket()
        {
            Values = new T[11];
            Count  = 0;
        }
        public void Add(T item)
        {
            if (Count >= Values.Length)
            {
                var ta = new T[Values.Length+3];
                Array.Copy(Values, 0, ta, 0, Count);
                Values = ta;
            }
            Values[Count++] = item;
        }
    }
}