| | | 1 | | //======================================================================= |
| | | 2 | | // SwiftIntStack.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 | | |
| | | 8 | | using SwiftCollections.Utility; |
| | | 9 | | using System; |
| | | 10 | | using System.Runtime.CompilerServices; |
| | | 11 | | |
| | | 12 | | namespace SwiftCollections; |
| | | 13 | | |
| | | 14 | | /// <summary> |
| | | 15 | | /// A minimal and efficient stack implementation for integers. |
| | | 16 | | /// Optimized for internal use within the SwiftCollections library. |
| | | 17 | | /// </summary> |
| | | 18 | | [Serializable] |
| | | 19 | | internal class SwiftIntStack |
| | | 20 | | { |
| | | 21 | | #region Constants |
| | | 22 | | |
| | | 23 | | /// <summary> |
| | | 24 | | /// The default initial capacity of the stack. |
| | | 25 | | /// </summary> |
| | | 26 | | public const int DefaultCapacity = 8; |
| | | 27 | | |
| | | 28 | | #endregion |
| | | 29 | | |
| | | 30 | | #region Fields |
| | | 31 | | |
| | | 32 | | /// <summary> |
| | | 33 | | /// The internal array holding stack elements. |
| | | 34 | | /// </summary> |
| | | 35 | | public int[] Array { get; private set; } |
| | | 36 | | |
| | | 37 | | /// <summary> |
| | | 38 | | /// The current count of elements in the stack. |
| | | 39 | | /// </summary> |
| | | 40 | | public int Count { get; private set; } |
| | | 41 | | |
| | | 42 | | #endregion |
| | | 43 | | |
| | | 44 | | #region Constructors |
| | | 45 | | |
| | | 46 | | /// <summary> |
| | | 47 | | /// Initializes a new instance of the <see cref="SwiftIntStack"/> class with the default capacity. |
| | | 48 | | /// </summary> |
| | 208 | 49 | | public SwiftIntStack() : this(DefaultCapacity) { } |
| | | 50 | | |
| | | 51 | | /// <summary> |
| | | 52 | | /// Initializes a new instance of the <see cref="SwiftIntStack"/> class with a specified initial capacity. |
| | | 53 | | /// </summary> |
| | | 54 | | /// <param name="capacity">The initial capacity of the stack.</param> |
| | 273 | 55 | | public SwiftIntStack(int capacity) |
| | | 56 | | { |
| | 273 | 57 | | Array = capacity == 0 ? new int[DefaultCapacity] : new int[capacity]; |
| | 273 | 58 | | Count = 0; |
| | 273 | 59 | | } |
| | | 60 | | |
| | | 61 | | /// <summary> |
| | | 62 | | /// Initializes a new instance of the <see cref="SwiftIntStack"/> class using the specified array as the underlying |
| | | 63 | | /// the initial number of elements in the stack. |
| | | 64 | | /// </summary> |
| | | 65 | | /// <remarks>This constructor allows advanced scenarios where the stack is initialized with a pre-existing |
| | | 66 | | /// array and a specific element count. The caller is responsible for ensuring that the array and count accurately |
| | | 67 | | /// represent the intended stack state.</remarks> |
| | | 68 | | /// <param name="array">The array that provides the underlying storage for the stack. This parameter cannot be null. |
| | | 69 | | /// <param name="count">The number of elements initially contained in the stack. Must be a non-negative integer and |
| | | 70 | | /// length of the array.</param> |
| | 1 | 71 | | public SwiftIntStack(int[] array, int count) |
| | | 72 | | { |
| | 1 | 73 | | Array = array; |
| | 1 | 74 | | Count = count; |
| | 1 | 75 | | } |
| | | 76 | | |
| | | 77 | | #endregion |
| | | 78 | | |
| | | 79 | | #region Public Methods |
| | | 80 | | |
| | | 81 | | /// <summary> |
| | | 82 | | /// Pushes an integer onto the stack. |
| | | 83 | | /// Expands the stack's capacity if necessary. |
| | | 84 | | /// </summary> |
| | | 85 | | /// <param name="value">The integer value to push.</param> |
| | | 86 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 87 | | public void Push(int value) |
| | | 88 | | { |
| | 71623 | 89 | | EnsureCapacity(Count + 1); |
| | 71623 | 90 | | Array[Count++] = value; |
| | 71623 | 91 | | } |
| | | 92 | | |
| | | 93 | | /// <summary> |
| | | 94 | | /// Removes and returns the top integer from the stack. |
| | | 95 | | /// </summary> |
| | | 96 | | /// <returns>The top integer from the stack.</returns> |
| | | 97 | | /// <exception cref="InvalidOperationException">Thrown when attempting to pop from an empty stack.</exception> |
| | | 98 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | 21191 | 99 | | public int Pop() => Array[--Count]; |
| | | 100 | | |
| | | 101 | | /// <summary> |
| | | 102 | | /// Returns the top integer from the stack without removing it. |
| | | 103 | | /// </summary> |
| | | 104 | | /// <returns>The top integer from the stack.</returns> |
| | | 105 | | /// <exception cref="InvalidOperationException">Thrown when attempting to peek an empty stack.</exception> |
| | | 106 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | 1 | 107 | | public int Peek() => Array[Count - 1]; |
| | | 108 | | |
| | | 109 | | /// <summary> |
| | | 110 | | /// Resets the stack while preserving its current capacity. |
| | | 111 | | /// </summary> |
| | | 112 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | 7 | 113 | | public void Reset() => Count = 0; |
| | | 114 | | |
| | | 115 | | /// <summary> |
| | | 116 | | /// Removes all elements from the stack. |
| | | 117 | | /// </summary> |
| | | 118 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | 29 | 119 | | public void Clear() => Count = 0; |
| | | 120 | | |
| | | 121 | | /// <summary> |
| | | 122 | | /// Ensures the stack has at least the specified capacity. |
| | | 123 | | /// Expands the internal array if necessary. |
| | | 124 | | /// </summary> |
| | | 125 | | /// <param name="capacity">The minimum capacity to ensure.</param> |
| | | 126 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 127 | | public void EnsureCapacity(int capacity) |
| | | 128 | | { |
| | 71684 | 129 | | if (capacity <= Array.Length) |
| | 71636 | 130 | | return; |
| | | 131 | | |
| | 48 | 132 | | int newCapacity = SwiftHashTools.NextPowerOfTwo(capacity); |
| | 48 | 133 | | int doubledCapacity = (int)Math.Min((long)Array.Length * 2, int.MaxValue); |
| | 48 | 134 | | if (newCapacity < doubledCapacity) |
| | 1 | 135 | | newCapacity = doubledCapacity; |
| | | 136 | | |
| | 48 | 137 | | int[] newArray = new int[newCapacity]; |
| | 48 | 138 | | System.Array.Copy(Array, 0, newArray, 0, Count); |
| | 48 | 139 | | Array = newArray; |
| | 48 | 140 | | } |
| | | 141 | | |
| | | 142 | | #endregion |
| | | 143 | | } |