Tag: Jagged Array

Jagged Array Collection Class (No Copy Resize)

Updated: Jun-21,2021

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
/// <summary>
///     Uses a multidimensional array to create a growable array with out copy or re-allocation.
/// </summary>
[DebuggerDisplay("Count = {Count}")]
[Serializable]
public struct JaggedArray<T> : IEnumerable<T>, IDisposable
{
    private const int   FirstDimensionMax = 4096;
    public const  int   ShiftCount        = 19;
    public const  int   Granularity       = 1 << ShiftCount;
    private       bool  _disposed;
    private       T[][] _array;
    public        int   Count;
    public        int   Length;
    public        int   NumberOfActiveArrays;
    public        bool  Allocated;
    public JaggedArray(int size)
    {
        if (size < Granularity)
            size = Granularity;
        try
        {
            NumberOfActiveArrays = (size + (Granularity - 1)) / Granularity;
            Length               = NumberOfActiveArrays       * Granularity;
            _array               = new T[FirstDimensionMax][];
            for (var i = 0; i < NumberOfActiveArrays; ++i)
                _array[i] = new T[Granularity];
        }
        catch (Exception ex)
        {
            throw new Exception($"Exception: {ex.Message}");
        }
        Count     = 0;
        _disposed = false;
        Allocated = true;
    }
    public T this[int index]
    {
        get
        {
            if (index >= Length)
                throw new Exception($"Getter: Index out of bounds, Index: '{index}' must be less than the Length: '{Length}'.");
            return _array[index >> ShiftCount][index & (Granularity - 1)];
        }
        set
        {
            if (index >= Length)
                ResizeArray();
            _array[index >> ShiftCount][index & (Granularity - 1)] = value;
            Count++;
        }
    }
    public void Dispose()
    {
        Dispose(true);
    }
    IEnumerator<T> IEnumerable<T>.GetEnumerator()
    {
        return GetEnumerator();
    }
    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
    public void Add(T Item)
    {
        if (Count >= Length)
            ResizeArray();
        var x = Count >> ShiftCount;
        var y = Count & (Granularity - 1);
        _array[x][y] = Item;
        Count++;
    }
    private void ResizeArray()
    {
        try
        {
            _array[NumberOfActiveArrays] = new T[Granularity];
            NumberOfActiveArrays++;
        }
        catch (Exception ex)
        {
            throw new Exception($"Exception: {ex.Message}");
        }
    }
    public void Zero()
    {
        for (var a = 0L; a < NumberOfActiveArrays; a++)
            _array[a] = Array.Empty<T>();
        Count = 0;
    }
    public void Clear()
    {
        for (var a = 0L; a < NumberOfActiveArrays; a++)
            Array.Clear(_array[a], 0, Granularity);
        Count = 0;
    }
    public int IndexOf(T item)
    {
        var i = 0;
        for (; i < NumberOfActiveArrays; i++)
        {
            var pos = Array.IndexOf(_array[i], item, 0);
            if (pos != -1)
                return i * Granularity + pos;
        }
        return -1;
    }
    public JaggedArray<T> Copy(int newsize)
    {
        var temp = new JaggedArray<T>(newsize);
        for (var a = 0L; a < NumberOfActiveArrays; a++)
            Array.Copy(_array[a], temp._array[a], Granularity);
        temp.Count = Count;
        return temp;
    }
    public void FromArray(T[][] array)
    {
        NumberOfActiveArrays = array.GetUpperBound(0) + 1;
        Length               = NumberOfActiveArrays * Granularity;
        _array               = new T[NumberOfActiveArrays][];
        for (var i = 0; i < NumberOfActiveArrays; ++i)
            _array[i] = new T[Granularity];
        for (var a = 0L; a < NumberOfActiveArrays; a++)
            Array.Copy(array[a], _array[a], Granularity);
    }
    public T[][] ToRawArray()
    {
        var ta = new T[NumberOfActiveArrays][];
        for (var i = 0; i < NumberOfActiveArrays; ++i)
            ta[i] = new T[Granularity];
        for (var a = 0L; a < NumberOfActiveArrays; a++)
            Array.Copy(_array[a], ta[a], Granularity);
        return ta;
    }
    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 void Dispose(bool disposing)
    {
        if (!_disposed)
            if (disposing)
                _array = null;
        _disposed = true;
    }
    public IEnumerator<T> GetEnumerator()
    {
        return GetEnum();
    }
    public IEnumerator<T> GetEnum()
    {
        for (var i = 0; i < Count; i++)
            yield return this[i];
    }
}