| | | 1 | | namespace MoreStructures.Stacks; |
| | | 2 | | |
| | | 3 | | /// <summary> |
| | | 4 | | /// Exposes properties shared by data structures based on a backing array of items of type <typeparamref name="T"/>. |
| | | 5 | | /// </summary> |
| | | 6 | | /// <typeparam name="T">The type of items, the data structure is composed of.</typeparam> |
| | | 7 | | public abstract class ArrayBasedDataStructure<T> |
| | | 8 | | { |
| | | 9 | | /// <summary> |
| | | 10 | | /// The default initial size of the array backing the data structure. |
| | | 11 | | /// </summary> |
| | | 12 | | /// <remarks> |
| | | 13 | | /// In an array initialized with capacity x, up to x insertions can be done in constant time, with no need for |
| | | 14 | | /// array resizing. |
| | | 15 | | /// </remarks> |
| | | 16 | | public const int DefaultInitialCapacity = 16; |
| | | 17 | | |
| | | 18 | | /// <summary> |
| | | 19 | | /// The default value for <see cref="IncreasingFactor"/>. |
| | | 20 | | /// </summary> |
| | | 21 | | public const double DefaultIncreasingFactor = 2; |
| | | 22 | | |
| | | 23 | | /// <summary> |
| | | 24 | | /// The array of items, backing this data structure. |
| | | 25 | | /// </summary> |
| | 3453 | 26 | | protected T?[] Items { get; set; } |
| | | 27 | | |
| | | 28 | | /// <summary> |
| | | 29 | | /// The multiplicative factor used to resize the underlying array, every time it gets full. |
| | | 30 | | /// </summary> |
| | | 31 | | /// <remarks> |
| | | 32 | | /// Required to be bigger than 1.0. |
| | | 33 | | /// </remarks> |
| | 765 | 34 | | public double IncreasingFactor { get; } |
| | | 35 | | |
| | | 36 | | /// <summary> |
| | | 37 | | /// Initializes the data structure with an array list of initial capacity equals to the provided |
| | | 38 | | /// <paramref name="capacity"/>. |
| | | 39 | | /// </summary> |
| | | 40 | | /// <param name="capacity"> |
| | | 41 | | /// The initial capacity of the backing array. If not specified, <see cref="DefaultInitialCapacity"/> is used. |
| | | 42 | | /// </param> |
| | | 43 | | /// <param name="increasingFactor"> |
| | | 44 | | /// <inheritdoc cref="IncreasingFactor" path="/summary"/> |
| | | 45 | | /// </param> |
| | 23 | 46 | | protected ArrayBasedDataStructure( |
| | 23 | 47 | | int capacity = DefaultInitialCapacity, double increasingFactor = DefaultIncreasingFactor) |
| | 23 | 48 | | { |
| | 23 | 49 | | if (capacity <= 0) |
| | 2 | 50 | | throw new ArgumentOutOfRangeException(nameof(capacity), "Must be positive."); |
| | | 51 | | |
| | 21 | 52 | | if (increasingFactor <= 1) |
| | 3 | 53 | | throw new ArgumentOutOfRangeException(nameof(increasingFactor), "Must be strictly bigger than 1."); |
| | | 54 | | |
| | 18 | 55 | | Items = new T[capacity]; |
| | 18 | 56 | | IncreasingFactor = increasingFactor; |
| | 18 | 57 | | } |
| | | 58 | | |
| | | 59 | | /// <summary> |
| | | 60 | | /// Resizes the <see cref="Items"/> array, applying the provided <paramref name="factor"/> to its length. |
| | | 61 | | /// </summary> |
| | | 62 | | /// <param name="factor">The multiplicative factor to be applied to the length of the array.</param> |
| | | 63 | | protected virtual void ResizeItems(double factor) |
| | 24 | 64 | | { |
| | 24 | 65 | | var oldItems = Items; |
| | 24 | 66 | | var newSize = (int)Math.Ceiling(oldItems.Length * factor); |
| | 24 | 67 | | Array.Resize(ref oldItems, newSize); |
| | 24 | 68 | | Items = oldItems; |
| | 24 | 69 | | } |
| | | 70 | | } |