rle_bitset/
lib.rs

1//! A no-std, no-alloc trait for querying and manipulating bits in a
2//! [`[usize]`] and iterating their run lengths.
3#![no_std]
4use core::cmp::min;
5use core::ops::{Bound::*, Range, RangeBounds};
6use primitive_traits::Integer;
7
8pub const WORD_WIDTH: usize = <usize as Integer>::WIDTH;
9
10/// A single inhabitancy type marking that we were out of range.
11#[derive(Debug, Eq, PartialEq)]
12pub struct OutOfRange();
13
14/// Returns the number of usizes needed to capture the given number of bits.
15pub fn words_needed(vals: usize) -> usize {
16    (vals / WORD_WIDTH) + min(0, vals % WORD_WIDTH)
17}
18
19/// A trait that allows reading, setting and iterating bits by their
20/// run lengths.
21pub trait RLEBits {
22    /// Gets the bit at the provided index, if it is within range.
23    fn get_bit(&self, bit: usize) -> Result<bool, OutOfRange>;
24    /// Sets the bit at the provided index, if it is within range.
25    fn set_bit(&mut self, bit: usize, value: bool) -> Result<(), OutOfRange>;
26    /// Returns an iterator over run lengths of the bits within the provided range.
27    fn run_lengths<'a, R: RangeBounds<usize>>(&'a self, range: R) -> Result<RLE<'a>, OutOfRange>;
28}
29
30impl RLEBits for [usize] {
31    fn get_bit(&self, bit: usize) ->  Result<bool, OutOfRange> {
32        let (x, y) = locate(self, bit)?;
33        let mask = 1 << y;
34        Ok(mask == (self[x] & mask))
35    }
36    fn set_bit(&mut self, bit: usize, value: bool) -> Result<(), OutOfRange> {
37        let (x, y) = locate(self, bit)?;
38        let mask = 1 << y;
39        if value {
40            self[x] |= mask;
41        } else {
42            self[x] &= !mask;
43        }
44        Ok(())
45    }
46    fn run_lengths<'a, R: RangeBounds<usize>>(&'a self, range: R) -> Result<RLE<'a>, OutOfRange> {
47        RLE::new(self, range)
48    }
49}
50
51fn locate(slice: &[usize], bit: usize) -> Result<(usize, usize), OutOfRange> {
52    if bit < (WORD_WIDTH * slice.len()) {
53        Ok((bit / WORD_WIDTH, bit % WORD_WIDTH))
54    } else {
55        Err(OutOfRange())
56    }
57}
58
59/// A run length - a range of the same value repeated.
60#[derive(Clone, Debug, Eq, PartialEq)]
61pub struct RL {
62    pub value: bool,
63    pub run: Range<usize>,
64}
65
66impl RL {
67    /// Creates a new [`$crate::RL`].
68    pub fn new(value: bool, start: usize, end: usize) -> RL {
69        RL { value, run: start..end }
70    }
71}
72
73/// An iterator over run lengths of bits.
74#[derive(Debug)]
75pub struct RLE<'a> {
76    storage: &'a [usize],
77    range: Range<usize>,
78    last: Option<RL>,
79}
80
81impl<'a> RLE<'a> {
82
83    /// Creates a new [`$crate::RLE`] iterating over the provided slice's bits
84    /// in the given range.
85    pub fn new<R: RangeBounds<usize>>(storage: &'a [usize], range: R) -> Result<RLE<'a>, OutOfRange> {
86        let size = storage.len() * WORD_WIDTH;
87        let s = match range.start_bound() {
88            Included(x) => if *x < size { Ok(*x) } else { Err(OutOfRange()) },
89            Excluded(x) => if (*x+1) < size { Ok(*x+1) } else { Err(OutOfRange()) },
90            Unbounded => Ok(0),
91        }?;
92        let e = match range.start_bound() {
93            Included(x) => if *x <  size { Ok(*x+1) } else { Err(OutOfRange()) },
94            Excluded(x) => if *x <= size { Ok(*x) } else { Err(OutOfRange()) },
95            Unbounded => Ok(size),
96        }?;
97        if e >= s { Ok(RLE { storage, range: s..e, last: None }) } else { Err(OutOfRange()) }
98    }
99
100    /// If we are within the specified range, return the position to start
101    fn start_run(&self) -> Option<(usize, bool)> {
102        if let Some(last) = &self.last {
103            if last.run.end < self.range.end { Some((last.run.end, !last.value)) } else { None }
104        } else {
105            if self.range.start < self.range.end { Some((self.range.start, 1 == (self.storage[0] & 1))) } else { None }
106        }
107    }
108
109    // Get the current block in a manner ready for `.trailing_zeros()`.
110    fn block(&self, block: usize, of: bool) -> usize {
111        if of { !self.storage[block] } else { self.storage[block] }
112    }
113}
114
115impl<'a> Iterator for RLE<'a> {
116    type Item = RL;
117    fn next(&mut self) -> Option<Self::Item> {
118        let (start, of) = self.start_run()?;
119        let x = start / WORD_WIDTH;
120        let y = start % WORD_WIDTH;
121        let bits_left = WORD_WIDTH - y; // in the block
122        let block = self.block(x, of) >> y;
123        let len = min(block.trailing_zeros() as usize, bits_left);
124        let mut end = start + len;
125        if len == bits_left {
126            let mut x = x + 1;
127            while end < self.range.end {
128                let extra = self.block(x, of).trailing_zeros() as usize;
129                end += extra;
130                if extra != WORD_WIDTH { break; }
131                x += 1;
132            }
133        }
134        let ret = RL::new(of, start, min(end, self.range.end));
135        self.last = Some(ret.clone());
136        Some(ret)
137    }
138}
rle_bitset/lib.rs

rle_bitset/
lib.rs
