< Summary

Information
Class: SwiftCollections.SwiftSortedList<T>
Assembly: SwiftCollections
File(s): File 1: /_/src/SwiftCollections/obj/Debug/net8.0/MemoryPack.Generator/MemoryPack.Generator.MemoryPackGenerator/SwiftCollections.SwiftSortedList_T_.MemoryPackFormatter.g.cs
File 2: /home/runner/work/SwiftCollections/SwiftCollections/src/SwiftCollections/Collection/SwiftSortedList.cs
Line coverage
98%
Covered lines: 368
Uncovered lines: 7
Coverable lines: 375
Total lines: 855
Line coverage: 98.1%
Branch coverage
90%
Covered branches: 126
Total branches: 140
Branch coverage: 90%
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 2: .cctor()100%11100%
File 2: .ctor()100%11100%
File 2: .ctor(...)100%11100%
File 2: .ctor(...)83.33%66100%
File 2: .ctor(...)100%88100%
File 2: .ctor(...)100%11100%
File 2: get_InnerArray()100%11100%
File 2: get_Count()100%11100%
File 2: get_Offset()100%11100%
File 2: get_Version()100%11100%
File 2: get_Capacity()100%11100%
File 2: get_Comparer()100%11100%
File 2: System.Collections.Generic.ICollection<T>.get_IsReadOnly()100%11100%
File 2: get_IsSynchronized()100%11100%
File 2: System.Collections.ICollection.get_SyncRoot()100%22100%
File 2: get_Item(...)100%22100%
File 2: get_State()100%11100%
File 2: set_State(...)66.66%66100%
File 2: Add(...)100%22100%
File 2: Insert(...)80%111081.48%
File 2: AddRange(...)100%2222100%
File 2: PopMin()100%44100%
File 2: PopMax()100%44100%
File 2: Remove(...)100%44100%
File 2: RemoveAt(...)75%121296.29%
File 2: Clear()75%44100%
File 2: FastClear()75%44100%
File 2: EnsureCapacity(...)100%22100%
File 2: Resize(...)100%44100%
File 2: RecenterArray()100%11100%
File 2: SetComparer(...)100%22100%
File 2: GetPhysicalIndex(...)100%11100%
File 2: AsReadOnlySpan()100%11100%
File 2: PeekMin()100%22100%
File 2: PeekMax()100%22100%
File 2: Contains(...)100%11100%
File 2: Exists(...)100%44100%
File 2: Find(...)100%44100%
File 2: IndexOf(...)100%22100%
File 2: InsertionPoint(...)50%22100%
File 2: Search(...)100%66100%
File 2: CopyTo(...)75%44100%
File 2: CopyTo(...)75%44100%
File 2: CloneTo(...)100%44100%
File 2: GetEnumerator()100%11100%
File 2: System.Collections.Generic.IEnumerable<T>.GetEnumerator()100%11100%
File 2: 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()75%4491.66%
File 2: Reset()100%22100%
File 2: Dispose()100%11100%

File(s)

/_/src/SwiftCollections/obj/Debug/net8.0/MemoryPack.Generator/MemoryPack.Generator.MemoryPackGenerator/SwiftCollections.SwiftSortedList_T_.MemoryPackFormatter.g.cs

File '/_/src/SwiftCollections/obj/Debug/net8.0/MemoryPack.Generator/MemoryPack.Generator.MemoryPackGenerator/SwiftCollections.SwiftSortedList_T_.MemoryPackFormatter.g.cs' does not exist (any more).

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

