< Summary

Information
Class: SwiftCollections.SwiftSortedList<T>
Assembly: SwiftCollections
File(s): File 1: /home/runner/work/SwiftCollections/SwiftCollections/src/SwiftCollections/Collection/SwiftSortedList.cs
File 2: /home/runner/work/SwiftCollections/SwiftCollections/src/SwiftCollections/Collection/SwiftSortedList.SwiftSorterEnumerator.cs
Line coverage
100%
Covered lines: 373
Uncovered lines: 0
Coverable lines: 373
Total lines: 1057
Line coverage: 100%
Branch coverage
100%
Covered branches: 138
Total branches: 138
Branch coverage: 100%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Crap Score Cyclomatic complexity Line coverage
File 1: .cctor()100%11100%
File 1: .ctor()100%11100%
File 1: .ctor(...)100%11100%
File 1: .ctor(...)100%66100%
File 1: .ctor(...)100%88100%
File 1: .ctor(...)100%11100%
File 1: get_InnerArray()100%11100%
File 1: get_Count()100%11100%
File 1: get_Offset()100%11100%
File 1: get_Version()100%11100%
File 1: get_Capacity()100%11100%
File 1: get_Comparer()100%11100%
File 1: get_IsReadOnly()100%11100%
File 1: get_IsSynchronized()100%11100%
File 1: get_SyncRoot()100%22100%
File 1: get_Item(...)100%11100%
File 1: get_State()100%11100%
File 1: set_State(...)100%44100%
File 1: Add(...)100%22100%
File 1: Insert(...)100%88100%
File 1: AddRange(...)100%88100%
File 1: AddRange(...)100%66100%
File 1: AddRange(...)100%44100%
File 1: ShouldUseTemporaryCopy(...)100%44100%
File 1: InitializeFromCollection(...)100%11100%
File 1: InitializeFromEnumerable(...)100%22100%
File 1: CopyToSortedArray(...)100%22100%
File 1: InitializeFromSortedItems(...)100%44100%
File 1: MergeSortedItems(...)100%1010100%
File 1: MergeCollectionItems(...)100%44100%
File 1: MergeEnumerableItems(...)100%66100%
File 1: PopMin()100%22100%
File 1: PopMax()100%22100%
File 1: Remove(...)100%44100%
File 1: RemoveAt(...)100%1010100%
File 1: Clear()100%22100%
File 1: Clear(...)100%44100%
File 1: FastClear()100%22100%
File 1: EnsureCapacity(...)100%22100%
File 1: Resize(...)100%44100%
File 1: RecenterArray()100%11100%
File 1: SetComparer(...)100%22100%
File 1: GetPhysicalIndex(...)100%11100%
File 1: AsReadOnlySpan()100%11100%
File 1: PeekMin()100%11100%
File 1: PeekMax()100%11100%
File 1: Contains(...)100%11100%
File 1: Exists(...)100%44100%
File 1: Find(...)100%44100%
File 1: IndexOf(...)100%22100%
File 1: InsertionPoint(...)100%22100%
File 1: Search(...)100%66100%
File 1: CopyTo(...)100%11100%
File 1: CopyTo(...)100%11100%
File 1: CloneTo(...)100%22100%
File 1: GetEnumerator()100%11100%
File 1: System.Collections.Generic.IEnumerable<T>.GetEnumerator()100%11100%
File 1: System.Collections.IEnumerable.GetEnumerator()100%11100%
File 2: .ctor(...)100%11100%
File 2: get_Current()100%11100%
File 2: System.Collections.IEnumerator.get_Current()100%22100%
File 2: MoveNext()100%22100%
File 2: Reset()100%11100%
File 2: Dispose()100%11100%

File(s)

/home/runner/work/SwiftCollections/SwiftCollections/src/SwiftCollections/Collection/SwiftSortedList.cs

