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.
5use alloc::{vec::Vec, string::String};
6
7use crate::{Options, Results, Push, Index, Len, Clear, Borrow, Container, IndexAs};
8
9/// A container that encodes repeated values with a `None` variant, at the cost of extra bits for every record.
10#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
11#[derive(Copy, Clone, Debug, Default, PartialEq)]
12pub struct Repeats<TC, CC=Vec<u64>, VC=Vec<u64>, WC=[u64; 2]> {
13    /// Some(x) encodes a value, and None indicates the prior `x` value.
14    pub inner: Options<TC, CC, VC, WC>,
15}
16
17impl<T: PartialEq, TC: Push<T> + Len> Push<T> for Repeats<TC>
18where
19    for<'a> &'a TC: Index,
20    for<'a> <&'a TC as Index>::Ref : PartialEq<T>,
21{
22    #[inline]
23    fn push(&mut self, item: T) {
24        // Look at the last `somes` value for a potential match.
25        let insert: Option<T> = if (&self.inner.somes).last().map(|x| x.eq(&item)) == Some(true) {
26            None
27        } else {
28            Some(item)
29        };
30        self.inner.push(insert);
31    }
32}
33
34impl<TC, CC, VC: Len, WC: IndexAs<u64>> Len for Repeats<TC, CC, VC, WC> {
35    #[inline(always)] fn len(&self) -> usize { self.inner.len() }
36}
37
38impl<TC: Index, CC: IndexAs<u64> + Len, VC: IndexAs<u64> + Len, WC: IndexAs<u64>> Index for Repeats<TC, CC, VC, WC> {
39    type Ref = TC::Ref;
40    #[inline(always)] fn get(&self, index: usize) -> Self::Ref {
41        match self.inner.get(index) {
42            Some(item) => item,
43            None => {
44                let pos = self.inner.indexes.rank(index) - 1;
45                self.inner.somes.get(pos)
46            },
47        }
48    }
49}
50
51impl<'a, TC> Index for &'a Repeats<TC>
52where
53    &'a TC: Index,
54{
55    type Ref = <&'a TC as Index>::Ref;
56    #[inline(always)] fn get(&self, index: usize) -> Self::Ref {
57        match (&self.inner).get(index) {
58            Some(item) => item,
59            None => {
60                let pos = self.inner.indexes.rank(index) - 1;
61                (&self.inner.somes).get(pos)
62            },
63        }
64    }
65}
66
67impl<TC: Borrow> Borrow for Repeats<TC> {
68    type Ref<'a> = TC::Ref<'a> where TC: 'a;
69    type Borrowed<'a> = Repeats<TC::Borrowed<'a>, &'a [u64], &'a [u64], &'a [u64]> where TC: 'a;
70    #[inline(always)]
71    fn borrow<'a>(&'a self) -> Self::Borrowed<'a> {
72        Repeats { inner: self.inner.borrow() }
73    }
74    #[inline(always)]
75    fn reborrow<'b, 'a: 'b>(thing: Self::Borrowed<'a>) -> Self::Borrowed<'b> where TC: 'a {
76        Repeats { inner: Options::<TC>::reborrow(thing.inner) }
77    }
78    #[inline(always)]
79    fn reborrow_ref<'b, 'a: 'b>(thing: Self::Ref<'a>) -> Self::Ref<'b> where Self: 'a {
80        TC::reborrow_ref(thing)
81    }
82}
83
84impl<TC: Container> Container for Repeats<TC>
85where
86    for<'a> &'a TC: Index,
87    for<'a> TC::Ref<'a>: PartialEq,
88    for<'a, 'b> <&'a TC as Index>::Ref: PartialEq<TC::Ref<'b>>,
89{
90    fn extend_from_self(&mut self, other: Self::Borrowed<'_>, range: core::ops::Range<usize>) {
91        if !range.is_empty() {
92            // Push the first element, resolving any `None` to its actual value.
93            self.push(other.get(range.start));
94            // The remaining elements can be bulk-copied from the inner `Options`,
95            // as any `None` now has a preceding `Some` to reference.
96            if range.start + 1 < range.end {
97                self.inner.extend_from_self(other.inner, range.start + 1 .. range.end);
98            }
99        }
100    }
101
102    fn reserve_for<'a, I>(&mut self, selves: I) where Self: 'a, I: Iterator<Item = Self::Borrowed<'a>> + Clone {
103        self.inner.somes.reserve_for(selves.map(|x| x.inner.somes));
104    }
105}
106
107impl<TC: Clear> Clear for Repeats<TC> {
108    fn clear(&mut self) {
109        self.inner.clear();
110    }
111}
112
113impl<'a, TC: crate::AsBytes<'a>, CC: crate::AsBytes<'a>, VC: crate::AsBytes<'a>> crate::AsBytes<'a> for Repeats<TC, CC, VC, &'a [u64]> {
114    const SLICE_COUNT: usize = <Options<TC, CC, VC, &'a [u64]> as crate::AsBytes<'a>>::SLICE_COUNT;
115    #[inline]
116    fn get_byte_slice(&self, index: usize) -> (u64, &'a [u8]) {
117        self.inner.get_byte_slice(index)
118    }
119}
120
121impl<'a, TC: crate::FromBytes<'a>, CC: crate::FromBytes<'a>, VC: crate::FromBytes<'a>> crate::FromBytes<'a> for Repeats<TC, CC, VC, &'a [u64]> {
122    const SLICE_COUNT: usize = <Options<TC, CC, VC, &'a [u64]>>::SLICE_COUNT;
123    #[inline(always)]
124    fn from_bytes(bytes: &mut impl Iterator<Item=&'a [u8]>) -> Self {
125        Self { inner: crate::FromBytes::from_bytes(bytes) }
126    }
127    #[inline(always)]
128    fn from_store(store: &crate::bytes::indexed::DecodedStore<'a>, offset: &mut usize) -> Self {
129        Self { inner: crate::FromBytes::from_store(store, offset) }
130    }
131    fn element_sizes(sizes: &mut Vec<usize>) -> Result<(), String> {
132        <Options<TC, CC, VC, &'a [u64]>>::element_sizes(sizes)
133    }
134}
135
136#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
137#[derive(Copy, Clone, Debug, Default, PartialEq)]
138pub struct Lookbacks<TC, VC = Vec<u8>, CC=Vec<u64>, RC=Vec<u64>, WC=[u64; 2], const N: u8 = 255> {
139    /// Ok(x) encodes a value, and Err(y) indicates a value `y` back.
140    pub inner: Results<TC, VC, CC, RC, WC>,
141}
142
143impl<T: PartialEq, TC: Push<T> + Len, VC: Push<u8>, const N: u8> Push<T> for Lookbacks<TC, VC, Vec<u64>, Vec<u64>, [u64; 2], N>
144where
145    for<'a> &'a TC: Index,
146    for<'a> <&'a TC as Index>::Ref : PartialEq<T>,
147{
148    #[inline]
149    fn push(&mut self, item: T) {
150        // Look backwards through (0 .. N) to look for a matching value.
151        let oks_len = self.inner.oks.len();
152        let find = (0u8 .. N).take(self.inner.oks.len()).find(|i| (&self.inner.oks).get(oks_len - (*i as usize) - 1) == item);
153        let insert: Result<T, u8> = if let Some(back) = find { Err(back) } else { Ok(item) };
154        self.inner.push(insert);
155    }
156}
157
158impl<TC, VC, CC, RC: Len, WC: IndexAs<u64>, const N: u8> Len for Lookbacks<TC, VC, CC, RC, WC, N> {
159    #[inline(always)] fn len(&self) -> usize { self.inner.len() }
160}
161
162impl<TC: Index, VC: IndexAs<u8>, CC: IndexAs<u64> + Len, RC: IndexAs<u64> + Len, WC: IndexAs<u64>, const N: u8> Index for Lookbacks<TC, VC, CC, RC, WC, N> {
163    type Ref = TC::Ref;
164    #[inline(always)] fn get(&self, index: usize) -> Self::Ref {
165        let rank = self.inner.indexes.rank(index);
166        if self.inner.indexes.get(index) {
167            self.inner.oks.get(rank)
168        } else {
169            let back: u8 = self.inner.errs.index_as(index - rank);
170            self.inner.oks.get(rank - 1 - (back as usize))
171        }
172    }
173}
174
175impl<'a, TC, const N: u8> Index for &'a Lookbacks<TC, Vec<u8>, Vec<u64>, Vec<u64>, [u64; 2], N>
176where
177    &'a TC: Index,
178{
179    type Ref = <&'a TC as Index>::Ref;
180    #[inline(always)] fn get(&self, index: usize) -> Self::Ref {
181        let rank = self.inner.indexes.rank(index);
182        if self.inner.indexes.get(index) {
183            (&self.inner.oks).get(rank)
184        } else {
185            let back: u8 = self.inner.errs.index_as(index - rank);
186            (&self.inner.oks).get(rank - 1 - (back as usize))
187        }
188    }
189}
190
191impl<TC: Borrow, const N: u8> Borrow for Lookbacks<TC, Vec<u8>, Vec<u64>, Vec<u64>, [u64; 2], N> {
192    type Ref<'a> = TC::Ref<'a> where TC: 'a;
193    type Borrowed<'a> = Lookbacks<TC::Borrowed<'a>, &'a [u8], &'a [u64], &'a [u64], &'a [u64], N> where TC: 'a;
194    #[inline(always)]
195    fn borrow<'a>(&'a self) -> Self::Borrowed<'a> {
196        Lookbacks { inner: self.inner.borrow() }
197    }
198    #[inline(always)]
199    fn reborrow<'b, 'a: 'b>(thing: Self::Borrowed<'a>) -> Self::Borrowed<'b> where TC: 'a {
200        Lookbacks { inner: Results::<TC, Vec<u8>>::reborrow(thing.inner) }
201    }
202    #[inline(always)]
203    fn reborrow_ref<'b, 'a: 'b>(thing: Self::Ref<'a>) -> Self::Ref<'b> where Self: 'a {
204        TC::reborrow_ref(thing)
205    }
206}
207
208impl<TC: Container, const N: u8> Container for Lookbacks<TC, Vec<u8>, Vec<u64>, Vec<u64>, [u64; 2], N>
209where
210    for<'a> &'a TC: Index,
211    for<'a> TC::Ref<'a>: PartialEq,
212    for<'a, 'b> <&'a TC as Index>::Ref: PartialEq<TC::Ref<'b>>,
213{
214    // Lookback offsets are relative to oks positions, so bulk-copying a subrange
215    // would break Err(n) references that point outside the range. Use the default
216    // implementation which resolves each element via `get()` and re-pushes.
217
218    fn reserve_for<'a, I>(&mut self, selves: I) where Self: 'a, I: Iterator<Item = Self::Borrowed<'a>> + Clone {
219        self.inner.oks.reserve_for(selves.clone().map(|x| x.inner.oks));
220        self.inner.errs.reserve_for(selves.map(|x| x.inner.errs));
221    }
222}
223
224impl<TC: Clear, const N: u8> Clear for Lookbacks<TC, Vec<u8>, Vec<u64>, Vec<u64>, [u64; 2], N> {
225    fn clear(&mut self) {
226        self.inner.clear();
227    }
228}
229
230impl<'a, TC: crate::AsBytes<'a>, VC: crate::AsBytes<'a>, CC: crate::AsBytes<'a>, RC: crate::AsBytes<'a>> crate::AsBytes<'a> for Lookbacks<TC, VC, CC, RC, &'a [u64]> {
231    const SLICE_COUNT: usize = <Results<TC, VC, CC, RC, &'a [u64]> as crate::AsBytes<'a>>::SLICE_COUNT;
232    #[inline]
233    fn get_byte_slice(&self, index: usize) -> (u64, &'a [u8]) {
234        self.inner.get_byte_slice(index)
235    }
236}
237
238impl<'a, TC: crate::FromBytes<'a>, VC: crate::FromBytes<'a>, CC: crate::FromBytes<'a>, RC: crate::FromBytes<'a>> crate::FromBytes<'a> for Lookbacks<TC, VC, CC, RC, &'a [u64]> {
239    const SLICE_COUNT: usize = <Results<TC, VC, CC, RC, &'a [u64]>>::SLICE_COUNT;
240    #[inline(always)]
241    fn from_bytes(bytes: &mut impl Iterator<Item=&'a [u8]>) -> Self {
242        Self { inner: crate::FromBytes::from_bytes(bytes) }
243    }
244    #[inline(always)]
245    fn from_store(store: &crate::bytes::indexed::DecodedStore<'a>, offset: &mut usize) -> Self {
246        Self { inner: crate::FromBytes::from_store(store, offset) }
247    }
248    fn element_sizes(sizes: &mut Vec<usize>) -> Result<(), String> {
249        <Results<TC, VC, CC, RC, &'a [u64]>>::element_sizes(sizes)
250    }
251}
252
253#[cfg(test)]
254mod test {
255
256    use alloc::vec::Vec;
257    use crate::common::{Push, Index, Len, Clear};
258    use crate::{Borrow, Container, AsBytes, FromBytes};
259    use crate::bytes::stash::Stash;
260    use super::{Repeats, Lookbacks};
261
262    /// Helper to populate a `Repeats<Vec<u64>>` from a slice.
263    fn repeats_from(values: &[u64]) -> Repeats<Vec<u64>> {
264        let mut repeats: Repeats<Vec<u64>> = Default::default();
265        for v in values {
266            repeats.push(v);
267        }
268        repeats
269    }
270
271    #[test]
272    fn push_and_index() {
273        let repeats = repeats_from(&[1, 1, 2, 2, 1]);
274
275        assert_eq!(repeats.len(), 5);
276        assert_eq!((&repeats).get(0), 1);
277        assert_eq!((&repeats).get(1), 1);
278        assert_eq!((&repeats).get(2), 2);
279        assert_eq!((&repeats).get(3), 2);
280        assert_eq!((&repeats).get(4), 1);
281
282        // Verify compression: only 3 distinct values stored (1, 2, 1).
283        assert_eq!(repeats.inner.somes.len(), 3);
284    }
285
286    #[test]
287    fn borrow_and_index() {
288        let mut repeats: Repeats<Vec<u64>> = Default::default();
289        for i in 0..50u64 {
290            repeats.push(&i);
291            repeats.push(&i); // repeat
292        }
293
294        assert_eq!(repeats.len(), 100);
295
296        let borrowed = repeats.borrow();
297        assert_eq!(borrowed.len(), 100);
298        for i in 0..50u64 {
299            assert_eq!(*borrowed.get(2 * i as usize), i);
300            assert_eq!(*borrowed.get(2 * i as usize + 1), i);
301        }
302    }
303
304    #[test]
305    fn ref_index() {
306        let repeats = repeats_from(&[10, 10, 20]);
307
308        assert_eq!((&repeats).get(0), 10u64);
309        assert_eq!((&repeats).get(1), 10u64);
310        assert_eq!((&repeats).get(2), 20u64);
311    }
312
313    #[test]
314    fn clear() {
315        let mut repeats = repeats_from(&[1, 2]);
316        assert_eq!(repeats.len(), 2);
317
318        repeats.clear();
319        assert_eq!(repeats.len(), 0);
320
321        repeats.push(&3u64);
322        assert_eq!(repeats.len(), 1);
323        assert_eq!((&repeats).get(0), 3);
324    }
325
326    #[test]
327    fn extend_from_self() {
328        let repeats = repeats_from(&[1, 1, 2, 3, 3]);
329
330        let mut dest: Repeats<Vec<u64>> = Default::default();
331        dest.extend_from_self(repeats.borrow(), 1..4);
332        assert_eq!(dest.len(), 3);
333        assert_eq!(*dest.borrow().get(0), 1);
334        assert_eq!(*dest.borrow().get(1), 2);
335        assert_eq!(*dest.borrow().get(2), 3);
336    }
337
338    #[test]
339    fn as_from_bytes() {
340        let mut repeats: Repeats<Vec<u64>> = Default::default();
341        for i in 0..100u64 {
342            repeats.push(&i);
343            repeats.push(&i);
344        }
345
346        let borrowed = repeats.borrow();
347        let rebuilt = Repeats::<&[u64], &[u64], &[u64], &[u64]>::from_bytes(
348            &mut borrowed.as_bytes().map(|(_, bytes)| bytes)
349        );
350        assert_eq!(rebuilt.len(), 200);
351        for i in 0..100u64 {
352            assert_eq!(*rebuilt.get(2 * i as usize), i);
353            assert_eq!(*rebuilt.get(2 * i as usize + 1), i);
354        }
355    }
356
357    #[test]
358    fn from_store_round_trip() {
359        let mut repeats: Repeats<Vec<u64>> = Default::default();
360        for i in 0..50u64 {
361            repeats.push(&i);
362            repeats.push(&i);
363        }
364
365        let mut store = Vec::new();
366        crate::bytes::indexed::encode(&mut store, &repeats.borrow());
367        let ds = crate::bytes::indexed::DecodedStore::new(&store);
368        let rebuilt = Repeats::<&[u64], &[u64], &[u64], &[u64]>::from_store(&ds, &mut 0);
369        assert_eq!(rebuilt.len(), 100);
370        for i in 0..50u64 {
371            assert_eq!(*rebuilt.get(2 * i as usize), i);
372            assert_eq!(*rebuilt.get(2 * i as usize + 1), i);
373        }
374    }
375
376    #[test]
377    fn validate_via_stash() {
378        let repeats = repeats_from(&[1, 1, 2, 2, 3]);
379
380        let mut bytes: Vec<u8> = Vec::new();
381        crate::bytes::indexed::write(&mut bytes, &repeats.borrow()).unwrap();
382        let stash: Stash<Repeats<Vec<u64>>, Vec<u8>> =
383            Stash::try_from_bytes(bytes).expect("Repeats<Vec<u64>> should validate");
384        let borrowed = stash.borrow();
385        assert_eq!(borrowed.len(), 5);
386        assert_eq!(*borrowed.get(0), 1);
387        assert_eq!(*borrowed.get(1), 1);
388        assert_eq!(*borrowed.get(2), 2);
389        assert_eq!(*borrowed.get(3), 2);
390        assert_eq!(*borrowed.get(4), 3);
391    }
392
393    #[test]
394    fn all_repeats() {
395        let mut repeats: Repeats<Vec<u64>> = Default::default();
396        for _ in 0..100 {
397            repeats.push(&42u64);
398        }
399        assert_eq!(repeats.len(), 100);
400        // Only one distinct value stored.
401        assert_eq!(repeats.inner.somes.len(), 1);
402
403        let borrowed = repeats.borrow();
404        for i in 0..100 {
405            assert_eq!(*borrowed.get(i), 42);
406        }
407    }
408
409    #[test]
410    fn no_repeats() {
411        let mut repeats: Repeats<Vec<u64>> = Default::default();
412        for i in 0..100u64 {
413            repeats.push(&i);
414        }
415        assert_eq!(repeats.len(), 100);
416        // Every value is distinct.
417        assert_eq!(repeats.inner.somes.len(), 100);
418
419        let borrowed = repeats.borrow();
420        for i in 0..100u64 {
421            assert_eq!(*borrowed.get(i as usize), i);
422        }
423    }
424
425    // --- Lookbacks tests ---
426
427    /// Helper to populate a `Lookbacks<Vec<u64>>` from a slice.
428    fn lookbacks_from(values: &[u64]) -> Lookbacks<Vec<u64>> {
429        let mut lookbacks: Lookbacks<Vec<u64>> = Default::default();
430        for v in values {
431            lookbacks.push(v);
432        }
433        lookbacks
434    }
435
436    #[test]
437    fn lookbacks_push_and_index() {
438        let lookbacks = lookbacks_from(&[10, 20, 10, 30, 20]);
439
440        assert_eq!(lookbacks.len(), 5);
441        assert_eq!((&lookbacks).get(0), 10);
442        assert_eq!((&lookbacks).get(1), 20);
443        assert_eq!((&lookbacks).get(2), 10);
444        assert_eq!((&lookbacks).get(3), 30);
445        assert_eq!((&lookbacks).get(4), 20);
446
447        // Values 10 and 20 at indices 2 and 4 should be lookbacks, not new oks.
448        assert_eq!(lookbacks.inner.oks.len(), 3);
449    }
450
451    #[test]
452    fn lookbacks_borrow_and_index() {
453        let mut lookbacks: Lookbacks<Vec<u64>> = Default::default();
454        for i in 0..50u64 {
455            lookbacks.push(&i);
456            lookbacks.push(&i); // lookback
457        }
458
459        assert_eq!(lookbacks.len(), 100);
460
461        let borrowed = lookbacks.borrow();
462        assert_eq!(borrowed.len(), 100);
463        for i in 0..50u64 {
464            assert_eq!(*borrowed.get(2 * i as usize), i);
465            assert_eq!(*borrowed.get(2 * i as usize + 1), i);
466        }
467    }
468
469    #[test]
470    fn lookbacks_clear() {
471        let mut lookbacks = lookbacks_from(&[1, 2]);
472        assert_eq!(lookbacks.len(), 2);
473
474        lookbacks.clear();
475        assert_eq!(lookbacks.len(), 0);
476
477        lookbacks.push(&3u64);
478        assert_eq!(lookbacks.len(), 1);
479        assert_eq!((&lookbacks).get(0), 3);
480    }
481
482    #[test]
483    fn lookbacks_extend_from_self() {
484        let lookbacks = lookbacks_from(&[10, 20, 30, 40, 50]);
485
486        let mut dest: Lookbacks<Vec<u64>> = Default::default();
487        dest.extend_from_self(lookbacks.borrow(), 1..4);
488        assert_eq!(dest.len(), 3);
489        assert_eq!(*dest.borrow().get(0), 20);
490        assert_eq!(*dest.borrow().get(1), 30);
491        assert_eq!(*dest.borrow().get(2), 40);
492    }
493
494    #[test]
495    fn lookbacks_as_from_bytes() {
496        let mut lookbacks: Lookbacks<Vec<u64>> = Default::default();
497        for i in 0..100u64 {
498            lookbacks.push(&i);
499            lookbacks.push(&i);
500        }
501
502        let borrowed = lookbacks.borrow();
503        let rebuilt = Lookbacks::<&[u64], &[u8], &[u64], &[u64], &[u64]>::from_bytes(
504            &mut borrowed.as_bytes().map(|(_, bytes)| bytes)
505        );
506        assert_eq!(rebuilt.len(), 200);
507        for i in 0..100u64 {
508            assert_eq!(*rebuilt.get(2 * i as usize), i);
509            assert_eq!(*rebuilt.get(2 * i as usize + 1), i);
510        }
511    }
512
513    #[test]
514    fn lookbacks_from_store_round_trip() {
515        let mut lookbacks: Lookbacks<Vec<u64>> = Default::default();
516        for i in 0..50u64 {
517            lookbacks.push(&i);
518            lookbacks.push(&i);
519        }
520
521        let mut store = Vec::new();
522        crate::bytes::indexed::encode(&mut store, &lookbacks.borrow());
523        let ds = crate::bytes::indexed::DecodedStore::new(&store);
524        let rebuilt = Lookbacks::<&[u64], &[u8], &[u64], &[u64], &[u64]>::from_store(&ds, &mut 0);
525        assert_eq!(rebuilt.len(), 100);
526        for i in 0..50u64 {
527            assert_eq!(*rebuilt.get(2 * i as usize), i);
528            assert_eq!(*rebuilt.get(2 * i as usize + 1), i);
529        }
530    }
531
532    #[test]
533    fn lookbacks_validate_via_stash() {
534        let lookbacks = lookbacks_from(&[1, 2, 1, 3, 2]);
535
536        let mut bytes: Vec<u8> = Vec::new();
537        crate::bytes::indexed::write(&mut bytes, &lookbacks.borrow()).unwrap();
538        let stash: Stash<Lookbacks<Vec<u64>>, Vec<u8>> =
539            Stash::try_from_bytes(bytes).expect("Lookbacks<Vec<u64>> should validate");
540        let borrowed = stash.borrow();
541        assert_eq!(borrowed.len(), 5);
542        assert_eq!(*borrowed.get(0), 1);
543        assert_eq!(*borrowed.get(1), 2);
544        assert_eq!(*borrowed.get(2), 1);
545        assert_eq!(*borrowed.get(3), 3);
546        assert_eq!(*borrowed.get(4), 2);
547    }
548
549    #[test]
550    fn lookbacks_all_same() {
551        let mut lookbacks: Lookbacks<Vec<u64>> = Default::default();
552        for _ in 0..100 {
553            lookbacks.push(&42u64);
554        }
555        assert_eq!(lookbacks.len(), 100);
556        // Only the first value is stored as Ok; rest are Err lookbacks.
557        assert_eq!(lookbacks.inner.oks.len(), 1);
558
559        let borrowed = lookbacks.borrow();
560        for i in 0..100 {
561            assert_eq!(*borrowed.get(i), 42);
562        }
563    }
564
565    #[test]
566    fn lookbacks_no_matches() {
567        let mut lookbacks: Lookbacks<Vec<u64>> = Default::default();
568        for i in 0..100u64 {
569            lookbacks.push(&(i * 1000)); // all distinct, spaced far apart
570        }
571        assert_eq!(lookbacks.len(), 100);
572        // Every value is unique; all stored as Ok.
573        assert_eq!(lookbacks.inner.oks.len(), 100);
574
575        let borrowed = lookbacks.borrow();
576        for i in 0..100u64 {
577            assert_eq!(*borrowed.get(i as usize), i * 1000);
578        }
579    }
580}
columnar/lookback.rs

columnar/
lookback.rs
