bitm/rank_select/
mod.rs

1mod utils;
2mod select;
3use std::ops::Deref;
4
5use self::select::{U64_PER_L1_ENTRY, U64_PER_L2_ENTRY, U64_PER_L2_RECORDS};
6pub use self::select::{Select, Select0, BinaryRankSearch, CombinedSampling,
7     ConstCombinedSamplingDensity, AdaptiveCombinedSamplingDensity, SelectForRank101111, Select0ForRank101111,
8     select64, optimal_combined_sampling};
9
10use super::{ceiling_div, n_lowest_bits};
11use dyn_size_of::GetSize;
12
13/// Trait for rank queries on bit vector.
14/// Rank query returns the number of ones (or zeros) in requested number of the first bits.
15pub trait Rank {
16    /// Returns the number of ones in first `index` bits or [`None`] if `index` is out of bounds.
17    fn try_rank(&self, index: usize) -> Option<usize>;
18
19    /// Returns the number of ones in first `index` bits or panics if `index` is out of bounds.
20    #[inline] fn rank(&self, index: usize) -> usize {
21        self.try_rank(index).expect("rank index out of bound")
22    }
23
24    /// Returns the number of ones in first `index` bits.
25    /// The result is undefined if `index` is out of bounds.
26    #[inline] unsafe fn rank_unchecked(&self, index: usize) -> usize {
27        self.rank(index)
28    }
29
30    /// Returns the number of zeros in first `index` bits or [`None`] if `index` is out of bounds.
31    #[inline] fn try_rank0(&self, index: usize) -> Option<usize> {
32         self.try_rank(index).map(|r| index-r)
33    }
34
35    /// Returns the number of zeros in first `index` bits or panics if `index` is out of bounds.
36    #[inline] fn rank0(&self, index: usize) -> usize { index - self.rank(index) }
37
38    /// Returns the number of ones in first `index` bits.
39    /// The result is undefined if `index` is out of bounds.
40    #[inline] unsafe fn rank0_unchecked(&self, index: usize) -> usize {
41        index - self.rank_unchecked(index)
42    }
43}
44
45/// Returns number of bits set (to one) in `content` whose length does not exceeds 8.
46#[inline] fn count_bits_in(content: &[u64]) -> usize {
47    let mut it = content.iter().map(|v| v.count_ones() as usize);
48    let mut result = 0;
49    if let Some(v) = it.next() { result += v; } else { return result; }
50    if let Some(v) = it.next() { result += v; } else { return result; }
51    if let Some(v) = it.next() { result += v; } else { return result; }
52    if let Some(v) = it.next() { result += v; } else { return result; }
53    if let Some(v) = it.next() { result += v; } else { return result; }
54    if let Some(v) = it.next() { result += v; } else { return result; }
55    if let Some(v) = it.next() { result += v; } else { return result; }
56    if let Some(v) = it.next() { result += v; }
57    return result;
58}
59
60/*#[inline] fn count_bits_in(content: &[u64]) -> usize {  // almost the same asm as above
61    let l = content.len();
62    let mut result = 0;
63    for i in 0..8 {
64        if i < l { result += unsafe{ content.get_unchecked(i) }.count_ones() as usize; }
65    }
66    return result;
67}*/
68
69/// Returns number of bits set (to one) in `content` whose length does not exceeds 8.
70/*#[inline] fn count_bits_in(mut content: &[u64]) -> usize {
71    let mut result = 0;
72    if content.len() >= 3 {
73        result += unsafe{ content.get_unchecked(0) }.count_ones() as usize +
74            unsafe{ content.get_unchecked(1) }.count_ones() as usize +
75            unsafe{ content.get_unchecked(2) }.count_ones() as usize;
76        content = &content[3..];
77        if content.len() >= 3 {
78            result += unsafe{ content.get_unchecked(0) }.count_ones() as usize +
79                unsafe{ content.get_unchecked(1) }.count_ones() as usize +
80                unsafe{ content.get_unchecked(2) }.count_ones() as usize;
81            content = &content[3..];
82        }
83    }
84    // up to 2 elements
85    let l = content.len();
86    if l > 0 {
87        result += unsafe{ content.get_unchecked(0) }.count_ones() as usize;
88        if l > 1 {
89            result += unsafe{ content.get_unchecked(1) }.count_ones() as usize;
90        }
91    }
92    result
93}*/
94
95/// Returns number of bits set (to one) in `content` whose length does not exceeds 8.
96/*#[inline] fn count_bits_in(mut content: &[u64]) -> usize {
97    let mut result = 0;
98    // up to 8 elements
99    if content.len() >= 4 {
100        result += unsafe{ content.get_unchecked(0) }.count_ones() as usize +
101            unsafe{ content.get_unchecked(1) }.count_ones() as usize +
102            unsafe{ content.get_unchecked(2) }.count_ones() as usize +
103            unsafe{ content.get_unchecked(3) }.count_ones() as usize;
104        content = &content[4..];
105    }
106    // up to 4 elements
107    if content.len() >= 2 {
108        result += unsafe{ content.get_unchecked(0) }.count_ones() as usize +
109            unsafe{ content.get_unchecked(1) }.count_ones() as usize;
110        content = &content[2..];
111    }
112    // up to 2 elements
113    let l = content.len();
114    if l > 0 {
115        result += unsafe{ content.get_unchecked(0) }.count_ones() as usize;
116        if l > 1 {
117            result += unsafe{ content.get_unchecked(1) }.count_ones() as usize;
118        }
119    }
120    result
121}*/
122
123
124
125/// The structure that holds bit vector `content` and `ranks` structure that takes no more than 3.125% extra space.
126/// It can return the number of ones (or zeros) in first `index` bits of the `content` (see `rank` and `rank0` method) in *O(1)* time.
127/// In addition, it supports select queries utilizing binary search over ranks (see [`BinaryRankSearch`])
128/// or (optionally, at the cost of extra space overhead; about 0.39% with default settings)
129/// combined sampling (which is usually faster; see [`CombinedSampling`]).
130///
131/// Any type that implements the [`Deref`] trait with `Target = [u64]` can be used as a bit vector.
132/// It is recommended to use this structure with bit vectors allocated with alignment to the CPU cache line or 64 bytes.
133/// Such a vector can be constructed, for example, by compiling `bitm` with the `aligned-vec` feature and using implementation
134/// of [`crate::BitVec`] trait for `aligned_vec::ABox<[u64]>`, for example: `ABox::with_zeroed_bits(number_of_bits)`.
135///
136/// The structure supports vectors up to 2<sup>64</sup> bits and its design is based on a 3-level (compact due to relative addressing)
137/// index that samples rank responses every 512 bits and is CPU cache friendly as the first level is small
138/// (each its entry covers 2<sup>32</sup> bits) and the other two are interleaved.
139///
140/// It uses modified version of the structure described in the paper:
141/// - Zhou D., Andersen D.G., Kaminsky M. (2013) "Space-Efficient, High-Performance Rank and Select Structures on Uncompressed Bit Sequences".
142///   In: Bonifaci V., Demetrescu C., Marchetti-Spaccamela A. (eds) Experimental Algorithms. SEA 2013.
143///   Lecture Notes in Computer Science, vol 7933. Springer, Berlin, Heidelberg. <https://doi.org/10.1007/978-3-642-38527-8_15>
144/// 
145/// The modification consists of different level 2 entries that hold 4 rank values (r0 <= r1 <= r2 <= r3) relative to level 1 entry.
146/// The content of level 2 entry, listing from the least significant bits, is:
147/// - original: r0 stored on 32 bits, r1-r0 on 10 bits, r2-r1 on 10 bits, r3-r2 on 10 bits;
148/// - our: r0 stored on 32 bits, r3-r0 on 11 bits, r2-r0 on 11 bits, r1-r0 on 10 bits.
149/// With this layout, we can read the corresponding value in the rank query without branching.
150/// 
151/// Another modification that makes our implementation unique is the ability of the select support structure to adapt
152/// the sampling density to the content of the bit vector (see [`CombinedSampling`] and [`AdaptiveCombinedSamplingDensity`]).
153/// 
154/// For in-word selection, the structure uses the [`select64`] function.
155#[derive(Clone)]
156pub struct RankSelect101111<Select = BinaryRankSearch, Select0 = BinaryRankSearch, BV = Box::<[u64]>> {
157    pub content: BV,  // bit vector
158    #[cfg(target_pointer_width = "64")] pub l1ranks: Box<[usize]>,  // Each cell holds one rank using 64 bits
159    pub l2ranks: Box<[u64]>,  // Each cell holds 4 ranks using [bits]: 32 (absolute), and, in reverse order (deltas): 10, 11, 11.
160    select: Select,  // support for select (one)
161    select0: Select0,  // support for select (zero)
162}
163
164impl<S, S0, BV> RankSelect101111<S, S0, BV> {
165    /// Returns reference to structure that support select (one) operation.
166    #[inline] pub fn select_support(&self) -> &S { &self.select }
167
168    /// Returns reference to structure that support select zero operation.
169    #[inline] pub fn select0_support(&self) -> &S0 { &self.select0 }
170}
171
172impl<S: GetSize, S0: GetSize, BV: GetSize> GetSize for RankSelect101111<S, S0, BV> {
173    #[cfg(target_pointer_width = "64")]
174    fn size_bytes_dyn(&self) -> usize {
175        self.content.size_bytes_dyn() + self.l2ranks.size_bytes_dyn() + self.l1ranks.size_bytes_dyn() + self.select.size_bytes_dyn() + self.select0.size_bytes_dyn()
176    }
177    #[cfg(target_pointer_width = "32")]
178    fn size_bytes_dyn(&self) -> usize {
179        self.content.size_bytes_dyn() + self.l2ranks.size_bytes_dyn() + self.select.size_bytes_dyn() + self.select0.size_bytes_dyn()
180    }
181    const USES_DYN_MEM: bool = true;
182}
183
184impl<S: SelectForRank101111, S0: Select0ForRank101111, BV: Deref<Target = [u64]>> From<BV> for RankSelect101111<S, S0, BV> {
185    #[inline] fn from(value: BV) -> Self { Self::build(value).0 }
186}
187
188impl<S: SelectForRank101111, S0, BV: Deref<Target = [u64]>> Select for RankSelect101111<S, S0, BV> {
189    #[inline] fn try_select(&self, rank: usize) -> Option<usize> {
190        self.select.select(&self.content, #[cfg(target_pointer_width = "64")] &self.l1ranks, &self.l2ranks, rank)
191    }
192
193    #[inline] unsafe fn select_unchecked(&self, rank: usize) -> usize {
194        self.select.select_unchecked(&self.content, #[cfg(target_pointer_width = "64")] &self.l1ranks, &self.l2ranks, rank)
195    }
196}
197
198impl<S, S0: Select0ForRank101111, BV: Deref<Target = [u64]>> Select0 for RankSelect101111<S, S0, BV> {
199    #[inline] fn try_select0(&self, rank: usize) -> Option<usize> {
200        self.select0.select0(&self.content, #[cfg(target_pointer_width = "64")] &self.l1ranks, &self.l2ranks, rank)
201    }
202
203    #[inline] unsafe fn select0_unchecked(&self, rank: usize) -> usize {
204        self.select0.select0_unchecked(&self.content, #[cfg(target_pointer_width = "64")] &self.l1ranks, &self.l2ranks, rank)
205    }
206}
207
208impl<S: SelectForRank101111, S0: Select0ForRank101111, BV: Deref<Target = [u64]>> Rank for RankSelect101111<S, S0, BV> {
209    #[inline] fn try_rank(&self, index: usize) -> Option<usize> {
210        let block = index / 512;
211        let word_idx = index / 64;
212        // we start from access to content, as if given index of content is not out of bounds,
213        // then corresponding indices l1ranks and l2ranks are also not out of bound
214        let mut r = (self.content.get(word_idx)? & n_lowest_bits(index as u8 % 64)).count_ones() as usize;
215        let block_content = *unsafe{ self.l2ranks.get_unchecked(index/2048) };  // sound after returning Some by content.get(word_idx)
216        #[cfg(target_pointer_width = "64")] { r += unsafe{ *self.l1ranks.get_unchecked(index >> 32) } + (block_content & 0xFFFFFFFFu64) as usize; } // 32 lowest bits   // for 34 bits: 0x3FFFFFFFFu64
217        #[cfg(target_pointer_width = "32")] { r += (block_content & 0xFFFFFFFFu64) as usize; }
218
219        r += (((block_content >> (11 * (!block & 3))) >> 32) & 0b1_11111_11111) as usize;
220
221        //Some(r + count_bits_in(unsafe {self.content.get_unchecked(block * 8/*word_idx&!7*/..word_idx)}))
222        Some(r + count_bits_in(unsafe {self.content.get_unchecked(word_idx&!7..word_idx)}))
223    }
224
225    #[inline] unsafe fn rank_unchecked(&self, index: usize) -> usize {
226        let block = index / 512;
227        let word_idx = index / 64;   
228        let block_content = *unsafe{ self.l2ranks.get_unchecked(index/2048) };
229        #[cfg(target_pointer_width = "64")] let mut r = *self.l1ranks.get_unchecked(index >> 32) + (block_content & 0xFFFFFFFFu64) as usize; // 32 lowest bits   // for 34 bits: 0x3FFFFFFFFu64
230        #[cfg(target_pointer_width = "32")] let mut r = (block_content & 0xFFFFFFFFu64) as usize;
231        r += (self.content.get_unchecked(word_idx) & n_lowest_bits(index as u8 % 64)).count_ones() as usize;
232
233        //r += (((block_content>>32) >> (33 - 11 * (block & 3))) & 0b1_11111_11111) as usize;
234        //r += (((block_content >> (33 - 11 * (block & 3))) >> 32) & 0b1_11111_11111) as usize;
235        //if block & 3 != 0 { r += ((block_content >> ((32+33) - 11 * (block & 3))) & 0b1_11111_11111) as usize }
236        //r += (((block_content >> 32) >> (11 * (3 - (block & 3)))) & 0b1_11111_11111) as usize;
237        
238        r += (((block_content >> (11 * (!block & 3))) >> 32) & 0b1_11111_11111) as usize;
239        //r += (((block_content >> 32) >> (11 * (!block & 3))) & 0b1_11111_11111) as usize;
240
241        //r + count_bits_in(self.content.get_unchecked(block * 8..word_idx))
242        r + count_bits_in(self.content.get_unchecked(word_idx&!7..word_idx))
243    }
244}
245
246impl<S: SelectForRank101111, S0: Select0ForRank101111, BV: Deref<Target = [u64]>> RankSelect101111<S, S0, BV> {
247    pub fn build(content: BV) -> (Self, usize) {
248        #[cfg(target_pointer_width = "64")] let mut l1ranks = Vec::with_capacity(ceiling_div(content.len(), U64_PER_L1_ENTRY));
249        let mut l2ranks = Vec::with_capacity(ceiling_div(content.len(), U64_PER_L2_ENTRY));
250        let mut current_total_rank: usize = 0;
251        for content in content.chunks(U64_PER_L1_ENTRY) {  // each l1 chunk has 1<<32 bits = (1<<32)/64 content elements
252            #[cfg(target_pointer_width = "64")] l1ranks.push(current_total_rank);
253            let mut current_rank: u64 = 0;
254            for chunk in content.chunks(U64_PER_L2_ENTRY) {   // each chunk has 32*64 = 2048 bits
255                let mut to_append = current_rank;
256                let mut vals = chunk.chunks(U64_PER_L2_RECORDS).map(|c| count_bits_in(c)); // each val has 8*64 = 512 bits
257                if let Some(v) = vals.next() {
258                    let mut chunk_sum = v as u64;  // now chunk_sum uses up to 10 bits
259                    to_append |= chunk_sum << (32+11+11);
260                    if let Some(v) = vals.next() {
261                        chunk_sum += v as u64;     // now chunk_sum uses up to 11 bits
262                        to_append |= chunk_sum << (32+11);
263                        if let Some(v) = vals.next() {
264                            chunk_sum += v as u64;     // now chunk_sum uses up to 11 bits
265                            to_append |= chunk_sum << 32;
266                            if let Some(v) = vals.next() { chunk_sum += v as u64; }
267                        } else {
268                            to_append |= chunk_sum << 32;   // replication of the last chunk_sum in the last l2rank
269                        }
270                    } else {
271                        to_append |= (chunk_sum << 32) | (chunk_sum << (32+11));    // replication of the last chunk_sum in the last l2rank
272                    }
273                    current_rank += chunk_sum;
274                } //else { to_append |= (0 << 32) | (0 << (32+11)) | (0 << (32+22)); }
275                l2ranks.push(to_append);
276            }
277            current_total_rank += current_rank as usize;
278        }
279        #[cfg(target_pointer_width = "64")] let l1ranks = l1ranks.into_boxed_slice();
280        let l2ranks = l2ranks.into_boxed_slice();
281        let select = S::new(&content, #[cfg(target_pointer_width = "64")] &l1ranks, &l2ranks, current_total_rank);
282        let select0 = S0::new0(&content, #[cfg(target_pointer_width = "64")] &l1ranks, &l2ranks, current_total_rank);
283        (Self{content, #[cfg(target_pointer_width = "64")] l1ranks, l2ranks, select, select0}, current_total_rank)
284    }
285}
286
287impl<S: SelectForRank101111, S0: Select0ForRank101111, BV: Deref<Target = [u64]>> AsRef<[u64]> for RankSelect101111<S, S0, BV> {
288    #[inline] fn as_ref(&self) -> &[u64] { &self.content }
289}
290
291/// Alias for backward compatibility. [`RankSelect101111`] with [`BinaryRankSearch`] (which does not introduce a space overhead) for select queries.
292pub type ArrayWithRank101111 = RankSelect101111<BinaryRankSearch, BinaryRankSearch>;
293
294/// The structure that holds array of bits `content` and `ranks` structure that takes no more than 6.25% extra space.
295/// It can returns the number of ones in first `index` bits of the `content` (see `rank` method) in *O(1)* time.
296/// Only `content` with less than 2<sup>32</sup> bit ones is supported.
297/// Any type that implements the [`Deref`] trait with `Target = [u64]` can be used as a bit vector.
298/// 
299/// Usually [`RankSelect101111`] should be preferred to [`ArrayWithRankSimple`].
300#[derive(Clone)]
301pub struct RankSimple<BV = Box<[u64]>> {
302    content: BV,
303    ranks: Box<[u32]>,
304}
305
306impl<BV: GetSize> GetSize for RankSimple<BV> {
307    fn size_bytes_dyn(&self) -> usize {
308        self.content.size_bytes_dyn() + self.ranks.size_bytes_dyn()
309    }
310    const USES_DYN_MEM: bool = true;
311}
312
313impl<BV: Deref<Target = [u64]>> From<BV> for RankSimple<BV> {
314    #[inline] fn from(value: BV) -> Self { Self::build(value).0 }
315}
316
317impl<BV: Deref<Target = [u64]>> RankSimple<BV> {
318
319    /// Constructs `ArrayWithRankSimple` and count number of bits set in `content`. Returns both.
320    pub fn build(content: BV) -> (Self, u32) {
321        let mut result = Vec::with_capacity(ceiling_div(content.len(), 8usize));
322        let mut current_rank: u32 = 0;
323        for seg_nr in 0..content.len() {
324            if seg_nr % 8 == 0 { result.push(current_rank); }
325            current_rank += content[seg_nr].count_ones();
326        }
327        (Self{content, ranks: result.into_boxed_slice()}, current_rank)
328    }
329
330    pub fn try_rank(&self, index: usize) -> Option<u32> {
331        let word_idx = index / 64;
332        let word_offset = index as u8 % 64;
333        let block = index / 512;
334        let mut r = (self.content.get(word_idx)? & n_lowest_bits(word_offset)).count_ones() as u32;
335        r += unsafe{self.ranks.get_unchecked(block)};   // sound after returning Some by content.get(word_idx)
336        for w in block * (512 / 64)..word_idx {
337            r += unsafe{self.content.get_unchecked(w)}.count_ones();    // sound after returning Some by content.get(word_idx)
338        }
339        Some(r)
340    }
341
342    pub fn rank(&self, index: usize) -> u32 {
343        let word_idx = index / 64;
344        let word_offset = index as u8 % 64;
345        let block = index / 512;
346        let mut r = self.ranks[block];
347        for w in block * (512 / 64)..word_idx {
348            r += self.content[w].count_ones();
349        }
350        r + (self.content[word_idx] & n_lowest_bits(word_offset)).count_ones() as u32
351    }
352
353    //pub fn select(&self, rank: u32) -> usize {}
354}
355
356impl<BV: Deref<Target = [u64]>> AsRef<[u64]> for RankSimple<BV> {
357    #[inline] fn as_ref(&self) -> &[u64] { &self.content }
358}
359
360impl<BV: Deref<Target = [u64]>> Rank for RankSimple<BV> {
361    #[inline] fn try_rank(&self, index: usize) -> Option<usize> {
362        Self::try_rank(self, index).map(|r| r as usize)
363    }
364
365    #[inline] fn rank(&self, index: usize) -> usize {
366        Self::rank(self, index) as usize
367    }
368}
369
370/// Alias for backward compatibility.
371pub type ArrayWithRankSimple = RankSimple;
372
373//impl Select for ArrayWithRankSimple {}
374
375#[cfg(test)]
376mod tests {
377    use crate::BitAccess;
378    use super::*;
379
380    fn check_all_ones<ArrayWithRank: AsRef<[u64]> + Rank + Select>(a: &ArrayWithRank) {
381        let mut rank = 0;
382        for index in a.as_ref().bit_ones() {
383            assert_eq!(a.rank(index), rank, "rank({}) should be {}", index, rank);
384            assert_eq!(a.select(rank), index, "select({}) should be {}", rank, index);
385            assert_eq!(unsafe{a.rank_unchecked(index)}, rank, "rank({}) should be {}", index, rank);
386            assert_eq!(unsafe{a.select_unchecked(rank)}, index, "select({}) should be {}", rank, index);
387            //assert_eq!(a.try_rank(index), Some(rank), "rank({}) should be {}", index, rank);
388            //assert_eq!(a.try_select(rank), Some(index), "select({}) should be {}", rank, index);
389            rank += 1;
390        }
391        assert_eq!(a.try_select(rank), None, "select({}) should be None", rank);
392    }
393
394    fn check_all_zeros<ArrayWithRank: AsRef<[u64]> + Rank + Select0>(a: &ArrayWithRank) {
395        let mut rank = 0;
396        for index in a.as_ref().bit_zeros() {
397            assert_eq!(a.rank0(index), rank, "rank0({}) should be {}", index, rank);
398            assert_eq!(a.select0(rank), index, "select0({}) should be {}", rank, index);
399            assert_eq!(unsafe{a.rank0_unchecked(index)}, rank, "rank0({}) should be {}", index, rank);
400            assert_eq!(unsafe{a.select0_unchecked(rank)}, index, "select0({}) should be {}", rank, index);
401            //assert_eq!(a.try_rank0(index), Some(rank), "rank0({}) should be {}", index, rank);
402            //assert_eq!(a.try_select0(rank), Some(index), "select0({}) should be {}", rank, index);
403            rank += 1;
404        }
405        assert_eq!(a.try_select0(rank), None, "select0({}) should be None", rank);
406    }
407
408    fn test_empty_array_rank<ArrayWithRank: From<Box<[u64]>> + AsRef<[u64]> + Rank + Select + Select0>() {
409        let a: ArrayWithRank = vec![].into_boxed_slice().into();
410        assert_eq!(a.try_rank(0), None);
411        assert_eq!(a.try_select(0), None);
412    }
413
414    #[test]
415    fn test_empty_array_rank_101111() {
416        test_empty_array_rank::<ArrayWithRank101111>();
417    }
418
419    #[test]
420    fn test_empty_array_rank_101111_combined() {
421        test_empty_array_rank::<RankSelect101111::<CombinedSampling, CombinedSampling>>();
422    }
423
424    fn test_array_with_rank<ArrayWithRank: From<Box<[u64]>> + AsRef<[u64]> + Rank + Select + Select0>() {
425        let a: ArrayWithRank = vec![0b1101, 0b110].into_boxed_slice().into();
426        assert_eq!(a.try_select(0), Some(0));
427        assert_eq!(a.try_select(1), Some(2));
428        assert_eq!(a.try_select(2), Some(3));
429        assert_eq!(a.try_select(3), Some(65));
430        assert_eq!(a.try_select(4), Some(66));
431        assert_eq!(a.try_select(5), None);
432        #[cfg(target_pointer_width = "64")] assert_eq!(a.try_select(1+(1<<32)), None);
433        #[cfg(target_pointer_width = "64")] assert_eq!(a.try_select(1+(1<<33)), None);
434        assert_eq!(a.rank(0), 0);
435        assert_eq!(a.rank(1), 1);
436        assert_eq!(a.rank(2), 1);
437        assert_eq!(a.rank(3), 2);
438        assert_eq!(a.rank(4), 3);
439        assert_eq!(a.rank(8), 3);
440        assert_eq!(a.rank(64), 3);
441        assert_eq!(a.rank(65), 3);
442        assert_eq!(a.rank(66), 4);
443        assert_eq!(a.rank(67), 5);
444        assert_eq!(a.rank(70), 5);
445        assert_eq!(a.try_rank(127), Some(5));
446        assert_eq!(a.try_rank(128), None);
447        #[cfg(target_pointer_width = "64")] assert_eq!(a.try_rank(1+(1<<32)), None);
448        check_all_ones(&a);
449        check_all_zeros(&a);
450    }
451
452    #[test]
453    fn array_with_rank_101111() {
454        test_array_with_rank::<ArrayWithRank101111>();
455    }
456
457    #[test]
458    fn array_with_rank_101111_combined() {
459        test_array_with_rank::<RankSelect101111::<CombinedSampling, CombinedSampling>>();
460    }
461
462    /*#[test]
463    fn array_with_rank_simple() {
464        test_array_with_rank::<ArrayWithRankSimple>();
465    }*/
466
467    fn test_big_array_with_rank<ArrayWithRank: From<Box<[u64]>> + AsRef<[u64]> + Rank + Select + Select0>() {
468        let a: ArrayWithRank = vec![0b1101; 60].into_boxed_slice().into();
469        assert_eq!(a.try_select0(488), Some(513));
470        assert_eq!(a.try_select(0), Some(0));
471        assert_eq!(a.try_select(1), Some(2));
472        assert_eq!(a.try_select(2), Some(3));
473        assert_eq!(a.try_select(3), Some(64));
474        assert_eq!(a.try_select(4), Some(66));
475        assert_eq!(a.try_select(5), Some(67));
476        assert_eq!(a.try_select(6), Some(128));
477        assert_eq!(a.try_select(7), Some(130));
478        assert_eq!(a.try_select(3*8), Some(512));
479        assert_eq!(a.try_select(3*8+1), Some(514));
480        assert_eq!(a.try_select(2*6*8), Some(2*1024));
481        assert_eq!(a.try_select(2*6*8+1), Some(2*1024+2));
482        assert_eq!(a.try_select(2*6*8+2), Some(2*1024+3));
483        assert_eq!(a.try_select(60*3), None);
484        assert_eq!(a.rank(0), 0);
485        assert_eq!(a.rank(1), 1);
486        assert_eq!(a.rank(2), 1);
487        assert_eq!(a.rank(3), 2);
488        assert_eq!(a.rank(4), 3);
489        assert_eq!(a.rank(8), 3);
490        assert_eq!(a.rank(64), 3);
491        assert_eq!(a.rank(65), 4);
492        assert_eq!(a.rank(66), 4);
493        assert_eq!(a.rank(67), 5);
494        assert_eq!(a.rank(68), 6);
495        assert_eq!(a.rank(69), 6);
496        assert_eq!(a.rank(128), 6);
497        assert_eq!(a.rank(129), 7);
498        assert_eq!(a.rank(512), 3*8);
499        assert_eq!(a.rank(513), 3*8+1);
500        assert_eq!(a.rank(514), 3*8+1);
501        assert_eq!(a.rank(515), 3*8+2);
502        assert_eq!(a.rank(1024), 6*8);
503        assert_eq!(a.rank(2*1024), 2*6*8);
504        assert_eq!(a.rank(2*1024+1), 2*6*8+1);
505        assert_eq!(a.rank(2*1024+2), 2*6*8+1);
506        assert_eq!(a.rank(2*1024+3), 2*6*8+2);
507        assert_eq!(a.try_rank(60*64), None);
508        check_all_ones(&a);
509        check_all_zeros(&a);
510    }
511
512    #[test]
513    fn big_array_with_rank_101111() {
514        test_big_array_with_rank::<ArrayWithRank101111>();
515    }
516
517    #[test]
518    fn big_array_with_rank_101111_combined() {
519        test_big_array_with_rank::<RankSelect101111::<CombinedSampling, CombinedSampling>>();
520    }
521
522    /*#[test]
523    fn big_array_with_rank_simple() {
524        test_big_array_with_rank::<ArrayWithRankSimple>();
525    }*/
526
527    fn test_content<ArrayWithRank: From<Box<[u64]>> + AsRef<[u64]> + Rank + Select + Select0>() {
528        let a: ArrayWithRank = vec![u64::MAX; 35].into_boxed_slice().into();
529        check_all_ones(&a);
530        check_all_zeros(&a);
531    }
532
533    #[test]
534    fn content_101111() {
535        test_content::<ArrayWithRank101111>();
536    }
537
538    #[test]
539    fn content_101111_combined() {
540        test_content::<RankSelect101111::<CombinedSampling, CombinedSampling>>();
541    }
542
543    /*#[test]
544    fn content_simple() {
545        test_content::<ArrayWithRankSimple>();
546    }*/
547
548    #[cfg(target_pointer_width = "64")] 
549    fn array_64bit<ArrayWithRank: From<Box<[u64]>> + AsRef<[u64]> + Rank + Select + Select0>() {
550        const SEGMENTS: usize = (1<<32)/64 * 2;
551        let a: ArrayWithRank = vec![0b01_01_01_01; SEGMENTS].into_boxed_slice().into();
552        assert_eq!(a.try_select(268435456), Some(4294967296));
553        assert_eq!(a.try_select(268435456+1), Some(4294967296+2));
554        assert_eq!(a.try_select(268435456+2), Some(4294967296+4));
555        assert_eq!(a.try_select(268435456+3), Some(4294967296+6));
556        assert_eq!(a.try_select(0), Some(0));
557        assert_eq!(a.try_select(1), Some(2));
558        assert_eq!(a.rank(0), 0);
559        assert_eq!(a.rank(1), 1);
560        assert_eq!(a.rank(2), 1);
561        assert_eq!(a.rank(1<<32), (1<<(32-6)) * 4);
562        assert_eq!(a.rank((1<<32)+1), (1<<(32-6)) * 4 + 1);
563        assert_eq!(a.rank((1<<32)+2), (1<<(32-6)) * 4 + 1);
564        assert_eq!(a.rank((1<<32)+3), (1<<(32-6)) * 4 + 2);
565        assert_eq!(a.try_rank(SEGMENTS*64), None);
566        check_all_ones(&a);
567        check_all_zeros(&a);
568    }
569
570    #[cfg(target_pointer_width = "64")] 
571    #[test]
572    #[ignore = "uses much memory and time"]
573    fn array_64bit_101111_binary() {
574        array_64bit::<ArrayWithRank101111>();
575    }
576
577    #[cfg(target_pointer_width = "64")] 
578    #[test]
579    #[ignore = "uses much memory and time"]
580    fn array_64bit_101111_combined() {
581        array_64bit::<RankSelect101111::<CombinedSampling, CombinedSampling>>();
582    }
583
584    #[cfg(target_pointer_width = "64")] 
585    fn array_64bit_filled<ArrayWithRank: From<Box<[u64]>> + AsRef<[u64]> + Rank + Select>() {
586        const SEGMENTS: usize = (1<<32)/64 * 2;
587        let a: ArrayWithRank = vec![u64::MAX; SEGMENTS].into_boxed_slice().into();
588        assert_eq!(a.select(4294965248), 4294965248);
589        assert_eq!(a.rank(0), 0);
590        assert_eq!(a.rank(1), 1);
591        assert_eq!(a.rank(2), 2);
592        for i in (1<<32)..(1<<32)+2048 {
593            assert_eq!(a.rank(i), i);
594            assert_eq!(a.select(i), i);
595        }
596        //check_all_ones(a);
597    }
598
599    #[cfg(target_pointer_width = "64")] 
600    #[test]
601    #[ignore = "uses much memory and time"]
602    fn array_64bit_filled_101111() {
603        array_64bit_filled::<ArrayWithRank101111>();
604    }
605
606    #[cfg(target_pointer_width = "64")] 
607    #[test]
608    #[ignore = "uses much memory and time"]
609    fn array_64bit_filled_101111_combined() {
610        array_64bit_filled::<RankSelect101111::<CombinedSampling, CombinedSampling>>();
611    }
612
613    #[cfg(target_pointer_width = "64")] 
614    fn array_64bit_halffilled<ArrayWithRank: From<Box<[u64]>> + AsRef<[u64]> + Rank + Select + Select0>() {
615        const SEGMENTS: usize = (1<<32)/64 * 2;
616        let a: ArrayWithRank = vec![0x5555_5555_5555_5555; SEGMENTS].into_boxed_slice().into();
617        check_all_ones(&a);
618        check_all_zeros(&a);
619    }
620
621    #[cfg(target_pointer_width = "64")] 
622    #[test]
623    #[ignore = "uses much memory and time"]
624    fn array_64bit_halffilled_101111_binary() {
625        array_64bit_halffilled::<ArrayWithRank101111>();
626    }
627
628    #[cfg(target_pointer_width = "64")] 
629    #[test]
630    #[ignore = "uses much memory and time"]
631    fn array_64bit_halffilled_101111_combined() {
632        array_64bit_halffilled::<RankSelect101111::<CombinedSampling, CombinedSampling>>();
633    }
634
635    #[cfg(target_pointer_width = "64")] 
636    fn array_64bit_zeroed_first<ArrayWithRank: From<Box<[u64]>> + AsRef<[u64]> + Rank + Select>() {
637        const SEGMENTS: usize = (1<<32)/64 + 1;
638        let mut content = vec![0; SEGMENTS].into_boxed_slice();
639        content[SEGMENTS-1] = 0b11<<62;
640        let a: ArrayWithRank = content.into();
641        assert_eq!(a.rank(0), 0);
642        assert_eq!(a.rank((1<<32)-1), 0);
643        assert_eq!(a.rank(1<<32), 0);
644        assert_eq!(a.rank((1<<32)+62), 0);
645        assert_eq!(a.rank((1<<32)+63), 1);
646        assert_eq!(a.select(0), (1<<32)+62);
647        assert_eq!(a.select(1), (1<<32)+63);
648        assert_eq!(a.try_select(2), None);
649    }
650
651    #[cfg(target_pointer_width = "64")] 
652    #[test]
653    #[ignore = "uses much memory and time"]
654    fn array_64bit_zeroed_first_101111() {
655        array_64bit_zeroed_first::<ArrayWithRank101111>();
656    }
657
658    #[cfg(target_pointer_width = "64")] 
659    #[test]
660    #[ignore = "uses much memory and time"]
661    fn array_64bit_zeroed_first_101111_combined() {
662        array_64bit_zeroed_first::<RankSelect101111::<CombinedSampling, CombinedSampling>>();
663    }
664}
bitm/rank_select/mod.rs

bitm/rank_select/
mod.rs
