iter_over(priority) and iter_under(priority)

[simbleau]

Similar to #35 , the reasoning is the same. Return an iter with elements above or under a priority.

Consider the following, which is illegal by rust's standards:

while let Some((obj, priority)) = queue.peek_max() {
    if priority > 5 { 
        queue.remove(obj)
   } else {
       break; // All elements in future iterations this will be < 5
   }
}

This is because you cannot mutably modify an object when you have immutable borrows (obj, in this case)

Thus, the equivalent workaround in the same time complexity would be:

let keys = Vec::new();
while let Some((obj, priority)) = queue.peek_max() {
    if priority > 5 {
        keys.add(obj.clone()) 
    } else {
        break;
    }
}
for key in keys {
    queue.remove(obj)
}

But in fact, this would infinitely block since peek_max() is never being changed.

This means the best you can do is O(n) because you are required to iterate over every element.

This could be done by sorting O(logn) and returning a slice over the sorted structure.

Proposed example would be:

while let Some((obj, priority)) = queue.iter_over(5) {
    println!("{}", obj) 
}

[simbleau]

It's also true that #35 would provide a better way to do this, (and in one line: queue.clear_over(5)) but I believe it would be a major convenience for developers.

[garro95]

Sorting (even using the heapsort) is O(n * log(n)), which is worse then O(n). If you just need to iterate without removing the elements, I think the best you can do is

pq.iter().filter(|(_, p)| p > priority)...