< Summary

Information
Class: SwiftCollections.SwiftSortedList<T>
Assembly: SwiftCollections
File(s): /home/runner/work/SwiftCollections/SwiftCollections/src/SwiftCollections/Collection/SwiftSortedList.cs
Line coverage
87%
Covered lines: 329
Uncovered lines: 48
Coverable lines: 377
Total lines: 1038
Line coverage: 87.2%
Branch coverage
78%
Covered branches: 112
Total branches: 142
Branch coverage: 78.8%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Crap Score Cyclomatic complexity Line coverage
.cctor()100%11100%
.ctor()100%11100%
.ctor(...)100%11100%
.ctor(...)100%66100%
.ctor(...)87.5%88100%
.ctor(...)100%11100%
get_InnerArray()100%11100%
get_Count()100%11100%
get_Offset()100%11100%
get_Version()100%11100%
get_Capacity()100%11100%
get_Comparer()100%11100%
get_IsReadOnly()100%11100%
get_IsSynchronized()100%11100%
get_SyncRoot()50%22100%
get_Item(...)100%11100%
get_State()100%11100%
set_State(...)100%44100%
Add(...)100%22100%
Insert(...)100%88100%
AddRange(...)87.5%8886.66%
AddRange(...)83.33%7669.23%
AddRange(...)75%4487.5%
ShouldUseTemporaryCopy(...)75%44100%
InitializeFromCollection(...)50%2290%
InitializeFromEnumerable(...)75%4490.9%
CopyToSortedArray(...)100%22100%
CopyCollectionToArray(...)0%620%
InitializeFromSortedItems(...)50%4488.88%
MergeSortedItems(...)0%110100%
MergeCollectionItems(...)33.33%6678.94%
MergeEnumerableItems(...)50%9880%
PopMin()100%22100%
PopMax()100%22100%
Remove(...)100%44100%
RemoveAt(...)100%1010100%
Clear()100%22100%
FastClear()100%22100%
EnsureCapacity(...)100%22100%
Resize(...)100%44100%
RecenterArray()100%11100%
SetComparer(...)100%22100%
GetPhysicalIndex(...)100%11100%
AsReadOnlySpan()100%11100%
PeekMin()100%11100%
PeekMax()100%11100%
Contains(...)100%11100%
Exists(...)100%44100%
Find(...)100%44100%
IndexOf(...)100%22100%
InsertionPoint(...)100%22100%
Search(...)100%66100%
CopyTo(...)100%11100%
CopyTo(...)100%11100%
CloneTo(...)100%22100%
GetEnumerator()100%11100%
System.Collections.Generic.IEnumerable<T>.GetEnumerator()100%11100%
System.Collections.IEnumerable.GetEnumerator()100%11100%
.ctor(...)100%11100%
get_Current()100%11100%
System.Collections.IEnumerator.get_Current()100%11100%
MoveNext()100%22100%
Reset()100%11100%
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 Chronicler;
 9using MemoryPack;
 10using SwiftCollections.Diagnostics;
 11using SwiftCollections.Utility;
 12using System;
 13using System.Collections;
 14using System.Collections.Generic;
 15using System.Linq;
 16using System.Runtime.CompilerServices;
 17using System.Text.Json.Serialization;
 18
 19namespace SwiftCollections;
 20
 21/// <summary>
 22/// Represents a dynamically sorted collection of elements.
 23/// Provides efficient O(log n) operations for adding, removing, and checking for the presence of elements.
 24/// </summary>
 25/// <remarks>
 26/// The comparer is not serialized. After deserialization the list uses
 27/// <see cref="Comparer{T}.Default"/>.
 28///
 29/// If a custom comparer is required it can be reapplied using
 30    /// <see cref="SetComparer(IComparer{T})"/>.
 31/// </remarks>
 32/// <typeparam name="T">The type of elements in the collection.</typeparam>
 33[Serializable]
 34[JsonConverter(typeof(StateJsonConverterFactory))]
 35[MemoryPackable]
 36public partial class SwiftSortedList<T> : IStateBacked<SwiftArrayState<T>>, ISwiftCloneable<T>, IEnumerable<T>, IEnumera
 37{
 38    #region Constants
 39
 40    /// <summary>
 41    /// The default initial capacity of the <see cref="SwiftSortedList{T}"/> if none is specified.
 42    /// Used to allocate a reasonable starting size to minimize resizing operations.
 43    /// </summary>
 44    public const int DefaultCapacity = 8;
 45
 246    private static readonly T[] _emptyArray = Array.Empty<T>();
 47
 48    #endregion
 49
 50    #region Fields
 51
 52    /// <summary>
 53    /// Represents the internal array that stores the sorted elements.
 54    /// </summary>
 55    private T[] _innerArray;
 56
 57    /// <summary>
 58    /// The number of elements contained in the <see cref="SwiftSortedList{T}"/>.
 59    /// </summary>
 60    private int _count;
 61
 62    /// <summary>
 63    /// The offset within the internal array where the logical start of the list begins.
 64    /// Used to efficiently manage insertions and deletions at both ends without excessive shifting.
 65    /// </summary>
 66    private int _offset;
 67
 68    /// <summary>
 69    /// A version counter used to track modifications to the sorted list.
 70    /// Incremented on mutations to detect changes during enumeration and ensure enumerator validity.
 71    /// </summary>
 72    [NonSerialized]
 73    private uint _version;
 74
 75    /// <summary>
 76    /// The comparer used to sort and compare elements in the collection.
 77    /// </summary>
 78    [NonSerialized]
 79    private IComparer<T> _comparer;
 80
 81    /// <summary>
 82    /// An object that can be used to synchronize access to the SwiftList.
 83    /// </summary>
 84    [NonSerialized]
 85    private object? _syncRoot;
 86
 87    #endregion
 88
 89    #region Constructors
 90
 91    /// <summary>
 92    /// Initializes a new instance of the SwiftSortedList class with the default capacity.
 93    /// </summary>
 94    /// <remarks>
 95    /// This constructor creates an empty sorted list.
 96    /// Items added to the list will be automatically ordered according to the default comparer for the item type.
 97    /// </remarks>
 11698    public SwiftSortedList() : this(0) { }
 99
 100    /// <summary>
 101    /// Initializes a new, empty instance of <see cref="SwiftSortedList{T}"/> uisng the specified <see cref="IComparer{T
 102    /// </summary>
 6103    public SwiftSortedList(IComparer<T> comparer) : this(0, comparer) { }
 104
 105    /// <summary>
 106    /// Initializes a new, empty instance of <see cref="SwiftSortedList{T}"/> with the specified initial capacity and <s
 107    /// </summary>
 108    /// <param name="capacity">The starting initial capacity.</param>
 109    /// <param name="comparer">The comparer to use. If null, the default comparer is used.</param>
 71110    public SwiftSortedList(int capacity, IComparer<T>? comparer = null)
 111    {
 71112        _comparer = comparer ?? Comparer<T>.Default;
 113
 71114        if (capacity == 0)
 115        {
 61116            _innerArray = _emptyArray;
 61117            _offset = 0;
 118        }
 119        else
 120        {
 10121            capacity = capacity <= DefaultCapacity ? DefaultCapacity : SwiftHashTools.NextPowerOfTwo(capacity);
 10122            _innerArray = new T[capacity];
 10123            _offset = capacity >> 1; // initial offset half of capacity
 124        }
 10125    }
 126
 127    /// <summary>
 128    /// Initializes a new instance of the <see cref="SwiftList{T}"/> class with elements from the specified collection.
 129    /// The collection must have a known count for optimized memory allocation.
 130    /// </summary>
 131    /// <exception cref="ArgumentException">Thrown if the input collection does not have a known count.</exception>
 4132    public SwiftSortedList(IEnumerable<T> items, IComparer<T>? comparer = null)
 133    {
 4134        SwiftThrowHelper.ThrowIfNull(items, nameof(items));
 135
 4136        _comparer = comparer ?? Comparer<T>.Default;
 137
 4138        if (items is ICollection<T> collection)
 139        {
 3140            int count = collection.Count;
 3141            if (count == 0)
 142            {
 1143                _innerArray = _emptyArray;
 1144                _offset = 0;
 145            }
 146            else
 147            {
 2148                int capacity = SwiftHashTools.NextPowerOfTwo(count <= DefaultCapacity ? DefaultCapacity : count);
 2149                _innerArray = new T[capacity];
 2150                _offset = (capacity - count) >> 1;
 2151                collection.CopyTo(_innerArray, _offset);
 2152                SwiftArraySortHelper.Sort(_innerArray, _offset, count, _comparer);
 2153                _count = count;
 154            }
 155        }
 156        else
 157        {
 1158            _innerArray = new T[DefaultCapacity];
 1159            _offset = DefaultCapacity >> 1;
 1160            AddRange(items); // Will handle capacity increases as needed
 161        }
 1162    }
 163
 164    ///  <summary>
 165    ///  Initializes a new instance of the <see cref="SwiftSortedList{T}"/> class with the specified <see cref="SwiftArr
 166    ///  </summary>
 167    ///  <param name="state">The state containing the internal array, count, offset, and version for initialization.</pa
 168    [MemoryPackConstructor]
 6169    public SwiftSortedList(SwiftArrayState<T> state)
 170    {
 6171        State = state;
 172
 173        // Validate that the internal array and comparer are not null after deserialization
 6174        SwiftThrowHelper.ThrowIfNull(_innerArray, nameof(_innerArray));
 6175        SwiftThrowHelper.ThrowIfNull(_comparer, nameof(_comparer));
 6176    }
 177
 178    #endregion
 179
 180    #region Properties
 181
 182    /// <summary>
 183    /// Gets the underlying array that stores the elements of the collection.
 184    /// </summary>
 185    /// <remarks>
 186    /// The returned array may contain unused elements beyond the logical contents of the collection.
 187    ///</remarks>
 188    [JsonIgnore]
 189    [MemoryPackIgnore]
 9190    public T[] InnerArray => _innerArray;
 191
 192    /// <inheritdoc cref="_count"/>
 193    [JsonIgnore]
 194    [MemoryPackIgnore]
 29195    public int Count => _count;
 196
 197    /// <inheritdoc cref="_offset"/>
 198    [JsonIgnore]
 199    [MemoryPackIgnore]
 22200    public int Offset => _offset;
 201
 202    /// <inheritdoc cref="_version"/>
 203    [JsonIgnore]
 204    [MemoryPackIgnore]
 5205    public uint Version => _version;
 206
 207    /// <summary>
 208    /// Gets the current capacity of the internal array.
 209    /// </summary>
 210    [JsonIgnore]
 211    [MemoryPackIgnore]
 20212    public int Capacity => _innerArray.Length;
 213
 214    /// <inheritdoc cref="_comparer"/>
 215    [JsonIgnore]
 216    [MemoryPackIgnore]
 1217    public IComparer<T> Comparer => _comparer;
 218
 219    /// <inheritdoc/>
 220    [JsonIgnore]
 221    [MemoryPackIgnore]
 1222    public bool IsReadOnly => false;
 223
 224    /// <inheritdoc/>
 225    [JsonIgnore]
 226    [MemoryPackIgnore]
 1227    public bool IsSynchronized => false;
 228
 229    /// <inheritdoc/>
 230    [JsonIgnore]
 231    [MemoryPackIgnore]
 1232    public object SyncRoot => _syncRoot ??= new object();
 233
 234    /// <summary>
 235    /// Gets the element at the specified arrayIndex.
 236    /// </summary>
 237    [JsonIgnore]
 238    [MemoryPackIgnore]
 239    public T this[int index]
 240    {
 241        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 242        get
 243        {
 2244            SwiftThrowHelper.ThrowIfListIndexInvalid(index, _count);
 1245            return _innerArray[GetPhysicalIndex(index)];
 246        }
 247    }
 248
 249    /// <summary>
 250    /// Gets or sets the current state of the array, including its items and structure.
 251    /// </summary>
 252    /// <remarks>
 253    /// Setting this property replaces the entire contents of the array with the specified state.
 254    /// The setter is intended for internal use and may reset internal metadata such as version and comparer.
 255    /// This property is intended for serialization and deserialization scenarios.
 256    /// </remarks>
 257    [JsonInclude]
 258    [MemoryPackInclude]
 259    public SwiftArrayState<T> State
 260    {
 261        get
 262        {
 3263            var items = new T[_count];
 3264            Array.Copy(_innerArray, _offset, items, 0, _count);
 3265            return new SwiftArrayState<T>(items);
 266        }
 267        internal set
 268        {
 6269            SwiftThrowHelper.ThrowIfNull(value.Items, nameof(value.Items));
 270
 6271            int count = value.Items.Length;
 272
 6273            if (count == 0)
 274            {
 1275                _innerArray = _emptyArray;
 1276                _offset = 0;
 1277                _count = 0;
 278            }
 279            else
 280            {
 5281                int capacity = SwiftHashTools.NextPowerOfTwo(count <= DefaultCapacity ? DefaultCapacity : count);
 5282                _innerArray = new T[capacity];
 283
 5284                int newOffset = (capacity - count) >> 1;
 285
 5286                Array.Copy(value.Items, 0, _innerArray, newOffset, count);
 287
 5288                _offset = newOffset;
 5289                _count = count;
 290            }
 291
 6292            _version = 0;
 6293            _comparer = Comparer<T>.Default;
 6294        }
 295    }
 296
 297    #endregion
 298
 299    #region Collection Manipulation
 300
 301    /// <inheritdoc/>
 302    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 303    public void Add(T item)
 304    {
 101305        int index = Search(item);
 201306        if (index < 0) index = ~index;
 101307        Insert(item, index);
 101308    }
 309
 310    /// <summary>
 311    /// Inserts an item into the internal array at the specified arrayIndex, shifting elements as needed.
 312    /// </summary>
 313    private void Insert(T item, int index)
 314    {
 101315        SwiftThrowHelper.ThrowIfArrayIndexInvalid(index, _count, nameof(index));
 101316        if (_offset + _count + 1 > _innerArray.Length)
 33317            Resize(_innerArray.Length * 2);
 318
 101319        int physicalIndex = GetPhysicalIndex(index);
 320
 101321        if (index < (uint)_count)
 322        {
 38323            int distanceToHead = physicalIndex - _offset;
 38324            int distanceToTail = (_offset + _count - 1) - physicalIndex;
 325
 38326            if (distanceToHead >= (uint)distanceToTail)
 327            {
 34328                if ((uint)_offset == 0)
 329                {
 330                    // Ensure capacity for recentering
 1331                    Resize(_innerArray.Length * 2);
 1332                    RecenterArray();
 1333                    physicalIndex = GetPhysicalIndex(index);
 334                }
 335
 34336                _offset--;
 34337                physicalIndex--;
 338                // Shift elements towards the head (left)
 34339                Array.Copy(_innerArray, _offset + 1, _innerArray, _offset, distanceToHead + 1);
 340            }
 341            else  // Shift elements towards the tail (right) to make space
 4342                Array.Copy(_innerArray, physicalIndex, _innerArray, physicalIndex + 1, _count - index);
 343        }
 344
 101345        _innerArray[physicalIndex] = item;
 101346        _count++;
 347
 101348        _version++;
 101349    }
 350
 351    /// <summary>
 352    /// Adds a range of elements to the collection, ensuring they are sorted and merged efficiently.
 353    /// </summary>
 354    /// <remarks>
 355    /// This compacts the active item range for efficiency. Known-count sources reuse existing capacity when possible.
 356    /// </remarks>
 357    public void AddRange(IEnumerable<T> items)
 358    {
 40359        SwiftThrowHelper.ThrowIfNull(items, nameof(items));
 360
 40361        if (items is ICollection<T> collection)
 362        {
 36363            AddRange(collection);
 36364            return;
 365        }
 366
 4367        if (items is IReadOnlyCollection<T> readOnlyCollection)
 368        {
 2369            AddRange(readOnlyCollection);
 2370            return;
 371        }
 372
 2373        T[] sortedItems = CopyToSortedArray(items);
 2374        if (sortedItems.Length == 0)
 1375            return;
 376
 1377        if ((uint)_count == 0)
 378        {
 1379            InitializeFromSortedItems(sortedItems);
 1380            return;
 381        }
 382
 0383        MergeSortedItems(sortedItems);
 0384    }
 385
 386    private void AddRange(ICollection<T> collection)
 387    {
 36388        int count = collection.Count;
 36389        if (count == 0)
 1390            return;
 391
 35392        if (ShouldUseTemporaryCopy(collection))
 393        {
 0394            T[] sortedItems = CopyCollectionToArray(collection);
 0395            SwiftArraySortHelper.Sort(sortedItems, 0, sortedItems.Length, _comparer);
 0396            MergeSortedItems(sortedItems);
 0397            return;
 398        }
 399
 35400        if ((uint)_count == 0)
 401        {
 28402            InitializeFromCollection(collection);
 28403            return;
 404        }
 405
 7406        MergeCollectionItems(collection, count);
 7407    }
 408
 409    private void AddRange(IReadOnlyCollection<T> collection)
 410    {
 2411        int count = collection.Count;
 2412        if (count == 0)
 0413            return;
 414
 2415        if ((uint)_count == 0)
 416        {
 1417            InitializeFromEnumerable(collection, count);
 1418            return;
 419        }
 420
 1421        MergeEnumerableItems(collection, count);
 1422    }
 423
 424    private bool ShouldUseTemporaryCopy(ICollection<T> collection) =>
 35425        ReferenceEquals(collection, this) ||
 35426        collection is T[] array && ReferenceEquals(array, _innerArray);
 427
 428    private void InitializeFromCollection(ICollection<T> collection)
 429    {
 28430        int count = collection.Count;
 28431        if (count == 0)
 0432            return;
 433
 28434        EnsureCapacity(count);
 435
 28436        _offset = (_innerArray.Length - count) >> 1;
 28437        collection.CopyTo(_innerArray, _offset);
 28438        SwiftArraySortHelper.Sort(_innerArray, _offset, count, _comparer);
 439
 28440        _count = count;
 28441        _version++;
 28442    }
 443
 444    private void InitializeFromEnumerable(IEnumerable<T> items, int count)
 445    {
 1446        if (count == 0)
 0447            return;
 448
 1449        EnsureCapacity(count);
 450
 1451        _offset = (_innerArray.Length - count) >> 1;
 1452        int index = _offset;
 66453        foreach (T item in items)
 32454            _innerArray[index++] = item;
 455
 1456        SwiftArraySortHelper.Sort(_innerArray, _offset, count, _comparer);
 457
 1458        _count = count;
 1459        _version++;
 1460    }
 461
 462    private T[] CopyToSortedArray(IEnumerable<T> items)
 463    {
 2464        T[] sortedItems = items.ToArray();
 465
 2466        if (sortedItems.Length > 0)
 1467            SwiftArraySortHelper.Sort(sortedItems, 0, sortedItems.Length, _comparer);
 468
 2469        return sortedItems;
 470    }
 471
 472    private static T[] CopyCollectionToArray(ICollection<T> collection)
 473    {
 0474        if (collection.Count == 0)
 0475            return _emptyArray;
 476
 0477        T[] items = new T[collection.Count];
 0478        collection.CopyTo(items, 0);
 0479        return items;
 480    }
 481
 482    private void InitializeFromSortedItems(T[] sortedItems)
 483    {
 1484        int initialCapacity = SwiftHashTools.NextPowerOfTwo(sortedItems.Length < DefaultCapacity ? DefaultCapacity : sor
 1485        int newOffset = (initialCapacity - sortedItems.Length) >> 1;
 1486        if ((uint)_innerArray.Length < (uint)initialCapacity)
 0487            _innerArray = new T[initialCapacity];
 488
 1489        Array.Copy(sortedItems, 0, _innerArray, newOffset, sortedItems.Length);
 1490        _offset = newOffset;
 1491        _count = sortedItems.Length;
 1492        _version++;
 1493    }
 494
 495    private void MergeSortedItems(T[] sortedItems)
 496    {
 0497        int newCount = _count + sortedItems.Length;
 0498        int totalRequiredCapacity = newCount + _offset;
 0499        int newCapacity = SwiftHashTools.NextPowerOfTwo(totalRequiredCapacity);
 0500        int mergedOffset = (newCapacity - newCount) >> 1;
 0501        T[] newArray = new T[newCapacity];
 502
 0503        int existingIndex = 0;
 0504        int newItemsIndex = 0;
 0505        int mergedIndex = mergedOffset;
 506
 0507        while (existingIndex < _count && newItemsIndex < sortedItems.Length)
 508        {
 0509            T existingItem = _innerArray[_offset + existingIndex];
 0510            T newItem = sortedItems[newItemsIndex];
 511
 0512            if (_comparer.Compare(existingItem, newItem) <= 0)
 513            {
 0514                newArray[mergedIndex++] = existingItem;
 0515                existingIndex++;
 516            }
 517            else
 518            {
 0519                newArray[mergedIndex++] = newItem;
 0520                newItemsIndex++;
 521            }
 522        }
 523
 524        // Copy any remaining existing items
 0525        while (existingIndex < _count)
 0526            newArray[mergedIndex++] = _innerArray[_offset + existingIndex++];
 527
 528        // Copy any remaining new items
 0529        while (newItemsIndex < sortedItems.Length)
 0530            newArray[mergedIndex++] = sortedItems[newItemsIndex++];
 531
 0532        _innerArray = newArray;
 0533        _offset = mergedOffset;
 0534        _count = newCount;
 535
 0536        _version++;
 0537    }
 538
 539    private void MergeCollectionItems(ICollection<T> collection, int collectionCount)
 540    {
 7541        int existingCount = _count;
 7542        int newCount = existingCount + collectionCount;
 543        T[] target;
 544        int mergedOffset;
 545
 7546        if (_innerArray.Length >= newCount)
 547        {
 7548            target = _innerArray;
 7549            mergedOffset = (_innerArray.Length - newCount) >> 1;
 7550            if (mergedOffset != _offset)
 7551                Array.Copy(_innerArray, _offset, target, mergedOffset, existingCount);
 552        }
 553        else
 554        {
 0555            int newCapacity = SwiftHashTools.NextPowerOfTwo(newCount <= DefaultCapacity ? DefaultCapacity : newCount);
 0556            target = new T[newCapacity];
 0557            mergedOffset = (newCapacity - newCount) >> 1;
 0558            Array.Copy(_innerArray, _offset, target, mergedOffset, existingCount);
 559        }
 560
 7561        int collectionOffset = mergedOffset + existingCount;
 7562        collection.CopyTo(target, collectionOffset);
 7563        SwiftArraySortHelper.Sort(target, mergedOffset, newCount, _comparer);
 564
 7565        _innerArray = target;
 7566        _offset = mergedOffset;
 7567        _count = newCount;
 568
 7569        _version++;
 7570    }
 571
 572    private void MergeEnumerableItems(IEnumerable<T> items, int itemCount)
 573    {
 1574        int existingCount = _count;
 1575        int newCount = existingCount + itemCount;
 576        T[] target;
 577        int mergedOffset;
 578
 1579        if (_innerArray.Length >= newCount)
 580        {
 0581            target = _innerArray;
 0582            mergedOffset = (_innerArray.Length - newCount) >> 1;
 0583            if (mergedOffset != _offset)
 0584                Array.Copy(_innerArray, _offset, target, mergedOffset, existingCount);
 585        }
 586        else
 587        {
 1588            int newCapacity = SwiftHashTools.NextPowerOfTwo(newCount <= DefaultCapacity ? DefaultCapacity : newCount);
 1589            target = new T[newCapacity];
 1590            mergedOffset = (newCapacity - newCount) >> 1;
 1591            Array.Copy(_innerArray, _offset, target, mergedOffset, existingCount);
 592        }
 593
 1594        int index = mergedOffset + existingCount;
 66595        foreach (T item in items)
 32596            target[index++] = item;
 597
 1598        SwiftArraySortHelper.Sort(target, mergedOffset, newCount, _comparer);
 599
 1600        _innerArray = target;
 1601        _offset = mergedOffset;
 1602        _count = newCount;
 603
 1604        _version++;
 1605    }
 606
 607    /// <summary>
 608    /// Removes and returns the minimum element in the sorter.
 609    /// </summary>
 610    /// <returns>The minimum element.</returns>
 611    public T PopMin()
 612    {
 3613        SwiftThrowHelper.ThrowIfTrue((uint)_count == 0, message: "Cannot pop from an empty list.");
 614
 2615        int index = GetPhysicalIndex(0);
 2616        T ret = _innerArray[index];
 2617        _innerArray[index] = default!;
 2618        _count--;
 619        // Increment _offset as we remove from the front
 2620        _offset = _count == 0 ? _innerArray.Length >> 1 : _offset + 1;
 621
 2622        _version++;
 623
 2624        return ret;
 625    }
 626
 627    /// <summary>
 628    /// Removes and returns the maximum element in the sorter.
 629    /// </summary>
 630    /// <returns>The maximum element.</returns>
 631    public T PopMax()
 632    {
 3633        SwiftThrowHelper.ThrowIfTrue((uint)_count == 0, message: "Cannot pop from an empty list.");
 634
 2635        int index = GetPhysicalIndex(--_count);
 2636        T ret = _innerArray[index];
 2637        _innerArray[index] = default!;
 3638        if ((uint)_count == 0) _offset = _innerArray.Length >> 1;
 639
 2640        _version++;
 641
 2642        return ret;
 643    }
 644
 645    /// <inheritdoc/>
 646    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 647    public bool Remove(T item)
 648    {
 11649        if ((uint)_count == 0) return false;
 650
 9651        int index = Search(item);
 11652        if (index < 0) return false;
 653
 7654        RemoveAt(index);
 7655        return true;
 656    }
 657
 658    /// <summary>
 659    /// Removes the element at the specified arrayIndex from the sorted list.
 660    /// Shifts elements as needed to maintain the sorted order and efficient space utilization.
 661    /// </summary>
 662    /// <param name="index">The zero-based arrayIndex of the element to remove.</param>
 663    public void RemoveAt(int index)
 664    {
 17665        SwiftThrowHelper.ThrowIfListIndexInvalid(index, _count);
 666
 17667        int physicalIndex = GetPhysicalIndex(index);
 668
 17669        _count--;
 17670        if ((uint)index < (uint)_count)
 671        {
 8672            int distanceToHead = physicalIndex - _offset;
 8673            int distanceToTail = (_offset + _count) - physicalIndex;
 674
 8675            if (distanceToHead < distanceToTail)
 676            {
 677                // Shift elements towards the tail (right) to fill the gap
 7678                Array.Copy(_innerArray, _offset, _innerArray, _offset + 1, distanceToHead);
 7679                _offset++;  // Adjust offset since we've moved elements towards the tail
 680            }
 681            else
 682            {
 683                // Shift elements towards the head (left) to fill the gap
 1684                Array.Copy(_innerArray, physicalIndex + 1, _innerArray, physicalIndex, distanceToTail);
 1685                _innerArray[GetPhysicalIndex(_count)] = default!; // Clear the last element
 686            }
 687        }
 688        else  // Removing the last element; simply clear it
 9689            _innerArray[GetPhysicalIndex(_count)] = default!;
 690
 691        // Only recenter if offset is non-zero and count is less than 25% of capacity
 17692        if (_offset != 0 && (uint)_count < _innerArray.Length * 0.25)
 693        {
 2694            if ((uint)_count == 0)
 1695                _offset = _innerArray.Length >> 1; // Reset offset to the middle when list is empty
 696            else
 1697                RecenterArray();
 698        }
 699
 17700        _version++;
 17701    }
 702
 703    /// <inheritdoc/>
 704    public void Clear()
 705    {
 3706        if ((uint)_count == 0) return;
 1707        Array.Clear(_innerArray, _offset, _count);
 1708        _count = 0;
 1709        _offset = _innerArray.Length >> 1; // Reset _offset to the middle of the array
 710
 1711        _version++;
 1712    }
 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    {
 5721        if ((uint)_count == 0) return;
 3722        _count = 0;
 3723        _offset = _innerArray.Length >> 1; // Reset offset to middle
 724
 3725        _version++;
 3726    }
 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    {
 53749        int newCapacity = newSize <= DefaultCapacity ? DefaultCapacity : newSize;
 750
 53751        T[] newArray = new T[newCapacity];
 53752        int newOffset = (newArray.Length - _count) >> 1; // Center the elements in the new array
 53753        if ((uint)_count > 0)
 3754            Array.Copy(_innerArray, _offset, newArray, newOffset, _count);
 755
 53756        _innerArray = newArray;
 53757        _offset = newOffset;
 758
 53759        _version++;
 53760    }
 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        SwiftThrowHelper.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)]
 379802    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)]
 13808    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    {
 20816        SwiftThrowHelper.ThrowIfTrue((uint)_count == 0, message: "Cannot peek from an empty list.");
 19817        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    {
 18827        SwiftThrowHelper.ThrowIfTrue((uint)_count == 0, message: "Cannot peek from an empty list.");
 17828        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        SwiftThrowHelper.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        SwiftThrowHelper.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    {
 117906        int low = 0;
 117907        int high = _count - 1;
 273908        while ((uint)low <= high)
 909        {
 168910            int mid = low + ((high - low) >> 1);
 168911            T midItem = _innerArray[GetPhysicalIndex(mid)];
 168912            int cmp = _comparer.Compare(midItem, item);
 168913            if ((uint)cmp == 0)
 12914                return mid; // Exact match found
 915
 156916            if (cmp < 0)
 106917                low = mid + 1; // Search in the right half
 918            else
 50919                high = mid - 1; // Search in the left half
 920        }
 105921        return ~low; // Item not found, should be inserted at arrayIndex low
 922    }
 923
 924    /// <inheritdoc/>
 925    public void CopyTo(T[] array, int arrayIndex)
 926    {
 2927        SwiftThrowHelper.ThrowIfNull(array, nameof(array));
 2928        SwiftThrowHelper.ThrowIfArrayIndexInvalid(arrayIndex, array.Length, nameof(arrayIndex));
 2929        SwiftThrowHelper.ThrowIfArgument(array.Length - arrayIndex < _count, nameof(array), "The target array is too sma
 930
 1931        Array.Copy(_innerArray, _offset, array, arrayIndex, _count);
 1932    }
 933
 934    /// <inheritdoc/>
 935    public void CopyTo(Array array, int arrayIndex)
 936    {
 2937        SwiftThrowHelper.ThrowIfNull(array, nameof(array));
 2938        SwiftThrowHelper.ThrowIfArrayIndexInvalid(arrayIndex, array.Length, nameof(arrayIndex));
 2939        SwiftThrowHelper.ThrowIfArgument(array.Length - arrayIndex < _count, nameof(array), "The target array is too sma
 940
 1941        Array.Copy(_innerArray, _offset, array, arrayIndex, _count);
 1942    }
 943
 944    /// <inheritdoc/>
 945    public void CloneTo(ICollection<T> output)
 946    {
 2947        SwiftThrowHelper.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>
 21962    public SwiftSorterEnumerator GetEnumerator() => new(this);
 14963    IEnumerator<T> IEnumerable<T>.GetEnumerator() => GetEnumerator();
 2964    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
 965
 966    /// <summary>
 967    /// Supports simple iteration over the elements of a <see cref="SwiftSortedList{T}"/> in sorted order.
 968    /// </summary>
 969    /// <remarks>
 970    /// The enumerator is invalidated if the underlying collection is modified after the enumerator created.
 971    /// In this case, calling MoveNext or Reset will throw an InvalidOperationException.
 972    /// The enumerator does not support writing to the collection.
 973    /// </remarks>
 974    public struct SwiftSorterEnumerator : IEnumerator<T>, IEnumerator, IDisposable
 975    {
 976        private readonly SwiftSortedList<T> _list;
 977        private readonly uint _count;
 978        private readonly uint _version;
 979        private int _index;
 980
 981        private T _current;
 982
 983        internal SwiftSorterEnumerator(SwiftSortedList<T> sortedList)
 984        {
 21985            _list = sortedList;
 21986            _count = (uint)sortedList._count;
 21987            _version = sortedList._version;
 21988            _index = 0;
 21989            _current = default!;
 21990        }
 991
 992        /// <inheritdoc/>
 36993        public T Current => _current;
 994
 995        object IEnumerator.Current
 996        {
 997            [MethodImpl(MethodImplOptions.AggressiveInlining)]
 998            get
 999            {
 21000                SwiftThrowHelper.ThrowIfTrue((uint)_index > _count, message: "Enumerator is past the end of the collecti
 11001                return _current!;
 1002            }
 1003
 1004        }
 1005
 1006        /// <inheritdoc/>
 1007        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 1008        public bool MoveNext()
 1009        {
 461010            SwiftThrowHelper.ThrowIfTrue(_version != _list._version, message: "Enumerator modified outside of enumeratio
 1011
 461012            if (_index < _count)
 1013            {
 281014                _current = _list._innerArray[_list.GetPhysicalIndex(_index)];
 281015                _index++;
 281016                return true;
 1017            }
 1018
 181019            _index = _list._count + 1;
 181020            _current = default!;
 181021            return false;
 1022        }
 1023
 1024        /// <inheritdoc/>
 1025        public void Reset()
 1026        {
 21027            SwiftThrowHelper.ThrowIfTrue(_version != _list._version, message: "Enumerator modified outside of enumeratio
 1028
 11029            _index = 0;
 11030            _current = default!;
 11031        }
 1032
 1033        /// <inheritdoc/>
 171034        public void Dispose() => _index = 0;
 1035    }
 1036
 1037    #endregion
 1038}
Generated by: ReportGenerator 5.5.10.0
07/01/2026 - 04:31:31
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>)
CopyCollectionToArray(System.Collections.Generic.ICollection`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()
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()