priority-queue icon indicating copy to clipboard operation
priority-queue copied to clipboard

`remove_until` like API, removes all items until a predicate matches

Open Dav1dde opened this issue 1 year ago • 1 comments

The idea is similar to #47 but instead of being able to skip items, it would remove all items until a predicate matches (excluding that element).

For example in Rust pseudo code:

let mut queue = PriorityQueue::new();
queue.push(1, "a");
queue.push(2, "b");
queue.push(3, "c");

let items = queue.remove_until(|k| k < 3).collect::<Vec<_>>();
assert_eq!(items, vec![(1, "a"), (2, "b")]);

assert_eq!(queue.peek(), Some((3, "c")));

Currently this requires to either peek and pop:

while let Some((k, _)) = queue.peek() {
    if k < 3 { 
        break 
    }

    let Some((k, v)) = queue.pop().unwrap();
} 

Or constant pops() with a push of the removed item which does not match the predicate.

Dav1dde avatar Jul 23 '24 08:07 Dav1dde

I have a similar request: Please add a new method pop_if() that removes and returns the "top" element from the queue as a Some((item, priority)), but only if the "top" element matches the given predicate. Otherwise, a None should be returned.

The rationale is that currently we need to write a code like this:

while queue.peek().is_some_and(|(item, priority)| some_condition(...)) {
    (item, priority) = queue.pop().unwrap();
    /* ... */
}

But the unwrap() is kind of ugly, because it shouldn't actually be needed. That is because, at this point, we already know for sure there is a next element. But, even more important, the peek() to investigate the "top" element plus the additional pop() to actually remove it, requires two lookups – where this operation should be possible with just a single one!

Hence, this should be simplified to:

while let Some((item, priority)) = queue.pop_if(|(item, priority)| some_condition(...)) {
    /* ... */
}

Or is there a better way already ???

lordmulder avatar Feb 11 '25 23:02 lordmulder