rheaps 0.16.0

Heap data structures for Rust
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

use crate::{Heap, MeldableHeap};

use super::soft_heap_core::{SoftHeapCore, SoftHeapError, SoftMeldError};

/// A Kaplan-Zwick binary-tree soft heap.
///
/// A soft heap may return keys out of order: after inserting `n` keys, at
/// most `error_rate * n` live keys may have had their priority corrupted.
/// The original keys are always returned, exactly once. Keys must be cloneable
/// because a soft heap retains a corrupted-key snapshot while returning the
/// original key by value.
///
/// ```
/// use rheaps::tree::BinaryTreeSoftHeap;
///
/// let mut heap = BinaryTreeSoftHeap::new(0.1).unwrap();
/// heap.push(4);
/// heap.push(1);
/// heap.push(3);
///
/// assert_eq!(heap.len(), 3);
/// // A soft heap may corrupt priorities, so only the count of returned
/// // original keys - not their order - is guaranteed here.
/// let popped: Vec<_> = core::iter::from_fn(|| heap.pop()).collect();
/// assert_eq!(popped.len(), 3);
/// ```
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct BinaryTreeSoftHeap<K> {
    core: SoftHeapCore<K, ()>,
}

impl<K: Ord + Clone> BinaryTreeSoftHeap<K> {
    /// Creates a heap with an error rate strictly between zero and one.
    pub fn new(error_rate: f64) -> Result<Self, SoftHeapError> {
        Ok(Self {
            core: SoftHeapCore::new(error_rate)?,
        })
    }
}

impl<K: Ord + Clone> BinaryTreeSoftHeap<K> {
    /// Returns the rank below which keys are never corrupted.
    #[must_use]
    pub const fn rank_limit(&self) -> usize {
        self.core.rank_limit()
    }

    /// Inserts a key.
    pub fn push(&mut self, key: K) {
        self.core.insert(key, ());
    }

    /// Returns the next key selected by the soft heap.
    #[must_use]
    pub fn peek(&self) -> Option<&K> {
        self.core.peek_entry().map(|(_, key, _)| key)
    }

    /// Removes and returns the next key selected by the soft heap.
    pub fn pop(&mut self) -> Option<K> {
        self.core.pop_item().map(|item| item.into_pair().0)
    }

    /// Returns the number of live keys.
    #[must_use]
    pub const fn len(&self) -> usize {
        self.core.len()
    }

    /// Returns whether the heap contains no keys.
    #[must_use]
    pub const fn is_empty(&self) -> bool {
        self.core.len() == 0
    }

    /// Removes all keys.
    pub fn clear(&mut self) {
        self.core.clear();
    }
}

impl<K: Ord + Clone> BinaryTreeSoftHeap<K> {
    /// Melds `other` into this heap, consuming the donor on success.
    pub fn meld(&mut self, other: Self) -> Result<(), SoftMeldError> {
        if self.rank_limit() != other.rank_limit() {
            return Err(SoftMeldError::IncompatibleErrorRate);
        }
        self.core.meld_from(other.core);
        Ok(())
    }
}

impl<T: Ord + Clone> Heap<T> for BinaryTreeSoftHeap<T> {
    fn push(&mut self, value: T) {
        Self::push(self, value);
    }

    fn peek(&self) -> Option<&T> {
        Self::peek(self)
    }

    fn pop(&mut self) -> Option<T> {
        Self::pop(self)
    }

    fn len(&self) -> usize {
        Self::len(self)
    }

    fn clear(&mut self) {
        Self::clear(self);
    }
}

impl<T: Ord + Clone> MeldableHeap<T> for BinaryTreeSoftHeap<T> {
    type MeldError = SoftMeldError;

    fn meld(&mut self, other: Self) -> Result<(), Self::MeldError> {
        Self::meld(self, other)
    }
}