orx-priority-queue 1.9.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

#![cfg(not(miri))]

mod priority_queue_deckey_tests;
mod priority_queue_tests;

#[test]
fn test_dary_forall() {
    test_dary_for::<2>();
    test_dary_for::<3>();
    test_dary_for::<4>();
    test_dary_for::<7>();
    test_dary_for::<8>();
    test_dary_for::<13>();
    test_dary_for::<16>();
    test_dary_for::<32>();
    test_dary_for::<64>();
}

fn test_dary_for<const D: usize>() {
    use orx_priority_queue::DaryHeapWithMap;
    use priority_queue_deckey_tests::*;
    use priority_queue_tests::*;

    let new_heap = DaryHeapWithMap::<usize, f64, D>::default;

    let change_key = [
        ChangeKeyMethod::Decrease,
        ChangeKeyMethod::Update,
        ChangeKeyMethod::TryDecrease,
    ];

    test_len(new_heap());
    test_is_empty(new_heap());
    test_peek(new_heap());
    test_clear(new_heap());
    test_push_pop(new_heap());
    test_push_pop_randomized(new_heap());
    test_push_then_pop(new_heap());
    test_push_then_pop_randomized(new_heap());

    test_contains(new_heap());
    test_key_of(new_heap());
    change_key
        .iter()
        .for_each(|change_key_method| test_change_key(new_heap(), *change_key_method));
    test_remove(new_heap());
    test_mixed(new_heap());

    change_key
        .iter()
        .for_each(|change_key_method| test_change_key_or_push(new_heap(), *change_key_method));
}

#[test]
fn from_iter_heapifies_and_tracks_positions() {
    use orx_priority_queue::{PriorityQueue, PriorityQueueDecKey, QuaternaryHeapWithMap};

    let mut heap = [(0, 42), (1, 7), (2, 24), (3, 3)]
        .into_iter()
        .collect::<QuaternaryHeapWithMap<_, _>>();

    assert_eq!(heap.key_of(&0), Some(42));
    assert_eq!(heap.key_of(&1), Some(7));
    assert_eq!(heap.key_of(&2), Some(24));
    assert_eq!(heap.key_of(&3), Some(3));
    assert_eq!(heap.pop(), Some((3, 3)));
    assert_eq!(heap.pop(), Some((1, 7)));
    assert_eq!(heap.pop(), Some((2, 24)));
    assert_eq!(heap.pop(), Some((0, 42)));
}