Bitv
- The bitvector typeBitvSet
- An implementation of a set using a bit vector as an underlying representation for holding numerical elements.for SmallBitv
for BigBitv
for Bitv
of Clone for Bitv
of ops::Index<uint, bool> for Bitv
for BitvSet
of cmp::Eq for BitvSet
of Container for BitvSet
of Mutable for BitvSet
of Set<uint> for BitvSet
from_bools
- Transform a [bool] into a bitv by converting each bool into a bit.from_bytes
- Transform a byte-vector into a bitvfrom_fn
- Create a bitv of the specified length where the value at each index is f(index).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
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.
SmallBitv
new
fn new(bits: uint) -> SmallBitv
bits_op
fn bits_op(&mut self, right_bits: uint, nbits: uint,
f: &fn(uint, uint) -> uint) -> bool
union
fn union(&mut self, s: &SmallBitv, nbits: uint) -> bool
intersect
fn intersect(&mut self, s: &SmallBitv, nbits: uint) -> bool
become
fn become(&mut self, s: &SmallBitv, nbits: uint) -> bool
difference
fn difference(&mut self, s: &SmallBitv, nbits: uint) -> bool
get
fn get(&self, i: uint) -> bool
set
fn set(&mut self, i: uint, x: bool)
equals
fn equals(&self, b: &SmallBitv, nbits: uint) -> bool
clear
fn clear(&mut self)
set_all
fn set_all(&mut self)
is_true
fn is_true(&self, nbits: uint) -> bool
is_false
fn is_false(&self, nbits: uint) -> bool
invert
fn invert(&mut self)
BigBitv
new
fn new(storage: ~[uint]) -> BigBitv
process
fn process(&mut self, b: &BigBitv, nbits: uint, op: &fn(uint, uint) -> uint)
-> bool
each_storage
fn each_storage(&mut self, op: &fn(v: &mut uint) -> bool) -> bool
invert
fn invert(&mut self)
union
fn union(&mut self, b: &BigBitv, nbits: uint) -> bool
intersect
fn intersect(&mut self, b: &BigBitv, nbits: uint) -> bool
become
fn become(&mut self, b: &BigBitv, nbits: uint) -> bool
difference
fn difference(&mut self, b: &BigBitv, nbits: uint) -> bool
get
fn get(&self, i: uint) -> bool
set
fn set(&mut self, i: uint, x: bool)
equals
fn equals(&self, b: &BigBitv, nbits: uint) -> bool
Bitv
new
fn new(nbits: uint, init: bool) -> Bitv
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.
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.
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
get
fn get(&self, i: uint) -> bool
Retrieve the value at index i
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.
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.
clear
fn clear(&mut self)
Set all bits to 0
set_all
fn set_all(&mut self)
Set all bits to 1
invert
fn invert(&mut self)
Invert all bits
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.
is_true
fn is_true(&self) -> bool
Returns true if all bits are 1
each
fn each(&self, f: &fn(bool) -> bool) -> bool
is_false
fn is_false(&self) -> bool
Returns true if all bits are 0
init_to_vec
fn init_to_vec(&self, i: uint) -> uint
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.
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
to_bools
fn to_bools(&self) -> ~[bool]
Transform self into a [bool] by turning each bit into a bool
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'.
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
ones
fn ones(&self, f: &fn(uint) -> bool) -> bool
Clone
for Bitv
clone
fn clone(&self) -> Bitv
Makes a copy of a bitvector
ops::Index<uint, bool>
for Bitv
index
fn index(&self, i: &uint) -> bool
BitvSet
new
fn new() -> BitvSet
Creates a new bit vector set with initially no contents
from_bitv
fn from_bitv(bitv: Bitv) -> BitvSet
Creates a new bit vector set from the given bit vector
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.
unwrap
fn unwrap(self) -> Bitv
Consumes this set to return the underlying bit vector
union_with
fn union_with(&mut self, other: &BitvSet)
Union in-place with the specified other bit vector
intersect_with
fn intersect_with(&mut self, other: &BitvSet)
Intersect in-place with the specified other bit vector
difference_with
fn difference_with(&mut self, other: &BitvSet)
Difference in-place with the specified other bit vector
symmetric_difference_with
fn symmetric_difference_with(&mut self, other: &BitvSet)
Symmetric difference in-place with the specified other bit vector
each
fn each(&self, blk: &fn(v: &uint) -> bool) -> bool
cmp::Eq
for BitvSet
eq
fn eq(&self, other: &BitvSet) -> bool
ne
fn ne(&self, other: &BitvSet) -> bool
Container
for BitvSet
len
fn len(&self) -> uint
is_empty
fn is_empty(&self) -> bool
Mutable
for BitvSet
clear
fn clear(&mut self)
Set<uint>
for BitvSet
contains
fn contains(&self, value: &uint) -> bool
insert
fn insert(&mut self, value: uint) -> bool
remove
fn remove(&mut self, value: &uint) -> bool
is_disjoint
fn is_disjoint(&self, other: &BitvSet) -> bool
is_subset
fn is_subset(&self, other: &BitvSet) -> bool
is_superset
fn is_superset(&self, other: &BitvSet) -> bool
difference
fn difference(&self, other: &BitvSet, f: &fn(&uint) -> bool) -> bool
symmetric_difference
fn symmetric_difference(&self, other: &BitvSet, f: &fn(&uint) -> bool) -> bool
intersection
fn intersection(&self, other: &BitvSet, f: &fn(&uint) -> bool) -> bool
union
fn union(&self, other: &BitvSet, f: &fn(&uint) -> bool) -> bool
from_bools
fn from_bools(bools: &[bool]) -> Bitv
Transform a [bool] into a bitv by converting each bool into a bit.
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.
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).