automerge/columnar/encoding/
boolean.rs

1use std::borrow::Cow;
2
3use super::{raw, Encodable, RawDecoder, Sink};
4
5/// Encodes booleans by storing the count of the same value.
6///
7/// The sequence of numbers describes the count of false values on even indices (0-indexed) and the
8/// count of true values on odd indices (0-indexed).
9///
10/// Counts are encoded as usize.
11pub(crate) struct BooleanEncoder<S> {
12    written: usize,
13    //buf: &'a mut Vec<u8>,
14    buf: S,
15    last: bool,
16    count: usize,
17}
18
19impl BooleanEncoder<Vec<u8>> {
20    pub(crate) fn new() -> BooleanEncoder<Vec<u8>> {
21        BooleanEncoder::from_sink(Vec::new())
22    }
23}
24
25impl<S: Sink> BooleanEncoder<S> {
26    pub(crate) fn from_sink(sink: S) -> Self {
27        BooleanEncoder {
28            written: 0,
29            buf: sink,
30            last: false,
31            count: 0,
32        }
33    }
34
35    pub(crate) fn append(&mut self, value: bool) {
36        if value == self.last {
37            self.count += 1;
38        } else {
39            self.written += self.count.encode(&mut self.buf);
40            self.last = value;
41            self.count = 1;
42        }
43    }
44
45    pub(crate) fn finish(mut self) -> (S, usize) {
46        if self.count > 0 {
47            self.written += self.count.encode(&mut self.buf);
48        }
49        (self.buf, self.written)
50    }
51}
52
53impl<S: Sink> From<S> for BooleanEncoder<S> {
54    fn from(output: S) -> Self {
55        BooleanEncoder::from_sink(output)
56    }
57}
58
59/// See the discussion of [`BooleanEncoder`] for details on this encoding
60#[derive(Clone, Debug)]
61pub(crate) struct BooleanDecoder<'a> {
62    decoder: RawDecoder<'a>,
63    last_value: bool,
64    count: usize,
65}
66
67impl<'a> From<Cow<'a, [u8]>> for BooleanDecoder<'a> {
68    fn from(bytes: Cow<'a, [u8]>) -> Self {
69        BooleanDecoder {
70            decoder: RawDecoder::from(bytes),
71            last_value: true,
72            count: 0,
73        }
74    }
75}
76
77impl<'a> From<&'a [u8]> for BooleanDecoder<'a> {
78    fn from(d: &'a [u8]) -> Self {
79        Cow::Borrowed(d).into()
80    }
81}
82
83// this is an endless iterator that returns false after input is exhausted
84impl Iterator for BooleanDecoder<'_> {
85    type Item = Result<bool, raw::Error>;
86
87    fn next(&mut self) -> Option<Self::Item> {
88        while self.count == 0 {
89            if self.decoder.done() && self.count == 0 {
90                return None;
91            }
92            self.count = match self.decoder.read() {
93                Ok(c) => c,
94                Err(e) => return Some(Err(e)),
95            };
96            self.last_value = !self.last_value;
97        }
98        self.count -= 1;
99        Some(Ok(self.last_value))
100    }
101}
102
103/// Like a `BooleanEncoder` but if all the values in the column are `false` then will return an
104/// empty range rather than a range with `count` false values.
105pub(crate) struct MaybeBooleanEncoder<S> {
106    encoder: BooleanEncoder<S>,
107    all_false: bool,
108}
109
110impl MaybeBooleanEncoder<Vec<u8>> {
111    pub(crate) fn new() -> MaybeBooleanEncoder<Vec<u8>> {
112        MaybeBooleanEncoder::from_sink(Vec::new())
113    }
114}
115
116impl<S: Sink> MaybeBooleanEncoder<S> {
117    pub(crate) fn from_sink(buf: S) -> MaybeBooleanEncoder<S> {
118        MaybeBooleanEncoder {
119            encoder: BooleanEncoder::from_sink(buf),
120            all_false: true,
121        }
122    }
123
124    pub(crate) fn append(&mut self, value: bool) {
125        if value {
126            self.all_false = false;
127        }
128        self.encoder.append(value);
129    }
130
131    pub(crate) fn finish(self) -> (S, usize) {
132        if self.all_false {
133            (self.encoder.buf, 0)
134        } else {
135            self.encoder.finish()
136        }
137    }
138}
139
140/// Like a `BooleanDecoder` but if the underlying range is empty then just returns an infinite
141/// sequence of `None`
142#[derive(Clone, Debug)]
143pub(crate) struct MaybeBooleanDecoder<'a>(BooleanDecoder<'a>);
144
145impl<'a> From<Cow<'a, [u8]>> for MaybeBooleanDecoder<'a> {
146    fn from(bytes: Cow<'a, [u8]>) -> Self {
147        MaybeBooleanDecoder(BooleanDecoder::from(bytes))
148    }
149}
150
151impl<'a> From<&'a [u8]> for MaybeBooleanDecoder<'a> {
152    fn from(d: &'a [u8]) -> Self {
153        Cow::Borrowed(d).into()
154    }
155}
156
157impl Iterator for MaybeBooleanDecoder<'_> {
158    type Item = Result<Option<bool>, raw::Error>;
159
160    fn next(&mut self) -> Option<Self::Item> {
161        if self.0.decoder.is_empty() {
162            None
163        } else {
164            self.0.next().transpose().map(Some).transpose()
165        }
166    }
167}
168
169#[cfg(test)]
170mod tests {
171    use super::*;
172
173    use proptest::prelude::*;
174
175    fn encode(vals: &[bool]) -> Vec<u8> {
176        let mut buf = Vec::new();
177        let mut encoder = BooleanEncoder::from_sink(&mut buf);
178        for val in vals {
179            encoder.append(*val);
180        }
181        encoder.finish();
182        buf
183    }
184
185    fn decode(buf: &[u8]) -> Vec<bool> {
186        BooleanDecoder::from(buf)
187            .collect::<Result<Vec<_>, _>>()
188            .unwrap()
189    }
190
191    proptest! {
192        #[test]
193        fn encode_decode_bools(vals in proptest::collection::vec(any::<bool>(), 0..100)) {
194            assert_eq!(vals, decode(&encode(&vals)))
195        }
196    }
197}
automerge/columnar/encoding/boolean.rs

automerge/columnar/encoding/
boolean.rs
