< Summary

Information
Class: SwiftCollections.SwiftSortedList<T>
Assembly: SwiftCollections
File(s): File 1: /_/src/SwiftCollections/obj/Release/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: 288
Uncovered lines: 4
Coverable lines: 292
Total lines: 916
Line coverage: 98.6%
Branch coverage
93%
Covered branches: 103
Total branches: 110
Branch coverage: 93.6%
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: get_IsReadOnly()100%11100%
File 2: get_IsSynchronized()100%11100%
File 2: get_SyncRoot()100%22100%
File 2: get_Item(...)100%11100%
File 2: get_State()100%11100%
File 2: set_State(...)75%44100%
File 2: Add(...)100%22100%
File 2: Insert(...)87.5%8885%
File 2: AddRange(...)100%44100%
File 2: CopyToSortedArray(...)100%44100%
File 2: CopyCollectionToArray(...)100%22100%
File 2: InitializeFromSortedItems(...)100%44100%
File 2: MergeSortedItems(...)100%1010100%
File 2: PopMin()100%22100%
File 2: PopMax()100%22100%
File 2: Remove(...)100%44100%
File 2: RemoveAt(...)90%101094.44%
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%11100%
File 2: PeekMax()100%11100%
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(...)100%11100%
File 2: CopyTo(...)100%11100%
File 2: CloneTo(...)100%22100%
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%11100%
File 2: MoveNext()100%22100%
File 2: Reset()100%11100%
File 2: Dispose()100%11100%

File(s)

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

