columnar/
lookback.rs

1//! Containers that can store either values, or offsets to prior values.
2//!
3//! This has the potential to be more efficient than a list of `T` when many values repeat in
4//! close proximity. Values must be equatable, and the degree of lookback can be configured.
5
6use crate::{Options, Results, Push, Index, Len, HeapSize};
7
8/// A container that encodes repeated values with a `None` variant, at the cost of extra bits for every record.
9#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
10#[derive(Clone, Debug, Default, PartialEq)]
11pub struct Repeats<TC, const N: u8 = 255> {
12    /// Some(x) encodes a value, and None indicates the prior `x` value.
13    pub inner: Options<TC>,
14}
15
16impl<T: PartialEq, TC: Push<T> + Len, const N: u8> Push<T> for Repeats<TC, N>
17where
18    for<'a> &'a TC: Index,
19    for<'a> <&'a TC as Index>::Ref : PartialEq<T>,
20{
21    #[inline]
22    fn push(&mut self, item: T) {
23        // Look at the last `somes` value for a potential match.
24        let insert: Option<T> = if (&self.inner.somes).last().map(|x| x.eq(&item)) == Some(true) {
25            None
26        } else {
27            Some(item)
28        };
29        self.inner.push(insert);
30    }
31}
32
33impl<TC: Len, const N: u8> Len for Repeats<TC, N> {
34    #[inline(always)] fn len(&self) -> usize { self.inner.len() }
35}
36
37impl<TC: Index, const N: u8> Index for Repeats<TC, N> {
38    type Ref = TC::Ref;
39    #[inline(always)] fn get(&self, index: usize) -> Self::Ref {
40        match self.inner.get(index) {
41            Some(item) => item,
42            None => {
43                let pos = self.inner.indexes.rank(index) - 1;
44                self.inner.somes.get(pos)
45            },
46        }
47    }
48}
49
50impl<TC: HeapSize, const N: u8> HeapSize for Repeats<TC, N> {
51    fn heap_size(&self) -> (usize, usize) {
52        self.inner.heap_size()
53    }
54}
55
56#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
57#[derive(Clone, Debug, Default, PartialEq)]
58pub struct Lookbacks<TC, VC = Vec<u8>, const N: u8 = 255> {
59    /// Ok(x) encodes a value, and Err(y) indicates a value `y` back.
60    pub inner: Results<TC, VC>,
61}
62
63impl<T: PartialEq, TC: Push<T> + Len, VC: Push<u8>, const N: u8> Push<T> for Lookbacks<TC, VC, N>
64where
65    for<'a> &'a TC: Index,
66    for<'a> <&'a TC as Index>::Ref : PartialEq<T>,
67{
68    #[inline]
69    fn push(&mut self, item: T) {
70        // Look backwards through (0 .. N) to look for a matching value.
71        let oks_len = self.inner.oks.len();
72        let find = (0u8 .. N).take(self.inner.oks.len()).find(|i| (&self.inner.oks).get(oks_len - (*i as usize) - 1) == item);
73        let insert: Result<T, u8> = if let Some(back) = find { Err(back) } else { Ok(item) };
74        self.inner.push(insert);
75    }
76}
77
78impl<TC, VC, const N: u8> Len for Lookbacks<TC, VC, N> {
79    #[inline(always)] fn len(&self) -> usize { self.inner.len() }
80}
81
82impl<TC: Index, VC: Index<Ref=u8>, const N: u8> Index for Lookbacks<TC, VC, N> {
83    type Ref = TC::Ref;
84    #[inline(always)] fn get(&self, index: usize) -> Self::Ref {
85        match self.inner.get(index) {
86            Ok(item) => item,
87            Err(back) => {
88                let pos = self.inner.indexes.rank(index) - 1;
89                self.inner.oks.get(pos - (back as usize))
90            },
91        }
92    }
93}
94impl<'a, TC, const N: u8> Index for &'a Lookbacks<TC, Vec<u8>, N>
95where
96    &'a TC: Index,
97{
98    type Ref = <&'a TC as Index>::Ref;
99    #[inline(always)] fn get(&self, index: usize) -> Self::Ref {
100        match (&self.inner).get(index) {
101            Ok(item) => item,
102            Err(back) => {
103                let pos = self.inner.indexes.rank(index) - 1;
104                (&self.inner.oks).get(pos - (*back as usize))
105            },
106        }
107    }
108}
109
110impl<TC: HeapSize, VC: HeapSize, const N: u8> HeapSize for Lookbacks<TC, VC, N> {
111    fn heap_size(&self) -> (usize, usize) {
112        self.inner.heap_size()
113    }
114}
columnar/lookback.rs

columnar/
lookback.rs
