libpitust 0.1.2

libpitust implements random utility functions I tend to use a lot
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

use std::{collections::BTreeMap, fmt::Debug, marker::PhantomData};

#[derive(Clone)]
pub struct DirtySparseMap<Key: Debug + Copy + Ord, Value> {
    inner: Vec<(Key, Value)>,
    whiteout: Vec<Key>,
}

#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct SparseMap<Key: Debug + Copy + Ord, Value> {
    inner: Vec<(Key, Value)>,
    _marker: PhantomData<Key>,
}

impl<Key: Debug + Copy + Ord, Value> DirtySparseMap<Key, Value> {
    pub fn new() -> DirtySparseMap<Key, Value> {
        DirtySparseMap {
            inner: vec![],
            whiteout: vec![],
        }
    }
    pub fn clean(&mut self) {
        self.inner.reverse();
        self.whiteout.sort_unstable();
        // FIXME: this can be done much more efficiently without binsearching
        self.inner
            .retain(|k| self.whiteout.binary_search(&k.0).is_err());
        self.inner.sort_by_key(|k| k.0);
        self.inner.dedup_by_key(|k| k.0);
        self.whiteout.clear();
    }
    pub fn to_clean(mut self) -> SparseMap<Key, Value> {
        self.clean();
        SparseMap {
            inner: self.inner,
            _marker: PhantomData,
        }
    }
    pub fn put(&mut self, key: Key, value: Value) {
        self.inner.push((key, value));
    }
    pub fn del(&mut self, key: Key) {
        self.whiteout.push(key);
    }
    pub fn with_clean<R>(&mut self, f: impl FnOnce(&mut SparseMap<Key, Value>) -> R) -> R {
        self.clean();
        let mut m = SparseMap {
            inner: core::mem::take(&mut self.inner),
            _marker: PhantomData,
        };
        let res = f(&mut m);
        self.inner = m.inner;
        res
    }
}
impl<Key: Debug + Copy + Ord, Value> SparseMap<Key, Value> {
    pub fn new() -> SparseMap<Key, Value> {
        SparseMap {
            inner: vec![],
            _marker: PhantomData,
        }
    }
    pub fn to_dirty(self) -> DirtySparseMap<Key, Value> {
        DirtySparseMap {
            inner: self.inner,
            whiteout: vec![],
        }
    }
    pub fn with_dirty<R>(&mut self, f: impl FnOnce(&mut DirtySparseMap<Key, Value>) -> R) -> R {
        let mut p = DirtySparseMap {
            inner: core::mem::take(&mut self.inner),
            whiteout: vec![],
        };
        let r = f(&mut p);
        self.inner = p.to_clean().inner;
        r
    }
    pub fn from_btree(tree: BTreeMap<Key, Value>) -> SparseMap<Key, Value> {
        SparseMap {
            inner: tree.into_iter().collect(),
            _marker: PhantomData,
        }
    }
    pub fn get(&self, key: Key) -> Option<&Value> {
        let idx = self.inner.binary_search_by_key(&key, |k| k.0).ok()?;
        Some(&self.inner[idx].1)
    }
    pub fn get_mut(&mut self, key: Key) -> Option<&mut Value> {
        let idx = self.inner.binary_search_by_key(&key, |k| k.0).ok()?;
        Some(&mut self.inner[idx].1)
    }
    /// Put an element into the map. **Note that this operation takes a linear amount of time to complete, if the element does not exist in the map**.
    pub fn put(&mut self, key: Key, value: Value) {
        match self.inner.binary_search_by_key(&key, |k| k.0) {
            Ok(idx) => self.inner[idx].1 = value,
            Err(idx) => self.inner.insert(idx, (key, value)),
        }
    }
    /// Put an element into the map. **Note that this operation takes a linear amount of time to complete, if the element exists in the map**.
    pub fn del(&mut self, key: Key) {
        if let Ok(idx) = self.inner.binary_search_by_key(&key, |k| k.0) {
            self.inner.remove(idx);
        }
    }
    /// Copy all elements from the other map into this one, replacing all that do not currently exist. This operation is O(n) where N is the number of elements in both maps.
    pub fn merge(&mut self, other: SparseMap<Key, Value>) {
        let mut new = vec![];
        let mut this = core::mem::take(&mut self.inner).into_iter().peekable();
        let mut other = other.inner.into_iter().peekable();
        while let (Some(a), Some(b)) = (this.peek(), other.peek()) {
            if a.0 == b.0 {
                this.next();
            } else if a.0 < b.0 {
                new.push(this.next().unwrap());
            } else {
                new.push(other.next().unwrap());
            }
        }
        while let Some(el) = this.next() {
            new.push(el);
        }
        while let Some(el) = other.next() {
            new.push(el);
        }
        self.inner = new;
    }
    pub fn len(&self) -> usize {
        self.inner.len()
    }
    pub fn iter(&self) -> impl Iterator<Item = (Key, &Value)> {
        self.inner.iter().map(|(k, v)| (*k, v))
    }
    pub fn iter_mut(&mut self) -> impl Iterator<Item = (Key, &mut Value)> {
        self.inner.iter_mut().map(|(k, v)| (*k, v))
    }
}

impl<Key: Debug + Copy + Ord, Value: Debug> Debug for SparseMap<Key, Value> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_map().entries(self.iter()).finish()
    }
}