primal_bit/
lib.rs

1// Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
2// file at the top-level directory of this distribution and at
3// http://rust-lang.org/COPYRIGHT.
4//
5// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8// option. This file may not be copied, modified, or distributed
9// except according to those terms.
10
11//! A very simple bit-vector that serves the needs of `primal`.
12
13#![deny(unsafe_code)]
14
15use std::fmt;
16use std::hash;
17use std::ops::Index;
18
19mod inner;
20mod iter;
21
22pub use crate::inner::BitVec;
23pub use crate::iter::{Iter, IntoOnes, Ones};
24
25const BITS: usize = 8;
26
27impl Index<usize> for BitVec {
28    type Output = bool;
29
30    #[inline]
31    fn index(&self, i: usize) -> &bool {
32        if self.get(i).expect("index out of bounds") {
33            &true
34        } else {
35            &false
36        }
37    }
38}
39
40impl BitVec {
41    /// Count the number of ones in the entire `BitVec`.
42    #[inline]
43    pub fn count_ones(&self) -> usize {
44        hamming::weight(self.as_bytes()) as usize
45    }
46
47    /// Count the number of ones for the bits up to but not including
48    /// the `bit`th bit.
49    #[inline]
50    pub fn count_ones_before(&self, bit: usize) -> usize {
51        assert!(bit <= self.len());
52        let (byte, bit) = (bit / BITS, bit % BITS);
53        let mask = (1 << bit) - 1;
54
55        let bytes = self.as_bytes();
56
57        hamming::weight(&bytes[..byte]) as usize
58            + bytes.get(byte).map_or(0, |b| (b & mask).count_ones() as usize)
59    }
60
61    /// Find the index of the `n`th (0-indexed) set bit.
62    pub fn find_nth_bit(&self, mut n: usize) -> Option<usize> {
63        if n >= self.len() {
64            return None;
65        }
66        n += 1;
67        let mut bytes = self.as_bytes();
68
69        let mut byte_idx = 0;
70        while bytes.len() > 240 {
71            let ix = bytes.len() / 2;
72            let (first, second) = bytes.split_at(ix);
73
74            let count = hamming::weight(first) as usize;
75            if count >= n {
76                bytes = first;
77            } else {
78                n -= count;
79                bytes = second;
80                byte_idx += ix;
81            }
82        }
83
84        let i = bytes.iter().position(|&b| {
85            let count = b.count_ones() as usize;
86            if count >= n {
87                true
88            } else {
89                n -= count;
90                false
91            }
92        })?;
93
94        // clear the bottom n-1 set bits, so that the lowest one
95        // is the one we care about
96        let mut b = bytes[i];
97        for _ in 1..n {
98            b &= b - 1;
99        }
100        assert!(b != 0);
101
102        Some((byte_idx + i) * BITS + b.trailing_zeros() as usize)
103    }
104
105    /// Sets all bits to 1.
106    ///
107    /// # Examples
108    ///
109    /// ```ignore
110    /// use std::collections::BitVec;
111    ///
112    /// let before = 0b01100000;
113    /// let after  = 0b11111111;
114    ///
115    /// let mut bv = BitVec::from_bytes(&[before]);
116    /// bv.set_all();
117    /// assert_eq!(bv, BitVec::from_bytes(&[after]));
118    /// ```
119    #[inline]
120    pub fn set_all(&mut self) {
121        for w in self.as_bytes_mut() { *w = !0; }
122        self.fix_last_block();
123    }
124
125    /// Clears all bits in this vector.
126    #[inline]
127    pub fn clear(&mut self) {
128        for w in self.as_bytes_mut() { *w = 0; }
129    }
130
131    /// Returns true if there are no bits in this vector
132    #[inline]
133    pub fn is_empty(&self) -> bool { self.len() == 0 }
134}
135
136impl Default for BitVec {
137    #[inline]
138    fn default() -> BitVec { BitVec::new() }
139}
140
141impl fmt::Debug for BitVec {
142    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
143        for bit in self {
144            write!(fmt, "{}", if bit { 1 } else { 0 })?;
145        }
146        Ok(())
147    }
148}
149
150impl hash::Hash for BitVec {
151    fn hash<H: hash::Hasher>(&self, state: &mut H) {
152        state.write_usize(self.len());
153        state.write(self.as_bytes());
154    }
155}
156
157impl PartialEq for BitVec {
158    #[inline]
159    fn eq(&self, other: &BitVec) -> bool {
160        self.len() == other.len() && self.as_bytes() == other.as_bytes()
161    }
162}
163
164impl Eq for BitVec {}
165
166#[cfg(test)]
167mod tests {
168    use super::BitVec;
169
170    #[test]
171    fn count_ones_before() {
172        let len = 10000;
173
174        let ones = BitVec::from_elem(len, true);
175        let zeros = BitVec::from_elem(len, false);
176        let mut halves = zeros.clone();
177        for i in 0..len / 2 {
178            halves.set(i * 2, true);
179        }
180        for i in 0..len + 1 {
181            assert_eq!(ones.count_ones_before(i), i);
182            assert_eq!(zeros.count_ones_before(i), 0);
183            assert_eq!(halves.count_ones_before(i), (i + 1) / 2);
184        }
185    }
186
187    #[test]
188    fn find_nth_bit() {
189        let len = 5000;
190
191        let ones = BitVec::from_elem(len, true);
192        let mut halves = BitVec::from_elem(len * 2, false);
193        for i in 0..len {
194            halves.set(i * 2, true);
195        }
196        for i in 0..len {
197            assert_eq!(ones.find_nth_bit(i), Some(i));
198            assert_eq!(halves.find_nth_bit(i), Some(i * 2));
199        }
200        assert_eq!(ones.find_nth_bit(len + 1), None);
201        assert_eq!(halves.find_nth_bit(len + 1), None);
202
203        assert_eq!(BitVec::new().find_nth_bit(0), None);
204        assert_eq!(BitVec::from_elem(len, false).find_nth_bit(0), None);
205    }
206
207    #[test]
208    fn get() {
209        let len = 10000;
210
211        let mut halves = BitVec::from_elem(len, false);
212        for i in 0..len {
213            assert_eq!(halves.get(i), Some(false));
214        }
215        for i in 0..len / 2 {
216            halves.set(i * 2, true);
217        }
218        for i in 0..len {
219            assert_eq!(halves.get(i), Some(i % 2 == 0));
220        }
221        assert_eq!(halves.get(len), None);
222    }
223
224    #[test]
225    fn clone() {
226        let len = 10000;
227
228        let ones = BitVec::from_elem(len, true);
229        let zeros = BitVec::from_elem(len, false);
230        let mut halves = zeros.clone();
231        for i in 0..len / 2 {
232            halves.set(i * 2, true);
233        }
234
235        assert_eq!(ones.clone(), ones);
236        assert_eq!(zeros.clone(), zeros);
237        assert_eq!(halves.clone(), halves);
238
239        let mut bv = BitVec::from_elem(len, false);
240        bv.clone_from(&ones);
241        assert_eq!(bv, ones);
242        bv.clone_from(&zeros);
243        assert_eq!(bv, zeros);
244        bv.clone_from(&halves);
245        assert_eq!(bv, halves);
246    }
247
248    #[test]
249    fn len_is_empty() {
250        let len = 10000;
251
252        let ones = BitVec::from_elem(len, true);
253        let zeros = BitVec::from_elem(len, false);
254        let default = BitVec::default();
255
256        assert_eq!(ones.len(), len);
257        assert_eq!(zeros.len(), len);
258        assert_eq!(default.len(), 0);
259
260        assert!(!ones.is_empty());
261        assert!(!zeros.is_empty());
262        assert!(default.is_empty());
263    }
264
265    #[test]
266    fn clear_set_all() {
267        let len = 10000;
268
269        let ones = BitVec::from_elem(len, true);
270        let zeros = BitVec::from_elem(len, false);
271
272        let mut bv = ones.clone();
273        assert_eq!(bv, ones);
274        bv.clear();
275        assert_eq!(bv, zeros);
276        bv.set_all();
277        assert_eq!(bv, ones);
278    }
279}
primal_bit/lib.rs

primal_bit/
lib.rs