#LineLine coverage
 1using MemoryPack;
 2using System;
 3using System.Collections;
 4using System.Collections.Generic;
 5using System.Linq;
 6using System.Runtime.CompilerServices;
 7using System.Text.Json.Serialization;
 8
 9namespace SwiftCollections;
 10
 11/// <summary>
 12/// Represents a dynamically sorted collection of elements.
 13/// Provides efficient O(log n) operations for adding, removing, and checking for the presence of elements.
 14/// </summary>
 15/// <remarks>
 16/// The comparer is not serialized. After deserialization the list uses
 17/// <see cref="Comparer{T}.Default"/>.
 18///
 19/// If a custom comparer is required it can be reapplied using
 20/// <see cref="SetComparer(IComparer{T})"/>.
 21/// </remarks>
 22/// <typeparam name="T">The type of elements in the collection.</typeparam>
 23[Serializable]
 24[JsonConverter(typeof(SwiftStateJsonConverterFactory))]
 25[MemoryPackable]
 26public partial class SwiftSortedList<T> : ISwiftCloneable<T>, IEnumerable<T>, IEnumerable, ICollection<T>, ICollection, 
 27{
 28    #region Constants
 29
 30    /// <summary>
 31    /// The default initial capacity of the <see cref="SwiftSortedList{T}"/> if none is specified.
 32    /// Used to allocate a reasonable starting size to minimize resizing operations.
 33    /// </summary>
 34    public const int DefaultCapacity = 8;
 35
 236    private static readonly T[] _emptyArray = Array.Empty<T>();
 37
 38    #endregion
 39
 40    #region Fields
 41
 42    /// <summary>
 43    /// Represents the internal array that stores the sorted elements.
 44    /// </summary>
 45    private T[] _innerArray;
 46
 47    /// <summary>
 48    /// The number of elements contained in the <see cref="SwiftSortedList{T}"/>.
 49    /// </summary>
 50    private int _count;
 51
 52    /// <summary>
 53    /// The offset within the internal array where the logical start of the list begins.
 54    /// Used to efficiently manage insertions and deletions at both ends without excessive shifting.
 55    /// </summary>
 56    private int _offset;
 57
 58    /// <summary>
 59    /// A version counter used to track modifications to the sorted list.
 60    /// Incremented on mutations to detect changes during enumeration and ensure enumerator validity.
 61    /// </summary>
 62    [NonSerialized]
 63    private uint _version;
 64
 65    /// <summary>
 66    /// The comparer used to sort and compare elements in the collection.
 67    /// </summary>
 68    [NonSerialized]
 69    private IComparer<T> _comparer;
 70
 71    /// <summary>
 72    /// An object that can be used to synchronize access to the SwiftList.
 73    /// </summary>
 74    [NonSerialized]
 75    private object _syncRoot;
 76
 77    #endregion
 78
 79    #region Constructors
 80
 15381    public SwiftSortedList() : this(0) { }
 82
 83    /// <summary>
 84    /// Initializes a new, empty instance of <see cref="SwiftSortedList{T}"/> uisng the specified <see cref="IComparer{T
 85    /// </summary>
 986    public SwiftSortedList(IComparer<T> comparer) : this(0, comparer) { }
 87
 88    /// <summary>
 89    /// Initializes a new, empty instance of <see cref="SwiftSortedList{T}"/> with the specified initial capacity and <s
 90    /// </summary>
 91    /// <param name="capacity">The starting initial capacity.</param>
 92    /// <param name="comparer">The comparer to use. If null, the default comparer is used.</param>
 5593    public SwiftSortedList(int capacity, IComparer<T> comparer = null)
 5594    {
 5595        _comparer = comparer ?? Comparer<T>.Default;
 96
 5597        if (capacity == 0)
 5498        {
 5499            _innerArray = _emptyArray;
 54100            _offset = 0;
 54101        }
 102        else
 1103        {
 1104            capacity = capacity <= DefaultCapacity ? DefaultCapacity : SwiftHashTools.NextPowerOfTwo(capacity);
 1105            _innerArray = new T[capacity];
 1106            _offset = capacity >> 1; // initial offset half of capacity
 1107        }
 55108    }
 109
 110    /// <summary>
 111    /// Initializes a new instance of the <see cref="SwiftList{T}"/> class with elements from the specified collection.
 112    /// The collection must have a known count for optimized memory allocation.
 113    /// </summary>
 114    /// <exception cref="ArgumentException">Thrown if the input collection does not have a known count.</exception>
 4115    public SwiftSortedList(IEnumerable<T> items, IComparer<T> comparer = null)
 4116    {
 4117        SwiftThrowHelper.ThrowIfNull(items, nameof(items));
 118
 4119        _comparer = comparer ?? Comparer<T>.Default;
 120
 4121        if (items is ICollection<T> collection)
 3122        {
 3123            int count = collection.Count;
 3124            if (count == 0)
 1125            {
 1126                _innerArray = _emptyArray;
 1127                _offset = 0;
 1128            }
 129            else
 2130            {
 2131                int capacity = SwiftHashTools.NextPowerOfTwo(count <= DefaultCapacity ? DefaultCapacity : count);
 2132                _innerArray = new T[capacity];
 2133                _offset = (capacity - count) >> 1;
 2134                collection.CopyTo(_innerArray, _offset);
 2135                Array.Sort(_innerArray, _offset, count, _comparer);
 2136                _count = count;
 2137            }
 3138        }
 139        else
 1140        {
 1141            _innerArray = new T[DefaultCapacity];
 1142            _offset = DefaultCapacity >> 1;
 1143            AddRange(items); // Will handle capacity increases as needed
 1144        }
 4145    }
 146
 147    ///  <summary>
 148    ///  Initializes a new instance of the <see cref="SwiftSortedList{T}"/> class with the specified <see cref="SwiftArr
 149    ///  </summary>
 150    ///  <param name="state">The state containing the internal array, count, offset, and version for initialization.</pa
 151    [MemoryPackConstructor]
 4152    public SwiftSortedList(SwiftArrayState<T> state)
 4153    {
 4154        State = state;
 4155    }
 156
 157    #endregion
 158
 159    #region Properties
 160
 161    [JsonIgnore]
 162    [MemoryPackIgnore]
 9163    public T[] InnerArray => _innerArray;
 164
 165    /// <inheritdoc cref="_count"/>
 166    [JsonIgnore]
 167    [MemoryPackIgnore]
 16168    public int Count => _count;
 169
 170    /// <inheritdoc cref="_offset"/>
 171    [JsonIgnore]
 172    [MemoryPackIgnore]
 12173    public int Offset => _offset;
 174
 175    /// <inheritdoc cref="_version"/>
 176    [JsonIgnore]
 177    [MemoryPackIgnore]
 5178    public uint Version => _version;
 179
 180    /// <summary>
 181    /// Gets the current capacity of the internal array.
 182    /// </summary>
 183    [JsonIgnore]
 184    [MemoryPackIgnore]
 7185    public int Capacity => _innerArray.Length;
 186
 187    /// <inheritdoc cref="_comparer"/>
 188    [JsonIgnore]
 189    [MemoryPackIgnore]
 1190    public IComparer<T> Comparer => _comparer;
 191
 192    [JsonIgnore]
 193    [MemoryPackIgnore]
 1194    bool ICollection<T>.IsReadOnly => false;
 195
 196    [JsonIgnore]
 197    [MemoryPackIgnore]
 1198    public bool IsSynchronized => false;
 199
 200    [JsonIgnore]
 201    [MemoryPackIgnore]
 1202    object ICollection.SyncRoot => _syncRoot ??= new object();
 203
 204    /// <summary>
 205    /// Gets the element at the specified arrayIndex.
 206    /// </summary>
 207    [JsonIgnore]
 208    [MemoryPackIgnore]
 209    public T this[int index]
 210    {
 211        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 212        get
 2213        {
 3214            if ((uint)index >= (uint)_count) throw new ArgumentOutOfRangeException(nameof(index));
 1215            return _innerArray[GetPhysicalIndex(index)];
 1216        }
 217    }
 218
 219    [JsonInclude]
 220    [MemoryPackInclude]
 221    public SwiftArrayState<T> State
 222    {
 223        get
 3224        {
 3225            var items = new T[_count];
 3226            Array.Copy(_innerArray, _offset, items, 0, _count);
 3227            return new SwiftArrayState<T>(items);
 3228        }
 229        internal set
 4230        {
 4231            int count = value.Items?.Length ?? 0;
 232
 4233            if (count == 0)
 1234            {
 1235                _innerArray = _emptyArray;
 1236                _offset = 0;
 1237                _count = 0;
 1238            }
 239            else
 3240            {
 3241                int capacity = SwiftHashTools.NextPowerOfTwo(count <= DefaultCapacity ? DefaultCapacity : count);
 3242                _innerArray = new T[capacity];
 243
 3244                int newOffset = (capacity - count) >> 1;
 245
 3246                Array.Copy(value.Items, 0, _innerArray, newOffset, count);
 247
 3248                _offset = newOffset;
 3249                _count = count;
 3250            }
 251
 4252            _version = 0;
 4253            _comparer = Comparer<T>.Default;
 4254        }
 255    }
 256
 257    #endregion
 258
 259    #region Collection Manipulation
 260
 261    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 262    public void Add(T item)
 80263    {
 80264        int index = Search(item);
 159265        if (index < 0) index = ~index;
 80266        Insert(item, index);
 80267    }
 268
 269    /// <summary>
 270    /// Inserts an item into the internal array at the specified arrayIndex, shifting elements as needed.
 271    /// </summary>
 272    private void Insert(T item, int index)
 80273    {
 80274        if ((uint)index > (uint)_count) throw new ArgumentOutOfRangeException(nameof(index));
 80275        if (_offset + _count + 1 > _innerArray.Length)
 28276            Resize(_innerArray.Length * 2);
 277
 80278        int physicalIndex = GetPhysicalIndex(index);
 279
 80280        if (index < (uint)_count)
 25281        {
 25282            int distanceToHead = physicalIndex - _offset;
 25283            int distanceToTail = (_offset + _count - 1) - physicalIndex;
 284
 25285            if (distanceToHead >= (uint)distanceToTail)
 21286            {
 21287                if ((uint)_offset == 0)
 0288                {
 289                    // Ensure capacity for recentering
 0290                    Resize(_innerArray.Length * 2);
 0291                    RecenterArray();
 0292                    physicalIndex = GetPhysicalIndex(index);
 0293                }
 294
 21295                _offset--;
 21296                physicalIndex--;
 297                // Shift elements towards the head (left)
 21298                Array.Copy(_innerArray, _offset + 1, _innerArray, _offset, distanceToHead + 1);
 21299            }
 300            else  // Shift elements towards the tail (right) to make space
 4301                Array.Copy(_innerArray, physicalIndex, _innerArray, physicalIndex + 1, _count - index);
 25302        }
 303
 80304        _innerArray[physicalIndex] = item;
 80305        _count++;
 306
 80307        _version++;
 80308    }
 309
 310    /// <summary>
 311    /// Adds a range of elements to the collection, ensuring they are sorted and merged efficiently.
 312    /// </summary>
 313    /// <remarks>
 314    /// This will compact the array for efficiency.
 315    /// </remarks>
 316    public void AddRange(IEnumerable<T> items)
 23317    {
 23318        SwiftThrowHelper.ThrowIfNull(items, nameof(items));
 319
 320        // Convert items to a sorted array
 321        T[] sortedItems;
 322
 23323        if (items is ICollection<T> collection)
 21324        {
 22325            if (collection.Count == 0) return;
 326
 20327            sortedItems = new T[collection.Count];
 20328            collection.CopyTo(sortedItems, 0);
 20329        }
 330        else
 2331        {
 2332            sortedItems = items.ToArray();
 3333            if (sortedItems.Length == 0) return;
 1334        }
 335
 21336        Array.Sort(sortedItems, 0, sortedItems.Length, _comparer);
 337
 21338        if ((uint)_count == 0)
 18339        {
 340            // If the list is empty, initialize with the sorted items
 18341            int initialCapacity = SwiftHashTools.NextPowerOfTwo(sortedItems.Length < DefaultCapacity ? DefaultCapacity :
 18342            int newOffset = (initialCapacity - sortedItems.Length) >> 1;
 34343            if ((uint)_innerArray.Length < initialCapacity) _innerArray = new T[initialCapacity];
 18344            Array.Copy(sortedItems, 0, _innerArray, newOffset, sortedItems.Length);
 18345            _offset = newOffset;
 18346            _count = sortedItems.Length;
 18347            _version++;
 18348            return;
 349        }
 350
 351        // Merge the sorted arrays
 3352        int newCount = _count + sortedItems.Length;
 3353        int totalRequiredCapacity = newCount + _offset;
 354
 355        // Determine new capacity and offset
 3356        int newCapacity = SwiftHashTools.NextPowerOfTwo(totalRequiredCapacity);
 3357        int mergedOffset = (newCapacity - newCount) >> 1;
 358
 359        // Create a new array with the new capacity
 3360        T[] newArray = new T[newCapacity];
 361
 362        // Merge existing items and new items into newArray
 3363        int existingIndex = 0;
 3364        int newItemsIndex = 0;
 3365        int mergedIndex = mergedOffset;
 366
 13367        while (existingIndex < _count && newItemsIndex < sortedItems.Length)
 10368        {
 10369            T existingItem = _innerArray[_offset + existingIndex];
 10370            T newItem = sortedItems[newItemsIndex];
 371
 10372            if (_comparer.Compare(existingItem, newItem) <= 0)
 4373            {
 4374                newArray[mergedIndex++] = existingItem;
 4375                existingIndex++;
 4376            }
 377            else
 6378            {
 6379                newArray[mergedIndex++] = newItem;
 6380                newItemsIndex++;
 6381            }
 10382        }
 383
 384        // Copy any remaining existing items
 4385        while (existingIndex < _count)
 1386            newArray[mergedIndex++] = _innerArray[_offset + existingIndex++];
 387
 388        // Copy any remaining new items
 7389        while (newItemsIndex < sortedItems.Length)
 4390            newArray[mergedIndex++] = sortedItems[newItemsIndex++];
 391
 392        // Set the new array and update the offset
 3393        _innerArray = newArray;
 3394        _offset = mergedOffset;
 3395        _count = newCount;
 396
 3397        _version++;
 23398    }
 399
 400    /// <summary>
 401    /// Removes and returns the minimum element in the sorter.
 402    /// </summary>
 403    /// <returns>The minimum element.</returns>
 404    public T PopMin()
 3405    {
 4406        if ((uint)_count == 0) throw new IndexOutOfRangeException();
 407
 2408        int index = GetPhysicalIndex(0);
 2409        T ret = _innerArray[index];
 2410        _innerArray[index] = default;
 2411        _count--;
 412        // Increment _offset as we remove from the front
 2413        _offset = _count == 0 ? _innerArray.Length >> 1 : _offset + 1;
 414
 2415        _version++;
 416
 2417        return ret;
 2418    }
 419
 420    /// <summary>
 421    /// Removes and returns the maximum element in the sorter.
 422    /// </summary>
 423    /// <returns>The maximum element.</returns>
 424    public T PopMax()
 3425    {
 4426        if ((uint)_count == 0) throw new IndexOutOfRangeException();
 427
 2428        int index = GetPhysicalIndex(--_count);
 2429        T ret = _innerArray[index];
 2430        _innerArray[index] = default;
 3431        if ((uint)_count == 0) _offset = _innerArray.Length >> 1;
 432
 2433        _version++;
 434
 2435        return ret;
 2436    }
 437
 438    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 439    public bool Remove(T item)
 10440    {
 11441        if ((uint)_count == 0) return false;
 442
 9443        int index = Search(item);
 11444        if (index < 0) return false;
 445
 7446        RemoveAt(index);
 7447        return true;
 10448    }
 449
 450    /// <summary>
 451    /// Removes the element at the specified arrayIndex from the sorted list.
 452    /// Shifts elements as needed to maintain the sorted order and efficient space utilization.
 453    /// </summary>
 454    /// <param name="index">The zero-based arrayIndex of the element to remove.</param>
 455    public void RemoveAt(int index)
 10456    {
 10457        if ((uint)index >= (uint)_count) throw new ArgumentOutOfRangeException(nameof(index));
 458
 10459        int physicalIndex = GetPhysicalIndex(index);
 460
 10461        _count--;
 10462        if ((uint)index < (uint)_count)
 7463        {
 7464            int distanceToHead = physicalIndex - _offset;
 7465            int distanceToTail = (_offset + _count) - physicalIndex;
 466
 7467            if (distanceToHead < distanceToTail)
 6468            {
 469                // Shift elements towards the tail (right) to fill the gap
 6470                Array.Copy(_innerArray, _offset, _innerArray, _offset + 1, distanceToHead);
 6471                _offset++;  // Adjust offset since we've moved elements towards the tail
 6472            }
 473            else
 1474            {
 475                // Shift elements towards the head (left) to fill the gap
 1476                Array.Copy(_innerArray, physicalIndex + 1, _innerArray, physicalIndex, distanceToTail);
 1477                _innerArray[GetPhysicalIndex(_count)] = default; // Clear the last element
 1478            }
 7479        }
 480        else  // Removing the last element; simply clear it
 3481            _innerArray[GetPhysicalIndex(_count)] = default;
 482
 483        // Only recenter if offset is non-zero and count is less than 25% of capacity
 10484        if (_offset != 0 && (uint)_count < _innerArray.Length * 0.25)
 1485        {
 1486            if ((uint)_count == 0)
 0487                _offset = _innerArray.Length >> 1; // Reset offset to the middle when list is empty
 488            else
 1489                RecenterArray();
 1490        }
 491
 10492        _version++;
 10493    }
 494
 495    public void Clear()
 2496    {
 3497        if ((uint)_count == 0) return;
 1498        Array.Clear(_innerArray, _offset, _count);
 1499        _count = 0;
 1500        _offset = _innerArray.Length == 0 ? 0 : _innerArray.Length >> 1; // Reset _offset to the middle of the array
 501
 1502        _version++;
 2503    }
 504
 505    /// <summary>
 506    /// Quickly clears the list by resetting the count and offset without modifying the internal array.
 507    /// Note: This leaves references in the internal array, which may prevent garbage collection of reference types.
 508    /// Use when performance is critical and you are certain that residual references are acceptable.
 509    /// </summary>
 510    public void FastClear()
 2511    {
 3512        if ((uint)_count == 0) return;
 1513        _count = 0;
 1514        _offset = _innerArray.Length == 0 ? 0 : _innerArray.Length >> 1; // Reset offset to middle
 515
 1516        _version++;
 2517    }
 518
 519    #endregion
 520
 521    #region Capacity Management
 522
 523    /// <summary>
 524    /// Ensures that the capacity of <see cref="SwiftSortedList{T}"/> is sufficient to accommodate the specified number 
 525    /// The capacity can increase by double to balance memory allocation efficiency and space.
 526    /// </summary>
 527    public void EnsureCapacity(int capacity)
 1528    {
 1529        capacity = SwiftHashTools.NextPowerOfTwo(capacity);
 1530        if (capacity > _innerArray.Length)
 1531            Resize(capacity);
 1532    }
 533
 534    /// <summary>
 535    /// Ensures that the capacity of <see cref="SwiftSortedList{T}"/> is sufficient to accommodate the specified number 
 536    /// The capacity can increase by double to balance memory allocation efficiency and space.
 537    /// </summary>
 538    private void Resize(int newSize)
 29539    {
 29540        int newCapacity = newSize <= DefaultCapacity ? DefaultCapacity : newSize;
 541
 29542        T[] newArray = new T[newCapacity];
 29543        int newOffset = (newArray.Length - _count) >> 1; // Center the elements in the new array
 29544        if ((uint)_count > 0)
 2545            Array.Copy(_innerArray, _offset, newArray, newOffset, _count);
 546
 29547        _innerArray = newArray;
 29548        _offset = newOffset;
 549
 29550        _version++;
 29551    }
 552
 553    /// <summary>
 554    /// Recenters the elements within the internal array to balance available space on both ends.
 555    /// This minimizes the need for shifting elements during future insertions and deletions.
 556    /// </summary>
 557    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 558    private void RecenterArray()
 1559    {
 1560        int newOffset = (_innerArray.Length - _count) >> 1;
 1561        Array.Copy(_innerArray, _offset, _innerArray, newOffset, _count);
 1562        _offset = newOffset;
 563
 1564        _version++;
 1565    }
 566
 567    #endregion
 568
 569    #region Utility Methods
 570
 571    /// <summary>
 572    /// Sets a new comparer for the sorted list and re-sorts the elements.
 573    /// </summary>
 574    /// <param name="comparer">The new comparer to use.</param>
 575    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 576    public void SetComparer(IComparer<T> comparer)
 2577    {
 2578        SwiftThrowHelper.ThrowIfNull(comparer, nameof(comparer));
 2579        if (ReferenceEquals(comparer, _comparer))
 1580            return;
 581
 1582        _comparer = comparer;
 1583        Array.Sort(_innerArray, _offset, _count, _comparer);
 1584        _version++;
 2585    }
 586
 587    /// <summary>
 588    /// Converts a logical arrayIndex within the list to the corresponding physical arrayIndex in the internal array.
 589    /// </summary>
 590    /// <param name="logicalIndex">The logical arrayIndex within the list.</param>
 591    /// <returns>The physical arrayIndex within the internal array.</returns>
 592    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 305593    private int GetPhysicalIndex(int logicalIndex) => _offset + logicalIndex;
 594
 595    /// <summary>
 596    /// Returns a read-only span over the populated sorted portion of the list.
 597    /// </summary>
 598    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 4599    public ReadOnlySpan<T> AsReadOnlySpan() => _innerArray.AsSpan(_offset, _count);
 600
 601    /// <summary>
 602    /// Returns the minimum element in the sorter without removing it.
 603    /// </summary>
 604    /// <returns>The minimum element.</returns>
 605    public T PeekMin()
 16606    {
 17607        if ((uint)_count == 0) throw new IndexOutOfRangeException();
 15608        return _innerArray[GetPhysicalIndex(0)];
 15609    }
 610
 611    /// <summary>
 612    /// Returns the maximum element in the sorter without removing it.
 613    /// </summary>
 614    /// <returns>The maximum element.</returns>
 615    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 616    public T PeekMax()
 14617    {
 15618        if ((uint)_count == 0) throw new IndexOutOfRangeException();
 13619        return _innerArray[GetPhysicalIndex(_count - 1)];
 13620    }
 621
 622    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 2623    public bool Contains(T item) => Search(item) >= 0;
 624
 625    /// <summary>
 626    /// Determines whether the <see cref="SwiftSortedList{T}"/> contains an element that matches the conditions defined 
 627    /// </summary>
 628    /// <param name="match">The predicate that defines the conditions of the element to search for.</param>
 629    /// <returns><c>true</c> if the <see cref="SwiftSortedList{T}"/> contains one or more elements that match the specif
 630    public bool Exists(Predicate<T> match)
 3631    {
 3632        SwiftThrowHelper.ThrowIfNull(match, nameof(match));
 633
 14634        for (int i = 0; i < _count; i++)
 6635        {
 6636            if (match(_innerArray[GetPhysicalIndex(i)]))
 1637                return true;
 5638        }
 639
 1640        return false;
 2641    }
 642
 643    /// <summary>
 644    /// Searches for an element that matches the conditions defined by the specified predicate, and returns the first ma
 645    /// </summary>
 646    /// <param name="match">The predicate that defines the conditions of the element to search for.</param>
 647    /// <returns>The first element that matches the conditions defined by the specified predicate, if found; otherwise, 
 648    public T Find(Predicate<T> match)
 2649    {
 2650        SwiftThrowHelper.ThrowIfNull(match, nameof(match));
 651
 16652        for (int i = 0; i < _count; i++)
 7653        {
 7654            T item = _innerArray[GetPhysicalIndex(i)];
 7655            if (match(item))
 1656                return item;
 6657        }
 658
 1659        return default;
 2660    }
 661
 662    /// <summary>
 663    /// Searches for the specified item in the sorted collection and returns the arrayIndex of the first occurrence.
 664    /// </summary>
 665    /// <param name="item">The item to search for.</param>
 666    /// <returns>The zero-based arrayIndex of the item if found; otherwise, -1.</returns>
 667    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 668    public int IndexOf(T item)
 2669    {
 2670        int index = Search(item);
 2671        return index >= 0 ? index : -1;
 2672    }
 673
 674    /// <summary>
 675    /// Determines the insertion point for a specified item in the collection.
 676    /// The insertion point is the arrayIndex where the item would be inserted if it were not already present.
 677    /// </summary>
 678    /// <param name="item">The item for which to find the insertion point.</param>
 679    /// <returns>The insertion point as a zero-based arrayIndex.</returns>
 680    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 681    public int InsertionPoint(T item)
 1682    {
 1683        int index = Search(item);
 1684        return index >= 0 ? index : ~index;
 1685    }
 686
 687    /// <summary>
 688    /// Searches for the specified item in the sorted collection.
 689    /// </summary>
 690    /// <param name="item">The item to search for.</param>
 691    /// <returns>
 692    /// The arrayIndex of the item if found or where the item should be inserted if not found.
 693    /// </returns>
 694    public int Search(T item)
 95695    {
 95696        int low = 0;
 95697        int high = _count - 1;
 221698        while ((uint)low <= high)
 137699        {
 137700            int mid = low + ((high - low) >> 1);
 137701            T midItem = _innerArray[GetPhysicalIndex(mid)];
 137702            int cmp = _comparer.Compare(midItem, item);
 137703            if ((uint)cmp == 0)
 11704                return mid; // Exact match found
 705
 126706            if (cmp < 0)
 89707                low = mid + 1; // Search in the right half
 708            else
 37709                high = mid - 1; // Search in the left half
 126710        }
 84711        return ~low; // Item not found, should be inserted at arrayIndex low
 95712    }
 713
 714    public void CopyTo(T[] array, int arrayIndex)
 2715    {
 2716        SwiftThrowHelper.ThrowIfNull(array, nameof(array));
 2717        if ((uint)arrayIndex > array.Length) throw new ArgumentOutOfRangeException(nameof(arrayIndex));
 3718        if (array.Length - arrayIndex < _count) throw new ArgumentException("The target array is too small.", nameof(arr
 719
 1720        Array.Copy(_innerArray, _offset, array, arrayIndex, _count);
 1721    }
 722
 723    public void CopyTo(Array array, int arrayIndex)
 2724    {
 2725        SwiftThrowHelper.ThrowIfNull(array, nameof(array));
 2726        if ((uint)arrayIndex > array.Length) throw new ArgumentOutOfRangeException(nameof(arrayIndex));
 3727        if (array.Length - arrayIndex < _count) throw new ArgumentException("The target array is too small.", nameof(arr
 728
 1729        Array.Copy(_innerArray, _offset, array, arrayIndex, _count);
 1730    }
 731
 732    public void CloneTo(ICollection<T> output)
 2733    {
 3734        if (output == null) throw new ArgumentNullException(nameof(output));
 1735        output.Clear();
 736
 9737        foreach (var item in this)
 3738            output.Add(item);
 1739    }
 740
 741    #endregion
 742
 743    #region Enumerators
 744
 745    /// <summary>
 746    /// Returns an enumerator that iterates through <see cref="SwiftSortedList{T}"/>.
 747    /// </summary>
 19748    public SwiftSorterEnumerator GetEnumerator() => new SwiftSorterEnumerator(this);
 12749    IEnumerator<T> IEnumerable<T>.GetEnumerator() => GetEnumerator();
 2750    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
 751
 752    public struct SwiftSorterEnumerator : IEnumerator<T>, IEnumerator, IDisposable
 753    {
 754        private readonly SwiftSortedList<T> _list;
 755        private readonly uint _count;
 756        private readonly uint _version;
 757        private int _index;
 758
 759        private T _current;
 760
 761        public SwiftSorterEnumerator(SwiftSortedList<T> sortedList)
 19762        {
 19763            _list = sortedList;
 19764            _count = (uint)sortedList._count;
 19765            _version = sortedList._version;
 19766            _index = 0;
 19767            _current = default;
 19768        }
 769
 36770        public T Current => _current;
 771
 772        object IEnumerator.Current
 773        {
 774            [MethodImpl(MethodImplOptions.AggressiveInlining)]
 775            get
 2776            {
 3777                if ((uint)_index > _count) throw new InvalidOperationException("Bad enumeration");
 1778                return _current;
 1779            }
 780
 781        }
 782
 783        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 784        public bool MoveNext()
 44785        {
 44786            if (_version != _list._version)
 0787                throw new InvalidOperationException("Enumerator modified outside of enumeration!");
 788
 44789            if (_index < _count)
 28790            {
 28791                _current = _list._innerArray[_list.GetPhysicalIndex(_index)];
 28792                _index++;
 28793                return true;
 794            }
 795
 16796            _index = _list._count + 1;
 16797            _current = default;
 16798            return false;
 44799        }
 800
 801        public void Reset()
 2802        {
 2803            if (_version != _list._version)
 1804                throw new InvalidOperationException("Enumerator modified outside of enumeration!");
 805
 1806            _index = 0;
 1807            _current = default;
 1808        }
 809
 30810        public void Dispose() { }
 811    }
 812
 813    #endregion
 814}
Generated by: ReportGenerator 5.5.4.0
04/03/2026 - 18:03:54
GitHub | reportgenerator.io

Methods/Properties

.cctor()
.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()
System.Collections.Generic.ICollection<T>.get_IsReadOnly()
get_IsSynchronized()
System.Collections.ICollection.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>)
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()