simple_sds_sbwt/
bit_vector.rs

1//! An immutable bit array supporting rank, select, and related queries.
2
3use crate::bit_vector::rank_support::RankSupport;
4use crate::bit_vector::select_support::SelectSupport;
5use crate::ops::{BitVec, Rank, Select, SelectZero, PredSucc};
6use crate::raw_vector::{RawVector, AccessRaw, PushRaw};
7use crate::serialize::Serialize;
8use crate::bits;
9
10use std::io::{Error, ErrorKind};
11use std::iter::{FusedIterator, FromIterator};
12use std::{cmp, io, marker};
13
14pub mod rank_support;
15pub mod select_support;
16
17#[cfg(test)]
18mod tests;
19
20//-----------------------------------------------------------------------------
21
22/// An immutable bit array supporting, rank, select, and related queries.
23///
24/// This structure contains [`RawVector`], which is in turn contains [`Vec`].
25/// Because most queries require separate support structures, the bit array itself is immutable.
26/// Conversions between `BitVector` and [`RawVector`] are possible using the [`From`] trait.
27/// The maximum length of the vector is approximately [`usize::MAX`] bits.
28///
29/// Conversions between various [`BitVec`] types are possible using the [`From`] trait.
30///
31/// `BitVector` implements the following `simple_sds` traits:
32/// * Basic functionality: [`BitVec`]
33/// * Queries and operations: [`Rank`], [`Select`], [`PredSucc`], [`SelectZero`]
34/// * Serialization: [`Serialize`]
35///
36/// See [`rank_support`] and [`select_support`] for algorithmic details on rank/select queries.
37/// Predecessor and successor queries depend on both support structures.
38///
39/// The support structures are serialized as [`Option`] and hence may be missing.
40/// When `BitVector` is used as a part of another structure, the user should enable the required support structures after loading.
41/// This makes interoperation with other libraries easier, as the other library only has to serialize the bitvector itself.
42/// Enabling support structures is fast if they were present in the serialized data.
43///
44/// # Examples
45///
46/// ```
47/// use simple_sds_sbwt::bit_vector::BitVector;
48/// use simple_sds_sbwt::ops::{BitVec, Rank, Select, SelectZero, PredSucc};
49/// use simple_sds_sbwt::raw_vector::{RawVector, AccessRaw};
50///
51/// let mut data = RawVector::with_len(137, false);
52/// data.set_bit(1, true); data.set_bit(33, true); data.set_bit(95, true); data.set_bit(123, true);
53/// let mut bv = BitVector::from(data);
54///
55/// // BitVec
56/// assert_eq!(bv.len(), 137);
57/// assert!(!bv.is_empty());
58/// assert_eq!(bv.count_ones(), 4);
59/// assert!(bv.get(33));
60/// assert!(!bv.get(34));
61/// for (index, value) in bv.iter().enumerate() {
62///     assert_eq!(value, bv.get(index));
63/// }
64///
65/// // Rank
66/// bv.enable_rank();
67/// assert!(bv.supports_rank());
68/// assert_eq!(bv.rank(33), 1);
69/// assert_eq!(bv.rank(34), 2);
70/// assert_eq!(bv.rank_zero(65), 63);
71///
72/// // Select
73/// bv.enable_select();
74/// assert!(bv.supports_select());
75/// assert_eq!(bv.select(1), Some(33));
76/// let mut iter = bv.select_iter(2);
77/// assert_eq!(iter.next(), Some((2, 95)));
78/// assert_eq!(iter.next(), Some((3, 123)));
79/// assert!(iter.next().is_none());
80/// let v: Vec<(usize, usize)> = bv.one_iter().collect();
81/// assert_eq!(v, vec![(0, 1), (1, 33), (2, 95), (3, 123)]);
82///
83/// // SelectZero
84/// bv.enable_select_zero();
85/// assert!(bv.supports_select_zero());
86/// assert_eq!(bv.select_zero(2), Some(3));
87/// let v: Vec<(usize, usize)> = bv.zero_iter().take(4).collect();
88/// assert_eq!(v, vec![(0, 0), (1, 2), (2, 3), (3, 4)]);
89///
90/// // PredSucc
91/// bv.enable_pred_succ();
92/// assert!(bv.supports_pred_succ());
93/// assert!(bv.predecessor(0).next().is_none());
94/// assert_eq!(bv.predecessor(1).next(), Some((0, 1)));
95/// assert_eq!(bv.predecessor(2).next(), Some((0, 1)));
96/// assert_eq!(bv.successor(122).next(), Some((3, 123)));
97/// assert_eq!(bv.successor(123).next(), Some((3, 123)));
98/// assert!(bv.successor(124).next().is_none());
99/// ```
100///
101/// # Notes
102///
103/// * `BitVector` never panics from I/O errors.
104#[derive(Clone, Debug, PartialEq, Eq)]
105pub struct BitVector {
106    ones: usize,
107    data: RawVector,
108    rank: Option<RankSupport>,
109    select: Option<SelectSupport<Identity>>,
110    select_zero: Option<SelectSupport<Complement>>,
111}
112
113impl BitVector {
114    /// Returns a copy of the source bitvector as `BitVector`.
115    ///
116    /// The copy is created by iterating over the set bits using [`Select::one_iter`].
117    /// [`From`] implementations from other bitvector types should generally use this function.
118    ///
119    /// # Examples
120    ///
121    /// ```
122    /// use simple_sds_sbwt::bit_vector::BitVector;
123    /// use simple_sds_sbwt::ops::BitVec;
124    /// use std::iter::FromIterator;
125    ///
126    /// let source: Vec<bool> = vec![true, false, true, true, false, true, true, false];
127    /// let bv = BitVector::from_iter(source);
128    /// let copy = BitVector::copy_bit_vec(&bv);
129    /// assert_eq!(copy.len(), bv.len());
130    /// assert_eq!(copy.count_ones(), bv.count_ones());
131    /// ```
132    pub fn copy_bit_vec<'a, T: BitVec<'a> + Select<'a>>(source: &'a T) -> Self {
133        let mut data = RawVector::with_len(source.len(), false);
134        for (_, index) in source.one_iter() {
135            data.set_bit(index, true);
136        }
137        BitVector::from(data)
138    }
139}
140
141//-----------------------------------------------------------------------------
142
143/// A read-only iterator over [`BitVector`].
144///
145/// The type of `Item` is [`bool`].
146/// There are efficient implementations of [`Iterator::nth`] and [`DoubleEndedIterator::nth_back`].
147///
148/// # Examples
149///
150/// ```
151/// use simple_sds_sbwt::bit_vector::BitVector;
152/// use simple_sds_sbwt::ops::BitVec;
153///
154/// let source: Vec<bool> = vec![true, false, true, true, false, true, true, false];
155/// let bv: BitVector = source.iter().cloned().collect();
156/// assert_eq!(bv.iter().len(), source.len());
157/// for (index, value) in bv.iter().enumerate() {
158///     assert_eq!(source[index], value);
159/// }
160/// ```
161#[derive(Clone, Debug)]
162pub struct Iter<'a> {
163    parent: &'a BitVector,
164    // The first index we have not visited.
165    next: usize,
166    // The first index we should not visit.
167    limit: usize,
168}
169
170impl<'a> Iterator for Iter<'a> {
171    type Item = bool;
172
173    fn next(&mut self) -> Option<Self::Item> {
174        if self.next >= self.limit {
175            None
176        } else {
177            let result = Some(self.parent.get(self.next));
178            self.next += 1;
179            result
180        }
181    }
182
183    fn nth(&mut self, n: usize) -> Option<Self::Item> {
184        self.next += cmp::min(n, self.limit - self.next);
185        self.next()
186    }
187
188    #[inline]
189    fn size_hint(&self) -> (usize, Option<usize>) {
190        let remaining = self.limit - self.next;
191        (remaining, Some(remaining))
192    }
193}
194
195impl<'a> DoubleEndedIterator for Iter<'a> {
196    fn next_back(&mut self) -> Option<Self::Item> {
197        if self.next >= self.limit {
198            None
199        } else {
200            self.limit -= 1;
201            Some(self.parent.get(self.limit))
202        }
203    }
204
205    fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
206        self.limit -= cmp::min(n, self.limit - self.next);
207        self.next_back()
208    }
209}
210
211impl<'a> ExactSizeIterator for Iter<'a> {}
212
213impl<'a> FusedIterator for Iter<'a> {}
214
215//-----------------------------------------------------------------------------
216
217impl<'a> BitVec<'a> for BitVector {
218    type Iter = Iter<'a>;
219
220    #[inline]
221    fn len(&self) -> usize {
222        self.data.len()
223    }
224
225    #[inline]
226    fn count_ones(&self) -> usize {
227        self.ones
228    }
229
230    #[inline]
231    fn get(&self, index: usize) -> bool {
232        self.data.bit(index)
233    }
234
235    fn iter(&'a self) -> Self::Iter {
236        Self::Iter {
237            parent: self,
238            next: 0,
239            limit: self.len(),
240        }
241    }
242}
243
244//-----------------------------------------------------------------------------
245
246impl<'a> Rank<'a> for BitVector {
247    fn supports_rank(&self) -> bool {
248        self.rank != None
249    }
250
251    fn enable_rank(&mut self) {
252        if !self.supports_rank() {
253            let rank_support = RankSupport::new(self);
254            self.rank = Some(rank_support);
255        }
256    }
257
258    fn rank(&self, index: usize) -> usize {
259        if index >= self.len() {
260            return self.count_ones();
261        }
262        let rank_support = self.rank.as_ref().unwrap();
263        unsafe { rank_support.rank_unchecked(self, index) }
264    }
265}
266
267//-----------------------------------------------------------------------------
268
269/// An implicit transformation of [`BitVector`] into another vector of the same length.
270///
271/// Types that implement this trait can be used as parameters for [`SelectSupport`] and [`OneIter`].
272pub trait Transformation {
273    /// Reads a bit from the transformed bitvector.
274    ///
275    /// # Arguments
276    ///
277    /// * `parent`: The parent bitvector.
278    /// * `index`: Index in the bit array.
279    ///
280    /// # Panics
281    ///
282    /// May panic if `index` is not a valid offset in the bit array.
283    fn bit(parent: &BitVector, index: usize) -> bool;
284
285    /// Reads a 64-bit word from the transformed bitvector.
286    ///
287    /// # Arguments
288    ///
289    /// * `parent`: The parent bitvector.
290    /// * `index`: Read the word starting at offset `index * 64` of the bit array.
291    ///
292    /// # Panics
293    ///
294    /// May panic if `index * 64` is not a valid offset in the bit array.
295    fn word(parent: &BitVector, index: usize) -> u64;
296
297    /// Unsafe version of [`Transformation::word`] without bounds checks.
298    ///
299    /// # Safety
300    ///
301    /// Behavior is undefined if `index * 64` is not a valid offset in the bit array.
302    unsafe fn word_unchecked(parent: &BitVector, index: usize) -> u64;
303
304    /// Returns the length of the integer array or the number of ones in the bit array of the transformed bitvector.
305    fn count_ones(parent: &BitVector) -> usize;
306
307    /// Returns an iterator over the set bits in the transformed bitvector.
308    fn one_iter(parent: &BitVector) -> OneIter<'_, Self>;
309}
310
311/// The bitvector as it is.
312#[derive(Clone, Debug, PartialEq, Eq)]
313pub struct Identity {}
314
315impl Transformation for Identity {
316    #[inline]
317    fn bit(parent: &BitVector, index: usize) -> bool {
318        parent.get(index)
319    }
320
321    #[inline]
322    fn word(parent: &BitVector, index: usize) -> u64 {
323        parent.data.word(index)
324    }
325
326    #[inline]
327    unsafe fn word_unchecked(parent: &BitVector, index: usize) -> u64 {
328        parent.data.word_unchecked(index)
329    }
330
331    #[inline]
332    fn count_ones(parent: &BitVector) -> usize {
333        parent.count_ones()
334    }
335
336    fn one_iter(parent: &BitVector) -> OneIter<'_, Self> {
337        parent.one_iter()
338    }
339}
340
341/// The bitvector implicitly transformed into its complement.
342#[derive(Clone, Debug, PartialEq, Eq)]
343pub struct Complement {}
344
345impl Transformation for Complement {
346    #[inline]
347    fn bit(parent: &BitVector, index: usize) -> bool {
348        !parent.get(index)
349    }
350
351    fn word(parent: &BitVector, index: usize) -> u64 {
352        let (last_index, offset) = bits::split_offset(parent.len());
353        if index >= last_index {
354            (!parent.data.word(index)) & unsafe { bits::low_set_unchecked(offset) }
355        } else {
356            unsafe { !parent.data.word_unchecked(index) }
357        }
358    }
359
360    unsafe fn word_unchecked(parent: &BitVector, index: usize) -> u64 {
361        let (last_index, offset) = bits::split_offset(parent.len());
362        if index >= last_index {
363            (!parent.data.word_unchecked(index)) & bits::low_set_unchecked(offset)
364        } else {
365            !parent.data.word_unchecked(index)
366        }
367    }
368
369    #[inline]
370    fn count_ones(parent: &BitVector) -> usize {
371        parent.count_zeros()
372    }
373
374    fn one_iter(parent: &BitVector) -> OneIter<'_, Self> {
375        parent.zero_iter()
376    }
377}
378
379//-----------------------------------------------------------------------------
380
381/// An iterator over the set bits in an implicitly transformed [`BitVector`].
382///
383/// The type of `Item` is `(`[`usize`]`, `[`usize`]`)`.
384/// This can be interpreted as:
385///
386/// * `(index, value)` or `(i, select(i))` in the integer array; or
387/// * `(rank(j), j)` in the bit array with `j` such that `self.get(j) == true`.
388///
389/// Note that `index` is not always the index provided by [`Iterator::enumerate`].
390/// Queries may create iterators in the middle of the bitvector.
391///
392/// The bitvector is assumed to be at least somewhat dense.
393/// If the frequency of ones is less than 1/64, iteration may be inefficient.
394/// The implementation of [`Iterator::nth`] is optimized to skip set bits without determining their positions.
395///
396/// This type must be parameterized with a [`Transformation`].
397///
398/// # Examples
399///
400/// ```
401/// use simple_sds_sbwt::bit_vector::BitVector;
402/// use simple_sds_sbwt::ops::{BitVec, Select, SelectZero};
403///
404/// let source: Vec<bool> = vec![true, false, true, true, false, true, true, false, true];
405/// let bv: BitVector = source.into_iter().collect();
406///
407/// let mut iter = bv.one_iter();
408/// assert_eq!(iter.len(), bv.count_ones());
409/// assert_eq!(iter.next(), Some((0, 0)));
410/// assert_eq!(iter.nth(0), Some((1, 2)));
411/// assert_eq!(iter.nth(1), Some((3, 5)));
412/// assert_eq!(iter.next(), Some((4, 6)));
413/// assert!(iter.nth(1).is_none());
414///
415/// let mut iter = bv.zero_iter();
416/// assert_eq!(iter.nth(1), Some((1, 4)));
417/// assert_eq!(iter.next(), Some((2, 7)));
418/// assert!(iter.next().is_none());
419/// ```
420#[derive(Clone, Debug)]
421pub struct OneIter<'a, T: Transformation + ?Sized> {
422    parent: &'a BitVector,
423    // The first (i, candidate for select(i)) we have not visited.
424    next: (usize, usize),
425    // The first (i, candidate for select(i)) we should not visit.
426    limit: (usize, usize),
427    // We use `T` only for accessing static methods.
428    _marker: marker::PhantomData<T>,
429}
430
431impl<'a, T: Transformation + ?Sized> OneIter<'a, T> {
432    // Build an empty iterator for the parent bitvector.
433    fn empty_iter(parent: &'a BitVector) -> OneIter<'a, T> {
434        OneIter {
435            parent,
436            next: (T::count_ones(parent), parent.len()),
437            limit: (T::count_ones(parent), parent.len()),
438            _marker: marker::PhantomData,
439        }
440    }
441}
442
443impl<'a, T: Transformation + ?Sized> Iterator for OneIter<'a, T> {
444    type Item = (usize, usize);
445
446    fn next(&mut self) -> Option<Self::Item> {
447        if self.next.0 >= self.limit.0 {
448            None
449        } else {
450            let (mut index, offset) = bits::split_offset(self.next.1);
451            // We trust that the iterator has been initialized properly and the above check
452            // guarantees that `self.next.1 < self.limit.1` and `self.limit.1 <= self.parent.len()`.
453            let mut word = unsafe { T::word_unchecked(self.parent, index) & !bits::low_set_unchecked(offset) };
454            while word == 0 {
455                index += 1;
456                word = unsafe { T::word_unchecked(self.parent, index) };
457            }
458            let offset = word.trailing_zeros() as usize;
459            let result = (self.next.0, bits::bit_offset(index, offset));
460            self.next = (result.0 + 1, result.1 + 1);
461            Some(result)
462        }
463    }
464
465    fn nth(&mut self, n: usize) -> Option<Self::Item> {
466        if self.next.0 + n >= self.limit.0 {
467            self.next = self.limit;
468            return None;
469        }
470        let (mut index, offset) = bits::split_offset(self.next.1);
471        let mut word = unsafe { T::word_unchecked(self.parent, index) & !bits::low_set_unchecked(offset) };
472        let mut relative_rank = n;
473        let mut ones = word.count_ones() as usize;
474        while ones <= relative_rank {
475            index += 1;
476            word = unsafe { T::word_unchecked(self.parent, index) };
477            relative_rank -= ones;
478            ones = word.count_ones() as usize;
479        }
480        let offset = unsafe { bits::select(word, relative_rank) };
481        let result = (self.next.0 + n, bits::bit_offset(index, offset));
482        self.next = (result.0 + 1, result.1 + 1);
483        Some(result)
484    }
485
486    #[inline]
487    fn size_hint(&self) -> (usize, Option<usize>) {
488        let remaining = self.limit.0 - self.next.0;
489        (remaining, Some(remaining))
490    }
491}
492
493impl<'a, T: Transformation + ?Sized> DoubleEndedIterator for OneIter<'a, T> {
494    fn next_back(&mut self) -> Option<Self::Item> {
495        if self.next.0 >= self.limit.0 {
496            None
497        } else {
498            self.limit = (self.limit.0 - 1, self.limit.1 - 1);
499            let (mut index, offset) = bits::split_offset(self.limit.1);
500            // We trust that the iterator has been initialized properly and the above check
501            // guarantees that `self.next.1 <= self.limit.1` and `self.limit.1 < self.parent.len()`.
502            let mut word = unsafe { T::word_unchecked(self.parent, index) & bits::low_set_unchecked(offset + 1) };
503            while word == 0 {
504                index -= 1;
505                word = unsafe { T::word_unchecked(self.parent, index) };
506            }
507            let offset = bits::WORD_BITS - 1 - (word.leading_zeros() as usize);
508            self.limit.1 = bits::bit_offset(index, offset);
509            Some(self.limit)
510        }
511    }
512}
513
514impl<'a, T: Transformation + ?Sized> ExactSizeIterator for OneIter<'a, T> {}
515
516impl<'a, T: Transformation + ?Sized> FusedIterator for OneIter<'a, T> {}
517
518//-----------------------------------------------------------------------------
519
520impl<'a> Select<'a> for BitVector {
521    type OneIter = OneIter<'a, Identity>;
522
523    fn supports_select(&self) -> bool {
524        self.select != None
525    }
526
527    fn enable_select(&mut self) {
528        if !self.supports_select() {
529            let select_support = SelectSupport::<Identity>::new(self);
530            self.select = Some(select_support);
531        }
532    }
533
534    fn one_iter(&'a self) -> Self::OneIter {
535        Self::OneIter {
536            parent: self,
537            next: (0, 0),
538            limit: (Identity::count_ones(self), self.len()),
539            _marker: marker::PhantomData,
540        }
541    }
542
543    fn select(&'a self, rank: usize) -> Option<usize> {
544         if rank >= Identity::count_ones(self) {
545             None
546        } else {
547            let select_support = self.select.as_ref().unwrap();
548            let value = unsafe { select_support.select_unchecked(self, rank) };
549            Some(value)
550        }
551    }
552
553    fn select_iter(&'a self, rank: usize) -> Self::OneIter {
554         if rank >= Identity::count_ones(self) {
555             Self::OneIter::empty_iter(self)
556        } else {
557            let select_support = self.select.as_ref().unwrap();
558            let value = unsafe { select_support.select_unchecked(self, rank) };
559            Self::OneIter {
560                parent: self,
561                next: (rank, value),
562                limit: (Identity::count_ones(self), self.len()),
563                _marker: marker::PhantomData,
564            }
565        }
566    }
567}
568
569//-----------------------------------------------------------------------------
570
571impl<'a> SelectZero<'a> for BitVector {
572    type ZeroIter = OneIter<'a, Complement>;
573
574    fn supports_select_zero(&self) -> bool {
575        self.select_zero != None
576    }
577
578    fn enable_select_zero(&mut self) {
579        if !self.supports_select_zero() {
580            let select_support = SelectSupport::<Complement>::new(self);
581            self.select_zero = Some(select_support);
582        }
583    }
584
585    fn zero_iter(&'a self) -> Self::ZeroIter {
586        Self::ZeroIter {
587            parent: self,
588            next: (0, 0),
589            limit: (Complement::count_ones(self), self.len()),
590            _marker: marker::PhantomData,
591        }
592    }
593
594    fn select_zero(&'a self, rank: usize) -> Option<usize> {
595         if rank >= Complement::count_ones(self) {
596             None
597        } else {
598            let select_support = self.select_zero.as_ref().unwrap();
599            let value = unsafe { select_support.select_unchecked(self, rank) };
600            Some(value)
601        }
602    }
603
604    fn select_zero_iter(&'a self, rank: usize) -> Self::ZeroIter {
605         if rank >= Complement::count_ones(self) {
606             Self::ZeroIter::empty_iter(self)
607        } else {
608            let select_support = self.select_zero.as_ref().unwrap();
609            let value = unsafe { select_support.select_unchecked(self, rank) };
610            Self::ZeroIter {
611                parent: self,
612                next: (rank, value),
613                limit: (Complement::count_ones(self), self.len()),
614                _marker: marker::PhantomData,
615            }
616        }
617    }
618}
619
620//-----------------------------------------------------------------------------
621
622impl<'a> PredSucc<'a> for BitVector {
623    type OneIter = OneIter<'a, Identity>;
624
625    fn supports_pred_succ(&self) -> bool {
626        self.rank != None && self.select != None
627    }
628
629    fn enable_pred_succ(&mut self) {
630        self.enable_rank();
631        self.enable_select();
632    }
633
634    fn predecessor(&'a self, value: usize) -> Self::OneIter {
635        let rank = self.rank(value + 1);
636        if rank == 0 {
637            Self::OneIter::empty_iter(self)
638        } else {
639            self.select_iter(rank - 1)
640        }
641    }
642
643    fn successor(&'a self, value: usize) -> Self::OneIter {
644        let rank = self.rank(value);
645        if rank >= self.count_ones() {
646            Self::OneIter::empty_iter(self)
647        } else {
648            self.select_iter(rank)
649        }
650    }
651}
652
653//-----------------------------------------------------------------------------
654
655impl Serialize for BitVector {
656    fn serialize_header<T: io::Write>(&self, writer: &mut T) -> io::Result<()> {
657        self.ones.serialize(writer)?;
658        Ok(())
659    }
660
661    fn serialize_body<T: io::Write>(&self, writer: &mut T) -> io::Result<()> {
662        self.data.serialize(writer)?;
663        self.rank.serialize(writer)?;
664        self.select.serialize(writer)?;
665        self.select_zero.serialize(writer)?;
666        Ok(())
667    }
668
669    fn load<T: io::Read>(reader: &mut T) -> io::Result<Self> {
670        let ones = usize::load(reader)?;
671        let data = RawVector::load(reader)?;
672        if ones > data.len() {
673            return Err(Error::new(ErrorKind::InvalidData, "Too many set bits"));
674        }
675
676        let rank = Option::<RankSupport>::load(reader)?;
677        if let Some(value) = rank.as_ref() {
678            if value.blocks() != bits::div_round_up(data.len(), RankSupport::BLOCK_SIZE) {
679                return Err(Error::new(ErrorKind::InvalidData, "Invalid number of rank blocks"))
680            }
681        }
682
683        let select = Option::<SelectSupport<Identity>>::load(reader)?;
684        if let Some(value) = select.as_ref() {
685            if value.superblocks() != bits::div_round_up(ones, SelectSupport::<Identity>::SUPERBLOCK_SIZE) {
686                return Err(Error::new(ErrorKind::InvalidData, "Invalid number of select superblocks"))
687            }
688        }
689
690        let select_zero = Option::<SelectSupport<Complement>>::load(reader)?;
691        if let Some(value) = select_zero.as_ref() {
692            if value.superblocks() != bits::div_round_up(data.len() - ones, SelectSupport::<Complement>::SUPERBLOCK_SIZE) {
693                return Err(Error::new(ErrorKind::InvalidData, "Invalid number of select_zero superblocks"))
694            }
695        }
696
697        Ok(BitVector {
698            ones, data, rank, select, select_zero,
699        })
700    }
701
702    fn size_in_elements(&self) -> usize {
703        self.ones.size_in_elements() +
704        self.data.size_in_elements() +
705        self.rank.size_in_elements() +
706        self.select.size_in_elements() +
707        self.select_zero.size_in_elements()
708    }
709}
710
711//-----------------------------------------------------------------------------
712
713impl AsRef<RawVector> for BitVector {
714    #[inline]
715    fn as_ref(&self) -> &RawVector {
716        &(self.data)
717    }
718}
719
720impl From<RawVector> for BitVector {
721    fn from(data: RawVector) -> Self {
722        let ones = data.count_ones();
723        BitVector {
724            ones,
725            data,
726            rank: None,
727            select: None,
728            select_zero: None,
729        }
730    }
731}
732
733impl From<BitVector> for RawVector {
734    fn from(source: BitVector) -> Self {
735        source.data
736    }
737}
738
739impl FromIterator<bool> for BitVector {
740    fn from_iter<I: IntoIterator<Item = bool>>(iter: I) -> Self {
741        let iter = iter.into_iter();
742        let (lower_bound, _) = iter.size_hint();
743        let mut data = RawVector::with_capacity(lower_bound);
744        for value in iter {
745            data.push_bit(value);
746        }
747        let ones = data.count_ones();
748        BitVector {
749            ones,
750            data,
751            rank: None,
752            select: None,
753            select_zero: None,
754        }
755    }
756}
757
758//-----------------------------------------------------------------------------
simple_sds_sbwt/bit_vector.rs

simple_sds_sbwt/
bit_vector.rs
