delta_encoding/
encoder.rs

1use num_traits::WrappingSub;
2
3/// Construct a delta-encoder
4#[derive(Debug, Default, Copy, Clone)]
5pub struct DeltaEncoder<T> {
6    current: T,
7}
8
9impl<T: WrappingSub + Copy> DeltaEncoder<T> {
10    /// Encode a value, and return the delta between the current value and the encoded value.
11    pub fn encode(&mut self, value: T) -> T {
12        let delta = value.wrapping_sub(&self.current);
13        self.current = value;
14        delta
15    }
16}
17
18/// A utility struct to construct a delta-encoded sequence from an iterator.
19#[derive(Clone, Debug)]
20#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
21pub struct DeltaEncoderIter<I>
22where
23    I: Iterator,
24    <I as Iterator>::Item: WrappingSub + Copy,
25{
26    iter: I,
27    encoder: DeltaEncoder<I::Item>,
28}
29
30impl<I> Iterator for DeltaEncoderIter<I>
31where
32    I: Iterator,
33    <I as Iterator>::Item: WrappingSub + Copy,
34{
35    type Item = I::Item;
36
37    fn next(&mut self) -> Option<Self::Item> {
38        Some(self.encoder.encode(self.iter.next()?))
39    }
40
41    fn size_hint(&self) -> (usize, Option<usize>) {
42        self.iter.size_hint()
43    }
44}
45
46impl<I> ExactSizeIterator for DeltaEncoderIter<I>
47where
48    I: ExactSizeIterator,
49    <I as Iterator>::Item: WrappingSub + Copy,
50{
51}
52
53pub trait DeltaEncoderExt: Iterator
54where
55    <Self as Iterator>::Item: Default + Copy + WrappingSub,
56{
57    /// Construct a delta-encoded iterator from an iterator.
58    /// The first element of the iterator is used as the starting point for the delta-encoding.
59    /// Note that unlike the [`DeltaEncoder.encode`] method, this method will panic if the delta is too large.
60    ///
61    /// ## Example
62    /// ```
63    /// use delta_encoding::DeltaEncoderExt;
64    ///
65    /// // Consuming original data into a delta-encoded iterator.
66    /// let mut encoded: Vec<i64> = vec![1, 2, 5, 4, 2].into_iter().deltas().collect();
67    /// assert_eq!(encoded, vec![1, 1, 3, -1, -2]);
68    ///
69    /// // Non-consuming original data, but avoiding the allocation of a new vector.
70    /// let mut encoded: Vec<i64> = vec![1, 2, 5, 4, 2].iter().copied().deltas().collect();
71    /// assert_eq!(encoded, vec![1, 1, 3, -1, -2]);
72    /// ```
73    fn deltas(self) -> DeltaEncoderIter<Self>
74    where
75        Self: Sized,
76    {
77        DeltaEncoderIter {
78            iter: self,
79            encoder: DeltaEncoder::default(),
80        }
81    }
82}
83
84impl<I> DeltaEncoderExt for I
85where
86    I: Iterator,
87    <I as Iterator>::Item: Default + Copy + WrappingSub,
88{
89}
90
91#[cfg(test)]
92mod tests {
93    use super::*;
94    use crate::tests::TEST_DATA;
95
96    fn run(original: &[i64], encoded: &[i64]) {
97        let mut enc = DeltaEncoder::default();
98        let result: Vec<i64> = original.iter().map(|&v| enc.encode(v)).collect();
99        assert_eq!(result, encoded, "encoded from: {original:?}");
100
101        let result: Vec<i64> = original.iter().copied().deltas().collect();
102        assert_eq!(result, encoded, "iter().copied() original: {original:?}");
103    }
104
105    #[test]
106    fn test() {
107        for &(original, encoded) in TEST_DATA {
108            run(original, encoded);
109        }
110    }
111}
delta_encoding/encoder.rs

delta_encoding/
encoder.rs
