Struct Bitv

pub struct Bitv {
    /// Internal representation of the bit vector (small or large)
    rep: BitvVariant,
    /// The number of valid bits in the internal representation
    nbits: uint,
}

The bitvector type

Struct BitvSet

pub struct BitvSet {
    priv size: uint,
    priv bitv: BigBitv,
}

An implementation of a set using a bit vector as an underlying representation for holding numerical elements.

It should also be noted that the amount of storage necessary for holding a set of objects is proportional to the maximum of the objects when viewed as a uint.

Implementation for SmallBitv

Method new

fn new(bits: uint) -> SmallBitv

Method bits_op

fn bits_op(&mut self, right_bits: uint, nbits: uint,
           f: &fn(uint, uint) -> uint) -> bool

Method union

fn union(&mut self, s: &SmallBitv, nbits: uint) -> bool

Method intersect

fn intersect(&mut self, s: &SmallBitv, nbits: uint) -> bool

Method become

fn become(&mut self, s: &SmallBitv, nbits: uint) -> bool

Method difference

fn difference(&mut self, s: &SmallBitv, nbits: uint) -> bool

Method get

fn get(&self, i: uint) -> bool

Method set

fn set(&mut self, i: uint, x: bool)

Method equals

fn equals(&self, b: &SmallBitv, nbits: uint) -> bool

Method clear

fn clear(&mut self)

Method set_all

fn set_all(&mut self)

Method is_true

fn is_true(&self, nbits: uint) -> bool

Method is_false

fn is_false(&self, nbits: uint) -> bool

Method invert

fn invert(&mut self)

Implementation for BigBitv

Method new

fn new(storage: ~[uint]) -> BigBitv

Method process

fn process(&mut self, b: &BigBitv, nbits: uint, op: &fn(uint, uint) -> uint)
 -> bool

Method each_storage

fn each_storage(&mut self, op: &fn(v: &mut uint) -> bool) -> bool

Method invert

fn invert(&mut self)

Method union

fn union(&mut self, b: &BigBitv, nbits: uint) -> bool

Method intersect

fn intersect(&mut self, b: &BigBitv, nbits: uint) -> bool

Method become

fn become(&mut self, b: &BigBitv, nbits: uint) -> bool

Method difference

fn difference(&mut self, b: &BigBitv, nbits: uint) -> bool

Method get

fn get(&self, i: uint) -> bool

Method set

fn set(&mut self, i: uint, x: bool)

Method equals

fn equals(&self, b: &BigBitv, nbits: uint) -> bool

Implementation for Bitv

Method new

fn new(nbits: uint, init: bool) -> Bitv

Method union

fn union(&mut self, v1: &Bitv) -> bool

Calculates the union of two bitvectors

Sets self to the union of self and v1. Both bitvectors must be the same length. Returns 'true' if self changed.

Method intersect

fn intersect(&mut self, v1: &Bitv) -> bool

Calculates the intersection of two bitvectors

Sets self to the intersection of self and v1. Both bitvectors must be the same length. Returns 'true' if self changed.

Method assign

fn assign(&mut self, v: &Bitv) -> bool

Assigns the value of v1 to self

Both bitvectors must be the same length. Returns true if self was changed

Method get

fn get(&self, i: uint) -> bool

Retrieve the value at index i

Method set

fn set(&mut self, i: uint, x: bool)

Set the value of a bit at a given index

i must be less than the length of the bitvector.

Method equal

fn equal(&self, v1: &Bitv) -> bool

Compares two bitvectors

Both bitvectors must be the same length. Returns true if both bitvectors contain identical elements.

Method clear

fn clear(&mut self)

Set all bits to 0

Method set_all

fn set_all(&mut self)

Set all bits to 1

Method invert

fn invert(&mut self)

Invert all bits

Method difference

fn difference(&mut self, v: &Bitv) -> bool

Calculate the difference between two bitvectors

Sets each element of v0 to the value of that element minus the element of v1 at the same index. Both bitvectors must be the same length.

Returns true if v0 was changed.

Method is_true

fn is_true(&self) -> bool

Returns true if all bits are 1

Method each

fn each(&self, f: &fn(bool) -> bool) -> bool

Method is_false

fn is_false(&self) -> bool

Returns true if all bits are 0

