frond 0.1.1

dynamic lexicographic containers
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

use std::collections::BTreeMap;

use super::{Key, Value};

pub struct Iter<'a> {
    inner: std::collections::btree_map::Range<'a, Vec<u8>, Vec<u8>>,
}

impl<'a> Iterator for Iter<'a> {
    type Item = (&'a [u8], &'a [u8]);

    fn next(&mut self) -> Option<Self::Item> {
        self.inner.next().map(|(k, v)| (&**k, &**v))
    }
}

impl<'a> DoubleEndedIterator for Iter<'a> {
    fn next_back(&mut self) -> Option<Self::Item> {
        self.inner.next_back().map(|(k, v)| (&**k, &**v))
    }
}

/// `Petal` is a dynamically-sized type (DST) that succinctly stores keys and values, accessible
/// lexicographically.
#[derive(Default, Clone)]
pub struct Petal {
    lo: Vec<u8>,
    hi: Option<Vec<u8>>,
    storage: BTreeMap<Vec<u8>, Vec<u8>>,
}

impl Petal {
    pub fn new() -> Box<Petal> {
        Box::default()
    }

    pub fn len(&self) -> usize {
        self.storage.len()
    }

    pub fn contains(&self, key: Key) -> bool {
        self.storage.contains_key(key)
    }

    pub fn get(&self, key: Key) -> Option<Value> {
        self.storage.get(key).map(|v| &**v)
    }

    pub fn range<'a>(
        &'a self,
        start: std::ops::Bound<&[u8]>,
        end: std::ops::Bound<&[u8]>,
    ) -> Iter<'a> {
        Iter {
            inner: self.storage.range::<[u8], _>((start, end)),
        }
    }

    #[must_use]
    pub fn batch<'a, I: IntoIterator<Item = (&'a [u8], Option<&'a [u8]>)>>(
        &self,
        iter: I,
    ) -> Box<Petal> {
        let mut ret = Box::new(Petal {
            hi: self.hi.clone(),
            lo: self.lo.clone(),
            storage: self.storage.clone(),
        });

        for (key, value_opt) in iter {
            self.assert_key_in_bounds(key);
            if let Some(value) = value_opt {
                ret.storage.insert(key.to_vec(), value.to_vec());
            }
        }

        ret
    }

    #[must_use]
    pub fn split(&self, split_key: Key) -> (Box<Petal>, Box<Petal>) {
        self.assert_key_in_bounds(split_key);

        let mut lhs_storage = BTreeMap::default();
        let mut rhs_storage = BTreeMap::default();

        for (k, v) in &self.storage {
            if &**k < split_key {
                lhs_storage.insert(k.clone(), v.clone());
            } else {
                rhs_storage.insert(k.clone(), v.clone());
            }
        }

        let lhs = Box::new(Petal {
            lo: self.lo.clone(),
            hi: Some(split_key.to_vec()),
            storage: lhs_storage,
        });

        let rhs = Box::new(Petal {
            lo: split_key.to_vec(),
            hi: self.hi.clone(),
            storage: rhs_storage,
        });

        (lhs, rhs)
    }

    #[must_use]
    pub fn merge(&self, rhs: &Petal) -> Box<Petal> {
        assert_eq!(self.hi.as_ref().unwrap(), &*rhs.lo);

        let storage = self
            .storage
            .iter()
            .chain(rhs.storage.iter())
            .map(|(k, v)| (k.clone(), v.clone()))
            .collect();

        Box::new(Petal {
            lo: self.lo.clone(),
            hi: rhs.hi.clone(),
            storage,
        })
    }

    fn assert_key_in_bounds(&self, key: Key) {
        assert!(key >= &self.lo);
        if let Some(hi) = &self.hi {
            assert!(key < &hi);
        }
    }
}