Skip to content

Bug in DoublePriorityQueue iter_mut #80

@Takashiidobe

Description

@Takashiidobe

It looks like DoublePriorityQueue panics when calling next_back immediately on an iter_mut call to a DPQ.

use priority_queue::DoublePriorityQueue;

#[test]
fn iter_mut_next_back_panics_on_first_call() {
    let mut pq = DoublePriorityQueue::new();
    pq.push("apples", 1);
    pq.push("bananas", 2);

    let mut iter = pq.iter_mut();
    iter.next_back();
}

Running that test with RUST_BACKTRACE=1 cargo test --test dpq_iter_mut_next_back -- --no-capture:

thread 'iter_mut_next_back_panics_on_first_call' panicked at /home/takashi/current/priority-queue/src/double_priority_queue/iterators.rs:198:9:
attempt to subtract with overflow

That line is here.

Creation of iter_mut is here?

My guess is that pos is supposed to be at the end of the DPQ, but new creates it at the start, and then the next_back code runs which immediately subtracts with underflow. I think just having a front and back position and using those to keep state should suffice?

Metadata

Metadata

Assignees

Labels

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions