< Summary

Class:Towel.DataStructures.QueueLinked<T>
Assembly:Towel
File(s):File 1: /home/runner/work/Towel/Towel/Sources/Towel/DataStructures/Queue.cs
Covered lines:47
Uncovered lines:46
Coverable lines:93
Total lines:430
Line coverage:50.5% (47 of 93)
Covered branches:11
Total branches:32
Branch coverage:34.3% (11 of 32)

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
File 1: .ctor(...)100%1100%
File 1: .ctor()100%1100%
File 1: .ctor(...)0%40%
File 1: get_Newest()0%40%
File 1: get_Oldest()0%40%
File 1: get_Count()100%1100%
File 1: ToArray()0%40%
File 1: Clone()100%10%
File 1: Enqueue(...)100%2100%
File 1: Dequeue()100%4100%
File 1: Peek()0%40%
File 1: Clear()100%10%
File 1: StepperBreak(...)75%477.77%
File 1: System.Collections.IEnumerable.GetEnumerator()100%10%
File 1: GetEnumerator()100%2100%

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
 20006048    internal Node(T value, Node? next = null)
 20006049    {
 20006050      Value = value;
 20006051      Next = next;
 20006052    }
 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>
 1163  public QueueLinked()
 1164  {
 1165    _head = _tail = null;
 1166    _count = 0;
 1167  }
 68
 069  internal QueueLinked(QueueLinked<T> queue)
 070  {
 071    if (queue._head is not null)
 072    {
 073      _head = new Node(value: queue._head.Value);
 074      Node? a = queue._head.Next;
 075      Node? b = _head;
 076      while (a is not null)
 077      {
 078        b.Next = new Node(value: a.Value);
 079        b = b.Next;
 080        a = a.Next;
 081      }
 082      _tail = b;
 083      _count = queue._count;
 084    }
 085  }
 86
 87  #endregion
 88
 89  #region Properties
 90
 91  /// <inheritdoc/>
 92  public T Newest =>
 093    _count <= 0 ? throw new InvalidOperationException("attempting to get the newest item in an empty queue") :
 094    _tail is null ? throw new TowelBugException($"{nameof(Count)} is greater than 0 but {nameof(_tail)} is null") :
 095    _tail.Value;
 96
 97  /// <inheritdoc/>
 98  public T Oldest =>
 099    _count <= 0 ? throw new InvalidOperationException("attempting to get the oldet item in an empty queue") :
 0100    _head is null ? throw new TowelBugException($"{nameof(Count)} is greater than 0 but {nameof(_head)} is null") :
 0101    _head.Value;
 102
 103  /// <inheritdoc/>
 12104  public int Count => _count;
 105
 106  #endregion
 107
 108  #region Methods
 109
 110  /// <inheritdoc/>
 111  public T[] ToArray()
 0112  {
 0113    if (_count is 0)
 0114    {
 0115      return Array.Empty<T>();
 116    }
 0117    T[] array = new T[_count];
 0118    for (var (i, node) = (0, _head); node is not null; node = node.Next, i++)
 0119    {
 0120      array[i] = node.Value;
 0121    }
 0122    return array;
 0123  }
 124
 125  /// <inheritdoc/>
 0126  public QueueLinked<T> Clone() => new(this);
 127
 128  /// <inheritdoc/>
 129  public void Enqueue(T enqueue)
 200060130  {
 200060131    if (_tail is null)
 10132    {
 10133      _head = _tail = new Node(value: enqueue);
 10134    }
 135    else
 200050136    {
 200050137      _tail = _tail.Next = new Node(value: enqueue);
 200050138    }
 200060139    _count++;
 200060140  }
 141
 142  /// <inheritdoc/>
 143  public T Dequeue()
 200025144  {
 200025145    if (_head is null)
 2146    {
 2147      throw new InvalidOperationException("deque from an empty queue");
 148    }
 200023149    T value = _head.Value;
 200023150    if (_head == _tail)
 3151    {
 3152      _tail = null;
 3153    }
 200023154    _head = _head.Next;
 200023155    _count--;
 200023156    return value;
 200023157  }
 158
 159  /// <inheritdoc/>
 160  public T Peek() =>
 0161    _count <= 0 ? throw new InvalidOperationException("attempting to peek an empty queue") :
 0162    _head is null ? throw new TowelBugException($"{nameof(Count)} is greater than 0 but {nameof(_head)} is null") :
 0163    _head.Value;
 164
 165  /// <inheritdoc/>
 166  public void Clear()
 0167  {
 0168    _head = null;
 0169    _tail = null;
 0170    _count = 0;
 0171  }
 172
 173  /// <inheritdoc/>
 174  public StepStatus StepperBreak<TStep>(TStep step = default)
 175    where TStep : struct, IFunc<T, StepStatus>
 3176  {
 38177    for (Node? node = _head; node is not null; node = node.Next)
 16178    {
 16179      if (step.Invoke(node.Value) is Break)
 0180      {
 0181        return Break;
 182      }
 16183    }
 3184    return Continue;
 3185  }
 186
 0187  System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() => GetEnumerator();
 188
 189  /// <inheritdoc/>
 190  public System.Collections.Generic.IEnumerator<T> GetEnumerator()
 6191  {
 76192    for (Node? node = _head; node is not null; node = node.Next)
 32193    {
 32194      yield return node.Value;
 32195    }
 6196  }
 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>
 215  public QueueArray()
 216  {
 217    _array = new T[DefaultMinimumCapacity];
 218    _count = 0;
 219  }
 220
 221  /// <summary>Constructs a new queue.</summary>
 222  /// <param name="minimumCapacity">The initial and smallest array size allowed by this list.</param>
 223  public QueueArray(int minimumCapacity)
 224  {
 225    if (minimumCapacity <= 0)
 226    {
 227      throw new ArgumentOutOfRangeException(nameof(minimumCapacity), minimumCapacity, $"{nameof(minimumCapacity)} <= 0")
 228    }
 229    _array = new T[minimumCapacity];
 230    _count = 0;
 231    _minimumCapacity = minimumCapacity;
 232  }
 233
 234  internal QueueArray(QueueArray<T> queue)
 235  {
 236    _minimumCapacity = queue._minimumCapacity;
 237    _start = queue._start;
 238    _count = queue._count;
 239    _array = (T[])queue._array.Clone();
 240  }
 241
 242  #endregion
 243
 244  #region Properties
 245
 246  /// <inheritdoc/>
 247  public int Count => _count;
 248
 249  /// <summary>Gets the current capacity of the list.</summary>
 250  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  {
 259    get => _minimumCapacity;
 260    set
 261    {
 262      if (!value.HasValue)
 263      {
 264        _minimumCapacity = value;
 265      }
 266      else if (value < 1)
 267      {
 268        throw new ArgumentOutOfRangeException(nameof(value), value, $"{nameof(value)} < 1");
 269      }
 270      if (value > _array.Length)
 271      {
 272        T[] array = new T[_array.Length * 2];
 273        for (int i = 0, index = _start; i < _count; i++, index = ++index >= _array.Length ? 0 : index)
 274        {
 275          array[i] = _array[index];
 276        }
 277        _start = 0;
 278        _array = array;
 279      }
 280      _minimumCapacity = value;
 281    }
 282  }
 283
 284  /// <inheritdoc/>
 285  public T Newest =>
 286    _count <= 0 ? throw new InvalidOperationException("attempting to get the newest item in an empty queue") :
 287    _array[(_start + _count - 1) % _array.Length];
 288
 289  /// <inheritdoc/>
 290  public T Oldest =>
 291    _count <= 0 ? throw new InvalidOperationException("attempting to get the oldet item in an empty queue") :
 292    _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 =>
 304      index < 0 || index >= _count ? throw new ArgumentOutOfRangeException(nameof(index), index, $"!(0 <= {nameof(index)
 305      _array[(_start + index) % _array.Length];
 306    set
 307    {
 308      if (index < 0 || index >= _count) throw new ArgumentOutOfRangeException(nameof(index), index, $"!(0 <= {nameof(ind
 309      _array[(_start + index) % _array.Length] = value;
 310    }
 311  }
 312
 313  #endregion
 314
 315  #region Methods
 316
 317  /// <inheritdoc/>
 318  public T[] ToArray()
 319  {
 320    if (_count <= 0)
 321    {
 322      return Array.Empty<T>();
 323    }
 324    T[] array = new T[_count];
 325    for (int i = 0, index = _start; i < _count; i++, index = ++index >= _array.Length ? 0 : index)
 326    {
 327      array[i] = _array[index];
 328    }
 329    return array;
 330  }
 331
 332  /// <inheritdoc/>
 333  public QueueArray<T> Clone() => new(this);
 334
 335  /// <inheritdoc/>
 336  public void Enqueue(T addition)
 337  {
 338    if (_count + 1 >= _array.Length)
 339    {
 340      if (_array.Length > int.MaxValue / 2)
 341      {
 342        throw new InvalidOperationException("your queue is so large that it can no longer double itself (Int32.MaxValue 
 343      }
 344      T[] array = new T[_array.Length * 2];
 345      for (int i = 0, index = _start; i < _count; i++, index = ++index >= _array.Length ? 0 : index)
 346      {
 347        array[i] = _array[index];
 348      }
 349      _start = 0;
 350      _array = array;
 351    }
 352    int end = _start + _count;
 353    if (end >= _array.Length)
 354    {
 355      end %= _array.Length;
 356    }
 357    _array[end] = addition;
 358    _count++;
 359  }
 360
 361  /// <inheritdoc/>
 362  public T Dequeue()
 363  {
 364    if (_count is 0)
 365    {
 366      throw new InvalidOperationException("attempting to queue from an empty queue.");
 367    }
 368    if (_count < _array.Length / 4 && _array.Length > _minimumCapacity)
 369    {
 370      int length = Math.Max(_minimumCapacity ?? DefaultMinimumCapacity, _array.Length / 2);
 371      T[] array = new T[length];
 372      for (int i = 0, index = _start; i < _count; i++, index = ++index >= _array.Length ? 0 : index)
 373      {
 374        array[i] = _array[index];
 375      }
 376      _start = 0;
 377      _array = array;
 378    }
 379    T element = _array[_start++];
 380    if (_start >= _array.Length)
 381    {
 382      _start = 0;
 383    }
 384    _count--;
 385    return element;
 386  }
 387
 388  /// <inheritdoc/>
 389  public T Peek() =>
 390    _count <= 0 ? throw new InvalidOperationException("attempting to peek an empty queue") :
 391    _array[_start];
 392
 393  /// <inheritdoc/>
 394  public void Clear()
 395  {
 396    _count = 0;
 397    _start = 0;
 398  }
 399
 400  /// <inheritdoc/>
 401  public StepStatus StepperBreak<TStep>(TStep step = default)
 402    where TStep : struct, IFunc<T, StepStatus>
 403  {
 404    for (int i = 0, index = _start; i < _count; i++, index = ++index >= _array.Length ? 0 : index)
 405    {
 406      if (step.Invoke(_array[index]) is Break)
 407      {
 408        return Break;
 409      }
 410    }
 411    return Continue;
 412  }
 413
 414  System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() => GetEnumerator();
 415
 416  /// <inheritdoc/>
 417  public System.Collections.Generic.IEnumerator<T> GetEnumerator()
 418  {
 419    for (int i = 0, index = _start; i < _count; i++, index++)
 420    {
 421      if (index == _array.Length)
 422      {
 423        index = 0;
 424      }
 425      yield return _array[index];
 426    }
 427  }
 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_Newest()
get_Oldest()
get_Count()
ToArray()
Clone()
Enqueue(...)
Dequeue()
Peek()
Clear()
StepperBreak(...)
System.Collections.IEnumerable.GetEnumerator()
GetEnumerator()