columnar/
sums.rs

1//! Containers for enumerations ("sum types") that store variants separately.
2//!
3//! The main work of these types is storing a discriminant and index efficiently,
4//! as containers for each of the variant types can hold the actual data.
5
6/// Stores for maintaining discriminants, and associated sequential indexes.
7///
8/// The sequential indexes are not explicitly maintained, but are supported
9/// by a `rank(index)` function that indicates how many of a certain variant
10/// precede the given index. While this could potentially be done with a scan
11/// of all preceding discriminants, the stores maintain running accumulations
12/// that make the operation constant time (using additional amortized memory).
13pub mod rank_select {
14
15    use crate::primitive::Bools;
16    use crate::common::index::CopyAs;
17    use crate::{Borrow, Len, Index, IndexAs, Push, Clear, HeapSize};
18
19    /// A store for maintaining `Vec<bool>` with fast `rank` and `select` access.
20    ///
21    /// The design is to have `u64` running counts for each block of 1024 bits,
22    /// which are roughly the size of a cache line. This is roughly 6% overhead,
23    /// above the bits themselves, which seems pretty solid.
24    #[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
25    #[derive(Copy, Clone, Debug, Default, PartialEq)]
26    pub struct RankSelect<CC = Vec<u64>, VC = Vec<u64>, WC = u64> {
27        /// Counts of the number of cumulative set (true) bits, *after* each block of 1024 bits.
28        pub counts: CC,
29        /// The bits themselves.
30        pub values: Bools<VC, WC>,
31    }
32
33    impl<CC: crate::common::BorrowIndexAs<u64>, VC: crate::common::BorrowIndexAs<u64>> RankSelect<CC, VC> {
34        #[inline(always)]
35        pub fn borrow<'a>(&'a self) -> RankSelect<CC::Borrowed<'a>, VC::Borrowed<'a>, &'a u64> {
36            RankSelect {
37                counts: self.counts.borrow(),
38                values: self.values.borrow(),
39            }
40        }
41        #[inline(always)]
42        pub fn reborrow<'b, 'a: 'b>(thing: RankSelect<CC::Borrowed<'a>, VC::Borrowed<'a>, &'a u64>) -> RankSelect<CC::Borrowed<'b>, VC::Borrowed<'b>, &'b u64> {
43            RankSelect {
44                counts: CC::reborrow(thing.counts),
45                values: Bools::<VC, u64>::reborrow(thing.values),
46            }
47        }
48    }
49
50    impl<'a, CC: crate::AsBytes<'a>, VC: crate::AsBytes<'a>> crate::AsBytes<'a> for RankSelect<CC, VC, &'a u64> {
51        #[inline(always)]
52        fn as_bytes(&self) -> impl Iterator<Item=(u64, &'a [u8])> {
53            crate::chain(self.counts.as_bytes(), self.values.as_bytes())
54        }
55    }
56    impl<'a, CC: crate::FromBytes<'a>, VC: crate::FromBytes<'a>> crate::FromBytes<'a> for RankSelect<CC, VC, &'a u64> {
57        #[inline(always)]
58        fn from_bytes(bytes: &mut impl Iterator<Item=&'a [u8]>) -> Self {
59            Self {
60                counts: crate::FromBytes::from_bytes(bytes),
61                values: crate::FromBytes::from_bytes(bytes),
62            }
63        }
64    }
65
66
67    impl<CC, VC: Len + IndexAs<u64>, WC: CopyAs<u64>> RankSelect<CC, VC, WC> {
68        #[inline(always)]
69        pub fn get(&self, index: usize) -> bool {
70            Index::get(&self.values, index)
71        }
72    }
73    impl<CC: Len + IndexAs<u64>, VC: Len + IndexAs<u64>, WC: CopyAs<u64>> RankSelect<CC, VC, WC> {
74        /// The number of set bits *strictly* preceding `index`.
75        ///
76        /// This number is accumulated first by reading out of `self.counts` at the correct position,
77        /// then by summing the ones in strictly prior `u64` entries, then by counting the ones in the
78        /// masked `u64` in which the bit lives.
79        pub fn rank(&self, index: usize) -> usize {
80            let bit = index % 64;
81            let block = index / 64;
82            let chunk = block / 16;
83            let mut count = if chunk > 0 { self.counts.index_as(chunk - 1) as usize } else { 0 };
84            for pos in (16 * chunk) .. block {
85                count += self.values.values.index_as(pos).count_ones() as usize;
86            }
87            // TODO: Panic if out of bounds?
88            let intra_word = if block == self.values.values.len() { self.values.last_word.copy_as() } else { self.values.values.index_as(block) };
89            count += (intra_word & ((1 << bit) - 1)).count_ones() as usize;
90            count
91        }
92        /// The index of the `rank`th set bit, should one exist.
93        pub fn select(&self, rank: u64) -> Option<usize> {
94            let mut chunk = 0;
95            // Step one is to find the position in `counts` where we go from `rank` to `rank + 1`.
96            // The position we are looking for is within that chunk of bits.
97            // TODO: Binary search is likely better at many scales. Rust's binary search is .. not helpful with ties.
98            while chunk < self.counts.len() && self.counts.index_as(chunk) <= rank {
99                chunk += 1;
100            }
101            let mut count = if chunk < self.counts.len() { self.counts.index_as(chunk) } else { 0 };
102            // Step two is to find the position within that chunk where the `rank`th bit is.
103            let mut block = 16 * chunk;
104            while block < self.values.values.len() && count + (self.values.values.index_as(block).count_ones() as u64) <= rank {
105                count += self.values.values.index_as(block).count_ones() as u64;
106                block += 1;
107            }
108            // Step three is to search the last word for the location, or return `None` if we run out of bits.
109            let last_bits = if block == self.values.values.len() { self.values.last_bits.copy_as() as usize } else { 64 };
110            let last_word = if block == self.values.values.len() { self.values.last_word.copy_as() } else { self.values.values.index_as(block) };
111            for shift in 0 .. last_bits {
112                if ((last_word >> shift) & 0x01 == 0x01) && count + 1 == rank {
113                    return Some(64 * block + shift);
114                }
115                count += (last_word >> shift) & 0x01;
116            }
117
118            None
119        }
120    }
121
122    impl<CC, VC: Len, WC: CopyAs<u64>> RankSelect<CC, VC, WC> {
123        pub fn len(&self) -> usize {
124            self.values.len()
125        }
126    }
127
128    // This implementation probably only works for `Vec<u64>` and `Vec<u64>`, but we could fix that.
129    // Partly, it's hard to name the `Index` flavor that allows one to get back a `u64`.
130    impl<CC: for<'a> Push<&'a u64> + Len + IndexAs<u64>, VC: for<'a> Push<&'a u64> + Len + IndexAs<u64>> RankSelect<CC, VC> {
131        #[inline]
132        pub fn push(&mut self, bit: bool) {
133            self.values.push(&bit);
134            while self.counts.len() < self.values.len() / 1024 {
135                let mut count = self.counts.last().unwrap_or(0);
136                let lower = 16 * self.counts.len();
137                let upper = lower + 16;
138                for i in lower .. upper {
139                    count += self.values.values.index_as(i).count_ones() as u64;
140                }
141                self.counts.push(&count);
142            }
143        }
144    }
145    impl<CC: Clear, VC: Clear> Clear for RankSelect<CC, VC> {
146        fn clear(&mut self) {
147            self.counts.clear();
148            self.values.clear();
149        }
150    }
151    impl<CC: HeapSize, VC: HeapSize> HeapSize for RankSelect<CC, VC> {
152        fn heap_size(&self) -> (usize, usize) {
153            let (l0, c0) = self.counts.heap_size();
154            let (l1, c1) = self.values.heap_size();
155            (l0 + l1, c0 + c1)
156        }
157    }
158}
159
160pub mod result {
161
162    use crate::common::index::CopyAs;
163    use crate::{Clear, Columnar, Container, Len, IndexMut, Index, IndexAs, Push, HeapSize, Borrow};
164    use crate::RankSelect;
165
166    #[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
167    #[derive(Copy, Clone, Debug, Default, PartialEq)]
168    pub struct Results<SC, TC, CC=Vec<u64>, VC=Vec<u64>, WC=u64> {
169        /// Bits set to `true` correspond to `Ok` variants.
170        pub indexes: RankSelect<CC, VC, WC>,
171        pub oks: SC,
172        pub errs: TC,
173    }
174
175    impl<S: Columnar, T: Columnar> Columnar for Result<S, T> {
176        fn copy_from<'a>(&mut self, other: crate::Ref<'a, Self>) {
177            match (&mut *self, other) {
178                (Ok(x), Ok(y)) => x.copy_from(y),
179                (Err(x), Err(y)) => x.copy_from(y),
180                (_, other) => { *self = Self::into_owned(other); },
181            }
182        }
183        fn into_owned<'a>(other: crate::Ref<'a, Self>) -> Self {
184            match other {
185                Ok(y) => Ok(S::into_owned(y)),
186                Err(y) => Err(T::into_owned(y)),
187            }
188        }
189        type Container = Results<S::Container, T::Container>;
190    }
191
192    impl<SC: Borrow, TC: Borrow> Borrow for Results<SC, TC> {
193        type Ref<'a> = Result<SC::Ref<'a>, TC::Ref<'a>> where SC: 'a, TC: 'a;
194        type Borrowed<'a> = Results<SC::Borrowed<'a>, TC::Borrowed<'a>, &'a [u64], &'a [u64], &'a u64> where SC: 'a, TC: 'a;
195        fn borrow<'a>(&'a self) -> Self::Borrowed<'a> {
196            Results {
197                indexes: self.indexes.borrow(),
198                oks: self.oks.borrow(),
199                errs: self.errs.borrow(),
200            }
201        }
202        #[inline(always)]
203        fn reborrow<'b, 'a: 'b>(thing: Self::Borrowed<'a>) -> Self::Borrowed<'b> where SC: 'a, TC: 'a {
204            Results {
205                indexes: RankSelect::<Vec<u64>, Vec<u64>>::reborrow(thing.indexes),
206                oks: SC::reborrow(thing.oks),
207                errs: TC::reborrow(thing.errs),
208            }
209        }
210        #[inline(always)]
211        fn reborrow_ref<'b, 'a: 'b>(thing: Self::Ref<'a>) -> Self::Ref<'b> where Self: 'a {
212            match thing {
213                Ok(y) => Ok(SC::reborrow_ref(y)),
214                Err(y) => Err(TC::reborrow_ref(y)),
215            }
216        }
217    }
218
219    impl<SC: Container, TC: Container> Container for Results<SC, TC> {
220        #[inline(always)]
221        fn extend_from_self(&mut self, other: Self::Borrowed<'_>, range: std::ops::Range<usize>) {
222            if !range.is_empty() {
223                // Starting offsets of each variant in `other`.
224                let oks_start = other.indexes.rank(range.start);
225                let errs_start = range.start - oks_start;
226
227                // Count the number of `Ok` and `Err` variants as we push, to determine the range.
228                // TODO: This could probably be `popcnt` somehow.
229                let mut oks = 0;
230                for index in range.clone() {
231                    let bit = other.indexes.get(index);
232                    self.indexes.push(bit);
233                    if bit { oks += 1; }
234                }
235                let errs = range.len() - oks;
236
237                self.oks.extend_from_self(other.oks, oks_start .. oks_start + oks);
238                self.errs.extend_from_self(other.errs, errs_start .. errs_start + errs);
239            }
240        }
241
242        fn reserve_for<'a, I>(&mut self, selves: I) where Self: 'a, I: Iterator<Item = Self::Borrowed<'a>> + Clone {
243            // TODO: reserve room in `self.indexes`.
244            self.oks.reserve_for(selves.clone().map(|x| x.oks));
245            self.errs.reserve_for(selves.map(|x| x.errs));
246        }
247    }
248
249    impl<'a, SC: crate::AsBytes<'a>, TC: crate::AsBytes<'a>, CC: crate::AsBytes<'a>, VC: crate::AsBytes<'a>> crate::AsBytes<'a> for Results<SC, TC, CC, VC, &'a u64> {
250        #[inline(always)]
251        fn as_bytes(&self) -> impl Iterator<Item=(u64, &'a [u8])> {
252            let iter = self.indexes.as_bytes();
253            let iter = crate::chain(iter, self.oks.as_bytes());
254            crate::chain(iter, self.errs.as_bytes())
255        }
256    }
257    impl<'a, SC: crate::FromBytes<'a>, TC: crate::FromBytes<'a>, CC: crate::FromBytes<'a>, VC: crate::FromBytes<'a>> crate::FromBytes<'a> for Results<SC, TC, CC, VC, &'a u64> {
258        #[inline(always)]
259        fn from_bytes(bytes: &mut impl Iterator<Item=&'a [u8]>) -> Self {
260            Self {
261                indexes: crate::FromBytes::from_bytes(bytes),
262                oks: crate::FromBytes::from_bytes(bytes),
263                errs: crate::FromBytes::from_bytes(bytes),
264            }
265        }
266    }
267
268    impl<SC, TC, CC, VC: Len, WC: CopyAs<u64>> Len for Results<SC, TC, CC, VC, WC> {
269        #[inline(always)] fn len(&self) -> usize { self.indexes.len() }
270    }
271
272    impl<SC, TC, CC, VC, WC> Index for Results<SC, TC, CC, VC, WC>
273    where
274        SC: Index,
275        TC: Index,
276        CC: IndexAs<u64> + Len,
277        VC: IndexAs<u64> + Len,
278        WC: CopyAs<u64>,
279    {
280        type Ref = Result<SC::Ref, TC::Ref>;
281        #[inline(always)]
282        fn get(&self, index: usize) -> Self::Ref {
283            if self.indexes.get(index) {
284                Ok(self.oks.get(self.indexes.rank(index)))
285            } else {
286                Err(self.errs.get(index - self.indexes.rank(index)))
287            }
288        }
289    }
290    impl<'a, SC, TC, CC, VC, WC> Index for &'a Results<SC, TC, CC, VC, WC>
291    where
292        &'a SC: Index,
293        &'a TC: Index,
294        CC: IndexAs<u64> + Len,
295        VC: IndexAs<u64> + Len,
296        WC: CopyAs<u64>,
297    {
298        type Ref = Result<<&'a SC as Index>::Ref, <&'a TC as Index>::Ref>;
299        #[inline(always)]
300        fn get(&self, index: usize) -> Self::Ref {
301            if self.indexes.get(index) {
302                Ok((&self.oks).get(self.indexes.rank(index)))
303            } else {
304                Err((&self.errs).get(index - self.indexes.rank(index)))
305            }
306        }
307    }
308
309    // NB: You are not allowed to change the variant, but can change its contents.
310    impl<SC: IndexMut, TC: IndexMut, CC: IndexAs<u64> + Len, VC: IndexAs<u64> + Len> IndexMut for Results<SC, TC, CC, VC> {
311        type IndexMut<'a> = Result<SC::IndexMut<'a>, TC::IndexMut<'a>> where SC: 'a, TC: 'a, CC: 'a, VC: 'a;
312        #[inline(always)]
313        fn get_mut(&mut self, index: usize) -> Self::IndexMut<'_> {
314            if self.indexes.get(index) {
315                Ok(self.oks.get_mut(self.indexes.rank(index)))
316            } else {
317                Err(self.errs.get_mut(index - self.indexes.rank(index)))
318            }
319        }
320    }
321
322    impl<S, SC: Push<S>, T, TC: Push<T>> Push<Result<S, T>> for Results<SC, TC> {
323        #[inline]
324        fn push(&mut self, item: Result<S, T>) {
325            match item {
326                Ok(item) => {
327                    self.indexes.push(true);
328                    self.oks.push(item);
329                }
330                Err(item) => {
331                    self.indexes.push(false);
332                    self.errs.push(item);
333                }
334            }
335        }
336    }
337    impl<'a, S, SC: Push<&'a S>, T, TC: Push<&'a T>> Push<&'a Result<S, T>> for Results<SC, TC> {
338        #[inline]
339        fn push(&mut self, item: &'a Result<S, T>) {
340            match item {
341                Ok(item) => {
342                    self.indexes.push(true);
343                    self.oks.push(item);
344                }
345                Err(item) => {
346                    self.indexes.push(false);
347                    self.errs.push(item);
348                }
349            }
350        }
351    }
352
353    impl<SC: Clear, TC: Clear> Clear for Results<SC, TC> {
354        fn clear(&mut self) {
355            self.indexes.clear();
356            self.oks.clear();
357            self.errs.clear();
358        }
359    }
360
361    impl<SC: HeapSize, TC: HeapSize> HeapSize for Results<SC, TC> {
362        fn heap_size(&self) -> (usize, usize) {
363            let (l0, c0) = self.oks.heap_size();
364            let (l1, c1) = self.errs.heap_size();
365            let (li, ci) = self.indexes.heap_size();
366            (l0 + l1 + li, c0 + c1 + ci)
367        }
368    }
369
370    impl<SC, TC, CC, VC, WC> Results<SC, TC, CC, VC, WC> {
371        /// Returns ok values if no errors exist.
372        pub fn unwrap(self) -> SC where TC: Len {
373            assert!(self.errs.is_empty());
374            self.oks
375        }
376        /// Returns error values if no oks exist.
377        pub fn unwrap_err(self) -> TC where SC: Len {
378            assert!(self.oks.is_empty());
379            self.errs
380        }
381    }
382    #[cfg(test)]
383    mod test {
384        #[test]
385        fn round_trip() {
386
387            use crate::common::{Index, Push, HeapSize, Len};
388
389            let mut column: crate::ContainerOf<Result<u64, u64>> = Default::default();
390            for i in 0..100 {
391                column.push(Ok::<u64, u64>(i));
392                column.push(Err::<u64, u64>(i));
393            }
394
395            assert_eq!(column.len(), 200);
396            assert_eq!(column.heap_size(), (1624, 2080));
397
398            for i in 0..100 {
399                assert_eq!(column.get(2*i+0), Ok(i as u64));
400                assert_eq!(column.get(2*i+1), Err(i as u64));
401            }
402
403            let mut column: crate::ContainerOf<Result<u64, u8>> = Default::default();
404            for i in 0..100 {
405                column.push(Ok::<u64, u8>(i as u64));
406                column.push(Err::<u64, u8>(i as u8));
407            }
408
409            assert_eq!(column.len(), 200);
410            assert_eq!(column.heap_size(), (924, 1184));
411
412            for i in 0..100 {
413                assert_eq!(column.get(2*i+0), Ok(i as u64));
414                assert_eq!(column.get(2*i+1), Err(i as u8));
415            }
416        }
417    }
418}
419
420pub mod option {
421
422    use crate::common::index::CopyAs;
423    use crate::{Clear, Columnar, Container, Len, IndexMut, Index, IndexAs, Push, HeapSize, Borrow};
424    use crate::RankSelect;
425
426#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
427    #[derive(Copy, Clone, Debug, Default, PartialEq)]
428    pub struct Options<TC, CC=Vec<u64>, VC=Vec<u64>, WC=u64> {
429        /// Uses two bits for each item, one to indicate the variant and one (amortized)
430        /// to enable efficient rank determination.
431        pub indexes: RankSelect<CC, VC, WC>,
432        pub somes: TC,
433    }
434
435    impl<T: Columnar> Columnar for Option<T> {
436        fn copy_from<'a>(&mut self, other: crate::Ref<'a, Self>) {
437            match (&mut *self, other) {
438                (Some(x), Some(y)) => { x.copy_from(y); }
439                (_, other) => { *self = Self::into_owned(other); }
440            }
441        }
442        fn into_owned<'a>(other: crate::Ref<'a, Self>) -> Self {
443            other.map(|x| T::into_owned(x))
444        }
445        type Container = Options<T::Container>;
446    }
447
448    impl<TC: Borrow> Borrow for Options<TC> {
449        type Ref<'a> = Option<TC::Ref<'a>> where TC: 'a;
450        type Borrowed<'a> = Options<TC::Borrowed<'a>, &'a [u64], &'a [u64], &'a u64> where TC: 'a;
451        fn borrow<'a>(&'a self) -> Self::Borrowed<'a> {
452            Options {
453                indexes: self.indexes.borrow(),
454                somes: self.somes.borrow(),
455            }
456        }
457        #[inline(always)]
458        fn reborrow<'b, 'a: 'b>(thing: Self::Borrowed<'a>) -> Self::Borrowed<'b> where TC: 'a {
459            Options {
460                indexes: RankSelect::<Vec<u64>, Vec<u64>>::reborrow(thing.indexes),
461                somes: TC::reborrow(thing.somes),
462            }
463        }
464        #[inline(always)]
465        fn reborrow_ref<'b, 'a: 'b>(thing: Self::Ref<'a>) -> Self::Ref<'b> where Self: 'a {
466            thing.map(TC::reborrow_ref)
467        }
468    }
469
470    impl<TC: Container> Container for Options<TC> {
471        #[inline(always)]
472        fn extend_from_self(&mut self, other: Self::Borrowed<'_>, range: std::ops::Range<usize>) {
473            if !range.is_empty() {
474                // Starting offsets of `Some` variants in `other`.
475                let somes_start = other.indexes.rank(range.start);
476
477                // Count the number of `Some` variants as we push, to determine the range.
478                // TODO: This could probably be `popcnt` somehow.
479                let mut somes = 0;
480                for index in range {
481                    let bit = other.indexes.get(index);
482                    self.indexes.push(bit);
483                    if bit { somes += 1; }
484                }
485
486                self.somes.extend_from_self(other.somes, somes_start .. somes_start + somes);
487            }
488        }
489
490        fn reserve_for<'a, I>(&mut self, selves: I) where Self: 'a, I: Iterator<Item = Self::Borrowed<'a>> + Clone {
491            // TODO: reserve room in `self.indexes`.
492            self.somes.reserve_for(selves.map(|x| x.somes));
493        }
494    }
495
496    impl<'a, TC: crate::AsBytes<'a>, CC: crate::AsBytes<'a>, VC: crate::AsBytes<'a>> crate::AsBytes<'a> for Options<TC, CC, VC, &'a u64> {
497        #[inline(always)]
498        fn as_bytes(&self) -> impl Iterator<Item=(u64, &'a [u8])> {
499            crate::chain(self.indexes.as_bytes(), self.somes.as_bytes())
500        }
501    }
502
503    impl <'a, TC: crate::FromBytes<'a>, CC: crate::FromBytes<'a>, VC: crate::FromBytes<'a>> crate::FromBytes<'a> for Options<TC, CC, VC, &'a u64> {
504        #[inline(always)]
505        fn from_bytes(bytes: &mut impl Iterator<Item=&'a [u8]>) -> Self {
506            Self {
507                indexes: crate::FromBytes::from_bytes(bytes),
508                somes: crate::FromBytes::from_bytes(bytes),
509            }
510        }
511    }
512
513    impl<T, CC, VC: Len, WC: CopyAs<u64>> Len for Options<T, CC, VC, WC> {
514        #[inline(always)] fn len(&self) -> usize { self.indexes.len() }
515    }
516
517    impl<TC: Index, CC: IndexAs<u64> + Len, VC: IndexAs<u64> + Len, WC: CopyAs<u64>> Index for Options<TC, CC, VC, WC> {
518        type Ref = Option<TC::Ref>;
519        #[inline(always)]
520        fn get(&self, index: usize) -> Self::Ref {
521            if self.indexes.get(index) {
522                Some(self.somes.get(self.indexes.rank(index)))
523            } else {
524                None
525            }
526        }
527    }
528    impl<'a, TC, CC: IndexAs<u64> + Len, VC: IndexAs<u64> + Len, WC: CopyAs<u64>> Index for &'a Options<TC, CC, VC, WC>
529    where &'a TC: Index
530    {
531        type Ref = Option<<&'a TC as Index>::Ref>;
532        #[inline(always)]
533        fn get(&self, index: usize) -> Self::Ref {
534            if self.indexes.get(index) {
535                Some((&self.somes).get(self.indexes.rank(index)))
536            } else {
537                None
538            }
539        }
540    }
541    impl<TC: IndexMut, CC: IndexAs<u64> + Len, VC: IndexAs<u64> + Len> IndexMut for Options<TC, CC, VC> {
542        type IndexMut<'a> = Option<TC::IndexMut<'a>> where TC: 'a, CC: 'a, VC: 'a;
543        #[inline(always)]
544        fn get_mut(&mut self, index: usize) -> Self::IndexMut<'_> {
545            if self.indexes.get(index) {
546                Some(self.somes.get_mut(self.indexes.rank(index)))
547            } else {
548                None
549            }
550        }
551    }
552
553    impl<T, TC: Push<T> + Len> Push<Option<T>> for Options<TC> {
554        #[inline]
555        fn push(&mut self, item: Option<T>) {
556            match item {
557                Some(item) => {
558                    self.indexes.push(true);
559                    self.somes.push(item);
560                }
561                None => {
562                    self.indexes.push(false);
563                }
564            }
565        }
566    }
567    impl<'a, T, TC: Push<&'a T> + Len> Push<&'a Option<T>> for Options<TC> {
568        #[inline]
569        fn push(&mut self, item: &'a Option<T>) {
570            match item {
571                Some(item) => {
572                    self.indexes.push(true);
573                    self.somes.push(item);
574                }
575                None => {
576                    self.indexes.push(false);
577                }
578            }
579        }
580    }
581
582    impl<TC: Clear> Clear for Options<TC> {
583        fn clear(&mut self) {
584            self.indexes.clear();
585            self.somes.clear();
586        }
587    }
588
589    impl<TC: HeapSize> HeapSize for Options<TC> {
590        fn heap_size(&self) -> (usize, usize) {
591            let (l0, c0) = self.somes.heap_size();
592            let (li, ci) = self.indexes.heap_size();
593            (l0 + li, c0 + ci)
594        }
595    }
596
597    #[cfg(test)]
598    mod test {
599
600        use crate::Columnar;
601        use crate::common::{Index, HeapSize, Len};
602        use crate::Options;
603
604        #[test]
605        fn round_trip_some() {
606            // Type annotation is important to avoid some inference overflow.
607            let store: Options<Vec<i32>> = Columnar::into_columns((0..100).map(Some));
608            assert_eq!(store.len(), 100);
609            assert!((&store).index_iter().zip(0..100).all(|(a, b)| a == Some(&b)));
610            assert_eq!(store.heap_size(), (408, 544));
611        }
612
613        #[test]
614        fn round_trip_none() {
615            let store = Columnar::into_columns((0..100).map(|_x| None::<i32>));
616            assert_eq!(store.len(), 100);
617            let foo = &store;
618            assert!(foo.index_iter().zip(0..100).all(|(a, _b)| a == None));
619            assert_eq!(store.heap_size(), (8, 32));
620        }
621
622        #[test]
623        fn round_trip_mixed() {
624            // Type annotation is important to avoid some inference overflow.
625            let store: Options<Vec<i32>>  = Columnar::into_columns((0..100).map(|x| if x % 2 == 0 { Some(x) } else { None }));
626            assert_eq!(store.len(), 100);
627            assert!((&store).index_iter().zip(0..100).all(|(a, b)| a == if b % 2 == 0 { Some(&b) } else { None }));
628            assert_eq!(store.heap_size(), (208, 288));
629        }
630    }
631}
columnar/sums.rs

columnar/
sums.rs
