< Summary

Class:Towel.DataStructures.QueueArray<T>
Assembly:Towel
File(s):File 1: /home/runner/work/Towel/Towel/Sources/Towel/DataStructures/Queue.cs
Covered lines:59
Uncovered lines:78
Coverable lines:137
Total lines:430
Line coverage:43% (59 of 137)
Covered branches:31
Total branches:66
Branch coverage:46.9% (31 of 66)

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
File 1: .ctor()100%1100%
File 1: .ctor(...)0%20%
File 1: .ctor(...)100%10%
File 1: get_Count()100%1100%
File 1: get_CurrentCapacity()100%10%
File 1: get_MinimumCapacity()100%10%
File 1: set_MinimumCapacity(...)0%100%
File 1: get_Newest()100%2100%
File 1: get_Oldest()100%2100%
File 1: get_Item(...)100%4100%
File 1: set_Item(...)0%40%
File 1: ToArray()0%60%
File 1: Clone()100%10%
File 1: Enqueue(...)80%1090.9%
File 1: Dequeue()42.85%1443.47%
File 1: Peek()0%20%
File 1: Clear()100%10%
File 1: StepperBreak(...)83.33%677.77%
File 1: System.Collections.IEnumerable.GetEnumerator()100%10%
File 1: GetEnumerator()100%4100%

File(s)

/home/runner/work/Towel/Towel/Sources/Towel/DataStructures/Queue.cs

