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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

use itertools::Itertools;
use orx_priority_queue::PriorityQueue;
use rand::prelude::*;
use std::cmp::Ordering;

pub fn test_push_pop<P>(mut pq: P)
where
    P: PriorityQueue<usize, f64>,
{
    const N: usize = 70;
    const M: usize = 50;

    pq.clear();
    assert_eq!(0, pq.len());

    // push with ascending priorities
    for i in 0..N {
        pq.push(i, i as f64);
    }
    assert_eq!(N, pq.len());

    // push with descending priorities
    for i in 0..M {
        pq.push(N + i, (N + M - i) as f64);
    }
    assert_eq!(N + M, pq.len());

    // popped in correct order
    for i in 0..N {
        assert_eq!(i, pq.pop_node().unwrap());
    }
    assert_eq!(M, pq.len());

    for i in 0..M {
        assert_eq!(N + M - 1 - i, pq.pop_node().unwrap());
    }
    assert!(pq.is_empty());
}

pub fn test_push_pop_randomized<P>(mut pq: P)
where
    P: PriorityQueue<usize, f64>,
{
    let mut rng = rand::rng();

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

    let mut vec = Vec::new();

    // push 100 -> 0, ..., 99
    for node in 0..100 {
        let priority = rng.random();
        pq.push(node, priority);
        vec.push((node, priority));
    }
    assert_eq!(100, pq.len());

    // pop 60
    let mut vec_popped60 = vec
        .into_iter()
        .sorted_by(|x, y| {
            if x.1 <= y.1 {
                Ordering::Less
            } else {
                Ordering::Greater
            }
        })
        .collect_vec();
    let mut vec_remaining40 = vec_popped60.split_off(60);
    assert_eq!(40, vec_remaining40.len());
    assert_eq!(60, vec_popped60.len());
    for vec_popped in vec_popped60 {
        let pq_popped = pq.pop();
        assert_eq!(Some(vec_popped), pq_popped);
    }
    assert_eq!(40, pq.len());

    // push 25 -> 100, ..., 124
    for node in 100..125 {
        let priority = rng.random();
        pq.push(node, priority);
        vec_remaining40.push((node, priority));
    }
    let vec_remaining65 = vec_remaining40
        .into_iter()
        .sorted_by(|x, y| {
            if x.1 <= y.1 {
                Ordering::Less
            } else {
                Ordering::Greater
            }
        })
        .collect_vec();
    assert_eq!(65, vec_remaining65.len());
    assert_eq!(65, pq.len());

    // pop 65
    for vec_popped in vec_remaining65 {
        let pq_popped = pq.pop();
        assert_eq!(Some(vec_popped), pq_popped);
    }

    assert!(pq.is_empty());
}