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