DynamicFSList.cs

Fast Search Concurrent Non-Concurrent List

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
[DebuggerDisplay("Count = {" + nameof(Count) + "}")]
public class DynamicFSList<T> : MonitorActionFunc, IEnumerable<T>
{
    private static IEqualityComparer<T> Comparer;
    private         VerticalList[]       _verticalLists;
    public          int                  Count;

    /// <summary>
    /// The initial size should be at least 1/8 of the expected total number of objects.
    /// For faster searching make initial size equal to the expected total number of objects.
    /// </summary>
    /// <param name="size"></param>
    public DynamicFSList(int size) : this(size, EqualityComparer<T>.Default)
    {
    }
    public DynamicFSList(int size, IEqualityComparer<T> comparer)
    {
        if (comparer == null)
            comparer = EqualityComparer<T>.Default;
        Comparer       = comparer;
        _verticalLists = new VerticalList[size];
        Count          = 0;
    }
    public (int mDepth, int index) MaximumListLength => GetMaximumListLength();
    public int                     TrueItemCount     => GetItemCount();
    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
    public IEnumerator<T> GetEnumerator()
    {
        var tmpThis = this;
        return tmpThis.Lock(tmpThis, () =>
        {
            return GetEnum();
        });
    }
    public void Clear()
    {
        _verticalLists.Clear();
    }
    public void Add(T item)
    {
        var tmpThis = this;
        tmpThis.Lock(tmpThis, () =>
        {
            var hashCode = Comparer.GetHashCode(item) & int.MaxValue;
            var pos      = hashCode % _verticalLists.Length;
            if (_verticalLists[pos] == null)
                _verticalLists[pos] = new VerticalList();
            _verticalLists[pos].Add(item);
            Count++;
            if (Count > _verticalLists.Length << 3)
                EnsureSize();
        });
    }
    public int AddWithLocation(T item)
    {
        var tmpThis = this;
        return tmpThis.Lock(tmpThis, () =>
        {
            var hashCode = Comparer.GetHashCode(item) & int.MaxValue;
            var pos      = hashCode % _verticalLists.Length;
            if (_verticalLists[pos] == null)
                _verticalLists[pos] = new VerticalList();
            _verticalLists[pos].Add(item);
            Count++;
            if (Count > _verticalLists.Length << 3)
                EnsureSize();
            return FindEntry(item, hashCode);
        });
    }
    public T[] ToArray()
    {
        var tmpThis = this;
        return tmpThis.Lock(tmpThis, () =>
        {
            var newArray = new T[Count];
            var ptr      = 0;
            for (var i = 0; i < _verticalLists.Length; i++)
                if (_verticalLists[i] != null)
                    for (var j = 0; j < _verticalLists[i].Count; ++j)
                    {
                        newArray[ptr] = _verticalLists[i].Values[j];
                        ptr++;
                    }
            return newArray;
        });
    }
    private (int mDepth, int index) GetMaximumListLength()
    {
        var max = 0;
        var j   = 0;
        for (var i = 0; i < _verticalLists.Length; i++)
            if (_verticalLists[i] != null)
            {
                var count = _verticalLists[i].Count;
                if (count > max)
                {
                    max = count;
                    j   = i;
                }
            }
        return (max, j);
    }
    private int GetItemCount()
    {
        var count = 0;
        for (var i = 0; i < _verticalLists.Length; i++)
            if (_verticalLists[i] != null)
            {
                var c = _verticalLists[i].Count;
                count += c;
            }
        return count;
    }
    public int FindEntry(T item)
    {
        var tmpThis = this;
        return tmpThis.Lock(tmpThis, () =>
        {
            var hashCode = Comparer.GetHashCode(item) & int.MaxValue;
            return FindEntry(item, hashCode);
        });
    }
    private int FindEntry(T item, int hashCode)
    {
        var tmpThis = this;
        return tmpThis.Lock(tmpThis, () =>
        {
            if (Count == 0)
                return -1;
            var pos = hashCode % _verticalLists.Length;
            if (_verticalLists[pos] == null)
                _verticalLists[pos] = new VerticalList();
            foreach (var i in _verticalLists[pos].Values)
                if (Comparer.Equals(i, item))
                    return pos;
            return -1;
        });
    }
    private void EnsureSize()
    {
        var cArray  = ToArray();
        var newSize = Count >> (1 + Count);
        _verticalLists = new VerticalList[newSize];
        foreach (var i in cArray)
        {
            var hashCode = Comparer.GetHashCode(i) & int.MaxValue;
            var pos      = hashCode % _verticalLists.Length;
            if (_verticalLists[pos] == null)
                _verticalLists[pos] = new VerticalList();
            _verticalLists[pos].Add(i);
        }
    }
    public bool Contains(T item)
    {
        var tmpThis = this;
        return tmpThis.Lock(tmpThis, () =>
        {
            var hashCode = Comparer.GetHashCode(item) & int.MaxValue;
            return FindEntry(item, hashCode) != -1;
        });
    }
    private IEnumerator<T> GetEnum()
    {
        for (var i = 0; i < _verticalLists.Length; i++)
            if (_verticalLists[i] != null)
                for (var j = 0; j < _verticalLists[i].Count; ++j)
                    yield return _verticalLists[i].Values[j];
    }
    private class VerticalList
    {
        public int Count;
        public T[] Values;
        public VerticalList()
        {
            Values = new T[3];
            Count  = 0;
        }
        public void Add(T item)
        {
            if (Contains(item))
                return;
            if (Count >= Values.Length)
                Array.Resize(ref Values, Values.Length + 3);
            Values[Count] = item;
            Count++;
        }
        private bool Contains(T item)
        {
            foreach (var i in Values)
                if (Comparer.Equals(i, item))
                    return true;
            return false;
        }
    }
}

Leave a Reply

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