1 // Licensed to the .NET Foundation under one or more agreements.
2 // The .NET Foundation licenses this file to you under the MIT license.
3 // See the LICENSE file in the project root for more information.
4 
5 using System.Diagnostics;
6 
7 namespace System.Collections.Generic
8 {
9     /// <summary>Provides a double-ended queue data structure.</summary>
10     /// <typeparam name="T">Type of the data stored in the dequeue.</typeparam>
11     [DebuggerDisplay("Count = {_size}")]
12     internal sealed class Dequeue<T>
13     {
14         private T[] _array = Array.Empty<T>();
15         private int _head; // First valid element in the queue
16         private int _tail; // First open slot in the dequeue, unless the dequeue is full
17         private int _size; // Number of elements.
18 
19         public int Count => _size;
20 
21         public bool IsEmpty => _size == 0;
22 
EnqueueTail(T item)23         public void EnqueueTail(T item)
24         {
25             if (_size == _array.Length)
26             {
27                 Grow();
28             }
29 
30             _array[_tail] = item;
31             if (++_tail == _array.Length)
32             {
33                 _tail = 0;
34             }
35             _size++;
36         }
37 
38         //// Uncomment if/when enqueueing at the head is needed
39         //public void EnqueueHead(T item)
40         //{
41         //    if (_size == _array.Length)
42         //    {
43         //        Grow();
44         //    }
45         //
46         //    _head = (_head == 0 ? _array.Length : _head) - 1;
47         //    _array[_head] = item;
48         //    _size++;
49         //}
50 
DequeueHead()51         public T DequeueHead()
52         {
53             Debug.Assert(!IsEmpty); // caller's responsibility to make sure there are elements remaining
54 
55             T item = _array[_head];
56             _array[_head] = default;
57 
58             if (++_head == _array.Length)
59             {
60                 _head = 0;
61             }
62             _size--;
63 
64             return item;
65         }
66 
DequeueTail()67         public T DequeueTail()
68         {
69             Debug.Assert(!IsEmpty); // caller's responsibility to make sure there are elements remaining
70 
71             if (--_tail == -1)
72             {
73                 _tail = _array.Length - 1;
74             }
75 
76             T item = _array[_tail];
77             _array[_tail] = default;
78 
79             _size--;
80             return item;
81         }
82 
GetEnumerator()83         public IEnumerator<T> GetEnumerator() // meant for debug purposes only
84         {
85             int pos = _head;
86             int count = _size;
87             while (count-- > 0)
88             {
89                 yield return _array[pos];
90                 pos = (pos + 1) % _array.Length;
91             }
92         }
93 
Grow()94         private void Grow()
95         {
96             Debug.Assert(_size == _array.Length);
97             Debug.Assert(_head == _tail);
98 
99             const int MinimumGrow = 4;
100 
101             int capacity = (int)(_array.Length * 2L);
102             if (capacity < _array.Length + MinimumGrow)
103             {
104                 capacity = _array.Length + MinimumGrow;
105             }
106 
107             T[] newArray = new T[capacity];
108 
109             if (_head == 0)
110             {
111                 Array.Copy(_array, 0, newArray, 0, _size);
112             }
113             else
114             {
115                 Array.Copy(_array, _head, newArray, 0, _array.Length - _head);
116                 Array.Copy(_array, 0, newArray, _array.Length - _head, _tail);
117             }
118 
119             _array = newArray;
120             _head = 0;
121             _tail = _size;
122         }
123     }
124 }
125