< Summary

Information
Class: SwiftCollections.SwiftSortedList<T>
Assembly: SwiftCollections
File(s): /home/runner/work/SwiftCollections/SwiftCollections/src/SwiftCollections/Collection/SwiftSortedList.cs
Line coverage
100%
Covered lines: 368
Uncovered lines: 0
Coverable lines: 368
Total lines: 1022
Line coverage: 100%
Branch coverage
100%
Covered branches: 132
Total branches: 132
Branch coverage: 100%
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(...)100%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()100%22100%
get_Item(...)100%11100%
get_State()100%11100%
set_State(...)100%44100%
Add(...)100%22100%
Insert(...)100%88100%
AddRange(...)100%88100%
AddRange(...)100%66100%
AddRange(...)100%44100%
ShouldUseTemporaryCopy(...)100%44100%
InitializeFromCollection(...)100%11100%
InitializeFromEnumerable(...)100%22100%
CopyToSortedArray(...)100%22100%
InitializeFromSortedItems(...)100%44100%
MergeSortedItems(...)100%1010100%
MergeCollectionItems(...)100%44100%
MergeEnumerableItems(...)100%66100%
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 System;
 9using System.Collections;
 10using System.Collections.Generic;
 11using System.Linq;
 12using System.Runtime.CompilerServices;
 13using System.Text.Json.Serialization;
 14using Chronicler;
 15using MemoryPack;
 16using SwiftCollections.Diagnostics;
 17using SwiftCollections.Utility;
 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>
 12298    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>
 75110    public SwiftSortedList(int capacity, IComparer<T>? comparer = null)
 111    {
 75112        _comparer = comparer ?? Comparer<T>.Default;
 113
 75114        if (capacity == 0)
 115        {
 64116            _innerArray = _emptyArray;
 64117            _offset = 0;
 118        }
 119        else
 120        {
 11121            capacity = capacity <= DefaultCapacity ? DefaultCapacity : SwiftHashTools.NextPowerOfTwo(capacity);
 11122            _innerArray = new T[capacity];
 11123            _offset = capacity >> 1; // initial offset half of capacity
 124        }
 11125    }
 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>
 5132    public SwiftSortedList(IEnumerable<T> items, IComparer<T>? comparer = null)
 133    {
 5134        SwiftThrowHelper.ThrowIfNull(items, nameof(items));
 135
 5136        _comparer = comparer ?? Comparer<T>.Default;
 137
 5138        if (items is ICollection<T> collection)
 139        {
 4140            int count = collection.Count;
 4141            if (count == 0)
 142            {
 1143                _innerArray = _emptyArray;
 1144                _offset = 0;
 145            }
 146            else
 147            {
 3148                int capacity = SwiftHashTools.NextPowerOfTwo(count <= DefaultCapacity ? DefaultCapacity : count);
 3149                _innerArray = new T[capacity];
 3150                _offset = (capacity - count) >> 1;
 3151                collection.CopyTo(_innerArray, _offset);
 3152                SwiftArraySortHelper.Sort(_innerArray, _offset, count, _comparer);
 3153                _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]
 17190    public T[] InnerArray => _innerArray;
 191
 192    /// <inheritdoc cref="_count"/>
 193    [JsonIgnore]
 194    [MemoryPackIgnore]
 51195    public int Count => _count;
 196
 197    /// <inheritdoc cref="_offset"/>
 198    [JsonIgnore]
 199    [MemoryPackIgnore]
 26200    public int Offset => _offset;
 201
 202    /// <inheritdoc cref="_version"/>
 203    [JsonIgnore]
 204    [MemoryPackIgnore]
 7205    public uint Version => _version;
 206
 207    /// <summary>
 208    /// Gets the current capacity of the internal array.
 209    /// </summary>
 210    [JsonIgnore]
 211    [MemoryPackIgnore]
 22212    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]
 2232    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        {
 21244            SwiftThrowHelper.ThrowIfListIndexInvalid(index, _count);
 20245            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    {
 99305        int index = Search(item);
 197306        if (index < 0) index = ~index;
 99307        Insert(item, index);
 99308    }
 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    {
 99315        SwiftThrowHelper.ThrowIfArrayIndexInvalid(index, _count, nameof(index));
 99316        if (_offset + _count + 1 > _innerArray.Length)
 34317            Resize(_innerArray.Length * 2);
 318
 99319        int physicalIndex = GetPhysicalIndex(index);
 320
 99321        if (index < (uint)_count)
 322        {
 38323            int distanceToHead = physicalIndex - _offset;
 38324            int distanceToTail = (_offset + _count - 1) - physicalIndex;
 325
 38326            if (distanceToHead >= (uint)distanceToTail)
 327            {
 35328                if ((uint)_offset == 0)
 329                {
 330                    // Ensure capacity for recentering
 1331                    Resize(_innerArray.Length * 2);
 1332                    RecenterArray();
 1333                    physicalIndex = GetPhysicalIndex(index);
 334                }
 335
 35336                _offset--;
 35337                physicalIndex--;
 338                // Shift elements towards the head (left)
 35339                Array.Copy(_innerArray, _offset + 1, _innerArray, _offset, distanceToHead + 1);
 340            }
 341            else  // Shift elements towards the tail (right) to make space
 3342                Array.Copy(_innerArray, physicalIndex, _innerArray, physicalIndex + 1, _count - index);
 343        }
 344
 99345        _innerArray[physicalIndex] = item;
 99346        _count++;
 347
 99348        _version++;
 99349    }
 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    {
 49359        SwiftThrowHelper.ThrowIfNull(items, nameof(items));
 360
 49361        if (items is ICollection<T> collection)
 362        {
 39363            AddRange(collection);
 39364            return;
 365        }
 366
 10367        if (items is IReadOnlyCollection<T> readOnlyCollection)
 368        {
 5369            AddRange(readOnlyCollection);
 5370            return;
 371        }
 372
 5373        T[] sortedItems = CopyToSortedArray(items);
 5374        if (sortedItems.Length == 0)
 1375            return;
 376
 4377        if ((uint)_count == 0)
 378        {
 2379            InitializeFromSortedItems(sortedItems);
 2380            return;
 381        }
 382
 2383        MergeSortedItems(sortedItems);
 2384    }
 385
 386    private void AddRange(ICollection<T> collection)
 387    {
 39388        int count = collection.Count;
 39389        if (count == 0)
 1390            return;
 391
 38392        if (ShouldUseTemporaryCopy(collection))
 393        {
 1394            T[] sortedItems = collection.ToArray();
 1395            SwiftArraySortHelper.Sort(sortedItems, 0, sortedItems.Length, _comparer);
 1396            MergeSortedItems(sortedItems);
 1397            return;
 398        }
 399
 37400        if ((uint)_count == 0)
 401        {
 28402            InitializeFromCollection(collection);
 28403            return;
 404        }
 405
 9406        MergeCollectionItems(collection, count);
 9407    }
 408
 409    private void AddRange(IReadOnlyCollection<T> collection)
 410    {
 5411        int count = collection.Count;
 5412        if (count == 0)
 1413            return;
 414
 4415        if ((uint)_count == 0)
 416        {
 1417            InitializeFromEnumerable(collection, count);
 1418            return;
 419        }
 420
 3421        MergeEnumerableItems(collection, count);
 3422    }
 423
 424    private bool ShouldUseTemporaryCopy(ICollection<T> collection) =>
 38425        ReferenceEquals(collection, this) ||
 38426        collection is T[] array && ReferenceEquals(array, _innerArray);
 427
 428    private void InitializeFromCollection(ICollection<T> collection)
 429    {
 28430        int count = collection.Count;
 28431        EnsureCapacity(count);
 432
 28433        _offset = (_innerArray.Length - count) >> 1;
 28434        collection.CopyTo(_innerArray, _offset);
 28435        SwiftArraySortHelper.Sort(_innerArray, _offset, count, _comparer);
 436
 28437        _count = count;
 28438        _version++;
 28439    }
 440
 441    private void InitializeFromEnumerable(IEnumerable<T> items, int count)
 442    {
 1443        EnsureCapacity(count);
 444
 1445        _offset = (_innerArray.Length - count) >> 1;
 1446        int index = _offset;
 66447        foreach (T item in items)
 32448            _innerArray[index++] = item;
 449
 1450        SwiftArraySortHelper.Sort(_innerArray, _offset, count, _comparer);
 451
 1452        _count = count;
 1453        _version++;
 1454    }
 455
 456    private T[] CopyToSortedArray(IEnumerable<T> items)
 457    {
 5458        T[] sortedItems = items.ToArray();
 459
 5460        if (sortedItems.Length > 0)
 4461            SwiftArraySortHelper.Sort(sortedItems, 0, sortedItems.Length, _comparer);
 462
 5463        return sortedItems;
 464    }
 465
 466    private void InitializeFromSortedItems(T[] sortedItems)
 467    {
 2468        int initialCapacity = SwiftHashTools.NextPowerOfTwo(sortedItems.Length < DefaultCapacity ? DefaultCapacity : sor
 2469        int newOffset = (initialCapacity - sortedItems.Length) >> 1;
 2470        if ((uint)_innerArray.Length < (uint)initialCapacity)
 1471            _innerArray = new T[initialCapacity];
 472
 2473        Array.Copy(sortedItems, 0, _innerArray, newOffset, sortedItems.Length);
 2474        _offset = newOffset;
 2475        _count = sortedItems.Length;
 2476        _version++;
 2477    }
 478
 479    private void MergeSortedItems(T[] sortedItems)
 480    {
 3481        int newCount = _count + sortedItems.Length;
 3482        int totalRequiredCapacity = newCount + _offset;
 3483        int newCapacity = SwiftHashTools.NextPowerOfTwo(totalRequiredCapacity);
 3484        int mergedOffset = (newCapacity - newCount) >> 1;
 3485        T[] newArray = new T[newCapacity];
 486
 3487        int existingIndex = 0;
 3488        int newItemsIndex = 0;
 3489        int mergedIndex = mergedOffset;
 490
 27491        while (existingIndex < _count && newItemsIndex < sortedItems.Length)
 492        {
 24493            T existingItem = _innerArray[_offset + existingIndex];
 24494            T newItem = sortedItems[newItemsIndex];
 495
 24496            if (_comparer.Compare(existingItem, newItem) <= 0)
 497            {
 21498                newArray[mergedIndex++] = existingItem;
 21499                existingIndex++;
 500            }
 501            else
 502            {
 3503                newArray[mergedIndex++] = newItem;
 3504                newItemsIndex++;
 505            }
 506        }
 507
 508        // Copy any remaining existing items
 20509        while (existingIndex < _count)
 17510            newArray[mergedIndex++] = _innerArray[_offset + existingIndex++];
 511
 512        // Copy any remaining new items
 5513        while (newItemsIndex < sortedItems.Length)
 2514            newArray[mergedIndex++] = sortedItems[newItemsIndex++];
 515
 3516        _innerArray = newArray;
 3517        _offset = mergedOffset;
 3518        _count = newCount;
 519
 3520        _version++;
 3521    }
 522
 523    private void MergeCollectionItems(ICollection<T> collection, int collectionCount)
 524    {
 9525        int existingCount = _count;
 9526        int newCount = existingCount + collectionCount;
 527        T[] target;
 528        int mergedOffset;
 529
 9530        if (_innerArray.Length >= newCount)
 531        {
 8532            target = _innerArray;
 8533            mergedOffset = (_innerArray.Length - newCount) >> 1;
 8534            if (mergedOffset != _offset)
 7535                Array.Copy(_innerArray, _offset, target, mergedOffset, existingCount);
 536        }
 537        else
 538        {
 1539            int newCapacity = SwiftHashTools.NextPowerOfTwo(newCount);
 1540            target = new T[newCapacity];
 1541            mergedOffset = (newCapacity - newCount) >> 1;
 1542            Array.Copy(_innerArray, _offset, target, mergedOffset, existingCount);
 543        }
 544
 9545        int collectionOffset = mergedOffset + existingCount;
 9546        collection.CopyTo(target, collectionOffset);
 9547        SwiftArraySortHelper.Sort(target, mergedOffset, newCount, _comparer);
 548
 9549        _innerArray = target;
 9550        _offset = mergedOffset;
 9551        _count = newCount;
 552
 9553        _version++;
 9554    }
 555
 556    private void MergeEnumerableItems(IEnumerable<T> items, int itemCount)
 557    {
 3558        int existingCount = _count;
 3559        int newCount = existingCount + itemCount;
 560        T[] target;
 561        int mergedOffset;
 562
 3563        if (_innerArray.Length >= newCount)
 564        {
 2565            target = _innerArray;
 2566            mergedOffset = (_innerArray.Length - newCount) >> 1;
 2567            if (mergedOffset != _offset)
 1568                Array.Copy(_innerArray, _offset, target, mergedOffset, existingCount);
 569        }
 570        else
 571        {
 1572            int newCapacity = SwiftHashTools.NextPowerOfTwo(newCount);
 1573            target = new T[newCapacity];
 1574            mergedOffset = (newCapacity - newCount) >> 1;
 1575            Array.Copy(_innerArray, _offset, target, mergedOffset, existingCount);
 576        }
 577
 3578        int index = mergedOffset + existingCount;
 78579        foreach (T item in items)
 36580            target[index++] = item;
 581
 3582        SwiftArraySortHelper.Sort(target, mergedOffset, newCount, _comparer);
 583
 3584        _innerArray = target;
 3585        _offset = mergedOffset;
 3586        _count = newCount;
 587
 3588        _version++;
 3589    }
 590
 591    /// <summary>
 592    /// Removes and returns the minimum element in the sorter.
 593    /// </summary>
 594    /// <returns>The minimum element.</returns>
 595    public T PopMin()
 596    {
 3597        SwiftThrowHelper.ThrowIfTrue((uint)_count == 0, message: "Cannot pop from an empty list.");
 598
 2599        int index = GetPhysicalIndex(0);
 2600        T ret = _innerArray[index];
 2601        _innerArray[index] = default!;
 2602        _count--;
 603        // Increment _offset as we remove from the front
 2604        _offset = _count == 0 ? _innerArray.Length >> 1 : _offset + 1;
 605
 2606        _version++;
 607
 2608        return ret;
 609    }
 610
 611    /// <summary>
 612    /// Removes and returns the maximum element in the sorter.
 613    /// </summary>
 614    /// <returns>The maximum element.</returns>
 615    public T PopMax()
 616    {
 5617        SwiftThrowHelper.ThrowIfTrue((uint)_count == 0, message: "Cannot pop from an empty list.");
 618
 4619        int index = GetPhysicalIndex(--_count);
 4620        T ret = _innerArray[index];
 4621        _innerArray[index] = default!;
 5622        if ((uint)_count == 0) _offset = _innerArray.Length >> 1;
 623
 4624        _version++;
 625
 4626        return ret;
 627    }
 628
 629    /// <inheritdoc/>
 630    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 631    public bool Remove(T item)
 632    {
 10633        if ((uint)_count == 0) return false;
 634
 8635        int index = Search(item);
 9636        if (index < 0) return false;
 637
 7638        RemoveAt(index);
 7639        return true;
 640    }
 641
 642    /// <summary>
 643    /// Removes the element at the specified arrayIndex from the sorted list.
 644    /// Shifts elements as needed to maintain the sorted order and efficient space utilization.
 645    /// </summary>
 646    /// <param name="index">The zero-based arrayIndex of the element to remove.</param>
 647    public void RemoveAt(int index)
 648    {
 17649        SwiftThrowHelper.ThrowIfListIndexInvalid(index, _count);
 650
 17651        int physicalIndex = GetPhysicalIndex(index);
 652
 17653        _count--;
 17654        if ((uint)index < (uint)_count)
 655        {
 8656            int distanceToHead = physicalIndex - _offset;
 8657            int distanceToTail = (_offset + _count) - physicalIndex;
 658
 8659            if (distanceToHead < distanceToTail)
 660            {
 661                // Shift elements towards the tail (right) to fill the gap
 7662                Array.Copy(_innerArray, _offset, _innerArray, _offset + 1, distanceToHead);
 7663                _offset++;  // Adjust offset since we've moved elements towards the tail
 664            }
 665            else
 666            {
 667                // Shift elements towards the head (left) to fill the gap
 1668                Array.Copy(_innerArray, physicalIndex + 1, _innerArray, physicalIndex, distanceToTail);
 1669                _innerArray[GetPhysicalIndex(_count)] = default!; // Clear the last element
 670            }
 671        }
 672        else  // Removing the last element; simply clear it
 9673            _innerArray[GetPhysicalIndex(_count)] = default!;
 674
 675        // Only recenter if offset is non-zero and count is less than 25% of capacity
 17676        if (_offset != 0 && (uint)_count < _innerArray.Length * 0.25)
 677        {
 2678            if ((uint)_count == 0)
 1679                _offset = _innerArray.Length >> 1; // Reset offset to the middle when list is empty
 680            else
 1681                RecenterArray();
 682        }
 683
 17684        _version++;
 17685    }
 686
 687    /// <inheritdoc/>
 688    public void Clear()
 689    {
 3690        if ((uint)_count == 0) return;
 1691        Array.Clear(_innerArray, _offset, _count);
 1692        _count = 0;
 1693        _offset = _innerArray.Length >> 1; // Reset _offset to the middle of the array
 694
 1695        _version++;
 1696    }
 697
 698    /// <summary>
 699    /// Quickly clears the list by resetting the count and offset without modifying the internal array.
 700    /// Note: This leaves references in the internal array, which may prevent garbage collection of reference types.
 701    /// Use when performance is critical and you are certain that residual references are acceptable.
 702    /// </summary>
 703    public void FastClear()
 704    {
 5705        if ((uint)_count == 0) return;
 3706        _count = 0;
 3707        _offset = _innerArray.Length >> 1; // Reset offset to middle
 708
 3709        _version++;
 3710    }
 711
 712    #endregion
 713
 714    #region Capacity Management
 715
 716    /// <summary>
 717    /// Ensures that the capacity of <see cref="SwiftSortedList{T}"/> is sufficient to accommodate the specified number 
 718    /// The capacity can increase by double to balance memory allocation efficiency and space.
 719    /// </summary>
 720    public void EnsureCapacity(int capacity)
 721    {
 30722        capacity = SwiftHashTools.NextPowerOfTwo(capacity);
 30723        if (capacity > _innerArray.Length)
 19724            Resize(capacity);
 30725    }
 726
 727    /// <summary>
 728    /// Ensures that the capacity of <see cref="SwiftSortedList{T}"/> is sufficient to accommodate the specified number 
 729    /// The capacity can increase by double to balance memory allocation efficiency and space.
 730    /// </summary>
 731    private void Resize(int newSize)
 732    {
 54733        int newCapacity = newSize <= DefaultCapacity ? DefaultCapacity : newSize;
 734
 54735        T[] newArray = new T[newCapacity];
 54736        int newOffset = (newArray.Length - _count) >> 1; // Center the elements in the new array
 54737        if ((uint)_count > 0)
 3738            Array.Copy(_innerArray, _offset, newArray, newOffset, _count);
 739
 54740        _innerArray = newArray;
 54741        _offset = newOffset;
 742
 54743        _version++;
 54744    }
 745
 746    /// <summary>
 747    /// Recenters the elements within the internal array to balance available space on both ends.
 748    /// This minimizes the need for shifting elements during future insertions and deletions.
 749    /// </summary>
 750    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 751    private void RecenterArray()
 752    {
 2753        int newOffset = (_innerArray.Length - _count) >> 1;
 2754        Array.Copy(_innerArray, _offset, _innerArray, newOffset, _count);
 2755        _offset = newOffset;
 756
 2757        _version++;
 2758    }
 759
 760    #endregion
 761
 762    #region Utility Methods
 763
 764    /// <summary>
 765    /// Sets a new comparer for the sorted list and re-sorts the elements.
 766    /// </summary>
 767    /// <param name="comparer">The new comparer to use.</param>
 768    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 769    public void SetComparer(IComparer<T> comparer)
 770    {
 6771        SwiftThrowHelper.ThrowIfNull(comparer, nameof(comparer));
 6772        if (ReferenceEquals(comparer, _comparer))
 1773            return;
 774
 5775        _comparer = comparer;
 5776        SwiftArraySortHelper.Sort(_innerArray, _offset, _count, _comparer);
 5777        _version++;
 5778    }
 779
 780    /// <summary>
 781    /// Converts a logical arrayIndex within the list to the corresponding physical arrayIndex in the internal array.
 782    /// </summary>
 783    /// <param name="logicalIndex">The logical arrayIndex within the list.</param>
 784    /// <returns>The physical arrayIndex within the internal array.</returns>
 785    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 383786    private int GetPhysicalIndex(int logicalIndex) => _offset + logicalIndex;
 787
 788    /// <summary>
 789    /// Returns a read-only span over the populated sorted portion of the list.
 790    /// </summary>
 791    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 20792    public ReadOnlySpan<T> AsReadOnlySpan() => _innerArray.AsSpan(_offset, _count);
 793
 794    /// <summary>
 795    /// Returns the minimum element in the sorter without removing it.
 796    /// </summary>
 797    /// <returns>The minimum element.</returns>
 798    public T PeekMin()
 799    {
 19800        SwiftThrowHelper.ThrowIfTrue((uint)_count == 0, message: "Cannot peek from an empty list.");
 18801        return _innerArray[GetPhysicalIndex(0)];
 802    }
 803
 804    /// <summary>
 805    /// Returns the maximum element in the sorter without removing it.
 806    /// </summary>
 807    /// <returns>The maximum element.</returns>
 808    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 809    public T PeekMax()
 810    {
 17811        SwiftThrowHelper.ThrowIfTrue((uint)_count == 0, message: "Cannot peek from an empty list.");
 16812        return _innerArray[GetPhysicalIndex(_count - 1)];
 813    }
 814
 815    /// <inheritdoc/>
 816    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 2817    public bool Contains(T item) => Search(item) >= 0;
 818
 819    /// <summary>
 820    /// Determines whether the <see cref="SwiftSortedList{T}"/> contains an element that matches the conditions defined 
 821    /// </summary>
 822    /// <param name="match">The predicate that defines the conditions of the element to search for.</param>
 823    /// <returns><c>true</c> if the <see cref="SwiftSortedList{T}"/> contains one or more elements that match the specif
 824    public bool Exists(Predicate<T> match)
 825    {
 3826        SwiftThrowHelper.ThrowIfNull(match, nameof(match));
 827
 14828        for (int i = 0; i < _count; i++)
 829        {
 6830            if (match(_innerArray[GetPhysicalIndex(i)]))
 1831                return true;
 832        }
 833
 1834        return false;
 835    }
 836
 837    /// <summary>
 838    /// Searches for an element that matches the conditions defined by the specified predicate, and returns the first ma
 839    /// </summary>
 840    /// <param name="match">The predicate that defines the conditions of the element to search for.</param>
 841    /// <returns>The first element that matches the conditions defined by the specified predicate, if found; otherwise, 
 842    public T Find(Predicate<T> match)
 843    {
 2844        SwiftThrowHelper.ThrowIfNull(match, nameof(match));
 845
 16846        for (int i = 0; i < _count; i++)
 847        {
 7848            T item = _innerArray[GetPhysicalIndex(i)];
 7849            if (match(item))
 1850                return item;
 851        }
 852
 1853        return default!;
 854    }
 855
 856    /// <summary>
 857    /// Searches for the specified item in the sorted collection and returns the arrayIndex of the first occurrence.
 858    /// </summary>
 859    /// <param name="item">The item to search for.</param>
 860    /// <returns>The zero-based arrayIndex of the item if found; otherwise, -1.</returns>
 861    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 862    public int IndexOf(T item)
 863    {
 2864        int index = Search(item);
 2865        return index >= 0 ? index : -1;
 866    }
 867
 868    /// <summary>
 869    /// Determines the insertion point for a specified item in the collection.
 870    /// The insertion point is the arrayIndex where the item would be inserted if it were not already present.
 871    /// </summary>
 872    /// <param name="item">The item for which to find the insertion point.</param>
 873    /// <returns>The insertion point as a zero-based arrayIndex.</returns>
 874    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 875    public int InsertionPoint(T item)
 876    {
 2877        int index = Search(item);
 2878        return index >= 0 ? index : ~index;
 879    }
 880
 881    /// <summary>
 882    /// Searches for the specified item in the sorted collection.
 883    /// </summary>
 884    /// <param name="item">The item to search for.</param>
 885    /// <returns>
 886    /// The arrayIndex of the item if found or where the item should be inserted if not found.
 887    /// </returns>
 888    public int Search(T item)
 889    {
 114890        int low = 0;
 114891        int high = _count - 1;
 260892        while ((uint)low <= high)
 893        {
 158894            int mid = low + ((high - low) >> 1);
 158895            T midItem = _innerArray[GetPhysicalIndex(mid)];
 158896            int cmp = _comparer.Compare(midItem, item);
 158897            if ((uint)cmp == 0)
 12898                return mid; // Exact match found
 899
 146900            if (cmp < 0)
 98901                low = mid + 1; // Search in the right half
 902            else
 48903                high = mid - 1; // Search in the left half
 904        }
 102905        return ~low; // Item not found, should be inserted at arrayIndex low
 906    }
 907
 908    /// <inheritdoc/>
 909    public void CopyTo(T[] array, int arrayIndex)
 910    {
 3911        SwiftThrowHelper.ThrowIfNull(array, nameof(array));
 3912        SwiftThrowHelper.ThrowIfArrayIndexInvalid(arrayIndex, array.Length, nameof(arrayIndex));
 3913        SwiftThrowHelper.ThrowIfArgument(array.Length - arrayIndex < _count, nameof(array), "The target array is too sma
 914
 2915        Array.Copy(_innerArray, _offset, array, arrayIndex, _count);
 2916    }
 917
 918    /// <inheritdoc/>
 919    public void CopyTo(Array array, int arrayIndex)
 920    {
 2921        SwiftThrowHelper.ThrowIfNull(array, nameof(array));
 2922        SwiftThrowHelper.ThrowIfArrayIndexInvalid(arrayIndex, array.Length, nameof(arrayIndex));
 2923        SwiftThrowHelper.ThrowIfArgument(array.Length - arrayIndex < _count, nameof(array), "The target array is too sma
 924
 1925        Array.Copy(_innerArray, _offset, array, arrayIndex, _count);
 1926    }
 927
 928    /// <inheritdoc/>
 929    public void CloneTo(ICollection<T> output)
 930    {
 2931        SwiftThrowHelper.ThrowIfNull(output, nameof(output));
 932
 1933        output.Clear();
 934
 8935        foreach (var item in this)
 3936            output.Add(item);
 1937    }
 938
 939    #endregion
 940
 941    #region Enumerators
 942
 943    /// <summary>
 944    /// Returns an enumerator that iterates through <see cref="SwiftSortedList{T}"/>.
 945    /// </summary>
 21946    public SwiftSorterEnumerator GetEnumerator() => new(this);
 15947    IEnumerator<T> IEnumerable<T>.GetEnumerator() => GetEnumerator();
 2948    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
 949
 950    /// <summary>
 951    /// Supports simple iteration over the elements of a <see cref="SwiftSortedList{T}"/> in sorted order.
 952    /// </summary>
 953    /// <remarks>
 954    /// The enumerator is invalidated if the underlying collection is modified after the enumerator created.
 955    /// In this case, calling MoveNext or Reset will throw an InvalidOperationException.
 956    /// The enumerator does not support writing to the collection.
 957    /// </remarks>
 958    public struct SwiftSorterEnumerator : IEnumerator<T>, IEnumerator, IDisposable
 959    {
 960        private readonly SwiftSortedList<T> _list;
 961        private readonly uint _count;
 962        private readonly uint _version;
 963        private int _index;
 964
 965        private T _current;
 966
 967        internal SwiftSorterEnumerator(SwiftSortedList<T> sortedList)
 968        {
 21969            _list = sortedList;
 21970            _count = (uint)sortedList._count;
 21971            _version = sortedList._version;
 21972            _index = 0;
 21973            _current = default!;
 21974        }
 975
 976        /// <inheritdoc/>
 33977        public T Current => _current;
 978
 979        object IEnumerator.Current
 980        {
 981            [MethodImpl(MethodImplOptions.AggressiveInlining)]
 982            get
 983            {
 2984                SwiftThrowHelper.ThrowIfTrue((uint)_index > _count, message: "Enumerator is past the end of the collecti
 1985                return _current!;
 986            }
 987
 988        }
 989
 990        /// <inheritdoc/>
 991        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 992        public bool MoveNext()
 993        {
 43994            SwiftThrowHelper.ThrowIfTrue(_version != _list._version, message: "Enumerator modified outside of enumeratio
 995
 43996            if (_index < _count)
 997            {
 25998                _current = _list._innerArray[_list.GetPhysicalIndex(_index)];
 25999                _index++;
 251000                return true;
 1001            }
 1002
 181003            _index = _list._count + 1;
 181004            _current = default!;
 181005            return false;
 1006        }
 1007
 1008        /// <inheritdoc/>
 1009        public void Reset()
 1010        {
 21011            SwiftThrowHelper.ThrowIfTrue(_version != _list._version, message: "Enumerator modified outside of enumeratio
 1012
 11013            _index = 0;
 11014            _current = default!;
 11015        }
 1016
 1017        /// <inheritdoc/>
 171018        public void Dispose() => _index = 0;
 1019    }
 1020
 1021    #endregion
 1022}
Generated by: ReportGenerator 5.5.11.0
08/05/2026 - 03:54:49
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()
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()