#LineLine coverage
 1namespace Towel.DataStructures;
 2
 3/// <summary>Implements First-In-First-Out queue data structure.</summary>
 4/// <typeparam name="T">The generic type within the structure.</typeparam>
 5public interface IQueue<T> : IDataStructure<T>,
 6  DataStructure.ICountable,
 7  DataStructure.IClearable
 8{
 9  #region Properties
 10
 11  /// <summary>The current newest element in the queue.</summary>
 12  T Newest { get; }
 13  /// <summary>The current oldest element in the queue.</summary>
 14  T Oldest { get; }
 15
 16  #endregion
 17
 18  #region Methods
 19
 20  /// <summary>Adds an item to the back of the queue.</summary>
 21  /// <param name="enqueue">The item to add to the queue.</param>
 22  void Enqueue(T enqueue);
 23  /// <summary>Gets the next item in the queue without removing it.</summary>
 24  /// <returns>The next item in the queue.</returns>
 25  T Peek();
 26  /// <summary>Removes the oldest item in the queue.</summary>
 27  /// <returns>The next item in the queue.</returns>
 28  T Dequeue();
 29
 30  #endregion
 31}
 32
 33/// <summary>Implements First-In-First-Out queue data structure using a linked list.</summary>
 34/// <typeparam name="T">The generic type within the structure.</typeparam>
 35public class QueueLinked<T> : IQueue<T>, ICloneable<QueueLinked<T>>
 36{
 37  internal Node? _head;
 38  internal Node? _tail;
 39  internal int _count;
 40
 41  #region Nested Types
 42
 43  internal class Node
 44  {
 45    internal T Value;
 46    internal Node? Next;
 47
 48    internal Node(T value, Node? next = null)
 49    {
 50      Value = value;
 51      Next = next;
 52    }
 53  }
 54
 55  #endregion
 56
 57  #region Constructors
 58
 59  /// <summary>
 60  /// Creates an instance of a queue.<br/>
 61  /// Runtime: O(1)
 62  /// </summary>
 63  public QueueLinked()
 64  {
 65    _head = _tail = null;
 66    _count = 0;
 67  }
 68
 69  internal QueueLinked(QueueLinked<T> queue)
 70  {
 71    if (queue._head is not null)
 72    {
 73      _head = new Node(value: queue._head.Value);
 74      Node? a = queue._head.Next;
 75      Node? b = _head;
 76      while (a is not null)
 77      {
 78        b.Next = new Node(value: a.Value);
 79        b = b.Next;
 80        a = a.Next;
 81      }
 82      _tail = b;
 83      _count = queue._count;
 84    }
 85  }
 86
 87  #endregion
 88
 89  #region Properties
 90
 91  /// <inheritdoc/>
 92  public T Newest =>
 93    _count <= 0 ? throw new InvalidOperationException("attempting to get the newest item in an empty queue") :
 94    _tail is null ? throw new TowelBugException($"{nameof(Count)} is greater than 0 but {nameof(_tail)} is null") :
 95    _tail.Value;
 96
 97  /// <inheritdoc/>
 98  public T Oldest =>
 99    _count <= 0 ? throw new InvalidOperationException("attempting to get the oldet item in an empty queue") :
 100    _head is null ? throw new TowelBugException($"{nameof(Count)} is greater than 0 but {nameof(_head)} is null") :
 101    _head.Value;
 102
 103  /// <inheritdoc/>
 104  public int Count => _count;
 105
 106  #endregion
 107
 108  #region Methods
 109
 110  /// <inheritdoc/>
 111  public T[] ToArray()
 112  {
 113    if (_count is 0)
 114    {
 115      return Array.Empty<T>();
 116    }
 117    T[] array = new T[_count];
 118    for (var (i, node) = (0, _head); node is not null; node = node.Next, i++)
 119    {
 120      array[i] = node.Value;
 121    }
 122    return array;
 123  }
 124
 125  /// <inheritdoc/>
 126  public QueueLinked<T> Clone() => new(this);
 127
 128  /// <inheritdoc/>
 129  public void Enqueue(T enqueue)
 130  {
 131    if (_tail is null)
 132    {
 133      _head = _tail = new Node(value: enqueue);
 134    }
 135    else
 136    {
 137      _tail = _tail.Next = new Node(value: enqueue);
 138    }
 139    _count++;
 140  }
 141
 142  /// <inheritdoc/>
 143  public T Dequeue()
 144  {
 145    if (_head is null)
 146    {
 147      throw new InvalidOperationException("deque from an empty queue");
 148    }
 149    T value = _head.Value;
 150    if (_head == _tail)
 151    {
 152      _tail = null;
 153    }
 154    _head = _head.Next;
 155    _count--;
 156    return value;
 157  }
 158
 159  /// <inheritdoc/>
 160  public T Peek() =>
 161    _count <= 0 ? throw new InvalidOperationException("attempting to peek an empty queue") :
 162    _head is null ? throw new TowelBugException($"{nameof(Count)} is greater than 0 but {nameof(_head)} is null") :
 163    _head.Value;
 164
 165  /// <inheritdoc/>
 166  public void Clear()
 167  {
 168    _head = null;
 169    _tail = null;
 170    _count = 0;
 171  }
 172
 173  /// <inheritdoc/>
 174  public StepStatus StepperBreak<TStep>(TStep step = default)
 175    where TStep : struct, IFunc<T, StepStatus>
 176  {
 177    for (Node? node = _head; node is not null; node = node.Next)
 178    {
 179      if (step.Invoke(node.Value) is Break)
 180      {
 181        return Break;
 182      }
 183    }
 184    return Continue;
 185  }
 186
 187  System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() => GetEnumerator();
 188
 189  /// <inheritdoc/>
 190  public System.Collections.Generic.IEnumerator<T> GetEnumerator()
 191  {
 192    for (Node? node = _head; node is not null; node = node.Next)
 193    {
 194      yield return node.Value;
 195    }
 196  }
 197
 198  #endregion
 199}
 200
 201/// <summary>Implements First-In-First-Out queue data structure using an array.</summary>
 202/// <typeparam name="T">The generic type within the structure.</typeparam>
 203public class QueueArray<T> : IQueue<T>, ICloneable<QueueArray<T>>
 204{
 205  internal const int DefaultMinimumCapacity = 1;
 206
 207  internal T[] _array;
 208  internal int _start;
 209  internal int _count;
 210  internal int? _minimumCapacity;
 211
 212  #region Constructors
 213
 214  /// <summary>Constructs a new queue.</summary>
 90215  public QueueArray()
 90216  {
 90217    _array = new T[DefaultMinimumCapacity];
 90218    _count = 0;
 90219  }
 220
 221  /// <summary>Constructs a new queue.</summary>
 222  /// <param name="minimumCapacity">The initial and smallest array size allowed by this list.</param>
 0223  public QueueArray(int minimumCapacity)
 0224  {
 0225    if (minimumCapacity <= 0)
 0226    {
 0227      throw new ArgumentOutOfRangeException(nameof(minimumCapacity), minimumCapacity, $"{nameof(minimumCapacity)} <= 0")
 228    }
 0229    _array = new T[minimumCapacity];
 0230    _count = 0;
 0231    _minimumCapacity = minimumCapacity;
 0232  }
 233
 0234  internal QueueArray(QueueArray<T> queue)
 0235  {
 0236    _minimumCapacity = queue._minimumCapacity;
 0237    _start = queue._start;
 0238    _count = queue._count;
 0239    _array = (T[])queue._array.Clone();
 0240  }
 241
 242  #endregion
 243
 244  #region Properties
 245
 246  /// <inheritdoc/>
 67247  public int Count => _count;
 248
 249  /// <summary>Gets the current capacity of the list.</summary>
 0250  public int CurrentCapacity => _array.Length;
 251
 252  /// <summary>
 253  /// Allows you to adjust the minimum capacity of this list.<br/>
 254  /// Runtime (Get): O(1)<br/>
 255  /// Runtime (Set): O(n), Î©(1)
 256  /// </summary>
 257  public int? MinimumCapacity
 258  {
 0259    get => _minimumCapacity;
 260    set
 0261    {
 0262      if (!value.HasValue)
 0263      {
 0264        _minimumCapacity = value;
 0265      }
 0266      else if (value < 1)
 0267      {
 0268        throw new ArgumentOutOfRangeException(nameof(value), value, $"{nameof(value)} < 1");
 269      }
 0270      if (value > _array.Length)
 0271      {
 0272        T[] array = new T[_array.Length * 2];
 0273        for (int i = 0, index = _start; i < _count; i++, index = ++index >= _array.Length ? 0 : index)
 0274        {
 0275          array[i] = _array[index];
 0276        }
 0277        _start = 0;
 0278        _array = array;
 0279      }
 0280      _minimumCapacity = value;
 0281    }
 282  }
 283
 284  /// <inheritdoc/>
 285  public T Newest =>
 200286    _count <= 0 ? throw new InvalidOperationException("attempting to get the newest item in an empty queue") :
 200287    _array[(_start + _count - 1) % _array.Length];
 288
 289  /// <inheritdoc/>
 290  public T Oldest =>
 200291    _count <= 0 ? throw new InvalidOperationException("attempting to get the oldet item in an empty queue") :
 200292    _array[_start];
 293
 294  /// <summary>
 295  /// Gets or sets the <typeparamref name="T"/> at an index in the queue.<br/>
 296  /// Runtime: O(1)
 297  /// </summary>
 298  /// <param name="index">The index of the <typeparamref name="T"/> to get or set.</param>
 299  /// <returns>The element at the provided index.</returns>
 300  /// <exception cref="ArgumentOutOfRangeException">Thrown when: index &lt;= 0 || index &gt; _count</exception>
 301  public T this[int index]
 302  {
 303    get =>
 5451304      index < 0 || index >= _count ? throw new ArgumentOutOfRangeException(nameof(index), index, $"!(0 <= {nameof(index)
 5451305      _array[(_start + index) % _array.Length];
 306    set
 0307    {
 0308      if (index < 0 || index >= _count) throw new ArgumentOutOfRangeException(nameof(index), index, $"!(0 <= {nameof(ind
 0309      _array[(_start + index) % _array.Length] = value;
 0310    }
 311  }
 312
 313  #endregion
 314
 315  #region Methods
 316
 317  /// <inheritdoc/>
 318  public T[] ToArray()
 0319  {
 0320    if (_count <= 0)
 0321    {
 0322      return Array.Empty<T>();
 323    }
 0324    T[] array = new T[_count];
 0325    for (int i = 0, index = _start; i < _count; i++, index = ++index >= _array.Length ? 0 : index)
 0326    {
 0327      array[i] = _array[index];
 0328    }
 0329    return array;
 0330  }
 331
 332  /// <inheritdoc/>
 0333  public QueueArray<T> Clone() => new(this);
 334
 335  /// <inheritdoc/>
 336  public void Enqueue(T addition)
 200406337  {
 200406338    if (_count + 1 >= _array.Length)
 120339    {
 120340      if (_array.Length > int.MaxValue / 2)
 0341      {
 0342        throw new InvalidOperationException("your queue is so large that it can no longer double itself (Int32.MaxValue 
 343      }
 120344      T[] array = new T[_array.Length * 2];
 787965345      for (int i = 0, index = _start; i < _count; i++, index = ++index >= _array.Length ? 0 : index)
 262535346      {
 262535347        array[i] = _array[index];
 262535348      }
 120349      _start = 0;
 120350      _array = array;
 120351    }
 200406352    int end = _start + _count;
 200406353    if (end >= _array.Length)
 8354    {
 8355      end %= _array.Length;
 8356    }
 200406357    _array[end] = addition;
 200406358    _count++;
 200406359  }
 360
 361  /// <inheritdoc/>
 362  public T Dequeue()
 200374363  {
 200374364    if (_count is 0)
 2365    {
 2366      throw new InvalidOperationException("attempting to queue from an empty queue.");
 367    }
 200372368    if (_count < _array.Length / 4 && _array.Length > _minimumCapacity)
 0369    {
 0370      int length = Math.Max(_minimumCapacity ?? DefaultMinimumCapacity, _array.Length / 2);
 0371      T[] array = new T[length];
 0372      for (int i = 0, index = _start; i < _count; i++, index = ++index >= _array.Length ? 0 : index)
 0373      {
 0374        array[i] = _array[index];
 0375      }
 0376      _start = 0;
 0377      _array = array;
 0378    }
 200372379    T element = _array[_start++];
 200372380    if (_start >= _array.Length)
 0381    {
 0382      _start = 0;
 0383    }
 200372384    _count--;
 200372385    return element;
 200372386  }
 387
 388  /// <inheritdoc/>
 389  public T Peek() =>
 0390    _count <= 0 ? throw new InvalidOperationException("attempting to peek an empty queue") :
 0391    _array[_start];
 392
 393  /// <inheritdoc/>
 394  public void Clear()
 0395  {
 0396    _count = 0;
 0397    _start = 0;
 0398  }
 399
 400  /// <inheritdoc/>
 401  public StepStatus StepperBreak<TStep>(TStep step = default)
 402    where TStep : struct, IFunc<T, StepStatus>
 3403  {
 57404    for (int i = 0, index = _start; i < _count; i++, index = ++index >= _array.Length ? 0 : index)
 16405    {
 16406      if (step.Invoke(_array[index]) is Break)
 0407      {
 0408        return Break;
 409      }
 16410    }
 3411    return Continue;
 3412  }
 413
 0414  System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() => GetEnumerator();
 415
 416  /// <inheritdoc/>
 417  public System.Collections.Generic.IEnumerator<T> GetEnumerator()
 6418  {
 114419    for (int i = 0, index = _start; i < _count; i++, index++)
 32420    {
 32421      if (index == _array.Length)
 2422      {
 2423        index = 0;
 2424      }
 32425      yield return _array[index];
 32426    }
 6427  }
 428
 429  #endregion
 430}
Generated by: ReportGenerator 4.8.11.0
08/14/2022 - 14:40:44
GitHub | www.palmmedia.de

Methods/Properties

.ctor()
.ctor(...)
.ctor(...)
get_Count()
get_CurrentCapacity()
get_MinimumCapacity()
set_MinimumCapacity(...)
get_Newest()
get_Oldest()
get_Item(...)
set_Item(...)
ToArray()
Clone()
Enqueue(...)
Dequeue()
Peek()
Clear()
StepperBreak(...)
System.Collections.IEnumerable.GetEnumerator()
GetEnumerator()