#LineLine coverage
 1//=======================================================================
 2// SwiftSortedList.cs
 3//=======================================================================
 4// MIT License, Copyright (c) 2024-present David Oravsky (mrdav30)
 5// See LICENSE file in the project root for full license information.
 6//=======================================================================
 7
 8using System;
 9using System.Collections;
 10using System.Collections.Generic;
 11using System.Linq;
 12using System.Runtime.CompilerServices;
 13using System.Text.Json.Serialization;
 14using Chronicler;
 15using Chronicler.Diagnostics;
 16using Chronicler.Serialization;
 17using MemoryPack;
 18using SwiftCollections.Utility;
 19
 20namespace SwiftCollections;
 21
 22/// <summary>
 23/// Represents a dynamically sorted collection of elements.
 24/// Provides efficient O(log n) operations for adding, removing, and checking for the presence of elements.
 25/// </summary>
 26/// <remarks>
 27/// The comparer is not serialized. After deserialization the list uses
 28/// <see cref="Comparer{T}.Default"/>.
 29///
 30/// If a custom comparer is required it can be reapplied using
 31/// <see cref="SetComparer(IComparer{T})"/>.
 32/// </remarks>
 33/// <typeparam name="T">The type of elements in the collection.</typeparam>
 34[Serializable]
 35[JsonConverter(typeof(StateJsonConverterFactory))]
 36[MemoryPackable]
 37public partial class SwiftSortedList<T> : IStateBacked<SwiftArrayState<T>>, ISwiftCloneable<T>, IEnumerable<T>, IEnumera
 38{
 39    #region Constants
 40
 41    /// <summary>
 42    /// The default initial capacity of the <see cref="SwiftSortedList{T}"/> if none is specified.
 43    /// Used to allocate a reasonable starting size to minimize resizing operations.
 44    /// </summary>
 45    public const int DefaultCapacity = 8;
 46
 347    private static readonly T[] _emptyArray = Array.Empty<T>();
 48
 49    #endregion
 50
 51    #region Fields
 52
 53    /// <summary>
 54    /// Represents the internal array that stores the sorted elements.
 55    /// </summary>
 56    private T[] _innerArray;
 57
 58    /// <summary>
 59    /// The number of elements contained in the <see cref="SwiftSortedList{T}"/>.
 60    /// </summary>
 61    private int _count;
 62
 63    /// <summary>
 64    /// The offset within the internal array where the logical start of the list begins.
 65    /// Used to efficiently manage insertions and deletions at both ends without excessive shifting.
 66    /// </summary>
 67    private int _offset;
 68
 69    /// <summary>
 70    /// A version counter used to track modifications to the sorted list.
 71    /// Incremented on mutations to detect changes during enumeration and ensure enumerator validity.
 72    /// </summary>
 73    [NonSerialized]
 74    private uint _version;
 75
 76    /// <summary>
 77    /// The comparer used to sort and compare elements in the collection.
 78    /// </summary>
 79    [NonSerialized]
 80    private IComparer<T> _comparer;
 81
 82    /// <summary>
 83    /// An object that can be used to synchronize access to the SwiftList.
 84    /// </summary>
 85    [NonSerialized]
 86    private object? _syncRoot;
 87
 88    #endregion
 89
 90    #region Constructors
 91
 92    /// <summary>
 93    /// Initializes a new instance of the SwiftSortedList class with the default capacity.
 94    /// </summary>
 95    /// <remarks>
 96    /// This constructor creates an empty sorted list.
 97    /// Items added to the list will be automatically ordered according to the default comparer for the item type.
 98    /// </remarks>
 12699    public SwiftSortedList() : this(0) { }
 100
 101    /// <summary>
 102    /// Initializes a new, empty instance of <see cref="SwiftSortedList{T}"/> uisng the specified <see cref="IComparer{T
 103    /// </summary>
 6104    public SwiftSortedList(IComparer<T> comparer) : this(0, comparer) { }
 105
 106    /// <summary>
 107    /// Initializes a new, empty instance of <see cref="SwiftSortedList{T}"/> with the specified initial capacity and <s
 108    /// </summary>
 109    /// <param name="capacity">The starting initial capacity.</param>
 110    /// <param name="comparer">The comparer to use. If null, the default comparer is used.</param>
 83111    public SwiftSortedList(int capacity, IComparer<T>? comparer = null)
 112    {
 83113        _comparer = comparer ?? Comparer<T>.Default;
 114
 83115        if (capacity == 0)
 116        {
 66117            _innerArray = _emptyArray;
 66118            _offset = 0;
 119        }
 120        else
 121        {
 17122            capacity = capacity <= DefaultCapacity ? DefaultCapacity : SwiftHashTools.NextPowerOfTwo(capacity);
 17123            _innerArray = new T[capacity];
 17124            _offset = capacity >> 1; // initial offset half of capacity
 125        }
 17126    }
 127
 128    /// <summary>
 129    /// Initializes a new instance of the <see cref="SwiftList{T}"/> class with elements from the specified collection.
 130    /// The collection must have a known count for optimized memory allocation.
 131    /// </summary>
 132    /// <exception cref="ArgumentException">Thrown if the input collection does not have a known count.</exception>
 23133    public SwiftSortedList(IEnumerable<T> items, IComparer<T>? comparer = null)
 134    {
 23135        ChronicleGuard.ThrowIfNull(items, nameof(items));
 136
 23137        _comparer = comparer ?? Comparer<T>.Default;
 138
 23139        if (items is ICollection<T> collection)
 140        {
 22141            int count = collection.Count;
 22142            if (count == 0)
 143            {
 7144                _innerArray = _emptyArray;
 7145                _offset = 0;
 146            }
 147            else
 148            {
 15149                int capacity = SwiftHashTools.NextPowerOfTwo(count <= DefaultCapacity ? DefaultCapacity : count);
 15150                _innerArray = new T[capacity];
 15151                _offset = (capacity - count) >> 1;
 15152                collection.CopyTo(_innerArray, _offset);
 15153                SwiftArraySortHelper.Sort(_innerArray, _offset, count, _comparer);
 15154                _count = count;
 155            }
 156        }
 157        else
 158        {
 1159            _innerArray = new T[DefaultCapacity];
 1160            _offset = DefaultCapacity >> 1;
 1161            AddRange(items); // Will handle capacity increases as needed
 162        }
 1163    }
 164
 165    ///  <summary>
 166    ///  Initializes a new instance of the <see cref="SwiftSortedList{T}"/> class with the specified <see cref="SwiftArr
 167    ///  </summary>
 168    ///  <param name="state">The state containing the internal array, count, offset, and version for initialization.</pa
 169    [MemoryPackConstructor]
 6170    public SwiftSortedList(SwiftArrayState<T> state)
 171    {
 6172        State = state;
 173
 174        // Validate that the internal array and comparer are not null after deserialization
 6175        ChronicleGuard.ThrowIfNull(_innerArray, nameof(_innerArray));
 6176        ChronicleGuard.ThrowIfNull(_comparer, nameof(_comparer));
 6177    }
 178
 179    #endregion
 180
 181    #region Properties
 182
 183    /// <summary>
 184    /// Gets the underlying array that stores the elements of the collection.
 185    /// </summary>
 186    /// <remarks>
 187    /// The returned array may contain unused elements beyond the logical contents of the collection.
 188    ///</remarks>
 189    [JsonIgnore]
 190    [MemoryPackIgnore]
 22191    public T[] InnerArray => _innerArray;
 192
 193    /// <inheritdoc cref="_count"/>
 194    [JsonIgnore]
 195    [MemoryPackIgnore]
 59196    public int Count => _count;
 197
 198    /// <inheritdoc cref="_offset"/>
 199    [JsonIgnore]
 200    [MemoryPackIgnore]
 26201    public int Offset => _offset;
 202
 203    /// <inheritdoc cref="_version"/>
 204    [JsonIgnore]
 205    [MemoryPackIgnore]
 7206    public uint Version => _version;
 207
 208    /// <summary>
 209    /// Gets the current capacity of the internal array.
 210    /// </summary>
 211    [JsonIgnore]
 212    [MemoryPackIgnore]
 22213    public int Capacity => _innerArray.Length;
 214
 215    /// <inheritdoc cref="_comparer"/>
 216    [JsonIgnore]
 217    [MemoryPackIgnore]
 1218    public IComparer<T> Comparer => _comparer;
 219
 220    /// <inheritdoc/>
 221    [JsonIgnore]
 222    [MemoryPackIgnore]
 1223    public bool IsReadOnly => false;
 224
 225    /// <inheritdoc/>
 226    [JsonIgnore]
 227    [MemoryPackIgnore]
 1228    public bool IsSynchronized => false;
 229
 230    /// <inheritdoc/>
 231    [JsonIgnore]
 232    [MemoryPackIgnore]
 2233    public object SyncRoot => _syncRoot ??= new object();
 234
 235    /// <summary>
 236    /// Gets the element at the specified arrayIndex.
 237    /// </summary>
 238    [JsonIgnore]
 239    [MemoryPackIgnore]
 240    public T this[int index]
 241    {
 242        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 243        get
 244        {
 21245            ChronicleGuard.ThrowIfListIndexInvalid(index, _count);
 20246            return _innerArray[GetPhysicalIndex(index)];
 247        }
 248    }
 249
 250    /// <summary>
 251    /// Gets or sets the current state of the array, including its items and structure.
 252    /// </summary>
 253    /// <remarks>
 254    /// Setting this property replaces the entire contents of the array with the specified state.
 255    /// The setter is intended for internal use and may reset internal metadata such as version and comparer.
 256    /// This property is intended for serialization and deserialization scenarios.
 257    /// </remarks>
 258    [JsonInclude]
 259    [MemoryPackInclude]
 260    public SwiftArrayState<T> State
 261    {
 262        get
 263        {
 3264            var items = new T[_count];
 3265            Array.Copy(_innerArray, _offset, items, 0, _count);
 3266            return new SwiftArrayState<T>(items);
 267        }
 268        internal set
 269        {
 6270            ChronicleGuard.ThrowIfNull(value.Items, nameof(value.Items));
 271
 6272            int count = value.Items.Length;
 273
 6274            if (count == 0)
 275            {
 1276                _innerArray = _emptyArray;
 1277                _offset = 0;
 1278                _count = 0;
 279            }
 280            else
 281            {
 5282                int capacity = SwiftHashTools.NextPowerOfTwo(count <= DefaultCapacity ? DefaultCapacity : count);
 5283                _innerArray = new T[capacity];
 284
 5285                int newOffset = (capacity - count) >> 1;
 286
 5287                Array.Copy(value.Items, 0, _innerArray, newOffset, count);
 288
 5289                _offset = newOffset;
 5290                _count = count;
 291            }
 292
 6293            _version = 0;
 6294            _comparer = Comparer<T>.Default;
 6295        }
 296    }
 297
 298    #endregion
 299
 300    #region Collection Manipulation
 301
 302    /// <inheritdoc/>
 303    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 304    public void Add(T item)
 305    {
 259306        int index = Search(item);
 517307        if (index < 0) index = ~index;
 259308        Insert(item, index);
 259309    }
 310
 311    /// <summary>
 312    /// Inserts an item into the internal array at the specified arrayIndex, shifting elements as needed.
 313    /// </summary>
 314    private void Insert(T item, int index)
 315    {
 259316        ChronicleGuard.ThrowIfArrayIndexInvalid(index, _count, nameof(index));
 259317        if (_offset + _count + 1 > _innerArray.Length)
 37318            Resize(_innerArray.Length * 2);
 319
 259320        int physicalIndex = GetPhysicalIndex(index);
 321
 259322        if (index < (uint)_count)
 323        {
 38324            int distanceToHead = physicalIndex - _offset;
 38325            int distanceToTail = (_offset + _count - 1) - physicalIndex;
 326
 38327            if (distanceToHead >= (uint)distanceToTail)
 328            {
 35329                if ((uint)_offset == 0)
 330                {
 331                    // Ensure capacity for recentering
 1332                    Resize(_innerArray.Length * 2);
 1333                    RecenterArray();
 1334                    physicalIndex = GetPhysicalIndex(index);
 335                }
 336
 35337                _offset--;
 35338                physicalIndex--;
 339                // Shift elements towards the head (left)
 35340                Array.Copy(_innerArray, _offset + 1, _innerArray, _offset, distanceToHead + 1);
 341            }
 342            else  // Shift elements towards the tail (right) to make space
 3343                Array.Copy(_innerArray, physicalIndex, _innerArray, physicalIndex + 1, _count - index);
 344        }
 345
 259346        _innerArray[physicalIndex] = item;
 259347        _count++;
 348
 259349        _version++;
 259350    }
 351
 352    /// <summary>
 353    /// Adds a range of elements to the collection, ensuring they are sorted and merged efficiently.
 354    /// </summary>
 355    /// <remarks>
 356    /// This compacts the active item range for efficiency. Known-count sources reuse existing capacity when possible.
 357    /// </remarks>
 358    public void AddRange(IEnumerable<T> items)
 359    {
 49360        ChronicleGuard.ThrowIfNull(items, nameof(items));
 361
 49362        if (items is ICollection<T> collection)
 363        {
 39364            AddRange(collection);
 39365            return;
 366        }
 367
 10368        if (items is IReadOnlyCollection<T> readOnlyCollection)
 369        {
 5370            AddRange(readOnlyCollection);
 5371            return;
 372        }
 373
 5374        T[] sortedItems = CopyToSortedArray(items);
 5375        if (sortedItems.Length == 0)
 1376            return;
 377
 4378        if ((uint)_count == 0)
 379        {
 2380            InitializeFromSortedItems(sortedItems);
 2381            return;
 382        }
 383
 2384        MergeSortedItems(sortedItems);
 2385    }
 386
 387    private void AddRange(ICollection<T> collection)
 388    {
 39389        int count = collection.Count;
 39390        if (count == 0)
 1391            return;
 392
 38393        if (ShouldUseTemporaryCopy(collection))
 394        {
 1395            T[] sortedItems = collection.ToArray();
 1396            SwiftArraySortHelper.Sort(sortedItems, 0, sortedItems.Length, _comparer);
 1397            MergeSortedItems(sortedItems);
 1398            return;
 399        }
 400
 37401        if ((uint)_count == 0)
 402        {
 28403            InitializeFromCollection(collection);
 28404            return;
 405        }
 406
 9407        MergeCollectionItems(collection, count);
 9408    }
 409
 410    private void AddRange(IReadOnlyCollection<T> collection)
 411    {
 5412        int count = collection.Count;
 5413        if (count == 0)
 1414            return;
 415
 4416        if ((uint)_count == 0)
 417        {
 1418            InitializeFromEnumerable(collection, count);
 1419            return;
 420        }
 421
 3422        MergeEnumerableItems(collection, count);
 3423    }
 424
 425    private bool ShouldUseTemporaryCopy(ICollection<T> collection) =>
 38426        ReferenceEquals(collection, this) ||
 38427        collection is T[] array && ReferenceEquals(array, _innerArray);
 428
 429    private void InitializeFromCollection(ICollection<T> collection)
 430    {
 28431        int count = collection.Count;
 28432        EnsureCapacity(count);
 433
 28434        _offset = (_innerArray.Length - count) >> 1;
 28435        collection.CopyTo(_innerArray, _offset);
 28436        SwiftArraySortHelper.Sort(_innerArray, _offset, count, _comparer);
 437
 28438        _count = count;
 28439        _version++;
 28440    }
 441
 442    private void InitializeFromEnumerable(IEnumerable<T> items, int count)
 443    {
 1444        EnsureCapacity(count);
 445
 1446        _offset = (_innerArray.Length - count) >> 1;
 1447        int index = _offset;
 66448        foreach (T item in items)
 32449            _innerArray[index++] = item;
 450
 1451        SwiftArraySortHelper.Sort(_innerArray, _offset, count, _comparer);
 452
 1453        _count = count;
 1454        _version++;
 1455    }
 456
 457    private T[] CopyToSortedArray(IEnumerable<T> items)
 458    {
 5459        T[] sortedItems = items.ToArray();
 460
 5461        if (sortedItems.Length > 0)
 4462            SwiftArraySortHelper.Sort(sortedItems, 0, sortedItems.Length, _comparer);
 463
 5464        return sortedItems;
 465    }
 466
 467    private void InitializeFromSortedItems(T[] sortedItems)
 468    {
 2469        int initialCapacity = SwiftHashTools.NextPowerOfTwo(sortedItems.Length < DefaultCapacity ? DefaultCapacity : sor
 2470        int newOffset = (initialCapacity - sortedItems.Length) >> 1;
 2471        if ((uint)_innerArray.Length < (uint)initialCapacity)
 1472            _innerArray = new T[initialCapacity];
 473
 2474        Array.Copy(sortedItems, 0, _innerArray, newOffset, sortedItems.Length);
 2475        _offset = newOffset;
 2476        _count = sortedItems.Length;
 2477        _version++;
 2478    }
 479
 480    private void MergeSortedItems(T[] sortedItems)
 481    {
 3482        int newCount = _count + sortedItems.Length;
 3483        int totalRequiredCapacity = newCount + _offset;
 3484        int newCapacity = SwiftHashTools.NextPowerOfTwo(totalRequiredCapacity);
 3485        int mergedOffset = (newCapacity - newCount) >> 1;
 3486        T[] newArray = new T[newCapacity];
 487
 3488        int existingIndex = 0;
 3489        int newItemsIndex = 0;
 3490        int mergedIndex = mergedOffset;
 491
 27492        while (existingIndex < _count && newItemsIndex < sortedItems.Length)
 493        {
 24494            T existingItem = _innerArray[_offset + existingIndex];
 24495            T newItem = sortedItems[newItemsIndex];
 496
 24497            if (_comparer.Compare(existingItem, newItem) <= 0)
 498            {
 21499                newArray[mergedIndex++] = existingItem;
 21500                existingIndex++;
 501            }
 502            else
 503            {
 3504                newArray[mergedIndex++] = newItem;
 3505                newItemsIndex++;
 506            }
 507        }
 508
 509        // Copy any remaining existing items
 20510        while (existingIndex < _count)
 17511            newArray[mergedIndex++] = _innerArray[_offset + existingIndex++];
 512
 513        // Copy any remaining new items
 5514        while (newItemsIndex < sortedItems.Length)
 2515            newArray[mergedIndex++] = sortedItems[newItemsIndex++];
 516
 3517        _innerArray = newArray;
 3518        _offset = mergedOffset;
 3519        _count = newCount;
 520
 3521        _version++;
 3522    }
 523
 524    private void MergeCollectionItems(ICollection<T> collection, int collectionCount)
 525    {
 9526        int existingCount = _count;
 9527        int newCount = existingCount + collectionCount;
 528        T[] target;
 529        int mergedOffset;
 530
 9531        if (_innerArray.Length >= newCount)
 532        {
 8533            target = _innerArray;
 8534            mergedOffset = (_innerArray.Length - newCount) >> 1;
 8535            if (mergedOffset != _offset)
 7536                Array.Copy(_innerArray, _offset, target, mergedOffset, existingCount);
 537        }
 538        else
 539        {
 1540            int newCapacity = SwiftHashTools.NextPowerOfTwo(newCount);
 1541            target = new T[newCapacity];
 1542            mergedOffset = (newCapacity - newCount) >> 1;
 1543            Array.Copy(_innerArray, _offset, target, mergedOffset, existingCount);
 544        }
 545
 9546        int collectionOffset = mergedOffset + existingCount;
 9547        collection.CopyTo(target, collectionOffset);
 9548        SwiftArraySortHelper.Sort(target, mergedOffset, newCount, _comparer);
 549
 9550        _innerArray = target;
 9551        _offset = mergedOffset;
 9552        _count = newCount;
 553
 9554        _version++;
 9555    }
 556
 557    private void MergeEnumerableItems(IEnumerable<T> items, int itemCount)
 558    {
 3559        int existingCount = _count;
 3560        int newCount = existingCount + itemCount;
 561        T[] target;
 562        int mergedOffset;
 563
 3564        if (_innerArray.Length >= newCount)
 565        {
 2566            target = _innerArray;
 2567            mergedOffset = (_innerArray.Length - newCount) >> 1;
 2568            if (mergedOffset != _offset)
 1569                Array.Copy(_innerArray, _offset, target, mergedOffset, existingCount);
 570        }
 571        else
 572        {
 1573            int newCapacity = SwiftHashTools.NextPowerOfTwo(newCount);
 1574            target = new T[newCapacity];
 1575            mergedOffset = (newCapacity - newCount) >> 1;
 1576            Array.Copy(_innerArray, _offset, target, mergedOffset, existingCount);
 577        }
 578
 3579        int index = mergedOffset + existingCount;
 78580        foreach (T item in items)
 36581            target[index++] = item;
 582
 3583        SwiftArraySortHelper.Sort(target, mergedOffset, newCount, _comparer);
 584
 3585        _innerArray = target;
 3586        _offset = mergedOffset;
 3587        _count = newCount;
 588
 3589        _version++;
 3590    }
 591
 592    /// <summary>
 593    /// Removes and returns the minimum element in the sorter.
 594    /// </summary>
 595    /// <returns>The minimum element.</returns>
 596    public T PopMin()
 597    {
 3598        ChronicleGuard.ThrowIfTrue((uint)_count == 0, message: "Cannot pop from an empty list.");
 599
 2600        int index = GetPhysicalIndex(0);
 2601        T ret = _innerArray[index];
 2602        _innerArray[index] = default!;
 2603        _count--;
 604        // Increment _offset as we remove from the front
 2605        _offset = _count == 0 ? _innerArray.Length >> 1 : _offset + 1;
 606
 2607        _version++;
 608
 2609        return ret;
 610    }
 611
 612    /// <summary>
 613    /// Removes and returns the maximum element in the sorter.
 614    /// </summary>
 615    /// <returns>The maximum element.</returns>
 616    public T PopMax()
 617    {
 5618        ChronicleGuard.ThrowIfTrue((uint)_count == 0, message: "Cannot pop from an empty list.");
 619
 4620        int index = GetPhysicalIndex(--_count);
 4621        T ret = _innerArray[index];
 4622        _innerArray[index] = default!;
 5623        if ((uint)_count == 0) _offset = _innerArray.Length >> 1;
 624
 4625        _version++;
 626
 4627        return ret;
 628    }
 629
 630    /// <inheritdoc/>
 631    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 632    public bool Remove(T item)
 633    {
 10634        if ((uint)_count == 0) return false;
 635
 8636        int index = Search(item);
 9637        if (index < 0) return false;
 638
 7639        RemoveAt(index);
 7640        return true;
 641    }
 642
 643    /// <summary>
 644    /// Removes the element at the specified arrayIndex from the sorted list.
 645    /// Shifts elements as needed to maintain the sorted order and efficient space utilization.
 646    /// </summary>
 647    /// <param name="index">The zero-based arrayIndex of the element to remove.</param>
 648    public void RemoveAt(int index)
 649    {
 17650        ChronicleGuard.ThrowIfListIndexInvalid(index, _count);
 651
 17652        int physicalIndex = GetPhysicalIndex(index);
 653
 17654        _count--;
 17655        if ((uint)index < (uint)_count)
 656        {
 8657            int distanceToHead = physicalIndex - _offset;
 8658            int distanceToTail = (_offset + _count) - physicalIndex;
 659
 8660            if (distanceToHead < distanceToTail)
 661            {
 662                // Shift elements towards the tail (right) to fill the gap
 7663                Array.Copy(_innerArray, _offset, _innerArray, _offset + 1, distanceToHead);
 7664                _offset++;  // Adjust offset since we've moved elements towards the tail
 665            }
 666            else
 667            {
 668                // Shift elements towards the head (left) to fill the gap
 1669                Array.Copy(_innerArray, physicalIndex + 1, _innerArray, physicalIndex, distanceToTail);
 1670                _innerArray[GetPhysicalIndex(_count)] = default!; // Clear the last element
 671            }
 672        }
 673        else  // Removing the last element; simply clear it
 9674            _innerArray[GetPhysicalIndex(_count)] = default!;
 675
 676        // Only recenter if offset is non-zero and count is less than 25% of capacity
 17677        if (_offset != 0 && (uint)_count < _innerArray.Length * 0.25)
 678        {
 2679            if ((uint)_count == 0)
 1680                _offset = _innerArray.Length >> 1; // Reset offset to the middle when list is empty
 681            else
 1682                RecenterArray();
 683        }
 684
 17685        _version++;
 17686    }
 687
 688    /// <inheritdoc/>
 689    public void Clear()
 690    {
 277691        if ((uint)_count == 0) return;
 9692        Array.Clear(_innerArray, _offset, _count);
 9693        _count = 0;
 9694        _offset = _innerArray.Length >> 1; // Reset _offset to the middle of the array
 695
 9696        _version++;
 9697    }
 698
 699    /// <summary>
 700    /// Removes all elements, optionally releasing references throughout retained backing storage.
 701    /// </summary>
 702    /// <param name="clearRetainedReferences">If true, also releases references outside the live range; otherwise uses o
 703    /// <remarks>Capacity is preserved. Full reference cleanup can take time proportional to retained capacity.</remarks
 704    public void Clear(bool clearRetainedReferences)
 705    {
 141706        if (clearRetainedReferences && RuntimeHelpers.IsReferenceOrContainsReferences<T>())
 707        {
 135708            Array.Clear(_innerArray, 0, _offset);
 135709            Array.Clear(_innerArray, _offset + _count, _innerArray.Length - _offset - _count);
 710        }
 141711        Clear();
 141712    }
 713
 714    /// <summary>
 715    /// Quickly clears the list by resetting the count and offset without modifying the internal array.
 716    /// Note: This leaves references in the internal array, which may prevent garbage collection of reference types.
 717    /// Use when performance is critical and you are certain that residual references are acceptable.
 718    /// </summary>
 719    public void FastClear()
 720    {
 138721        if ((uint)_count == 0) return;
 136722        _count = 0;
 136723        _offset = _innerArray.Length >> 1; // Reset offset to middle
 724
 136725        _version++;
 136726    }
 727
 728    #endregion
 729
 730    #region Capacity Management
 731
 732    /// <summary>
 733    /// Ensures that the capacity of <see cref="SwiftSortedList{T}"/> is sufficient to accommodate the specified number 
 734    /// The capacity can increase by double to balance memory allocation efficiency and space.
 735    /// </summary>
 736    public void EnsureCapacity(int capacity)
 737    {
 30738        capacity = SwiftHashTools.NextPowerOfTwo(capacity);
 30739        if (capacity > _innerArray.Length)
 19740            Resize(capacity);
 30741    }
 742
 743    /// <summary>
 744    /// Ensures that the capacity of <see cref="SwiftSortedList{T}"/> is sufficient to accommodate the specified number 
 745    /// The capacity can increase by double to balance memory allocation efficiency and space.
 746    /// </summary>
 747    private void Resize(int newSize)
 748    {
 57749        int newCapacity = newSize <= DefaultCapacity ? DefaultCapacity : newSize;
 750
 57751        T[] newArray = new T[newCapacity];
 57752        int newOffset = (newArray.Length - _count) >> 1; // Center the elements in the new array
 57753        if ((uint)_count > 0)
 3754            Array.Copy(_innerArray, _offset, newArray, newOffset, _count);
 755
 57756        _innerArray = newArray;
 57757        _offset = newOffset;
 758
 57759        _version++;
 57760    }
 761
 762    /// <summary>
 763    /// Recenters the elements within the internal array to balance available space on both ends.
 764    /// This minimizes the need for shifting elements during future insertions and deletions.
 765    /// </summary>
 766    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 767    private void RecenterArray()
 768    {
 2769        int newOffset = (_innerArray.Length - _count) >> 1;
 2770        Array.Copy(_innerArray, _offset, _innerArray, newOffset, _count);
 2771        _offset = newOffset;
 772
 2773        _version++;
 2774    }
 775
 776    #endregion
 777
 778    #region Utility Methods
 779
 780    /// <summary>
 781    /// Sets a new comparer for the sorted list and re-sorts the elements.
 782    /// </summary>
 783    /// <param name="comparer">The new comparer to use.</param>
 784    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 785    public void SetComparer(IComparer<T> comparer)
 786    {
 6787        ChronicleGuard.ThrowIfNull(comparer, nameof(comparer));
 6788        if (ReferenceEquals(comparer, _comparer))
 1789            return;
 790
 5791        _comparer = comparer;
 5792        SwiftArraySortHelper.Sort(_innerArray, _offset, _count, _comparer);
 5793        _version++;
 5794    }
 795
 796    /// <summary>
 797    /// Converts a logical arrayIndex within the list to the corresponding physical arrayIndex in the internal array.
 798    /// </summary>
 799    /// <param name="logicalIndex">The logical arrayIndex within the list.</param>
 800    /// <returns>The physical arrayIndex within the internal array.</returns>
 801    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 622802    private int GetPhysicalIndex(int logicalIndex) => _offset + logicalIndex;
 803
 804    /// <summary>
 805    /// Returns a read-only span over the populated sorted portion of the list.
 806    /// </summary>
 807    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 20808    public ReadOnlySpan<T> AsReadOnlySpan() => _innerArray.AsSpan(_offset, _count);
 809
 810    /// <summary>
 811    /// Returns the minimum element in the sorter without removing it.
 812    /// </summary>
 813    /// <returns>The minimum element.</returns>
 814    public T PeekMin()
 815    {
 19816        ChronicleGuard.ThrowIfTrue((uint)_count == 0, message: "Cannot peek from an empty list.");
 18817        return _innerArray[GetPhysicalIndex(0)];
 818    }
 819
 820    /// <summary>
 821    /// Returns the maximum element in the sorter without removing it.
 822    /// </summary>
 823    /// <returns>The maximum element.</returns>
 824    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 825    public T PeekMax()
 826    {
 17827        ChronicleGuard.ThrowIfTrue((uint)_count == 0, message: "Cannot peek from an empty list.");
 16828        return _innerArray[GetPhysicalIndex(_count - 1)];
 829    }
 830
 831    /// <inheritdoc/>
 832    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 2833    public bool Contains(T item) => Search(item) >= 0;
 834
 835    /// <summary>
 836    /// Determines whether the <see cref="SwiftSortedList{T}"/> contains an element that matches the conditions defined 
 837    /// </summary>
 838    /// <param name="match">The predicate that defines the conditions of the element to search for.</param>
 839    /// <returns><c>true</c> if the <see cref="SwiftSortedList{T}"/> contains one or more elements that match the specif
 840    public bool Exists(Predicate<T> match)
 841    {
 3842        ChronicleGuard.ThrowIfNull(match, nameof(match));
 843
 14844        for (int i = 0; i < _count; i++)
 845        {
 6846            if (match(_innerArray[GetPhysicalIndex(i)]))
 1847                return true;
 848        }
 849
 1850        return false;
 851    }
 852
 853    /// <summary>
 854    /// Searches for an element that matches the conditions defined by the specified predicate, and returns the first ma
 855    /// </summary>
 856    /// <param name="match">The predicate that defines the conditions of the element to search for.</param>
 857    /// <returns>The first element that matches the conditions defined by the specified predicate, if found; otherwise, 
 858    public T Find(Predicate<T> match)
 859    {
 2860        ChronicleGuard.ThrowIfNull(match, nameof(match));
 861
 16862        for (int i = 0; i < _count; i++)
 863        {
 7864            T item = _innerArray[GetPhysicalIndex(i)];
 7865            if (match(item))
 1866                return item;
 867        }
 868
 1869        return default!;
 870    }
 871
 872    /// <summary>
 873    /// Searches for the specified item in the sorted collection and returns the arrayIndex of the first occurrence.
 874    /// </summary>
 875    /// <param name="item">The item to search for.</param>
 876    /// <returns>The zero-based arrayIndex of the item if found; otherwise, -1.</returns>
 877    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 878    public int IndexOf(T item)
 879    {
 2880        int index = Search(item);
 2881        return index >= 0 ? index : -1;
 882    }
 883
 884    /// <summary>
 885    /// Determines the insertion point for a specified item in the collection.
 886    /// The insertion point is the arrayIndex where the item would be inserted if it were not already present.
 887    /// </summary>
 888    /// <param name="item">The item for which to find the insertion point.</param>
 889    /// <returns>The insertion point as a zero-based arrayIndex.</returns>
 890    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 891    public int InsertionPoint(T item)
 892    {
 2893        int index = Search(item);
 2894        return index >= 0 ? index : ~index;
 895    }
 896
 897    /// <summary>
 898    /// Searches for the specified item in the sorted collection.
 899    /// </summary>
 900    /// <param name="item">The item to search for.</param>
 901    /// <returns>
 902    /// The arrayIndex of the item if found or where the item should be inserted if not found.
 903    /// </returns>
 904    public int Search(T item)
 905    {
 274906        int low = 0;
 274907        int high = _count - 1;
 455908        while ((uint)low <= high)
 909        {
 193910            int mid = low + ((high - low) >> 1);
 193911            T midItem = _innerArray[GetPhysicalIndex(mid)];
 193912            int cmp = _comparer.Compare(midItem, item);
 193913            if ((uint)cmp == 0)
 12914                return mid; // Exact match found
 915
 181916            if (cmp < 0)
 133917                low = mid + 1; // Search in the right half
 918            else
 48919                high = mid - 1; // Search in the left half
 920        }
 262921        return ~low; // Item not found, should be inserted at arrayIndex low
 922    }
 923
 924    /// <inheritdoc/>
 925    public void CopyTo(T[] array, int arrayIndex)
 926    {
 3927        ChronicleGuard.ThrowIfNull(array, nameof(array));
 3928        ChronicleGuard.ThrowIfArrayIndexInvalid(arrayIndex, array.Length, nameof(arrayIndex));
 3929        ChronicleGuard.ThrowIfArgument(array.Length - arrayIndex < _count, nameof(array), "The target array is too small
 930
 2931        Array.Copy(_innerArray, _offset, array, arrayIndex, _count);
 2932    }
 933
 934    /// <inheritdoc/>
 935    public void CopyTo(Array array, int arrayIndex)
 936    {
 2937        ChronicleGuard.ThrowIfNull(array, nameof(array));
 2938        ChronicleGuard.ThrowIfArrayIndexInvalid(arrayIndex, array.Length, nameof(arrayIndex));
 2939        ChronicleGuard.ThrowIfArgument(array.Length - arrayIndex < _count, nameof(array), "The target array is too small
 940
 1941        Array.Copy(_innerArray, _offset, array, arrayIndex, _count);
 1942    }
 943
 944    /// <inheritdoc/>
 945    public void CloneTo(ICollection<T> output)
 946    {
 2947        ChronicleGuard.ThrowIfNull(output, nameof(output));
 948
 1949        output.Clear();
 950
 8951        foreach (var item in this)
 3952            output.Add(item);
 1953    }
 954
 955    #endregion
 956
 957    #region Enumerators
 958
 959    /// <summary>
 960    /// Returns an enumerator that iterates through <see cref="SwiftSortedList{T}"/>.
 961    /// </summary>
 59962    public SwiftSorterEnumerator GetEnumerator() => new(this);
 35963    IEnumerator<T> IEnumerable<T>.GetEnumerator() => GetEnumerator();
 20964    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
 965
 966
 967
 968    #endregion
 969}

/home/runner/work/SwiftCollections/SwiftCollections/src/SwiftCollections/Collection/SwiftSortedList.SwiftSorterEnumerator.cs

#LineLine coverage
 1//=======================================================================
 2// SwiftSortedList.SwiftSorterEnumerator.cs
 3//=======================================================================
 4// MIT License, Copyright (c) 2024-present David Oravsky (mrdav30)
 5// See LICENSE file in the project root for full license information.
 6//=======================================================================
 7
 8using System;
 9using System.Collections;
 10using System.Collections.Generic;
 11using System.Runtime.CompilerServices;
 12using Chronicler.Diagnostics;
 13
 14namespace SwiftCollections;
 15
 16public partial class SwiftSortedList<T>
 17{
 18    /// <summary>
 19    /// Supports simple iteration over the elements of a <see cref="SwiftSortedList{T}"/> in sorted order.
 20    /// </summary>
 21    /// <remarks>
 22    /// The enumerator is invalidated if the underlying collection is modified after the enumerator created.
 23    /// In this case, calling MoveNext or Reset will throw an InvalidOperationException.
 24    /// The enumerator does not support writing to the collection.
 25    /// </remarks>
 26    public struct SwiftSorterEnumerator : IEnumerator<T>, IEnumerator, IDisposable
 27    {
 28        private readonly SwiftSortedList<T> _list;
 29        private readonly uint _count;
 30        private readonly uint _version;
 31        private int _index;
 32
 33        private T _current;
 34
 35        internal SwiftSorterEnumerator(SwiftSortedList<T> sortedList)
 36        {
 5937            _list = sortedList;
 5938            _count = (uint)sortedList._count;
 5939            _version = sortedList._version;
 5940            _index = 0;
 5941            _current = default!;
 5942        }
 43
 44        /// <inheritdoc/>
 5745        public T Current => _current;
 46
 47        object IEnumerator.Current
 48        {
 49            [MethodImpl(MethodImplOptions.AggressiveInlining)]
 50            get
 51            {
 3252                ChronicleGuard.ThrowIfTrue(_index == 0 || (uint)_index > _count, message: "Enumerator is past the end of
 1353                return _current!;
 54            }
 55
 56        }
 57
 58        /// <inheritdoc/>
 59        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 60        public bool MoveNext()
 61        {
 12662            ChronicleGuard.ThrowIfTrue(_version != _list._version, message: "Enumerator modified outside of enumeration!
 63
 12364            if (_index < _count)
 65            {
 6966                _current = _list._innerArray[_list.GetPhysicalIndex(_index)];
 6967                _index++;
 6968                return true;
 69            }
 70
 5471            _index = _list._count + 1;
 5472            _current = default!;
 5473            return false;
 74        }
 75
 76        /// <inheritdoc/>
 77        public void Reset()
 78        {
 1179            ChronicleGuard.ThrowIfTrue(_version != _list._version, message: "Enumerator modified outside of enumeration!
 80
 781            _index = 0;
 782            _current = default!;
 783        }
 84
 85        /// <inheritdoc/>
 4086        public void Dispose() => _index = 0;
 87    }
 88}
Generated by: ReportGenerator 5.5.12.0
11/05/2026 - 04:17:34
GitHub | reportgenerator.io

Methods/Properties

.cctor()
.ctor()
.ctor(System.Collections.Generic.IComparer`1<T>)
.ctor(System.Int32,System.Collections.Generic.IComparer`1<T>)
.ctor(System.Collections.Generic.IEnumerable`1<T>,System.Collections.Generic.IComparer`1<T>)
.ctor(SwiftCollections.SwiftArrayState`1<T>)
get_InnerArray()
get_Count()
get_Offset()
get_Version()
get_Capacity()
get_Comparer()
get_IsReadOnly()
get_IsSynchronized()
get_SyncRoot()
get_Item(System.Int32)
get_State()
set_State(SwiftCollections.SwiftArrayState`1<T>)
Add(T)
Insert(T,System.Int32)
AddRange(System.Collections.Generic.IEnumerable`1<T>)
AddRange(System.Collections.Generic.ICollection`1<T>)
AddRange(System.Collections.Generic.IReadOnlyCollection`1<T>)
ShouldUseTemporaryCopy(System.Collections.Generic.ICollection`1<T>)
InitializeFromCollection(System.Collections.Generic.ICollection`1<T>)
InitializeFromEnumerable(System.Collections.Generic.IEnumerable`1<T>,System.Int32)
CopyToSortedArray(System.Collections.Generic.IEnumerable`1<T>)
InitializeFromSortedItems(T[])
MergeSortedItems(T[])
MergeCollectionItems(System.Collections.Generic.ICollection`1<T>,System.Int32)
MergeEnumerableItems(System.Collections.Generic.IEnumerable`1<T>,System.Int32)
PopMin()
PopMax()
Remove(T)
RemoveAt(System.Int32)
Clear()
Clear(System.Boolean)
FastClear()
EnsureCapacity(System.Int32)
Resize(System.Int32)
RecenterArray()
SetComparer(System.Collections.Generic.IComparer`1<T>)
GetPhysicalIndex(System.Int32)
AsReadOnlySpan()
PeekMin()
PeekMax()
Contains(T)
Exists(System.Predicate`1<T>)
Find(System.Predicate`1<T>)
IndexOf(T)
InsertionPoint(T)
Search(T)
CopyTo(T[],System.Int32)
CopyTo(System.Array,System.Int32)
CloneTo(System.Collections.Generic.ICollection`1<T>)
GetEnumerator()
System.Collections.Generic.IEnumerable<T>.GetEnumerator()
System.Collections.IEnumerable.GetEnumerator()
.ctor(SwiftCollections.SwiftSortedList`1<T>)
get_Current()
System.Collections.IEnumerator.get_Current()
MoveNext()
Reset()
Dispose()