| | | 1 | | // Copyright (c) 2020-2024 dotBunny Inc. |
| | | 2 | | // dotBunny licenses this file to you under the BSL-1.0 license. |
| | | 3 | | // See the LICENSE file in the project root for more information. |
| | | 4 | | |
| | | 5 | | using System; |
| | | 6 | | |
| | | 7 | | namespace GDX.Collections |
| | | 8 | | { |
| | | 9 | | /// <summary> |
| | | 10 | | /// An array where indices are allocated from and stored in an in-place linked list. |
| | | 11 | | /// Allocating or deallocating a single int from this array is very fast, as is single datum lookup, |
| | | 12 | | /// but neither the allocated indices nor the free indices can be reliably iterated without an external data str |
| | | 13 | | /// This structure can be adapted to an arbitrary of external, parallel arrays. |
| | | 14 | | /// </summary> |
| | | 15 | | public struct FreeList |
| | | 16 | | { |
| | | 17 | | /// <summary> |
| | | 18 | | /// Data storage for allocated indices as well as the in-place free-list. |
| | | 19 | | /// </summary> |
| | | 20 | | public int[] Indices; |
| | | 21 | | |
| | | 22 | | /// <summary> |
| | | 23 | | /// The next available index of the free-list. |
| | | 24 | | /// </summary> |
| | | 25 | | public int CurrentFreeIndex; |
| | | 26 | | |
| | | 27 | | /// <summary> |
| | | 28 | | /// The total number of currently-allocated indices. |
| | | 29 | | /// </summary> |
| | | 30 | | public int Count; |
| | | 31 | | |
| | | 32 | | /// <summary> |
| | | 33 | | /// </summary> |
| | | 34 | | /// <param name="initialCapacity">The initial capacity of the array.</param> |
| | | 35 | | public FreeList(int initialCapacity) |
| | 8 | 36 | | { |
| | 8 | 37 | | Indices = new int[initialCapacity]; |
| | 8 | 38 | | CurrentFreeIndex = 0; |
| | 8 | 39 | | Count = 0; |
| | | 40 | | |
| | 48 | 41 | | for (int i = 0; i < initialCapacity; i++) |
| | 16 | 42 | | { |
| | 16 | 43 | | Indices[i] = i + 1; |
| | 16 | 44 | | } |
| | 8 | 45 | | } |
| | | 46 | | |
| | | 47 | | /// <summary> |
| | | 48 | | /// Removes all allocated data and rebuilds the free-list. |
| | | 49 | | /// </summary> |
| | | 50 | | public void Clear() |
| | 1 | 51 | | { |
| | 1 | 52 | | int length = Indices.Length; |
| | 6 | 53 | | for (int i = 0; i < length; i++) |
| | 2 | 54 | | { |
| | 2 | 55 | | Indices[i] = i + 1; |
| | 2 | 56 | | } |
| | | 57 | | |
| | 1 | 58 | | Count = 0; |
| | 1 | 59 | | CurrentFreeIndex = 0; |
| | 1 | 60 | | } |
| | | 61 | | |
| | | 62 | | /// <summary> |
| | | 63 | | /// Allocates an index from the free-list and stores an integer there, expanding the array if necessary. |
| | | 64 | | /// </summary> |
| | | 65 | | /// <param name="data">The integer value to store at the allocated index.</param> |
| | | 66 | | /// <param name="allocatedIndex">The index allocated from the free-list.</param> |
| | | 67 | | /// <param name="expandBy">How much the array should expand by when out of space.</param> |
| | | 68 | | /// <returns>True if the array expanded.</returns> |
| | | 69 | | public bool AddWithExpandCheck(int data, out int allocatedIndex, int expandBy) |
| | 1 | 70 | | { |
| | 1 | 71 | | int currentIndex = CurrentFreeIndex; |
| | 1 | 72 | | int oldLength = Indices.Length; |
| | 1 | 73 | | int expandedLength = oldLength + expandBy; |
| | | 74 | | |
| | 1 | 75 | | bool needsExpansion = currentIndex >= oldLength; |
| | 1 | 76 | | if (needsExpansion) |
| | 1 | 77 | | { |
| | 1 | 78 | | int[] newIndices = new int[expandedLength]; |
| | 1 | 79 | | Array.Copy(Indices, 0, newIndices, 0, oldLength); |
| | 1 | 80 | | Indices = newIndices; |
| | | 81 | | |
| | 22 | 82 | | for (int i = oldLength; i < expandedLength; i++) |
| | 10 | 83 | | { |
| | 10 | 84 | | Indices[i] = i + 1; |
| | 10 | 85 | | } |
| | 1 | 86 | | } |
| | | 87 | | |
| | 1 | 88 | | CurrentFreeIndex = Indices[currentIndex]; |
| | 1 | 89 | | Indices[currentIndex] = data; |
| | 1 | 90 | | ++Count; |
| | | 91 | | |
| | 1 | 92 | | allocatedIndex = currentIndex; |
| | | 93 | | |
| | 1 | 94 | | return needsExpansion; |
| | 1 | 95 | | } |
| | | 96 | | |
| | | 97 | | /// <summary> |
| | | 98 | | /// Allocates an index from the free-list and stores an integer there, expanding the array by twice the curr |
| | | 99 | | /// necessary. |
| | | 100 | | /// </summary> |
| | | 101 | | /// <param name="data">The integer value to store at the allocated index.</param> |
| | | 102 | | /// <param name="allocatedIndex">The index allocated from the free-list.</param> |
| | | 103 | | /// <returns>True if the array expanded.</returns> |
| | | 104 | | public bool AddWithExpandCheck(int data, out int allocatedIndex) |
| | 5 | 105 | | { |
| | 5 | 106 | | int currentIndex = CurrentFreeIndex; |
| | 5 | 107 | | int oldLength = Indices.Length; |
| | 5 | 108 | | int expandedLength = oldLength * 2; |
| | | 109 | | |
| | 5 | 110 | | bool needsExpansion = currentIndex >= oldLength; |
| | 5 | 111 | | if (needsExpansion) |
| | 2 | 112 | | { |
| | 2 | 113 | | int[] newIndices = new int[expandedLength]; |
| | 2 | 114 | | Array.Copy(Indices, 0, newIndices, 0, oldLength); |
| | 2 | 115 | | Indices = newIndices; |
| | | 116 | | |
| | 8 | 117 | | for (int i = oldLength; i < expandedLength; i++) |
| | 2 | 118 | | { |
| | 2 | 119 | | Indices[i] = i + 1; |
| | 2 | 120 | | } |
| | 2 | 121 | | } |
| | | 122 | | |
| | 5 | 123 | | CurrentFreeIndex = Indices[currentIndex]; |
| | 5 | 124 | | Indices[currentIndex] = data; |
| | 5 | 125 | | ++Count; |
| | | 126 | | |
| | 5 | 127 | | allocatedIndex = currentIndex; |
| | | 128 | | |
| | 5 | 129 | | return needsExpansion; |
| | 5 | 130 | | } |
| | | 131 | | |
| | | 132 | | /// <summary> |
| | | 133 | | /// Allocates an index from the free-list and stores an integer there, without checking for expansion. |
| | | 134 | | /// </summary> |
| | | 135 | | /// <param name="data">The integer value to store at the allocated index.</param> |
| | | 136 | | /// <returns>The index allocated from the free-list.</returns> |
| | | 137 | | public int AddUnchecked(int data) |
| | 10 | 138 | | { |
| | 10 | 139 | | int currentIndex = CurrentFreeIndex; |
| | | 140 | | |
| | 10 | 141 | | CurrentFreeIndex = Indices[currentIndex]; |
| | 9 | 142 | | Indices[currentIndex] = data; |
| | 9 | 143 | | ++Count; |
| | | 144 | | |
| | 9 | 145 | | return currentIndex; |
| | 9 | 146 | | } |
| | | 147 | | |
| | | 148 | | /// <summary> |
| | | 149 | | /// Deallocates the given index and adds it to the free-list. |
| | | 150 | | /// </summary> |
| | | 151 | | /// <param name="index">The index to add to the free-list.</param> |
| | | 152 | | public void RemoveAt(int index) |
| | 1 | 153 | | { |
| | 1 | 154 | | Indices[index] = CurrentFreeIndex; |
| | 1 | 155 | | CurrentFreeIndex = index; |
| | 1 | 156 | | --Count; |
| | 1 | 157 | | } |
| | | 158 | | |
| | | 159 | | /// <summary> |
| | | 160 | | /// Retrieves the value stored at the given index and deallocates the index, adding it to the free-list. |
| | | 161 | | /// </summary> |
| | | 162 | | /// <param name="index">The index to add to the free-list.</param> |
| | | 163 | | /// <returns>The value stored at the given index.</returns> |
| | | 164 | | public int GetAndRemoveAt(int index) |
| | 1 | 165 | | { |
| | 1 | 166 | | int data = Indices[index]; |
| | 1 | 167 | | Indices[index] = CurrentFreeIndex; |
| | 1 | 168 | | CurrentFreeIndex = index; |
| | 1 | 169 | | --Count; |
| | | 170 | | |
| | 1 | 171 | | return data; |
| | 1 | 172 | | } |
| | | 173 | | } |
| | | 174 | | } |