search

BlueRaja / High-Speed-Priority-Queue-for-C-Sharp

A C# priority queue optimized for pathfinding applications
MIT License
1.15k stars 169 forks source link

Reused nodes QueueIndex breaks debug #42

Closed phildo77 closed 5 years ago

phildo77 commented 6 years ago

FYI - Reusing nodes (from one queue to another) breaks the debug check for QueueIndex in Contains(node).

Maybe change the QueueIndex back to zero on a Dequeue or possibly change to 0 in debug check before Contains?

EDIT: Sorry - this is for FastPriorityQueue

BlueRaja commented 5 years ago

[EDIT] Ah, I was wrong! queue.Contains(node) works correctly on an empty queue.

I tried implementing your suggestion, but it led to an unacceptable speed regression (3% if I set the QueueIndex to 0, 20% (!!) if I check bounds in Contains()).

In the end, I've decided to add a ResetNode() method. Nodes that are added to a queue belong to that queue forever, until oldQueue.ResetNode(node) is called. Attempting to call Enqueue or Contains on the wrong queue for a node will lead to an exception in Debug mode, undefined behavior in Release. None of this applies to SimplePriorityQueue, which still behaves as you'd expect.

BlueRaja commented 5 years ago

Added in v4.2.0