# Using priority\_queue::PriorityQueue::change\_priority

**URL:** <https://users.rust-lang.org/t/using-priority-queue-change-priority/102000>\
**Category:** help\
**Created:** [November 2, 2023, 5:45pm UTC](https://users.rust-lang.org/t/using-priority-queue-change-priority/102000 "2023-11-02T17:45:35Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![cscherrer](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/cscherrer/32/36694_2.png) [@cscherrer](https://users.rust-lang.org/u/cscherrer)\
**Post date:** [November 2, 2023, 5:45pm UTC](https://users.rust-lang.org/t/using-priority-queue-change-priority/102000/1 "2023-11-02T17:45:35Z")

</div>

Hi, I'm working through some little projects to help me learn Rust. Currently I'm working on a prime number sieve (implementation [here](https://github.com/cscherrer/prime-sieve)). This is a [Sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes), using some ideas from [Melissa O'Neil's JFP paper](https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf).

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":

```rust
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:

```rust
#[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

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

```

that includes this loop:

```rust
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:

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

```

So my ~~first~~ twentieth or so attempt is

```rust
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:

```rust
 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
 
 For more information about this error, try `rustc --explain E0499`.
 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?

---

<div class="post-metadata">

**Author:** ![semicoleon](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/semicoleon/32/22313_2.png) [@semicoleon](https://users.rust-lang.org/u/semicoleon)\
**Post date:** [November 2, 2023, 6:37pm UTC](https://users.rust-lang.org/t/using-priority-queue-change-priority/102000/2 "2023-11-02T18:37:19Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![cscherrer](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/cscherrer/32/36694_2.png) [@cscherrer](https://users.rust-lang.org/u/cscherrer)\
**Post date:** [November 2, 2023, 6:44pm UTC](https://users.rust-lang.org/t/using-priority-queue-change-priority/102000/3 "2023-11-02T18:44:20Z")

</div>

Thanks @semicoleon 🙂

> [@semicoleon](#):
>
> Your first version compiles because the `ref_f` value is not in use by the time you need mutable access to `active_filters`.

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?

> [@semicoleon](#):
>
> > 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.

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.

---

<div class="post-metadata">

**Author:** ![semicoleon](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/semicoleon/32/22313_2.png) [@semicoleon](https://users.rust-lang.org/u/semicoleon)\
**Post date:** [November 2, 2023, 6:55pm UTC](https://users.rust-lang.org/t/using-priority-queue-change-priority/102000/4 "2023-11-02T18:55:15Z")

</div>

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

```rust
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.

```rust
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.

---

<div class="post-metadata">

**Author:** ![cscherrer](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/cscherrer/32/36694_2.png) [@cscherrer](https://users.rust-lang.org/u/cscherrer)\
**Post date:** [November 2, 2023, 6:59pm UTC](https://users.rust-lang.org/t/using-priority-queue-change-priority/102000/5 "2023-11-02T18:59:04Z")

</div>

Thank you! I'll need to think about this for a while to understand the details.

---

<div class="post-metadata">

**Author:** ![system](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/system/32/51372_2.png) [@system](https://users.rust-lang.org/u/system)\
**Post date:** [January 31, 2024, 6:59pm UTC](https://users.rust-lang.org/t/using-priority-queue-change-priority/102000/6 "2024-01-31T18:59:20Z")

</div>

Closed on January 31, 2024, 6:59pm UTC

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.