# Using priority_queue::PriorityQueue::change_priority

Hi, I'm working through some little projects to help me learn Rust. Currently I'm working on a prime number sieve (implementation here). This is a Sieve of Eratosthenes, using some ideas from Melissa O'Neil's JFP paper.

I'm a little stuck on something, hoping to get some advice to get unstuck. After the small primes (2, 3, 5, 7), I have a struct to help me walk through "bigger primes":

``````struct BiggerPrimes {
state: Wheel,
active_filters: PriorityQueue<Filter, Reverse<u64>>,
queued_filters: VecDeque<Filter>,
}
``````

For my current question, the `Wheel` and `VecDeque` stuff isn't important -- all of that is working fine. But `PriorityQueue`s are giving me some grief.

`Filter` looks like this:

``````#[derive(Hash, Copy, Clone, Eq, PartialEq)]
struct Filter {
base: u64,
state: u64,
}
``````

The idea is that each `base` is a prime, and `state` steps through multiples of that prime.

Then `BiggerPrimes` has a method

``````fn step(&mut self) -> Option<u64>
``````

that includes this loop:

``````while let Some((ref_f, _)) = self.active_filters.peek() {
match ref_f.state {
x if x < n => {
let mut f = self.active_filters.pop().unwrap().0;
f.state += f.base;
self.active_filters.push(f, Reverse(f.state));
}
x if x == n => {
return None;
}
_ => {
break;
}
}
}
``````

Here `ref_f: &Filter` and `f: Filter`. Note that unlike `BinaryHeap`s, a `PriorityQueue` takes the item and priority separately as arguments.

The code works fine as is, but it's much slower than the `BinaryHeap` implementation. But currently I'm popping the queue, updating `f`, and then pushing it back on. I'd guess it could be more efficient to use `PriorityQueue::change_priority`, which has this spec:

``````pub fn change_priority<Q>(&mut self, item: &Q, new_priority: P) -> Option<P>
``````

So my first twentieth or so attempt is

``````let fs = &mut self.active_filters;
while let Some((ref_f, _)) = fs.peek_mut() {
match ref_f.state {
x if x < n => {
ref_f.state += ref_f.base;
fs.change_priority(ref_f, Reverse(ref_f.state));
}
x if x == n => {
return None;
}
_ => {
break;
}
}
}
``````

This doesn't work:

`````` 1  error[E0499]: cannot borrow `*fs` as mutable more than once at a time
--> src/main.rs:106:21
|
103 |         while let Some((ref_f, _)) = fs.peek_mut() {
|                                      -- first mutable borrow occurs here
...
106 |                     fs.change_priority(ref_f, Reverse(ref_f.state));
|                     ^^                 ----- first borrow later used here
|                     |
|                     second mutable borrow occurs here

error: could not compile `prime-sieve` (bin "prime-sieve") due to previous error
``````

Sorry this is so long, but my questions are

1. How can I fix this?
2. Why is the compiler happy with the current `while` loop? It seems like `self.active_filters` is borrowed twice. Even stranger, `self: &mut`, `ref_f: &Filter`, and `mut f: Filter` are all alive at once. How is rustc happy with this?

Your first version compiles because the `ref_f` value is not in use by the time you need mutable access to `active_filters`.

Note that `peek_mut` includes this line in it's documentation

The item is a mutable reference, but it's a logic error to modify it in a way that change the result of `Hash` or `Eq`.

Your modifications will do exactly that, so your second version is wrong even if you fix it so it compiles.

Thanks @semicoleon Does "not in use" mean its lifetime has ended? Is that because I don't match on the whole value, but only its `state` field?

Hmm, good point. I know the `base` fields will all be distinct, so I could implement `Hash` and `Eq` to only look at those. But I'm guessing that's not the reason it won't compile.

We can break the first version in the same way for illustrative purposes

``````while let Some((ref_f, _)) = self.active_filters.peek() {
match ref_f.state {
x if x < n => {
let mut f = self.active_filters.pop().unwrap().0;
f.state += f.base;
self.active_filters.push(f, Reverse(f.state));
let _ = ref_f;
}
x if x == n => {
return None;
}
_ => {
break;
}
}
}
``````

By referencing `ref_f` after we need to borrow `active_filters` again, we force the borrow to live longer which creates a conflict.

You can make the second version compile by creating a copy of `ref_f` so that the borrow can end earlier, like in the first version.

``````while let Some((ref_f, _)) = self.active_filters.peek_mut() {
match ref_f.state {
x if x < n => {
ref_f.state += ref_f.base;
let f = *ref_f;
self.active_filters.change_priority(&f, Reverse(f.state));
}
x if x == n => {
return None;
}
_ => {
break;
}
}
}
``````

Then `ref_f` is no longer used by the time you need to borrow `active_filters` again.

Though of course that assumes you made the change to the `Hash` and `Eq` impls, otherwise things may break at runtime.

1 Like