Trait BitString

pub trait BitString: Eq {
    // Required methods
    fn get(&self, ndx: usize) -> bool;
    fn set(&mut self, ndx: usize, bit: bool);
    fn flip(&mut self, ndx: usize);
    fn len(&self) -> usize;
    fn clip(&mut self, len: usize);
    fn append(&mut self, bit: bool);
    fn null() -> Self;

    // Provided methods
    fn shared_prefix_len(&self, other: &Self) -> usize { ... }
    fn shared_prefix(&self, other: &Self) -> Self
       where Self: Clone { ... }
    fn subset_cmp(&self, other: &Self) -> Option<Ordering> { ... }
    fn lexicographic_cmp(&self, other: &Self) -> Ordering { ... }
}

A bit string with variable (but possibly limited) length.

The length limit might depend on the current string; that is why writing a bit might truncate the string (but not the bit that was just modified). “Writing” a bit also includes writing without actually changing it.

This special case is needed to handle variants with different (maximum) lengths: a small prefix indicates the variant, then follows the actual data of the variant.

As an example one might want to combine IPv4 and IPv6 cidr representations into one BitString type; the empty bit string would represent 0.0.0.0/0 + ::/0.

Apart from this special case writing a bit must not modify any other bits or change the length.

The required Eq implementation must match comparing two bitstrings by their bits (up to their length); i.e. BitStrings must not carry additional data apart from the bits (and mustn’t compare unused bits in the storage if their value isn’t fixed).

Required Methods

fn get(&self, ndx: usize) -> bool

Get the ndxth bit.

Panics

Should panic if ndx >= self.len().

fn set(&mut self, ndx: usize, bit: bool)

Set the ndxth bit to bit.

Might clip the length to ndx+1.

Panics

Should panic if ndx >= self.len().

fn flip(&mut self, ndx: usize)

Flips the ndxth bit.

Panics

Should panic if ndx >= self.len().

fn len(&self) -> usize

Current length of the bit string in bits.

fn clip(&mut self, len: usize)

Set current length to len.

Does nothing if len <= self.len().

If necessary should also zero the underlying storage if Eq needs it to work properly.

fn append(&mut self, bit: bool)

Append a bit.

Panics

Might panic if underlying storage can only store a limited number of bits.

fn null() -> Self

Create a new zero-length bit string.

Underlying storage should be zeroed if Eq needs it to work properly.

Provided Methods

fn shared_prefix_len(&self, other: &Self) -> usize

Length of the longest shared prefix of two bit strings.

fn shared_prefix(&self, other: &Self) -> Self

where Self: Clone,

Longest shared prefix of two bit strings.

fn subset_cmp(&self, other: &Self) -> Option<Ordering>

Partial ordering on bit strings.

Formal definition:

    `a < b` iff `a != b` and `b` is a prefix of `a`

If you view a bit string as a set including all bit strings starting with it, this is the subset relation.

fn lexicographic_cmp(&self, other: &Self) -> Ordering

Lexicographic ordering on bit strings.

Formal definition:

    `a < b` iff `a != b` and (
        `b` is a prefix of `a`
        or `a[s] < b[s]`
             where s is the smallest index with `a[s] != b[s]`)

Or, if you define _|_ < false < true:

    `a < b` iff `a[s] < b[s]`
        where s is the smallest index with `a[s] != b[s]`

Object Safety

This trait is not object safe.

Implementors