Unit Test Breaks with 4 elements in queue

[msusol]

I was using your repository for a Median Maintenance algorithm using two Priority Queues: One supports Max, one supports Min. Your library is perfect, it seemed, for this.

But here is what happens in a simple case:

hLow := NewPQueue(lane.MAXPQ)
hLow.Push("1",1)
hLow.Push("2",2)
hLow.Push("3",3)
hLow.Push("4",4) // Pop order at this point: 3/3 4/4 2/2 1/1
v,p := hLow.Pop() // should be 4/4 -> get 3/3
hLow.Push("4",4) // resulting Pop order: 4/4 4/4 2/2 1/1

and I can break your Unit Test just by adding a 4th element in the queue:

func TestMaxPQueuePush_protects_max_order(t *testing.T) {
pqueue := NewPQueue(MAXPQ)

pqueue.Push("1", 1)
pqueue.Push("2", 2)
pqueue.Push("3", 3)
pqueue.Push("4", 4)

// Heap queue index starts at one, zero index should always be nil
firstItem := pqueue.items[1]
firstItemValue, ok := firstItem.value.(string)
assert.True(t, ok)
assert.Equal(t, firstItemValue, "4")    // pqueue_test.go:38
assert.Equal(t, firstItem.priority, 4)   // pqueue_test.go:39

firstItem = pqueue.items[2]
firstItemValue, ok = firstItem.value.(string)
assert.True(t, ok)
assert.Equal(t, firstItemValue, "3")
assert.Equal(t, firstItem.priority, 3)

firstItem = pqueue.items[3]
firstItemValue, ok = firstItem.value.(string)
assert.True(t, ok)
assert.Equal(t, firstItemValue, "1")
assert.Equal(t, firstItem.priority, 1)

firstItem = pqueue.items[4]
firstItemValue, ok = firstItem.value.(string)
assert.True(t, ok)
assert.Equal(t, firstItemValue, "2")
assert.Equal(t, firstItem.priority, 2)

}

--- FAIL: TestMaxPQueuePush_protects_max_order (0.00 seconds)
Location: pqueue_test.go:38
Error: Not equal: "3" (expected)
!= "4" (actual)

    Location:       pqueue_test.go:39
Error:      Not equal: 3 (expected)
                != 4 (actual)

    Location:       pqueue_test.go:44
Error:      Not equal: "4" (expected)
                != "3" (actual)

    Location:       pqueue_test.go:45
Error:      Not equal: 4 (expected)
                != 3 (actual)

    Location:       pqueue_test.go:50
Error:      Not equal: "2" (expected)
                != "1" (actual)

    Location:       pqueue_test.go:51
Error:      Not equal: 2 (expected)
                != 1 (actual)

    Location:       pqueue_test.go:56
Error:      Not equal: "1" (expected)
                != "2" (actual)

    Location:       pqueue_test.go:57
Error:      Not equal: 1 (expected)
                != 2 (actual)

[oleiade]

Hi @msusol

I think your problem is related to #7
I've pushed a potential fix in master and improved concurrnet insertion testing. Could you test if it fixes your problem too?

Cheers

[oleiade]

No replies from issue creator. Closing.