Dequeue of FastPriorityQueue returned in wrong order

[CharlesPublic]

Hello BlueRaja,

i think i just found a bug in the FastPriorityQueue.

I enqueue 1 M entries, then dequeue 1 M entries, this works fine for the SimplePriorityQueue. But when i use the FastPriorityQueue then some of the dequeued Values come back in the wrong order.

Here is my test:

public class Bug_FastPriorityQueue
{

    public void Test()
    {
        // generate 1 M random ints
        var randomInts = GenerateRandomInts(
                1_000_000, int.MinValue + 5, int.MaxValue - 5);

        var len = randomInts.Length;
        var intNodes = randomInts.Select(x => new IntNode(x)).ToList();

        var fastQ = new FastPriorityQueue<IntNode>(len);

        // Enqueue all
        foreach (var item in intNodes)
            fastQ.Enqueue(item, item.Val);

        var dequeuedList = new List<IntNode>(len);

        // Dequeue all
        while (fastQ.Count > 0)
            dequeuedList.Add(fastQ.Dequeue());

        // lets get the inner int Value only
        var intsOnly = dequeuedList.Select(x => x.Val).ToList();

        // sort the dequeuedList, let's see if there's any errors
        var intsOrdered = intsOnly.OrderBy(x => x).ToList();

        // test if SequenceEqual
        for (int i = 0; i < intsOnly.Count; i++)
        {
            var item1 = intsOnly[i];
            var item2 = intsOrdered[i];

            if (item1 != item2)
            {
                // lets look at the incorrect ranges...
                var list1 = intsOrdered.Skip(i - 2).Take(5).ToList();
                var list2 = intsOnly.Skip(i - 2).Take(5).ToList();

                Debug.WriteLine($"wrong order at index {i}");
                Debug.WriteLine($"{string.Join(", ", list1)} expected");
                Debug.WriteLine($"{string.Join(", ", list2)} actual");

                throw new Exception("found wrong values");
            }
        }

        // the order of the dequeued values is not ok in my tests
        var orderOk = intsOnly.SequenceEqual(intsOrdered);

        if (!orderOk)
            throw new Exception("order is wrong");
    }

    public static int[] GenerateRandomInts
      (int numInts, int min, int maxIncl)
    {

        var ret = new int[numInts];
        var rnd = new Random();

        for (int i = 0; i < numInts; i++)
        {
            ret[i] = (rnd.Next(min, maxIncl + 1));
        }

        return ret;
    }

}

public class IntNode : FastPriorityQueueNode
{
    public int Val { get; set; }

    public IntNode(int val)
    {
        this.Val = val;
    }

    public override string ToString()
    {
        return Val.ToString();
    }

}

EDIT:

The Bug doesn't occur in SimplePriorityQueue The Bug doesn't occur in GenericPriorityQueue

The Bug occurs in StablePriorityQueue The Bug occurs in FastPriorityQueue

---

I've tested this both in debug and release mode.

I found many wrong results like:

wrong order at index 110 -2147090649, -2147089868, -2147082607, -2147082606, -2147068169 expected -2147090649, -2147089868, -2147082606, -2147082607, -2147068169 actual

Cheers

[BlueRaja]

That's because those numbers are not exactly representable as floats, which is what FastPriorityQueue uses for priorities. Try the GenericPriorityQueue instead.

[Sp3ci3s8472]

That's because those numbers are not exactly representable as floats, which is what FastPriorityQueue uses for priorities. Try the GenericPriorityQueue instead.

This seems to be similar to the problem I'm experiencing and while using floats.