DoublePriorityQueue panicked at 'called `Option::unwrap()` on a `None` value' about priority-queue HOT 7 CLOSED

Just verified, yes, it doesn't crash now and the algorithm results are fully correct. Thank you so much, our project will probably switch back to priority_queue!

from priority-queue.

To clarify: I was using the priority queue differently beforehand, inserting all graph nodes which means about 50 million for my largest dataset. However, this new method keeps the number of current nodes commonly below 100, which either way didn't solve the issue described.

from priority-queue.

Hi @kleinesfilmroellchen, sorry for the delay, but I have been very busy and I could not respond to this issue as promptly as I wanted.
Can you please provide me a sequence of operations that make the queue crash? It would be very useful to find the bug.
Thanks in advance

from priority-queue.

That's hard to do, as the bug usually occurs after several thousand operations on the queue. However, through some debugging I found the following:

• When an element is pushed into the queue, it appears to be added to the IndexMap correctly.
• However, when later the queue is heapified, this element is missing. When debug printing self.store.map in the closure after map.rs line 651, it crashes. Modifying the debug implementation to not unwrap, the output data structure has a single None at the newly added item. As far as I can tell (the internal data structures are hard to understand) this means that the element is in the heap, but not in the index map (or something? idk). The element is currently at the end after being inserted, so maybe that also plays into it. Honestly, the control flow is too hard for me to understand and I gave up.
• The bug appears both with heapify_min and heapify_max, though I have only deeply investigated heapify_max. It also happens when manually heapify()-ing the priority queue (I made the function public for testing) after performing push(). Though I don't know if that should just be no-oping or if the data structure can't handle multiple (manual) heapifications.

Hope this helps. I have to switch to standard library BinaryHeap because deadline, but thanks for investigating this.

from priority-queue.

Thank you for your report. Could you post at least the full log? It would be very helpful

from priority-queue.

I don't quite understand. What I posted above is the full log, everything else is stuff from my application. I just added a {:#?} to print the queue. To print all queue states is impossible; they easily fill up my terminal history by the time it crashes.

from priority-queue.

@kleinesfilmroellchen I think I fixed the bug and I could not reproduce it anymore. I would be very grateful if you could confirm it. Thank you in advance for your time

from priority-queue.