ObjectBase.cs

Base Object Array Class

Updated: May-13,2021

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Runtime.Serialization;
using System.Security.Cryptography;
using System.Threading;
/// <summary>
///     Name: ObjectBase.cs
///     Date: January-1, 2021
///     Note: Map indexed object array.
///     Attn: Should be used for ALL object classes going forward *** MJS *** 4.11.21
/// </summary>
[DebuggerDisplay("Count = {" + nameof(Count) + "}")]
[Serializable]
public class ObjectBase : MonitorActionFuncWrapper, IEnumerable<object>
{
    [NonSerialized] private static readonly SizeHelper32      _sh = new();
    [NonSerialized] private readonly        SerializationInfo _sInfo;
    private volatile                        object[]          _array;
    [NonSerialized] private                 HashAlgorithm     _hash;
    [NonSerialized] private volatile        Set20B            _map;
    public volatile                         int               Count;
    public ObjectBase() : this(1024)
    {
    }
    public ObjectBase(int size, int bitWidth = 64)
    {
        BitWidth = bitWidth;
        SelectHashAlgorithm(bitWidth);
        _array = new object[size];
        _map   = new Set20B(size);
    }
    public ObjectBase(ICollection col, int size, int bitWidth = 64)
    {
        BitWidth = bitWidth;
        SelectHashAlgorithm(bitWidth);
        _array = new object[size];
        _map   = new Set20B(size);
        AddRange(col);
    }
    protected ObjectBase(SerializationInfo info, StreamingContext context)
    {
        _sInfo = info;
    }
    public object this[int index]
    {
        get
        {
            return Lock(this, () =>
            {
                var array = _array;
                if (index >= Count)
                    throw new Exception("Error: Index out of range.");
                return array[index];
            });
        }
    }
    public int BitWidth
    {
        get;
        private set;
    }
    public KeyValuePair<IGrouping<int, int>, int>[] BucketDepthList
    {
        get
        {
            var lst = new List<int>();
            foreach (var i in _map)
                lst.Add(_map.GetBucketDepth(i).bucketDepth);
            var grp = lst.GroupBy(x => x)
                .Where(g => g.Count() > 1)
                .ToDictionary(x => x, y => y.Count())
                .ToArray()
                .OrderByDescending(z => z.Value)
                .ToArray();
            return grp;
        }
    }
    public IEnumerator<object> GetEnumerator()
    {
        return Lock(this, () =>
        {
            return GetEnum();
        });
    }
    IEnumerator IEnumerable.GetEnumerator()
    {
        return Lock(this, () =>
        {
            return GetEnum();
        });
    }
    public void GetObjectData(SerializationInfo info, StreamingContext context)
    {
        info.AddValue("BitWidth", BitWidth);
        info.AddValue("Array",    _array, typeof(object[]));
    }
    public void OnDeserialization(object sender)
    {
        if (_sInfo == null)
            return;
        BitWidth = _sInfo.GetInt32("BitWidth");
        Count    = 0;
        var array = (object[]) _sInfo.GetValue("Array", typeof(object[]));
        if (array == null)
            throw new Exception("Array cannot be null.");
        foreach (var t in array)
            Add(t);
    }
    public bool Add(object item)
    {
        return Lock(this, () =>
        {
            var (idx, exists) = GetIndex(item);
            if (idx >= _array.Length)
                Array.Resize(ref _array, (int) _sh.GetNewSize((ulong) _array.Length));
            if (exists == false)
            {
                _array[idx] = item;
                Interlocked.Increment(ref Count);
            }
            return exists == false;
        });
    }
    public void AddRange(ICollection col)
    {
        var array = col.Cast<object>().ToArray();
        array.AsParallel().WithDegreeOfParallelism(2).ForAll(i =>
        {
            Add(i);
        });
    }
    public void Clear()
    {
        Lock(this, () =>
        {
            _array = new object[_array.Length];
            _map   = new Set20B(_array.Length);
        });
    }
    private IEnumerator<object> GetEnum()
    {
        var ary = _array;
        var cnt = Count;
        for (var i = 0; i < cnt; i++)
            yield return ary[i];
    }
    public object[] ToArray()
    {
        return Lock(this, () =>
        {
            var newArray = new object[Count];
            using (var en = GetEnumerator())
            {
                var ptr = 0;
                while (en.MoveNext())
                {
                    var value = en.Current;
                    if (value == null)
                        break;
                    newArray[ptr++] = value;
                }
                return newArray;
            }
        });
    }
    public bool Contains(object item)
    {
        return Lock(this, () =>
        {
            return MapContains(item);
        });
    }
    private bool MapContains(object obj)
    {
        if (obj == null)
            throw new ArgumentNullException(nameof(obj));
        var bytes = obj.GetBytes();
        var hash  = _hash.ComputeHash(bytes, 0, bytes.Length);
        return _map.Contains(hash);
    }
    internal (int idx, bool exists) GetIndex(object obj, bool add = true)
    {
        return Lock(this, () =>
        {
            var bytes  = obj.GetBytes();
            var hash   = _hash.ComputeHash(bytes, 0, bytes.Length);
            var exists = false;
            if (!_map.Contains(hash))
            {
                if (add)
                    _map.Add(hash);
            }
            else
            {
                exists = true;
            }
            return (_map.FindEntry(hash), exists);
        });
    }
    private void SelectHashAlgorithm(int bitWidth)
    {
        BitWidth = bitWidth;
        switch (bitWidth)
        {
            case 64:
                _hash = new Fnv1a64Fast();
                break;
            case 128:
                _hash = new FNVx();
                break;
            case 256:
                _hash = new FNVx(256);
                break;
            case 512:
                _hash = new FNVx(512);
                break;
            case 1024:
                _hash = new FNVx(1024);
                break;
            default:
                throw new ArgumentException("Supported bit widths are: 64, 128, 256, 512 and 1024 Bits.");
        }
    }
    public bool Remove(object item)
    {
        var (idx, exists) = GetIndex(item);
        if (exists)
        {
            var tob = new ObjectBase(_array.Length, BitWidth);
            for (var i = 0; i < Count; i++)
                if (i != idx)
                    tob.Add(_array[i]);
            Count  = tob.Count;
            _array = tob._array;
            _map   = tob._map;
            return true;
        }
        return false;
    }
    public bool Remove(int index)
    {
        if (index < _array.Length)
        {
            var (idx, exists) = GetIndex(_array[index]);
            if (exists && idx == index)
            {
                var tob = new ObjectBase(_array.Length, BitWidth);
                for (var i = 0; i < Count; i++)
                    if (i != idx)
                        tob.Add(_array[i]);
                Count  = tob.Count;
                _array = tob._array;
                _map   = tob._map;
                return true;
            }
        }
        return false;
    }
    public void UnionWith(IEnumerable<object> other)
    {
        if (other == null)
            throw new ArgumentNullException(nameof(other));
        foreach (var obj in other)
            Add(obj);
    }
    public void ExceptWith(IEnumerable<object> other)
    {
        if (other == null)
            throw new ArgumentNullException(nameof(other));
        if (Equals(other, this))
            Clear();
        else
            foreach (var obj in other)
                Remove(obj);
    }
    public bool Overlaps(IEnumerable<object> other)
    {
        if (other == null)
            throw new ArgumentNullException(nameof(other));
        foreach (var obj in other)
            if (Contains(obj))
                return true;
        return false;
    }
    public int RemoveWhere(Predicate<object> match)
    {
        if (match == null)
            throw new ArgumentNullException(nameof(match));
        var num = 0;
        for (var i = 0; i < Count; ++i)
        {
            var obj = _array[i];
            if (match(obj) && Remove(obj))
                ++num;
        }
        return num;
    }
    public bool ContainsAllElements(IEnumerable<object> other)
    {
        foreach (var obj in other)
            if (!Contains(obj))
                return false;
        return true;
    }
    public void TrimExcess()
    {
        Array.Resize(ref _array, Count);
    }
    internal class Set20B
    {
        private int    _count;
        private int[]  _hashBuckets;
        private Slot[] _slots;
        public Set20B(int size)
        {
            _hashBuckets = new int[size];
            _slots       = new Slot[size];
            _count       = 0;
        }
        public IEnumerator<byte[]> GetEnumerator()
        {
            for (var i = 0; i < _count; i++)
                if (_slots[i].HashCode > 0)
                    yield return _slots[i].Value;
        }
        public bool Add(byte[] item)
        {
            var hashCode = 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;
            ++_count;
            return false;
        }
        private void Resize()
        {
            var newSize        = (int) _sh.GetNewSize((ulong) _hashBuckets.Length);
            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 = 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;
        }
        private int FindEntry(byte[] item, int hashCode)
        {
            for (var position = _hashBuckets[hashCode % _hashBuckets.Length] - 1; position >= 0; position = _slots[position].Next)
                if (_slots[position].HashCode == hashCode && Equals(_slots[position].Value, item))
                    return position;
            return -1;
        }
        public int FindEntry(byte[] item)
        {
            var hashCode = GetHashCode(item) & int.MaxValue;
            for (var position = _hashBuckets[hashCode % _hashBuckets.Length] - 1; position >= 0; position = _slots[position].Next)
                if (_slots[position].HashCode == hashCode && Equals(_slots[position].Value, item))
                    return position;
            return -1;
        }
        public (int bucketDepth, bool exists) GetBucketDepth(byte[] item)
        {
            var hashCode    = GetHashCode(item) & int.MaxValue;
            var bucketDepth = 1;
            for (var position = _hashBuckets[hashCode % _hashBuckets.Length] - 1; position >= 0; position = _slots[position].Next)
            {
                if (_slots[position].HashCode == hashCode && Equals(_slots[position].Value, item))
                    return (bucketDepth, true);
                ++bucketDepth;
            }
            return (-1, false);
        }
        public bool Contains(byte[] item)
        {
            return FindEntry(item, GetHashCode(item) & int.MaxValue) != -1;
        }
        private static bool Equals(byte[] x, byte[] y)
        {
            if (x == null || y == null)
                return false;
            return x.Length == y.Length && x.Compare(y);
        }
        private static unsafe int GetHashCode(byte[] obj)
        {
            var cbSize = obj.Length;
            var h1     = 0xCBF29CE484222325;
            fixed (byte* pb = obj)
            {
                var nb = pb;
                while (cbSize >= 8)
                {
                    h1     ^= *(ulong*) nb;
                    h1     *= 0x100000001B3;
                    nb     += 8;
                    cbSize -= 8;
                }
            }
            return (int) h1;
        }
        private struct Slot
        {
            public int    HashCode;
            public int    Next;
            public byte[] Value;
        }
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *