Skip to content

Bug in DoublePriorityQueue iter_mut len() #81

@Takashiidobe

Description

@Takashiidobe

DoublePriorityQueue's mutable iterators do not keep track of length properly which is required for an ExactSizedIterator.

Take this example: after the first next, you would assume that there should be two items left in the iterator:

use priority_queue::DoublePriorityQueue;

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

    let mut iter = pq.iter_mut();
    assert_eq!(iter.next(), Some((&mut "apples", &mut 1)));

    assert_eq!(iter.len(), 2);
}

But the second test fails:

running 1 test
test iter_mut_len_does_not_track_progress ... FAILED

failures:

---- iter_mut_len_does_not_track_progress stdout ----

thread 'iter_mut_len_does_not_track_progress' panicked at tests/dpq_iter_mut_len.rs:13:5:
assertion `left == right` failed
  left: 3
 right: 2
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Also, size_hint is incorrectly set to (0, None), even though it should be (3, Some(3)) since the exact size of the iterator is known at creation time, although that seems to be for regular queues too.

use priority_queue::DoublePriorityQueue;

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

    let iter = pq.iter();
    assert_eq!(iter.size_hint(), (3, Some(3)));
    let iter_mut = pq.iter_mut();
    assert_eq!(iter_mut.size_hint(), (3, Some(3)));
}
running 1 test
test iter_mut_size_hint_is_incorrect ... FAILED

failures:

---- iter_mut_size_hint_is_incorrect stdout ----

thread 'iter_mut_size_hint_is_incorrect' panicked at tests/dpq_iter_mut_len.rs:11:5:
assertion `left == right` failed
  left: (0, None)
 right: (3, Some(3))
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Metadata

Metadata

Assignees

Labels

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions