-
Notifications
You must be signed in to change notification settings - Fork 1.9k
/
FixedSizeQueue.cs
151 lines (131 loc) · 4.02 KB
/
FixedSizeQueue.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.
using Microsoft.ML.Runtime;
namespace Microsoft.ML.Internal.Utilities
{
using Conditional = System.Diagnostics.ConditionalAttribute;
/// <summary>
/// A fixed-length circular array. Items are added at the end. If the array is full, adding
/// an item will result in discarding the least recently added item.
/// </summary>
[BestFriend]
internal sealed class FixedSizeQueue<T>
{
private readonly T[] _array;
private int _startIndex;
private int _count;
public FixedSizeQueue(int capacity)
{
Contracts.Assert(capacity > 0, "Array capacity should be greater than zero");
_array = new T[capacity];
AssertValid();
}
[Conditional("DEBUG")]
private void AssertValid()
{
Contracts.Assert(Utils.Size(_array) >= 0);
Contracts.Assert(0 <= _startIndex && _startIndex < _array.Length);
Contracts.Assert(0 <= _count && _count <= _array.Length);
}
public int Count
{
get
{
AssertValid();
return _count;
}
}
public int Capacity
{
get
{
AssertValid();
return _array.Length;
}
}
public bool IsFull
{
get
{
AssertValid();
return _count == _array.Length;
}
}
public T this[int index]
{
get
{
AssertValid();
Contracts.Assert(index >= 0 && index < _count);
return _array[(_startIndex + index) % _array.Length];
}
}
public void AddLast(T item)
{
AssertValid();
if (_count == _array.Length)
{
// Replace least recently added item (found at _startIndex)
_array[_startIndex] = item;
_startIndex = (_startIndex + 1) % _array.Length;
}
else
{
_array[(_startIndex + _count) % _array.Length] = item;
_count++;
}
AssertValid();
}
public T PeekFirst()
{
AssertValid();
Contracts.Assert(_count != 0, "Array is empty");
return _array[_startIndex];
}
public T PeekLast()
{
AssertValid();
Contracts.Assert(_count != 0, "Array is empty");
return _array[(_startIndex + _count - 1) % _array.Length];
}
public T RemoveFirst()
{
AssertValid();
Contracts.Assert(_count != 0, "Array is empty");
T item = _array[_startIndex];
_array[_startIndex] = default(T);
_startIndex = (_startIndex + 1) % _array.Length;
_count--;
AssertValid();
return item;
}
public T RemoveLast()
{
AssertValid();
Contracts.Assert(_count != 0, "Array is empty");
int lastIndex = (_startIndex + _count - 1) % _array.Length;
T item = _array[lastIndex];
_array[lastIndex] = default(T);
_count--;
AssertValid();
return item;
}
public void Clear()
{
AssertValid();
for (int i = 0; i < _count; i++)
_array[(_startIndex + i) % _array.Length] = default(T);
_startIndex = 0;
_count = 0;
AssertValid();
}
public FixedSizeQueue<T> Clone()
{
var q = new FixedSizeQueue<T>(Capacity);
for (int index = 0; index < Count; index++)
q.AddLast(this[index]);
return q;
}
}
}