Deque
Deque copied to clipboard
`GetEnumerator` is sometimes incorrect
Reproduce code:
[Test]
public void TestDequeMax() {
List<double> data = [
44.49936768747009, 44.279118538246706, 40.661350841514555, 42.4633762329716, 42.495742714005836,
47.03919736601132, 47.11837082730667, 57.25198844070602, 49.53911309399272, 52.54464904573255,
60.25212401912705, 53.61876998925497, 62.31002403596365, 63.158534790205174, 60.30414043552428,
61.78719065768428, 62.31178895690037, 56.96034247748777, 54.35790196041077, 51.48640367050706,
47.798653776379766, 54.664793836960264, 45.602999059138334, 51.107756817722816, 43.789460335621,
43.31361007592743, 45.01618591961488, 37.625738940194296, 44.23020047542071, 42.08008050410699,
36.97243196327399, 43.336071294688246, 43.80899082738759, 45.11498749354516, 46.80470833977162,
48.549116832982264, 46.8778087882746, 50.05034454386571, 53.25999558553829, 55.53014712489571,
51.26268409519357, 57.0075918440639, 58.95906608654632, 62.823734587928016, 54.96323923653695,
57.28665468446822, 62.66266591583821, 57.14007175976193, 53.21629512193634, 59.79140692295943,
52.18821059595763, 56.186171894054006, 54.376410556273086, 46.44933198774159, 50.660173432309506,
49.523869536647204, 44.16122552818299, 40.81530944518996, 45.8602057952838, 42.6022716023271,
42.13534214961749, 36.88642341587338, 38.39391195052792, 41.58638031928658, 39.280949353423395,
41.048899559810685, 45.19268369884699, 44.604463363484456, 46.48602832576217, 55.19848309750659,
52.12151860635208, 53.55050993756979, 59.21322376340062, 58.5441428658852, 53.95693933136484,
58.19544369732815, 56.29029348300317, 55.927161215367946, 61.137433133411584, 62.54940008775334,
56.91817187588727, 53.52219666017001, 58.617188167542096, 56.447937701489245, 49.02917463886819,
46.49215648745752, 50.81039857960671, 45.08407893511854, 47.945081093782576, 46.59670953849308,
39.754349358150044, 37.86085009876948, 42.9429169053711, 37.00801109967222, 38.080775647888,
38.20196484145875, 42.417217701672314, 41.993034744690064, 49.78659268801961, 52.52399477611651,
53.71822024557462, 53.226471785844836, 49.75548254036254, 51.28589204070622, 55.17316039653904,
60.2770827480571, 62.48564673691092, 54.802179514484884, 54.36657438556807, 56.575284101002964,
58.82408788562007, 54.489540218743386, 55.7570029455628, 58.37924980655473, 48.947531870341,
49.348680466142376, 45.85404458564423, 45.881938398839296, 42.49063009675827, 48.52440759479678,
41.74718964268368, 37.528557012096755, 40.29062410035228, 40.18183720678498, 42.98006582130367,
39.73125981529792, 44.78583741662692, 45.91525638092429, 44.54788838242877
];
Queue<double> queue = new Queue<double>();
Deque<double> deque = new Deque<double>();
int windowSize = 68;
for (var index = 0; index < data.Count; index++) {
double newData = data[index];
queue.Enqueue(newData);
if (queue.Count > windowSize)
queue.Dequeue();
deque.AddBack(newData);
if (deque.Count > windowSize)
deque.RemoveFront();
Assert.AreEqual(
queue.Max(), deque.Max(), 1e-10,
$"Mismatch at index {index}"
);
}
}
Result:
Mismatch at index 128
Expected: 62.549400087753341d +/- 1E-10.0d
But was: 63.158534790205174d
Off by: -0.60913470245183277d
The problem is related to GetEnumerator. A smaller reproduction
[Test]
public void SimpleTestDeque() {
List<int> data = [];
for (int i = 0; i < 129; i++)
{
data.Add(i);
}
Deque<int> deque = new Deque<int>();
int windowSize = 68;
for (var index = 0; index < data.Count; index++) {
int element = data[index];
deque.AddBack(element);
if (deque.Count > windowSize)
deque.RemoveFront();
}
Assert.AreEqual(deque.Count, windowSize); // this passed
var list = EnumeratorToList(deque.GetEnumerator());
Assert.AreEqual(list.Count, windowSize); // this failed
}
public static List<T> EnumeratorToList<T>(IEnumerator<T> enumerator)
{
var list = new List<T>();
while (enumerator.MoveNext())
{
list.Add(enumerator.Current);
}
return list;
}