| | | 1 | | namespace MoreStructures.Queues; |
| | | 2 | | |
| | | 3 | | /// <summary> |
| | | 4 | | /// A <see cref="IQueue{T}"/> implementation based on an array list of items. |
| | | 5 | | /// </summary> |
| | | 6 | | /// <typeparam name="T"><inheritdoc cref="IQueue{T}"/></typeparam> |
| | | 7 | | /// <remarks> |
| | | 8 | | /// <para id="advantages"> |
| | | 9 | | /// ADVANTAGES AND DISADVANTAGES |
| | | 10 | | /// <br/> |
| | | 11 | | /// - The advantages an disadvantages of using an array list over a linked list-based implementation are the same |
| | | 12 | | /// as the ones described in <see cref="Stacks.LinkedListStack{T}"/>. |
| | | 13 | | /// </para> |
| | | 14 | | /// </remarks> |
| | | 15 | | public class ArrayListQueue<T> : Stacks.ArrayBasedDataStructure<T>, IQueue<T> |
| | | 16 | | { |
| | 1775 | 17 | | private int StartIndex { get; set; } = 0; |
| | | 18 | | |
| | | 19 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 20 | | /// <remarks> |
| | | 21 | | /// Stored and updated in constant time at each <see cref="Enqueue(T)"/> and <see cref="Dequeue"/>. |
| | | 22 | | /// <br/> |
| | | 23 | | /// Time and Space Complexity are O(1). |
| | | 24 | | /// </remarks> |
| | 2825 | 25 | | public int Count { get; private set; } = 0; |
| | | 26 | | |
| | | 27 | | /// <inheritdoc/> |
| | | 28 | | public ArrayListQueue(int capacity = DefaultInitialCapacity, double increasingFactor = DefaultIncreasingFactor) |
| | 6 | 29 | | : base(capacity, increasingFactor) |
| | 6 | 30 | | { |
| | 6 | 31 | | } |
| | | 32 | | |
| | | 33 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 34 | | /// <remarks> |
| | | 35 | | /// Checks and returns the item of the underlying array list at the first index set (which is |
| | | 36 | | /// internally stored), if it exists. |
| | | 37 | | /// <br/> |
| | | 38 | | /// Throws a <see cref="InvalidOperationException"/> if the underlying array is empty. |
| | | 39 | | /// <br/> |
| | | 40 | | /// Time and Space Complexity are O(1). |
| | | 41 | | /// </remarks> |
| | | 42 | | public T Peek() |
| | 9 | 43 | | { |
| | 9 | 44 | | if (Count == 0) |
| | 3 | 45 | | throw new InvalidOperationException($"Cannot {nameof(Peek)} on an empty queue."); |
| | 6 | 46 | | return Items[IndexOfNthItem(0)]!; |
| | 6 | 47 | | } |
| | | 48 | | |
| | | 49 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 50 | | /// <remarks> |
| | | 51 | | /// First, it retrieves the least recent item set into the underlying array list (whose index is internally |
| | | 52 | | /// stored). |
| | | 53 | | /// <br/> |
| | | 54 | | /// Then, it reset the value at such index and decreases the <see cref="Count"/> by 1. |
| | | 55 | | /// <br/> |
| | | 56 | | /// Then, if the new <see cref="Count"/> is smaller than the current capacity by more than twice the |
| | | 57 | | /// <see cref="Stacks.ArrayBasedDataStructure{T}.IncreasingFactor"/> compoundly |
| | | 58 | | /// (i.e. capacity * increasingFactor^2), the underlying array list is resized to have a new capacity equal to the |
| | | 59 | | /// old capacity times the increasing factor. |
| | | 60 | | /// <br/> |
| | | 61 | | /// Finally, it returns the retrieved item as result. |
| | | 62 | | /// <br/> |
| | | 63 | | /// Raises an <see cref="InvalidOperationException"/> if the array list is empty. |
| | | 64 | | /// <br/> |
| | | 65 | | /// Time and Space Complexity are O(1). |
| | | 66 | | /// </remarks> |
| | | 67 | | public T Dequeue() |
| | 288 | 68 | | { |
| | 288 | 69 | | if (Count == 0) |
| | 3 | 70 | | throw new InvalidOperationException($"Cannot {nameof(Dequeue)} on an empty queue."); |
| | | 71 | | |
| | 285 | 72 | | var index = IndexOfNthItem(0); |
| | 285 | 73 | | var item = Items[index]!; |
| | 285 | 74 | | Items[index] = default; |
| | 285 | 75 | | StartIndex = (StartIndex + 1) % Items.Length; |
| | 285 | 76 | | Count--; |
| | | 77 | | |
| | 285 | 78 | | if (Count <= Items.Length / (IncreasingFactor * IncreasingFactor)) |
| | 118 | 79 | | ResizeItems(1.0 / IncreasingFactor); |
| | | 80 | | |
| | 285 | 81 | | return item; |
| | 285 | 82 | | } |
| | | 83 | | |
| | | 84 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 85 | | /// <remarks> |
| | | 86 | | /// If there is available room in the underlying array, the new <paramref name="item"/> is stored in the first |
| | | 87 | | /// available location (applying circular arithmetic to indexes) and the <see cref="Count"/> is increased by 1. |
| | | 88 | | /// <br/> |
| | | 89 | | /// Otherwise the underlying array is resized by the |
| | | 90 | | /// <see cref="Stacks.ArrayBasedDataStructure{T}.IncreasingFactor"/>, to accomodate the new |
| | | 91 | | /// <paramref name="item"/>. |
| | | 92 | | /// <br/> |
| | | 93 | | /// Time and Space Complexity are O(1) if <see cref="Count"/> before insertion is strictly smaller than the current |
| | | 94 | | /// capacity. |
| | | 95 | | /// <br/> |
| | | 96 | | /// Time and Space Complexity are O(n) if <see cref="Count"/> before insertion is equal to the current capacity. |
| | | 97 | | /// <br/> |
| | | 98 | | /// If the <see cref="Stacks.ArrayBasedDataStructure{T}.IncreasingFactor"/> is set to a sensible value (e.g. 2.0), |
| | | 99 | | /// the amortized cost over n insertions becomes O(1). |
| | | 100 | | /// </remarks> |
| | | 101 | | public void Enqueue(T item) |
| | 286 | 102 | | { |
| | 286 | 103 | | if (Count == Items.Length) |
| | 2 | 104 | | ResizeItems(IncreasingFactor); |
| | | 105 | | |
| | 286 | 106 | | Items[IndexOfNthItem(Count)] = item; |
| | 286 | 107 | | Count++; |
| | 286 | 108 | | } |
| | | 109 | | |
| | 577 | 110 | | private int IndexOfNthItem(int nth) => (StartIndex + nth + Items.Length) % Items.Length; |
| | | 111 | | |
| | | 112 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 113 | | /// <remarks> |
| | | 114 | | /// After resizing, it copies items appropriately to restore circular arithmetic of indexes which is now based on |
| | | 115 | | /// a different modulo. |
| | | 116 | | /// <br/> |
| | | 117 | | /// If the size of the array has been increased, copy will happen from the front of the backing array to the front |
| | | 118 | | /// of its second half (introduced by the resizing). |
| | | 119 | | /// <br/> |
| | | 120 | | /// If the size of the array has been reduced, copy will simply scan the entire old array, remapping indexes into |
| | | 121 | | /// the new array. |
| | | 122 | | /// </remarks> |
| | | 123 | | protected override void ResizeItems(double factor) |
| | 120 | 124 | | { |
| | 120 | 125 | | var oldSize = Items.Length; |
| | | 126 | | |
| | 120 | 127 | | if (factor > 1) |
| | 2 | 128 | | { |
| | 2 | 129 | | base.ResizeItems(factor); |
| | | 130 | | |
| | 56 | 131 | | for (var i = 0; i < StartIndex + Count - oldSize; i++) |
| | 26 | 132 | | { |
| | 26 | 133 | | var oldIndex = i % Items.Length; |
| | 26 | 134 | | var newIndex = (oldSize + i) % Items.Length; |
| | 26 | 135 | | Items[newIndex] = Items[oldIndex]; |
| | 26 | 136 | | Items[oldIndex] = default; |
| | 26 | 137 | | } |
| | 2 | 138 | | } |
| | | 139 | | else |
| | 118 | 140 | | { |
| | 118 | 141 | | var oldItems = Items; |
| | 118 | 142 | | var newSize = (int)Math.Ceiling(oldItems.Length * factor); |
| | 118 | 143 | | var newItems = new T?[newSize]; |
| | | 144 | | |
| | 830 | 145 | | for (var i = 0; i < Count; i++) |
| | 297 | 146 | | newItems[(StartIndex + i) % newSize] = oldItems[(StartIndex + i) % oldSize]; |
| | 118 | 147 | | } |
| | 120 | 148 | | } |
| | | 149 | | } |