| | | 1 | | namespace MoreStructures.Stacks; |
| | | 2 | | |
| | | 3 | | /// <summary> |
| | | 4 | | /// A <see cref="IStack{T}"/> implementation based on an array list of items. |
| | | 5 | | /// </summary> |
| | | 6 | | /// <typeparam name="T"><inheritdoc cref="IStack{T}"/></typeparam> |
| | | 7 | | /// <remarks> |
| | | 8 | | /// <para id="advantages"> |
| | | 9 | | /// ADVANTAGES AND DISADVANTAGES |
| | | 10 | | /// <br/> |
| | | 11 | | /// - Compared to an implementation based on a linked list, such as <see cref="LinkedListStack{T}"/>, it has a |
| | | 12 | | /// lower memory footprint and a lower cost of memory management, due to the fact that a single object made of a |
| | | 13 | | /// contiguous area in memory is used, to store all items. |
| | | 14 | | /// <br/> |
| | | 15 | | /// - In particular, no need for per-item additional space is required, as it happens for "next" references and |
| | | 16 | | /// objects overhead in linked list-based solutions. |
| | | 17 | | /// <br/> |
| | | 18 | | /// - On the flip side, the requirement for a potentially large contiguous chunk of memory in the heap may produce |
| | | 19 | | /// <see cref="OutOfMemoryException"/> when trying to instantiate or resize stacks of large capacity, especially |
| | | 20 | | /// when the memory is heavily fragmented. |
| | | 21 | | /// <br/> |
| | | 22 | | /// - Moreover, each insert which happens when the underlying array has been fully occupied requires work |
| | | 23 | | /// proportional to the current size of the stack, since the underlying array cannot be extended without |
| | | 24 | | /// instantiating a larger array and performing a full copy from the old to the new one. |
| | | 25 | | /// <br/> |
| | | 26 | | /// - That means that insertion cost won't be O(1) all the time, but only in average, as amortized complexity over |
| | | 27 | | /// n operations (assuming that <see cref="ArrayBasedDataStructure{T}.IncreasingFactor"/> is left to its default |
| | | 28 | | /// value <see cref="ArrayBasedDataStructure{T}.DefaultIncreasingFactor"/>, or chosen sensibly). |
| | | 29 | | /// <br/> |
| | | 30 | | /// - That can be a significant drawback in realtime systems where insertion cost has to be highly predictable and |
| | | 31 | | /// also very low. |
| | | 32 | | /// </para> |
| | | 33 | | /// </remarks> |
| | | 34 | | public class ArrayListStack<T> : ArrayBasedDataStructure<T>, IStack<T> |
| | | 35 | | { |
| | | 36 | | /// <inheritdoc/> |
| | | 37 | | public ArrayListStack(int capacity = DefaultInitialCapacity, double increasingFactor = DefaultIncreasingFactor) |
| | 17 | 38 | | : base(capacity, increasingFactor) |
| | 12 | 39 | | { |
| | 12 | 40 | | } |
| | | 41 | | |
| | | 42 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 43 | | /// <remarks> |
| | | 44 | | /// Stored and updated in constant time at each <see cref="Push(T)"/> and <see cref="Pop"/>. |
| | | 45 | | /// <br/> |
| | | 46 | | /// Time and Space Complexity are O(1). |
| | | 47 | | /// </remarks> |
| | 319 | 48 | | public int Count { get; private set; } = 0; |
| | | 49 | | |
| | | 50 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 51 | | /// <remarks> |
| | | 52 | | /// Checks and returns the item of the underlying array list at the last index set (which is |
| | | 53 | | /// <see cref="Count"/> - 1), if it exists. |
| | | 54 | | /// <br/> |
| | | 55 | | /// Throws a <see cref="InvalidOperationException"/> if the underlying array is empty. |
| | | 56 | | /// <br/> |
| | | 57 | | /// Time and Space Complexity are O(1). |
| | | 58 | | /// </remarks> |
| | | 59 | | public T Peek() |
| | 4 | 60 | | { |
| | 4 | 61 | | if (Count == 0) |
| | 1 | 62 | | throw new InvalidOperationException($"Cannot {nameof(Peek)} on an empty stack."); |
| | 3 | 63 | | return Items[Count - 1]!; |
| | 3 | 64 | | } |
| | | 65 | | |
| | | 66 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 67 | | /// <remarks> |
| | | 68 | | /// First, it retrieves the last item set into the underlying array list (which is the one at index |
| | | 69 | | /// <see cref="Count"/> - 1). |
| | | 70 | | /// <br/> |
| | | 71 | | /// Then, it reset the value of the last item and decreases the <see cref="Count"/> by 1. |
| | | 72 | | /// <br/> |
| | | 73 | | /// Then, if the new <see cref="Count"/> is smaller than the current capacity by more than twice the |
| | | 74 | | /// <see cref="ArrayBasedDataStructure{T}.IncreasingFactor"/> compoundly (i.e. capacity * increasingFactor^2), the |
| | | 75 | | /// underlying array list is resized to have a new capacity equal to the old capacity times the increasing factor. |
| | | 76 | | /// <br/> |
| | | 77 | | /// Finally, it returns the retrieved item as result. |
| | | 78 | | /// <br/> |
| | | 79 | | /// Raises an <see cref="InvalidOperationException"/> if the array list is empty. |
| | | 80 | | /// <br/> |
| | | 81 | | /// Time and Space Complexity are O(1). |
| | | 82 | | /// </remarks> |
| | | 83 | | public T Pop() |
| | 28 | 84 | | { |
| | 28 | 85 | | if (Count == 0) |
| | 2 | 86 | | throw new InvalidOperationException($"Cannot {nameof(Pop)} on an empty stack."); |
| | 26 | 87 | | var item = Items[Count - 1]!; |
| | 26 | 88 | | Items[Count - 1] = default; |
| | 26 | 89 | | Count--; |
| | | 90 | | |
| | 26 | 91 | | if (Count <= Items.Length / (IncreasingFactor * IncreasingFactor)) |
| | 16 | 92 | | ResizeItems(1.0 / IncreasingFactor); |
| | | 93 | | |
| | 26 | 94 | | return item; |
| | 26 | 95 | | } |
| | | 96 | | |
| | | 97 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 98 | | /// <remarks> |
| | | 99 | | /// If there is available room in the underlying array, the new <paramref name="item"/> is stored in the first |
| | | 100 | | /// available location and the <see cref="Count"/> is increased by 1. |
| | | 101 | | /// <br/> |
| | | 102 | | /// Otherwise the underlying array is resized by the <see cref="ArrayBasedDataStructure{T}.IncreasingFactor"/>, to |
| | | 103 | | /// accomodate the new <paramref name="item"/>. |
| | | 104 | | /// <br/> |
| | | 105 | | /// Time and Space Complexity are O(1) if <see cref="Count"/> before insertion is strictly smaller than the current |
| | | 106 | | /// capacity. |
| | | 107 | | /// <br/> |
| | | 108 | | /// Time and Space Complexity are O(n) if <see cref="Count"/> before insertion is equal to the current capacity. |
| | | 109 | | /// <br/> |
| | | 110 | | /// If the <see cref="ArrayBasedDataStructure{T}.IncreasingFactor"/> is set to a sensible value (e.g. 2.0), the |
| | | 111 | | /// amortized cost over n insertions becomes O(1). |
| | | 112 | | /// </remarks> |
| | | 113 | | public void Push(T item) |
| | 33 | 114 | | { |
| | 33 | 115 | | if (Count == Items.Length) |
| | 6 | 116 | | ResizeItems(IncreasingFactor); |
| | | 117 | | |
| | 33 | 118 | | Items[Count] = item; |
| | 33 | 119 | | Count++; |
| | 33 | 120 | | } |
| | | 121 | | } |