mheap 0.1.1

Flexible binary heaps
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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164

use crate::{sift, storage::Storage, tree, ordering::Ordering, Position};

pub trait RawHeap: Storage {
    /// Take an element at `pos` and move it up the heap.
    ///
    /// Returns the new position of the element.
    fn sift_up(&mut self, pos: Position, ord: &impl Ordering<Self::Key>) -> Position {
        sift::sift_up(self, pos, ord)
    }

    /// Take an element at `pos` and move it down the heap, while its elements are larger.
    ///
    /// Returns the new position of the element.
    fn sift_down(&mut self, pos: Position, ord: &impl Ordering<Self::Key>) -> Position {
        sift::sift_down(self, pos, ord)
    }

    /// Take an element at `pos` and move it all the way down the heap (ignores the element key/value)
    fn sift_down_to_bottom(&mut self, pos: Position, ord: &impl Ordering<Self::Key>) -> Position {
        sift::sift_down_to_bottom(self, pos, ord)
    }

    /// Restore heap invariant by moving the element up or down the heap
    ///
    /// Returns the new position of the element.
    fn fixup_sift(&mut self, pos: Position, ord: &impl Ordering<Self::Key>) -> Position {
        sift::fixup_sift(self, pos, ord)
    }

    /// Specialized version of [`Self::fixup_sift`] that is faster when the element is known to be close to the bottom of the heap
    fn fixup_sift_to_bottom(&mut self, pos: Position, ord: &impl Ordering<Self::Key>) -> Position {
        let pos = self.sift_down_to_bottom(pos, ord);
        self.sift_up(pos, ord)
    }

    fn peek(&self) -> Option<&Self::Item> {
        Some(self.get(tree::root(self)?))
    }

    fn peek_mut(&mut self) -> Option<PeekMut<'_, Self>> {
        PeekMut::new(self)
    }

    fn pop_swap(
        &mut self,
        mut last_item: Self::Item,
        ord: &impl Ordering<Self::Key>,
    ) -> Self::Item {
        if let Some(pos) = tree::root(self) {
            std::mem::swap(self.get_mut(pos), &mut last_item);
            self.fixup_sift_to_bottom(pos, ord);
        }
        last_item
    }

    fn rebuild(&mut self, ord: &impl Ordering<Self::Key>) {
        for i in tree::rebuild_range(self).rev() {
            self.sift_down(i, ord);
        }
    }

    fn rebuild_tail(&mut self, start: Position, ord: &impl Ordering<Self::Key>) {
        if start == self.len() {
            return;
        }
        if tree::better_to_rebuild(self, start) {
            self.rebuild(ord);
        } else {
            assert!(start < self.len());
            for i in start..self.len() {
                self.sift_up(i, ord);
            }
        }
    }
}

impl<S: Storage + ?Sized> RawHeap for S {}

/// Structure wrapping a mutable reference to the top item on a [`RawHeap`].
///
/// This `struct` is created by the [`peek_mut`] method on [`RawHeap`]. See
/// its documentation for more.
///
/// [`peek_mut`]: RawHeap::peek_mut
pub struct PeekMut<'a, S: RawHeap + ?Sized> {
    // Invariant: heap is not empty
    heap: &'a mut S,
    sift: bool,
}

impl<'a, S: RawHeap + ?Sized> Drop for PeekMut<'a, S> {
    fn drop(&mut self) {
        if cfg!(debug_assertions) && self.sift {
            if !std::thread::panicking() {
                panic!("PeekMut must be restored before dropping");
            }
        }
    }
}

impl<'a, S: RawHeap + ?Sized> PeekMut<'a, S> {
    /// The heap must have a root node (i.e. not empty)
    fn new(heap: &'a mut S) -> Option<Self> {
        if heap.is_empty() {
            return None;
        }
        Some(Self { heap, sift: false })
    }

    fn assert_invariant(&self) {
        debug_assert!(!self.heap.is_empty());
        if self.heap.is_empty() {
            // SAFETY: checked invariant in the constructor
            unsafe {
                std::hint::unreachable_unchecked();
            }
        }
    }

    pub fn pos(&self) -> Position {
        self.assert_invariant();
        tree::root(self.heap).unwrap()
    }

    pub fn as_ref(&self) -> &S::Item {
        self.heap.get(self.pos())
    }

    pub fn as_mut(&mut self) -> &mut S::Item {
        self.assert_invariant();

        // there is not need to restore the heap if it is the only element in the heap
        if tree::child(self.heap, self.pos(), 0).is_some() {
            self.sift = true;
        }

        self.heap.get_mut(self.pos())
    }

    pub fn restore(&mut self, ord: &impl Ordering<S::Key>) -> bool {
        if self.sift {
            self.sift = false;
            self.assert_invariant();
            self.heap.sift_down(self.pos(), ord) != self.pos()
        } else {
            false
        }
    }

    pub fn ignore_mutation(&mut self) {
        self.sift = false;
    }

    pub fn heap_incoherent(&self) -> &S {
        self.assert_invariant();
        self.heap
    }

    pub fn heap_mut(&mut self) -> &mut S {
        self.assert_invariant();
        assert!(!self.sift);
        self.heap
    }
}