Deque icon indicating copy to clipboard operation
Deque copied to clipboard

`GetEnumerator` is sometimes incorrect

Open qouteall opened this issue 1 year ago • 1 comments

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

qouteall avatar Sep 07 '24 11:09 qouteall

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;
    }

qouteall avatar Nov 10 '24 09:11 qouteall