1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124
use std::cmp::min;
use fixed_bit_string::Iter;
/// A bit string with fixed length.
///
/// All bits must me mutable, and there must be no dependencies between
/// bits (i.e. setting one bit must not change any other bit).
pub trait FixedBitString {
/// Treat bit string as integer, where bit 0 is the most significant
/// bit.
///
/// Increment by one, i.e. start by incrementing the bit with the
/// highest index.
///
/// Don't touch first `prefix` bits; return true on overflow.
///
/// # Panics
///
/// Should panic if `prefix > self.len()`.
fn inc(&mut self, prefix: usize) -> bool;
/// Iterate through all bit strings until `inc` overflows.
///
/// All generated values will share the first `prefix` bits. If you
/// want to iterate over all values make sure to call
/// `self.set_false_from(prefix)` before.
///
/// # Panics
///
/// Should panic if `prefix > self.len()`.
fn iter(&self, prefix: usize) -> Iter<Self>
where
Self: Sized + Clone,
{
Iter::new(self.clone(), prefix)
}
/// Length of the bit string in bits.
fn len() -> usize;
/// Get the `ndx`th bit.
///
/// # Panics
///
/// Should panic if `ndx >= self.len()`.
fn get(&self, ndx: usize) -> bool;
/// Set the `ndx`th bit to `bit`.
///
/// # Panics
///
/// Should panic if `ndx >= self.len()`.
fn set(&mut self, ndx: usize, bit: bool);
/// Set the `ndx`th bit to `true`.
///
/// # Panics
///
/// Should panic if `ndx >= self.len()`.
fn on(&mut self, ndx: usize) {
self.set(ndx, true);
}
/// Set the `ndx`th bit to `false`.
///
/// # Panics
///
/// Should panic if `ndx >= self.len()`.
fn off(&mut self, ndx: usize) {
self.set(ndx, false);
}
/// Flips the `ndx`th bit.
///
/// # Panics
///
/// Should panic if `ndx >= self.len()`.
fn flip(&mut self, ndx: usize) {
let old_value = self.get(ndx);
self.set(ndx, !old_value);
}
/// Length of the longest shared prefix of two bit strings.
fn shared_prefix_len(&self, other: &Self, max_len: usize) -> usize {
let max_len = min(max_len, Self::len());
for i in 0..max_len {
if self.get(i) != other.get(i) {
return i;
}
}
max_len
}
/// Set all bits in [ndx..] to `false`.
///
/// Doesn't do anything if `ndx >= self.len()`.
fn set_false_from(&mut self, ndx: usize);
/// Whether all bits in [ndx..] are `false`.
///
/// Returns `true` if `ndx >= self.len()`.
fn is_false_from(&self, ndx: usize) -> bool;
/// Set all bits in [ndx..] to `true`.
///
/// Doesn't do anything if `ndx >= self.len()`.
fn set_true_from(&mut self, ndx: usize);
/// Whether all bits in [ndx..] are `true`.
///
/// Returns `true` if `ndx >= self.len()`.
fn is_true_from(&self, ndx: usize) -> bool;
/// New bit string with all bits set to `false`.
fn new_all_false() -> Self;
/// New bit string with all bits set to `true`.
fn new_all_true() -> Self;
/// check whether another bit string `other` shares the first
/// `prefix` bits with `self`
fn contains(&self, prefix: usize, other: &Self) -> bool;
}