orx-priority-queue 1.8.0

Priority queue traits and high performance d-ary heap implementations.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

use orx_priority_queue::PriorityQueueDecKey;
use rand::prelude::*;
use std::collections::HashSet;

pub fn test_remove<P>(mut pq: P)
where
    P: PriorityQueueDecKey<usize, f64>,
{
    const LEN: usize = 125;

    pq.clear();
    assert!(pq.is_empty());

    let mut rng = rand::rng();

    let mut vec = Vec::new();
    for node in 0..LEN {
        let priority = rng.random();
        pq.push(node, priority);
        vec.push(priority);
    }
    assert_eq!(LEN, pq.len());
    assert_eq!(LEN, vec.len());

    // remove randomly ~60%
    let mut removed = HashSet::new();
    for (node_to_rmv, key) in vec.iter().enumerate() {
        let do_remove = rng.random::<f64>() < 0.6;
        if do_remove {
            let key_removed = pq.remove(&node_to_rmv);
            assert_eq!(key, &key_removed);
            removed.insert(node_to_rmv);

            assert_eq!(LEN, pq.len() + removed.len());
            assert!(!pq.contains(&node_to_rmv));
            assert_eq!(None, pq.key_of(&node_to_rmv));
        }
    }
    assert_eq!(LEN, pq.len() + removed.len());

    // pop remaining
    while let Some((node, key)) = pq.pop() {
        assert!(!removed.contains(&node));
        assert_eq!(vec[node], key);
    }
    assert!(pq.is_empty());
}