Method init_to_vec

fn init_to_vec(&self, i: uint) -> uint

Method to_vec

fn to_vec(&self) -> ~[uint]

Converts self to a vector of uint with the same length.

Each uint in the resulting vector has either value 0u or 1u.

Method to_bytes

fn to_bytes(&self) -> ~[u8]

Organise the bits into bytes, such that the first bit in the bitv becomes the high-order bit of the first byte. If the size of the bitv is not a multiple of 8 then trailing bits will be filled-in with false/0

Method to_bools

fn to_bools(&self) -> ~[bool]

Transform self into a [bool] by turning each bit into a bool

Method to_str

fn to_str(&self) -> ~str

Converts self to a string.

The resulting string has the same length as self, and each character is either '0' or '1'.

Method eq_vec

fn eq_vec(&self, v: ~[uint]) -> bool

Compare a bitvector to a vector of uint

The uint vector is expected to only contain the values 0u and 1u. Both the bitvector and vector must have the same length

Method ones

fn ones(&self, f: &fn(uint) -> bool) -> bool

Implementation of Clone for Bitv

Method clone

fn clone(&self) -> Bitv

Makes a copy of a bitvector

Implementation of ops::Index<uint, bool> for Bitv

Method index

fn index(&self, i: &uint) -> bool

Implementation for BitvSet

Method new

fn new() -> BitvSet

Creates a new bit vector set with initially no contents

Method from_bitv

fn from_bitv(bitv: Bitv) -> BitvSet

Creates a new bit vector set from the given bit vector

Method capacity

fn capacity(&self) -> uint

Returns the capacity in bits for this bit vector. Inserting any element less than this amount will not trigger a resizing.

Method unwrap

fn unwrap(self) -> Bitv

Consumes this set to return the underlying bit vector

Method union_with

fn union_with(&mut self, other: &BitvSet)

Union in-place with the specified other bit vector

Method intersect_with

fn intersect_with(&mut self, other: &BitvSet)

Intersect in-place with the specified other bit vector

Method difference_with

fn difference_with(&mut self, other: &BitvSet)

Difference in-place with the specified other bit vector

Method symmetric_difference_with

fn symmetric_difference_with(&mut self, other: &BitvSet)

Symmetric difference in-place with the specified other bit vector

Method each

fn each(&self, blk: &fn(v: &uint) -> bool) -> bool

Implementation of cmp::Eq for BitvSet

Method eq

fn eq(&self, other: &BitvSet) -> bool

Method ne

fn ne(&self, other: &BitvSet) -> bool

Implementation of Container for BitvSet

Method len

fn len(&self) -> uint

Method is_empty

fn is_empty(&self) -> bool

Implementation of Mutable for BitvSet

Method clear

fn clear(&mut self)

Implementation of Set<uint> for BitvSet

Method contains

fn contains(&self, value: &uint) -> bool

Method insert

fn insert(&mut self, value: uint) -> bool

Method remove

fn remove(&mut self, value: &uint) -> bool

Method is_disjoint

fn is_disjoint(&self, other: &BitvSet) -> bool

Method is_subset

fn is_subset(&self, other: &BitvSet) -> bool

Method is_superset

fn is_superset(&self, other: &BitvSet) -> bool

Method difference

fn difference(&self, other: &BitvSet, f: &fn(&uint) -> bool) -> bool

Method symmetric_difference

fn symmetric_difference(&self, other: &BitvSet, f: &fn(&uint) -> bool) -> bool

Method intersection

fn intersection(&self, other: &BitvSet, f: &fn(&uint) -> bool) -> bool

Method union

fn union(&self, other: &BitvSet, f: &fn(&uint) -> bool) -> bool

Function from_bools

fn from_bools(bools: &[bool]) -> Bitv

Transform a [bool] into a bitv by converting each bool into a bit.

Function from_bytes

fn from_bytes(bytes: &[u8]) -> Bitv

Transform a byte-vector into a bitv. Each byte becomes 8 bits, with the most significant bits of each byte coming first. Each bit becomes true if equal to 1 or false if equal to 0.

Function from_fn

fn from_fn(len: uint, f: &fn(index: uint) -> bool) -> Bitv

Create a bitv of the specified length where the value at each index is f(index).