File '/_/src/SwiftCollections/obj/Release/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 Chronicler;
 2using MemoryPack;
 3using System;
 4using System.Collections;
 5using System.Collections.Generic;
 6using System.Linq;
 7using System.Runtime.CompilerServices;
 8using System.Text.Json.Serialization;
 9
 10namespace SwiftCollections;
 11
 12/// <summary>
 13/// Represents a dynamically sorted collection of elements.
 14/// Provides efficient O(log n) operations for adding, removing, and checking for the presence of elements.
 15/// </summary>
 16/// <remarks>
 17/// The comparer is not serialized. After deserialization the list uses
 18/// <see cref="Comparer{T}.Default"/>.
 19///
 20/// If a custom comparer is required it can be reapplied using
 21/// <see cref="SetComparer(IComparer{T})"/>.
 22/// </remarks>
 23/// <typeparam name="T">The type of elements in the collection.</typeparam>
 24[Serializable]
 25[JsonConverter(typeof(StateJsonConverterFactory))]
 26[MemoryPackable]
 27public partial class SwiftSortedList<T> : IStateBacked<SwiftArrayState<T>>, ISwiftCloneable<T>, IEnumerable<T>, IEnumera
 28{
 29    #region Constants
 30
 31    /// <summary>
 32    /// The default initial capacity of the <see cref="SwiftSortedList{T}"/> if none is specified.
 33    /// Used to allocate a reasonable starting size to minimize resizing operations.
 34    /// </summary>
 35    public const int DefaultCapacity = 8;
 36
 237    private static readonly T[] _emptyArray = Array.Empty<T>();
 38
 39    #endregion
 40
 41    #region Fields
 42
 43    /// <summary>
 44    /// Represents the internal array that stores the sorted elements.
 45    /// </summary>
 46    private T[] _innerArray;
 47
 48    /// <summary>
 49    /// The number of elements contained in the <see cref="SwiftSortedList{T}"/>.
 50    /// </summary>
 51    private int _count;
 52
 53    /// <summary>
 54    /// The offset within the internal array where the logical start of the list begins.
 55    /// Used to efficiently manage insertions and deletions at both ends without excessive shifting.
 56    /// </summary>
 57    private int _offset;
 58
 59    /// <summary>
 60    /// A version counter used to track modifications to the sorted list.
 61    /// Incremented on mutations to detect changes during enumeration and ensure enumerator validity.
 62    /// </summary>
 63    [NonSerialized]
 64    private uint _version;
 65
 66    /// <summary>
 67    /// The comparer used to sort and compare elements in the collection.
 68    /// </summary>
 69    [NonSerialized]
 70    private IComparer<T> _comparer;
 71
 72    /// <summary>
 73    /// An object that can be used to synchronize access to the SwiftList.
 74    /// </summary>
 75    [NonSerialized]
 76    private object? _syncRoot;
 77
 78    #endregion
 79
 80    #region Constructors
 81
 82    /// <summary>
 83    /// Initializes a new instance of the SwiftSortedList class with the default capacity.
 84    /// </summary>
 85    /// <remarks>
 86    /// This constructor creates an empty sorted list.
 87    /// Items added to the list will be automatically ordered according to the default comparer for the item type.
 88    /// </remarks>
 10289    public SwiftSortedList() : this(0) { }
 90
 91    /// <summary>
 92    /// Initializes a new, empty instance of <see cref="SwiftSortedList{T}"/> uisng the specified <see cref="IComparer{T
 93    /// </summary>
 694    public SwiftSortedList(IComparer<T> comparer) : this(0, comparer) { }
 95
 96    /// <summary>
 97    /// Initializes a new, empty instance of <see cref="SwiftSortedList{T}"/> with the specified initial capacity and <s
 98    /// </summary>
 99    /// <param name="capacity">The starting initial capacity.</param>
 100    /// <param name="comparer">The comparer to use. If null, the default comparer is used.</param>
 55101    public SwiftSortedList(int capacity, IComparer<T>? comparer = null)
 102    {
 55103        _comparer = comparer ?? Comparer<T>.Default;
 104
 55105        if (capacity == 0)
 106        {
 54107            _innerArray = _emptyArray;
 54108            _offset = 0;
 109        }
 110        else
 111        {
 1112            capacity = capacity <= DefaultCapacity ? DefaultCapacity : SwiftHashTools.NextPowerOfTwo(capacity);
 1113            _innerArray = new T[capacity];
 1114            _offset = capacity >> 1; // initial offset half of capacity
 115        }
 1116    }
 117
 118    /// <summary>
 119    /// Initializes a new instance of the <see cref="SwiftList{T}"/> class with elements from the specified collection.
 120    /// The collection must have a known count for optimized memory allocation.
 121    /// </summary>
 122    /// <exception cref="ArgumentException">Thrown if the input collection does not have a known count.</exception>
 4123    public SwiftSortedList(IEnumerable<T> items, IComparer<T>? comparer = null)
 124    {
 4125        SwiftThrowHelper.ThrowIfNull(items, nameof(items));
 126
 4127        _comparer = comparer ?? Comparer<T>.Default;
 128
 4129        if (items is ICollection<T> collection)
 130        {
 3131            int count = collection.Count;
 3132            if (count == 0)
 133            {
 1134                _innerArray = _emptyArray;
 1135                _offset = 0;
 136            }
 137            else
 138            {
 2139                int capacity = SwiftHashTools.NextPowerOfTwo(count <= DefaultCapacity ? DefaultCapacity : count);
 2140                _innerArray = new T[capacity];
 2141                _offset = (capacity - count) >> 1;
 2142                collection.CopyTo(_innerArray, _offset);
 2143                Array.Sort(_innerArray, _offset, count, _comparer);
 2144                _count = count;
 145            }
 146        }
 147        else
 148        {
 1149            _innerArray = new T[DefaultCapacity];
 1150            _offset = DefaultCapacity >> 1;
 1151            AddRange(items); // Will handle capacity increases as needed
 152        }
 1153    }
 154
 155    ///  <summary>
 156    ///  Initializes a new instance of the <see cref="SwiftSortedList{T}"/> class with the specified <see cref="SwiftArr
 157    ///  </summary>
 158    ///  <param name="state">The state containing the internal array, count, offset, and version for initialization.</pa
 159    [MemoryPackConstructor]
 4160    public SwiftSortedList(SwiftArrayState<T> state)
 161    {
 4162        State = state;
 163
 164        // Validate that the internal array and comparer are not null after deserialization
 4165        SwiftThrowHelper.ThrowIfNull(_innerArray, nameof(_innerArray));
 4166        SwiftThrowHelper.ThrowIfNull(_comparer, nameof(_comparer));
 4167    }
 168
 169    #endregion
 170
 171    #region Properties
 172
 173    /// <summary>
 174    /// Gets the underlying array that stores the elements of the collection.
 175    /// </summary>
 176    /// <remarks>
 177    /// The returned array may contain unused elements beyond the logical contents of the collection.
 178    ///</remarks>
 179    [JsonIgnore]
 180    [MemoryPackIgnore]
 9181    public T[] InnerArray => _innerArray;
 182
 183    /// <inheritdoc cref="_count"/>
 184    [JsonIgnore]
 185    [MemoryPackIgnore]
 16186    public int Count => _count;
 187
 188    /// <inheritdoc cref="_offset"/>
 189    [JsonIgnore]
 190    [MemoryPackIgnore]
 12191    public int Offset => _offset;
 192
 193    /// <inheritdoc cref="_version"/>
 194    [JsonIgnore]
 195    [MemoryPackIgnore]
 5196    public uint Version => _version;
 197
 198    /// <summary>
 199    /// Gets the current capacity of the internal array.
 200    /// </summary>
 201    [JsonIgnore]
 202    [MemoryPackIgnore]
 7203    public int Capacity => _innerArray.Length;
 204
 205    /// <inheritdoc cref="_comparer"/>
 206    [JsonIgnore]
 207    [MemoryPackIgnore]
 1208    public IComparer<T> Comparer => _comparer;
 209
 210    /// <inheritdoc/>
 211    [JsonIgnore]
 212    [MemoryPackIgnore]
 1213    public bool IsReadOnly => false;
 214
 215    /// <inheritdoc/>
 216    [JsonIgnore]
 217    [MemoryPackIgnore]
 1218    public bool IsSynchronized => false;
 219
 220    /// <inheritdoc/>
 221    [JsonIgnore]
 222    [MemoryPackIgnore]
 1223    public object SyncRoot => _syncRoot ??= new object();
 224
 225    /// <summary>
 226    /// Gets the element at the specified arrayIndex.
 227    /// </summary>
 228    [JsonIgnore]
 229    [MemoryPackIgnore]
 230    public T this[int index]
 231    {
 232        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 233        get
 234        {
 2235            SwiftThrowHelper.ThrowIfListIndexInvalid(index, _count, nameof(index));
 1236            return _innerArray[GetPhysicalIndex(index)];
 237        }
 238    }
 239
 240    /// <summary>
 241    /// Gets or sets the current state of the array, including its items and structure.
 242    /// </summary>
 243    /// <remarks>
 244    /// Setting this property replaces the entire contents of the array with the specified state.
 245    /// The setter is intended for internal use and may reset internal metadata such as version and comparer.
 246    /// This property is intended for serialization and deserialization scenarios.
 247    /// </remarks>
 248    [JsonInclude]
 249    [MemoryPackInclude]
 250    public SwiftArrayState<T> State
 251    {
 252        get
 253        {
 3254            var items = new T[_count];
 3255            Array.Copy(_innerArray, _offset, items, 0, _count);
 3256            return new SwiftArrayState<T>(items);
 257        }
 258        internal set
 259        {
 4260            SwiftThrowHelper.ThrowIfNull(value.Items, nameof(value.Items));
 261
 4262            int count = value.Items.Length;
 263
 4264            if (count == 0)
 265            {
 1266                _innerArray = _emptyArray;
 1267                _offset = 0;
 1268                _count = 0;
 269            }
 270            else
 271            {
 3272                int capacity = SwiftHashTools.NextPowerOfTwo(count <= DefaultCapacity ? DefaultCapacity : count);
 3273                _innerArray = new T[capacity];
 274
 3275                int newOffset = (capacity - count) >> 1;
 276
 3277                Array.Copy(value.Items, 0, _innerArray, newOffset, count);
 278
 3279                _offset = newOffset;
 3280                _count = count;
 281            }
 282
 4283            _version = 0;
 4284            _comparer = Comparer<T>.Default;
 4285        }
 286    }
 287
 288    #endregion
 289
 290    #region Collection Manipulation
 291
 292    /// <inheritdoc/>
 293    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 294    public void Add(T item)
 295    {
 80296        int index = Search(item);
 159297        if (index < 0) index = ~index;
 80298        Insert(item, index);
 80299    }
 300
 301    /// <summary>
 302    /// Inserts an item into the internal array at the specified arrayIndex, shifting elements as needed.
 303    /// </summary>
 304    private void Insert(T item, int index)
 305    {
 80306        SwiftThrowHelper.ThrowIfArrayIndexInvalid(index, _count, nameof(index));
 80307        if (_offset + _count + 1 > _innerArray.Length)
 28308            Resize(_innerArray.Length * 2);
 309
 80310        int physicalIndex = GetPhysicalIndex(index);
 311
 80312        if (index < (uint)_count)
 313        {
 25314            int distanceToHead = physicalIndex - _offset;
 25315            int distanceToTail = (_offset + _count - 1) - physicalIndex;
 316
 25317            if (distanceToHead >= (uint)distanceToTail)
 318            {
 21319                if ((uint)_offset == 0)
 320                {
 321                    // Ensure capacity for recentering
 0322                    Resize(_innerArray.Length * 2);
 0323                    RecenterArray();
 0324                    physicalIndex = GetPhysicalIndex(index);
 325                }
 326
 21327                _offset--;
 21328                physicalIndex--;
 329                // Shift elements towards the head (left)
 21330                Array.Copy(_innerArray, _offset + 1, _innerArray, _offset, distanceToHead + 1);
 331            }
 332            else  // Shift elements towards the tail (right) to make space
 4333                Array.Copy(_innerArray, physicalIndex, _innerArray, physicalIndex + 1, _count - index);
 334        }
 335
 80336        _innerArray[physicalIndex] = item;
 80337        _count++;
 338
 80339        _version++;
 80340    }
 341
 342    /// <summary>
 343    /// Adds a range of elements to the collection, ensuring they are sorted and merged efficiently.
 344    /// </summary>
 345    /// <remarks>
 346    /// This will compact the array for efficiency.
 347    /// </remarks>
 348    public void AddRange(IEnumerable<T> items)
 349    {
 23350        SwiftThrowHelper.ThrowIfNull(items, nameof(items));
 351
 23352        T[] sortedItems = CopyToSortedArray(items);
 23353        if (sortedItems.Length == 0)
 2354            return;
 355
 21356        if ((uint)_count == 0)
 357        {
 18358            InitializeFromSortedItems(sortedItems);
 18359            return;
 360        }
 361
 3362        MergeSortedItems(sortedItems);
 3363    }
 364
 365    private T[] CopyToSortedArray(IEnumerable<T> items)
 366    {
 23367        T[] sortedItems = items is ICollection<T> collection
 23368            ? CopyCollectionToArray(collection)
 23369            : items.ToArray();
 370
 23371        if (sortedItems.Length > 0)
 21372            Array.Sort(sortedItems, 0, sortedItems.Length, _comparer);
 373
 23374        return sortedItems;
 375    }
 376
 377    private static T[] CopyCollectionToArray(ICollection<T> collection)
 378    {
 21379        if (collection.Count == 0)
 1380            return _emptyArray;
 381
 20382        T[] items = new T[collection.Count];
 20383        collection.CopyTo(items, 0);
 20384        return items;
 385    }
 386
 387    private void InitializeFromSortedItems(T[] sortedItems)
 388    {
 18389        int initialCapacity = SwiftHashTools.NextPowerOfTwo(sortedItems.Length < DefaultCapacity ? DefaultCapacity : sor
 18390        int newOffset = (initialCapacity - sortedItems.Length) >> 1;
 18391        if ((uint)_innerArray.Length < (uint)initialCapacity)
 16392            _innerArray = new T[initialCapacity];
 393
 18394        Array.Copy(sortedItems, 0, _innerArray, newOffset, sortedItems.Length);
 18395        _offset = newOffset;
 18396        _count = sortedItems.Length;
 18397        _version++;
 18398    }
 399
 400    private void MergeSortedItems(T[] sortedItems)
 401    {
 3402        int newCount = _count + sortedItems.Length;
 3403        int totalRequiredCapacity = newCount + _offset;
 3404        int newCapacity = SwiftHashTools.NextPowerOfTwo(totalRequiredCapacity);
 3405        int mergedOffset = (newCapacity - newCount) >> 1;
 3406        T[] newArray = new T[newCapacity];
 407
 3408        int existingIndex = 0;
 3409        int newItemsIndex = 0;
 3410        int mergedIndex = mergedOffset;
 411
 13412        while (existingIndex < _count && newItemsIndex < sortedItems.Length)
 413        {
 10414            T existingItem = _innerArray[_offset + existingIndex];
 10415            T newItem = sortedItems[newItemsIndex];
 416
 10417            if (_comparer.Compare(existingItem, newItem) <= 0)
 418            {
 4419                newArray[mergedIndex++] = existingItem;
 4420                existingIndex++;
 421            }
 422            else
 423            {
 6424                newArray[mergedIndex++] = newItem;
 6425                newItemsIndex++;
 426            }
 427        }
 428
 429        // Copy any remaining existing items
 4430        while (existingIndex < _count)
 1431            newArray[mergedIndex++] = _innerArray[_offset + existingIndex++];
 432
 433        // Copy any remaining new items
 7434        while (newItemsIndex < sortedItems.Length)
 4435            newArray[mergedIndex++] = sortedItems[newItemsIndex++];
 436
 3437        _innerArray = newArray;
 3438        _offset = mergedOffset;
 3439        _count = newCount;
 440
 3441        _version++;
 3442    }
 443
 444    /// <summary>
 445    /// Removes and returns the minimum element in the sorter.
 446    /// </summary>
 447    /// <returns>The minimum element.</returns>
 448    public T PopMin()
 449    {
 3450        SwiftThrowHelper.ThrowIfTrue((uint)_count == 0, message: "Cannot pop from an empty list.");
 451
 2452        int index = GetPhysicalIndex(0);
 2453        T ret = _innerArray[index];
 2454        _innerArray[index] = default!;
 2455        _count--;
 456        // Increment _offset as we remove from the front
 2457        _offset = _count == 0 ? _innerArray.Length >> 1 : _offset + 1;
 458
 2459        _version++;
 460
 2461        return ret;
 462    }
 463
 464    /// <summary>
 465    /// Removes and returns the maximum element in the sorter.
 466    /// </summary>
 467    /// <returns>The maximum element.</returns>
 468    public T PopMax()
 469    {
 3470        SwiftThrowHelper.ThrowIfTrue((uint)_count == 0, message: "Cannot pop from an empty list.");
 471
 2472        int index = GetPhysicalIndex(--_count);
 2473        T ret = _innerArray[index];
 2474        _innerArray[index] = default!;
 3475        if ((uint)_count == 0) _offset = _innerArray.Length >> 1;
 476
 2477        _version++;
 478
 2479        return ret;
 480    }
 481
 482    /// <inheritdoc/>
 483    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 484    public bool Remove(T item)
 485    {
 11486        if ((uint)_count == 0) return false;
 487
 9488        int index = Search(item);
 11489        if (index < 0) return false;
 490
 7491        RemoveAt(index);
 7492        return true;
 493    }
 494
 495    /// <summary>
 496    /// Removes the element at the specified arrayIndex from the sorted list.
 497    /// Shifts elements as needed to maintain the sorted order and efficient space utilization.
 498    /// </summary>
 499    /// <param name="index">The zero-based arrayIndex of the element to remove.</param>
 500    public void RemoveAt(int index)
 501    {
 10502        SwiftThrowHelper.ThrowIfListIndexInvalid(index, _count, nameof(index));
 503
 10504        int physicalIndex = GetPhysicalIndex(index);
 505
 10506        _count--;
 10507        if ((uint)index < (uint)_count)
 508        {
 7509            int distanceToHead = physicalIndex - _offset;
 7510            int distanceToTail = (_offset + _count) - physicalIndex;
 511
 7512            if (distanceToHead < distanceToTail)
 513            {
 514                // Shift elements towards the tail (right) to fill the gap
 6515                Array.Copy(_innerArray, _offset, _innerArray, _offset + 1, distanceToHead);
 6516                _offset++;  // Adjust offset since we've moved elements towards the tail
 517            }
 518            else
 519            {
 520                // Shift elements towards the head (left) to fill the gap
 1521                Array.Copy(_innerArray, physicalIndex + 1, _innerArray, physicalIndex, distanceToTail);
 1522                _innerArray[GetPhysicalIndex(_count)] = default!; // Clear the last element
 523            }
 524        }
 525        else  // Removing the last element; simply clear it
 3526            _innerArray[GetPhysicalIndex(_count)] = default!;
 527
 528        // Only recenter if offset is non-zero and count is less than 25% of capacity
 10529        if (_offset != 0 && (uint)_count < _innerArray.Length * 0.25)
 530        {
 1531            if ((uint)_count == 0)
 0532                _offset = _innerArray.Length >> 1; // Reset offset to the middle when list is empty
 533            else
 1534                RecenterArray();
 535        }
 536
 10537        _version++;
 10538    }
 539
 540    /// <inheritdoc/>
 541    public void Clear()
 542    {
 3543        if ((uint)_count == 0) return;
 1544        Array.Clear(_innerArray, _offset, _count);
 1545        _count = 0;
 1546        _offset = _innerArray.Length == 0 ? 0 : _innerArray.Length >> 1; // Reset _offset to the middle of the array
 547
 1548        _version++;
 1549    }
 550
 551    /// <summary>
 552    /// Quickly clears the list by resetting the count and offset without modifying the internal array.
 553    /// Note: This leaves references in the internal array, which may prevent garbage collection of reference types.
 554    /// Use when performance is critical and you are certain that residual references are acceptable.
 555    /// </summary>
 556    public void FastClear()
 557    {
 3558        if ((uint)_count == 0) return;
 1559        _count = 0;
 1560        _offset = _innerArray.Length == 0 ? 0 : _innerArray.Length >> 1; // Reset offset to middle
 561
 1562        _version++;
 1563    }
 564
 565    #endregion
 566
 567    #region Capacity Management
 568
 569    /// <summary>
 570    /// Ensures that the capacity of <see cref="SwiftSortedList{T}"/> is sufficient to accommodate the specified number 
 571    /// The capacity can increase by double to balance memory allocation efficiency and space.
 572    /// </summary>
 573    public void EnsureCapacity(int capacity)
 574    {
 1575        capacity = SwiftHashTools.NextPowerOfTwo(capacity);
 1576        if (capacity > _innerArray.Length)
 1577            Resize(capacity);
 1578    }
 579
 580    /// <summary>
 581    /// Ensures that the capacity of <see cref="SwiftSortedList{T}"/> is sufficient to accommodate the specified number 
 582    /// The capacity can increase by double to balance memory allocation efficiency and space.
 583    /// </summary>
 584    private void Resize(int newSize)
 585    {
 29586        int newCapacity = newSize <= DefaultCapacity ? DefaultCapacity : newSize;
 587
 29588        T[] newArray = new T[newCapacity];
 29589        int newOffset = (newArray.Length - _count) >> 1; // Center the elements in the new array
 29590        if ((uint)_count > 0)
 2591            Array.Copy(_innerArray, _offset, newArray, newOffset, _count);
 592
 29593        _innerArray = newArray;
 29594        _offset = newOffset;
 595
 29596        _version++;
 29597    }
 598
 599    /// <summary>
 600    /// Recenters the elements within the internal array to balance available space on both ends.
 601    /// This minimizes the need for shifting elements during future insertions and deletions.
 602    /// </summary>
 603    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 604    private void RecenterArray()
 605    {
 1606        int newOffset = (_innerArray.Length - _count) >> 1;
 1607        Array.Copy(_innerArray, _offset, _innerArray, newOffset, _count);
 1608        _offset = newOffset;
 609
 1610        _version++;
 1611    }
 612
 613    #endregion
 614
 615    #region Utility Methods
 616
 617    /// <summary>
 618    /// Sets a new comparer for the sorted list and re-sorts the elements.
 619    /// </summary>
 620    /// <param name="comparer">The new comparer to use.</param>
 621    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 622    public void SetComparer(IComparer<T> comparer)
 623    {
 2624        SwiftThrowHelper.ThrowIfNull(comparer, nameof(comparer));
 2625        if (ReferenceEquals(comparer, _comparer))
 1626            return;
 627
 1628        _comparer = comparer;
 1629        Array.Sort(_innerArray, _offset, _count, _comparer);
 1630        _version++;
 1631    }
 632
 633    /// <summary>
 634    /// Converts a logical arrayIndex within the list to the corresponding physical arrayIndex in the internal array.
 635    /// </summary>
 636    /// <param name="logicalIndex">The logical arrayIndex within the list.</param>
 637    /// <returns>The physical arrayIndex within the internal array.</returns>
 638    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 305639    private int GetPhysicalIndex(int logicalIndex) => _offset + logicalIndex;
 640
 641    /// <summary>
 642    /// Returns a read-only span over the populated sorted portion of the list.
 643    /// </summary>
 644    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 4645    public ReadOnlySpan<T> AsReadOnlySpan() => _innerArray.AsSpan(_offset, _count);
 646
 647    /// <summary>
 648    /// Returns the minimum element in the sorter without removing it.
 649    /// </summary>
 650    /// <returns>The minimum element.</returns>
 651    public T PeekMin()
 652    {
 16653        SwiftThrowHelper.ThrowIfTrue((uint)_count == 0, message: "Cannot peek from an empty list.");
 15654        return _innerArray[GetPhysicalIndex(0)];
 655    }
 656
 657    /// <summary>
 658    /// Returns the maximum element in the sorter without removing it.
 659    /// </summary>
 660    /// <returns>The maximum element.</returns>
 661    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 662    public T PeekMax()
 663    {
 14664        SwiftThrowHelper.ThrowIfTrue((uint)_count == 0, message: "Cannot peek from an empty list.");
 13665        return _innerArray[GetPhysicalIndex(_count - 1)];
 666    }
 667
 668    /// <inheritdoc/>
 669    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 2670    public bool Contains(T item) => Search(item) >= 0;
 671
 672    /// <summary>
 673    /// Determines whether the <see cref="SwiftSortedList{T}"/> contains an element that matches the conditions defined 
 674    /// </summary>
 675    /// <param name="match">The predicate that defines the conditions of the element to search for.</param>
 676    /// <returns><c>true</c> if the <see cref="SwiftSortedList{T}"/> contains one or more elements that match the specif
 677    public bool Exists(Predicate<T> match)
 678    {
 3679        SwiftThrowHelper.ThrowIfNull(match, nameof(match));
 680
 14681        for (int i = 0; i < _count; i++)
 682        {
 6683            if (match(_innerArray[GetPhysicalIndex(i)]))
 1684                return true;
 685        }
 686
 1687        return false;
 688    }
 689
 690    /// <summary>
 691    /// Searches for an element that matches the conditions defined by the specified predicate, and returns the first ma
 692    /// </summary>
 693    /// <param name="match">The predicate that defines the conditions of the element to search for.</param>
 694    /// <returns>The first element that matches the conditions defined by the specified predicate, if found; otherwise, 
 695    public T Find(Predicate<T> match)
 696    {
 2697        SwiftThrowHelper.ThrowIfNull(match, nameof(match));
 698
 16699        for (int i = 0; i < _count; i++)
 700        {
 7701            T item = _innerArray[GetPhysicalIndex(i)];
 7702            if (match(item))
 1703                return item;
 704        }
 705
 1706        return default!;
 707    }
 708
 709    /// <summary>
 710    /// Searches for the specified item in the sorted collection and returns the arrayIndex of the first occurrence.
 711    /// </summary>
 712    /// <param name="item">The item to search for.</param>
 713    /// <returns>The zero-based arrayIndex of the item if found; otherwise, -1.</returns>
 714    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 715    public int IndexOf(T item)
 716    {
 2717        int index = Search(item);
 2718        return index >= 0 ? index : -1;
 719    }
 720
 721    /// <summary>
 722    /// Determines the insertion point for a specified item in the collection.
 723    /// The insertion point is the arrayIndex where the item would be inserted if it were not already present.
 724    /// </summary>
 725    /// <param name="item">The item for which to find the insertion point.</param>
 726    /// <returns>The insertion point as a zero-based arrayIndex.</returns>
 727    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 728    public int InsertionPoint(T item)
 729    {
 1730        int index = Search(item);
 1731        return index >= 0 ? index : ~index;
 732    }
 733
 734    /// <summary>
 735    /// Searches for the specified item in the sorted collection.
 736    /// </summary>
 737    /// <param name="item">The item to search for.</param>
 738    /// <returns>
 739    /// The arrayIndex of the item if found or where the item should be inserted if not found.
 740    /// </returns>
 741    public int Search(T item)
 742    {
 95743        int low = 0;
 95744        int high = _count - 1;
 221745        while ((uint)low <= high)
 746        {
 137747            int mid = low + ((high - low) >> 1);
 137748            T midItem = _innerArray[GetPhysicalIndex(mid)];
 137749            int cmp = _comparer.Compare(midItem, item);
 137750            if ((uint)cmp == 0)
 11751                return mid; // Exact match found
 752
 126753            if (cmp < 0)
 89754                low = mid + 1; // Search in the right half
 755            else
 37756                high = mid - 1; // Search in the left half
 757        }
 84758        return ~low; // Item not found, should be inserted at arrayIndex low
 759    }
 760
 761    /// <inheritdoc/>
 762    public void CopyTo(T[] array, int arrayIndex)
 763    {
 2764        SwiftThrowHelper.ThrowIfNull(array, nameof(array));
 2765        SwiftThrowHelper.ThrowIfArrayIndexInvalid(arrayIndex, array.Length, nameof(arrayIndex));
 2766        SwiftThrowHelper.ThrowIfArgument(array.Length - arrayIndex < _count, nameof(array), "The target array is too sma
 767
 1768        Array.Copy(_innerArray, _offset, array, arrayIndex, _count);
 1769    }
 770
 771    /// <inheritdoc/>
 772    public void CopyTo(Array array, int arrayIndex)
 773    {
 2774        SwiftThrowHelper.ThrowIfNull(array, nameof(array));
 2775        SwiftThrowHelper.ThrowIfArrayIndexInvalid(arrayIndex, array.Length, nameof(arrayIndex));
 2776        SwiftThrowHelper.ThrowIfArgument(array.Length - arrayIndex < _count, nameof(array), "The target array is too sma
 777
 1778        Array.Copy(_innerArray, _offset, array, arrayIndex, _count);
 1779    }
 780
 781    /// <inheritdoc/>
 782    public void CloneTo(ICollection<T> output)
 783    {
 2784        SwiftThrowHelper.ThrowIfNull(output, nameof(output));
 785
 1786        output.Clear();
 787
 8788        foreach (var item in this)
 3789            output.Add(item);
 1790    }
 791
 792    #endregion
 793
 794    #region Enumerators
 795
 796    /// <summary>
 797    /// Returns an enumerator that iterates through <see cref="SwiftSortedList{T}"/>.
 798    /// </summary>
 19799    public SwiftSorterEnumerator GetEnumerator() => new(this);
 12800    IEnumerator<T> IEnumerable<T>.GetEnumerator() => GetEnumerator();
 2801    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
 802
 803    /// <summary>
 804    /// Supports simple iteration over the elements of a <see cref="SwiftSortedList{T}"/> in sorted order.
 805    /// </summary>
 806    /// <remarks>
 807    /// The enumerator is invalidated if the underlying collection is modified after the enumerator created.
 808    /// In this case, calling MoveNext or Reset will throw an InvalidOperationException.
 809    /// The enumerator does not support writing to the collection.
 810    /// </remarks>
 811    public struct SwiftSorterEnumerator : IEnumerator<T>, IEnumerator, IDisposable
 812    {
 813        private readonly SwiftSortedList<T> _list;
 814        private readonly uint _count;
 815        private readonly uint _version;
 816        private int _index;
 817
 818        private T _current;
 819
 820        internal SwiftSorterEnumerator(SwiftSortedList<T> sortedList)
 821        {
 19822            _list = sortedList;
 19823            _count = (uint)sortedList._count;
 19824            _version = sortedList._version;
 19825            _index = 0;
 19826            _current = default!;
 19827        }
 828
 829        /// <inheritdoc/>
 36830        public T Current => _current;
 831
 832        object IEnumerator.Current
 833        {
 834            [MethodImpl(MethodImplOptions.AggressiveInlining)]
 835            get
 836            {
 2837                SwiftThrowHelper.ThrowIfTrue((uint)_index > _count, message: "Enumerator is past the end of the collecti
 1838                return _current!;
 839            }
 840
 841        }
 842
 843        /// <inheritdoc/>
 844        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 845        public bool MoveNext()
 846        {
 44847            SwiftThrowHelper.ThrowIfTrue(_version != _list._version, message: "Enumerator modified outside of enumeratio
 848
 44849            if (_index < _count)
 850            {
 28851                _current = _list._innerArray[_list.GetPhysicalIndex(_index)];
 28852                _index++;
 28853                return true;
 854            }
 855
 16856            _index = _list._count + 1;
 16857            _current = default!;
 16858            return false;
 859        }
 860
 861        /// <inheritdoc/>
 862        public void Reset()
 863        {
 2864            SwiftThrowHelper.ThrowIfTrue(_version != _list._version, message: "Enumerator modified outside of enumeratio
 865
 1866            _index = 0;
 1867            _current = default!;
 1868        }
 869
 870        /// <inheritdoc/>
 15871        public void Dispose() => _index = 0;
 872    }
 873
 874    #endregion
 875}
Generated by: ReportGenerator 5.5.10.0
05/19/2026 - 03:35: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()
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>)
CopyToSortedArray(System.Collections.Generic.IEnumerable`1<T>)
CopyCollectionToArray(System.Collections.Generic.ICollection`1<T>)
InitializeFromSortedItems(T[])
MergeSortedItems(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()