Struct collections::BitvSetExperimental
[-]
[+]
[src]
pub struct BitvSet(_);
An implementation of a set using a bit vector as an underlying representation for holding unsigned 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.
Example
extern crate collections; fn main() { use std::collections::{BitvSet, Bitv}; use std::collections::bitv; // It's a regular set let mut s = BitvSet::new(); s.insert(0); s.insert(3); s.insert(7); s.remove(&7); if !s.contains(&7) { println!("There is no 7"); } // Can initialize from a `Bitv` let other = BitvSet::from_bitv(bitv::from_bytes(&[0b11010000])); s.union_with(&other); // Print 0, 1, 3 in some order for x in s.iter() { println!("{}", x); } // Can convert back to a `Bitv` let bv: Bitv = s.into_bitv(); assert!(bv.get(3)); }use std::collections::{BitvSet, Bitv}; use std::collections::bitv; // It's a regular set let mut s = BitvSet::new(); s.insert(0); s.insert(3); s.insert(7); s.remove(&7); if !s.contains(&7) { println!("There is no 7"); } // Can initialize from a `Bitv` let other = BitvSet::from_bitv(bitv::from_bytes(&[0b11010000])); s.union_with(&other); // Print 0, 1, 3 in some order for x in s.iter() { println!("{}", x); } // Can convert back to a `Bitv` let bv: Bitv = s.into_bitv(); assert!(bv.get(3));
Methods
impl BitvSet
fn new() -> BitvSet
Creates a new bit vector set with initially no contents.
Example
extern crate collections; fn main() { use std::collections::BitvSet; let mut s = BitvSet::new(); }use std::collections::BitvSet; let mut s = BitvSet::new();
fn with_capacity(nbits: uint) -> BitvSet
Creates a new bit vector set with initially no contents, able to
hold nbits elements without resizing.
Example
extern crate collections; fn main() { use std::collections::BitvSet; let mut s = BitvSet::with_capacity(100); assert!(s.capacity() >= 100); }use std::collections::BitvSet; let mut s = BitvSet::with_capacity(100); assert!(s.capacity() >= 100);
fn from_bitv(bitv: Bitv) -> BitvSet
Creates a new bit vector set from the given bit vector.
Example
extern crate collections; fn main() { use std::collections::{bitv, BitvSet}; let bv = bitv::from_bytes(&[0b01100000]); let s = BitvSet::from_bitv(bv); // Print 1, 2 in arbitrary order for x in s.iter() { println!("{}", x); } }use std::collections::{bitv, BitvSet}; let bv = bitv::from_bytes(&[0b01100000]); let s = BitvSet::from_bitv(bv); // Print 1, 2 in arbitrary order for x in s.iter() { println!("{}", x); }
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.
Example
extern crate collections; fn main() { use std::collections::BitvSet; let mut s = BitvSet::with_capacity(100); assert!(s.capacity() >= 100); }use std::collections::BitvSet; let mut s = BitvSet::with_capacity(100); assert!(s.capacity() >= 100);
fn reserve(&mut self, size: uint)
Grows the underlying vector to be able to store size bits.
Example
extern crate collections; fn main() { use std::collections::BitvSet; let mut s = BitvSet::new(); s.reserve(10); assert!(s.capacity() >= 10); }use std::collections::BitvSet; let mut s = BitvSet::new(); s.reserve(10); assert!(s.capacity() >= 10);
fn into_bitv(self) -> Bitv
Consumes this set to return the underlying bit vector.
Example
extern crate collections; fn main() { use std::collections::BitvSet; let mut s = BitvSet::new(); s.insert(0); s.insert(3); let bv = s.into_bitv(); assert!(bv.get(0)); assert!(bv.get(3)); }use std::collections::BitvSet; let mut s = BitvSet::new(); s.insert(0); s.insert(3); let bv = s.into_bitv(); assert!(bv.get(0)); assert!(bv.get(3));
fn get_ref<'a>(&'a self) -> &'a Bitv
Returns a reference to the underlying bit vector.
Example
extern crate collections; fn main() { use std::collections::BitvSet; let mut s = BitvSet::new(); s.insert(0); let bv = s.get_ref(); assert_eq!(bv[0], true); }use std::collections::BitvSet; let mut s = BitvSet::new(); s.insert(0); let bv = s.get_ref(); assert_eq!(bv[0], true);
fn shrink_to_fit(&mut self)
Truncates the underlying vector to the least length required.
Example
extern crate collections; fn main() { use std::collections::BitvSet; let mut s = BitvSet::new(); s.insert(32183231); s.remove(&32183231); // Internal storage will probably be bigger than necessary println!("old capacity: {}", s.capacity()); // Now should be smaller s.shrink_to_fit(); println!("new capacity: {}", s.capacity()); }use std::collections::BitvSet; let mut s = BitvSet::new(); s.insert(32183231); s.remove(&32183231); // Internal storage will probably be bigger than necessary println!("old capacity: {}", s.capacity()); // Now should be smaller s.shrink_to_fit(); println!("new capacity: {}", s.capacity());
fn iter<'a>(&'a self) -> BitPositions<'a>
Iterator over each u32 stored in the BitvSet.
Example
extern crate collections; fn main() { use std::collections::BitvSet; use std::collections::bitv; let s = BitvSet::from_bitv(bitv::from_bytes(&[0b01001010])); // Print 1, 4, 6 in arbitrary order for x in s.iter() { println!("{}", x); } }use std::collections::BitvSet; use std::collections::bitv; let s = BitvSet::from_bitv(bitv::from_bytes(&[0b01001010])); // Print 1, 4, 6 in arbitrary order for x in s.iter() { println!("{}", x); }
fn union<'a>(&'a self, other: &'a BitvSet) -> TwoBitPositions<'a>
Iterator over each u32 stored in self union other.
See union_with for an efficient in-place version.
Example
extern crate collections; fn main() { use std::collections::BitvSet; use std::collections::bitv; let a = BitvSet::from_bitv(bitv::from_bytes(&[0b01101000])); let b = BitvSet::from_bitv(bitv::from_bytes(&[0b10100000])); // Print 0, 1, 2, 4 in arbitrary order for x in a.union(&b) { println!("{}", x); } }use std::collections::BitvSet; use std::collections::bitv; let a = BitvSet::from_bitv(bitv::from_bytes(&[0b01101000])); let b = BitvSet::from_bitv(bitv::from_bytes(&[0b10100000])); // Print 0, 1, 2, 4 in arbitrary order for x in a.union(&b) { println!("{}", x); }
fn intersection<'a>(&'a self, other: &'a BitvSet) -> Take<TwoBitPositions<'a>>
Iterator over each uint stored in self intersect other.
See intersect_with for an efficient in-place version.
Example
extern crate collections; fn main() { use std::collections::BitvSet; use std::collections::bitv; let a = BitvSet::from_bitv(bitv::from_bytes(&[0b01101000])); let b = BitvSet::from_bitv(bitv::from_bytes(&[0b10100000])); // Print 2 for x in a.intersection(&b) { println!("{}", x); } }use std::collections::BitvSet; use std::collections::bitv; let a = BitvSet::from_bitv(bitv::from_bytes(&[0b01101000])); let b = BitvSet::from_bitv(bitv::from_bytes(&[0b10100000])); // Print 2 for x in a.intersection(&b) { println!("{}", x); }
fn difference<'a>(&'a self, other: &'a BitvSet) -> TwoBitPositions<'a>
Iterator over each uint stored in the self setminus other.
See difference_with for an efficient in-place version.
Example
extern crate collections; fn main() { use std::collections::BitvSet; use std::collections::bitv; let a = BitvSet::from_bitv(bitv::from_bytes(&[0b01101000])); let b = BitvSet::from_bitv(bitv::from_bytes(&[0b10100000])); // Print 1, 4 in arbitrary order for x in a.difference(&b) { println!("{}", x); } // Note that difference is not symmetric, // and `b - a` means something else. // This prints 0 for x in b.difference(&a) { println!("{}", x); } }use std::collections::BitvSet; use std::collections::bitv; let a = BitvSet::from_bitv(bitv::from_bytes(&[0b01101000])); let b = BitvSet::from_bitv(bitv::from_bytes(&[0b10100000])); // Print 1, 4 in arbitrary order for x in a.difference(&b) { println!("{}", x); } // Note that difference is not symmetric, // and `b - a` means something else. // This prints 0 for x in b.difference(&a) { println!("{}", x); }
fn symmetric_difference<'a>(&'a self, other: &'a BitvSet) -> TwoBitPositions<'a>
Iterator over each u32 stored in the symmetric difference of self and other.
See symmetric_difference_with for
an efficient in-place version.
Example
extern crate collections; fn main() { use std::collections::BitvSet; use std::collections::bitv; let a = BitvSet::from_bitv(bitv::from_bytes(&[0b01101000])); let b = BitvSet::from_bitv(bitv::from_bytes(&[0b10100000])); // Print 0, 1, 4 in arbitrary order for x in a.symmetric_difference(&b) { println!("{}", x); } }use std::collections::BitvSet; use std::collections::bitv; let a = BitvSet::from_bitv(bitv::from_bytes(&[0b01101000])); let b = BitvSet::from_bitv(bitv::from_bytes(&[0b10100000])); // Print 0, 1, 4 in arbitrary order for x in a.symmetric_difference(&b) { println!("{}", x); }
fn union_with(&mut self, other: &BitvSet)
Unions in-place with the specified other bit vector.
Example
extern crate collections; fn main() { use std::collections::BitvSet; use std::collections::bitv; let a = 0b01101000; let b = 0b10100000; let res = 0b11101000; let mut a = BitvSet::from_bitv(bitv::from_bytes(&[a])); let b = BitvSet::from_bitv(bitv::from_bytes(&[b])); let res = BitvSet::from_bitv(bitv::from_bytes(&[res])); a.union_with(&b); assert_eq!(a, res); }use std::collections::BitvSet; use std::collections::bitv; let a = 0b01101000; let b = 0b10100000; let res = 0b11101000; let mut a = BitvSet::from_bitv(bitv::from_bytes(&[a])); let b = BitvSet::from_bitv(bitv::from_bytes(&[b])); let res = BitvSet::from_bitv(bitv::from_bytes(&[res])); a.union_with(&b); assert_eq!(a, res);
fn intersect_with(&mut self, other: &BitvSet)
Intersects in-place with the specified other bit vector.
Example
extern crate collections; fn main() { use std::collections::BitvSet; use std::collections::bitv; let a = 0b01101000; let b = 0b10100000; let res = 0b00100000; let mut a = BitvSet::from_bitv(bitv::from_bytes(&[a])); let b = BitvSet::from_bitv(bitv::from_bytes(&[b])); let res = BitvSet::from_bitv(bitv::from_bytes(&[res])); a.intersect_with(&b); assert_eq!(a, res); }use std::collections::BitvSet; use std::collections::bitv; let a = 0b01101000; let b = 0b10100000; let res = 0b00100000; let mut a = BitvSet::from_bitv(bitv::from_bytes(&[a])); let b = BitvSet::from_bitv(bitv::from_bytes(&[b])); let res = BitvSet::from_bitv(bitv::from_bytes(&[res])); a.intersect_with(&b); assert_eq!(a, res);
fn difference_with(&mut self, other: &BitvSet)
Makes this bit vector the difference with the specified other bit vector in-place.
Example
extern crate collections; fn main() { use std::collections::BitvSet; use std::collections::bitv; let a = 0b01101000; let b = 0b10100000; let a_b = 0b01001000; // a - b let b_a = 0b10000000; // b - a let mut bva = BitvSet::from_bitv(bitv::from_bytes(&[a])); let bvb = BitvSet::from_bitv(bitv::from_bytes(&[b])); let bva_b = BitvSet::from_bitv(bitv::from_bytes(&[a_b])); let bvb_a = BitvSet::from_bitv(bitv::from_bytes(&[b_a])); bva.difference_with(&bvb); assert_eq!(bva, bva_b); let bva = BitvSet::from_bitv(bitv::from_bytes(&[a])); let mut bvb = BitvSet::from_bitv(bitv::from_bytes(&[b])); bvb.difference_with(&bva); assert_eq!(bvb, bvb_a); }use std::collections::BitvSet; use std::collections::bitv; let a = 0b01101000; let b = 0b10100000; let a_b = 0b01001000; // a - b let b_a = 0b10000000; // b - a let mut bva = BitvSet::from_bitv(bitv::from_bytes(&[a])); let bvb = BitvSet::from_bitv(bitv::from_bytes(&[b])); let bva_b = BitvSet::from_bitv(bitv::from_bytes(&[a_b])); let bvb_a = BitvSet::from_bitv(bitv::from_bytes(&[b_a])); bva.difference_with(&bvb); assert_eq!(bva, bva_b); let bva = BitvSet::from_bitv(bitv::from_bytes(&[a])); let mut bvb = BitvSet::from_bitv(bitv::from_bytes(&[b])); bvb.difference_with(&bva); assert_eq!(bvb, bvb_a);
fn symmetric_difference_with(&mut self, other: &BitvSet)
Makes this bit vector the symmetric difference with the specified other bit vector in-place.
Example
extern crate collections; fn main() { use std::collections::BitvSet; use std::collections::bitv; let a = 0b01101000; let b = 0b10100000; let res = 0b11001000; let mut a = BitvSet::from_bitv(bitv::from_bytes(&[a])); let b = BitvSet::from_bitv(bitv::from_bytes(&[b])); let res = BitvSet::from_bitv(bitv::from_bytes(&[res])); a.symmetric_difference_with(&b); assert_eq!(a, res); }use std::collections::BitvSet; use std::collections::bitv; let a = 0b01101000; let b = 0b10100000; let res = 0b11001000; let mut a = BitvSet::from_bitv(bitv::from_bytes(&[a])); let b = BitvSet::from_bitv(bitv::from_bytes(&[b])); let res = BitvSet::from_bitv(bitv::from_bytes(&[res])); a.symmetric_difference_with(&b); assert_eq!(a, res);
fn len(&self) -> uint
Return the number of set bits in this set.
fn is_empty(&self) -> bool
Returns whether there are no bits set in this set
fn clear(&mut self)
Clears all bits in this set
fn contains(&self, value: &uint) -> bool
Returns true if this set contains the specified integer.
fn is_disjoint(&self, other: &BitvSet) -> bool
Returns true if the set has no elements in common with other.
This is equivalent to checking for an empty intersection.
fn is_subset(&self, other: &BitvSet) -> bool
Returns true if the set is a subset of another.
fn is_superset(&self, other: &BitvSet) -> bool
Returns true if the set is a superset of another.
fn insert(&mut self, value: uint) -> bool
Adds a value to the set. Returns true if the value was not already
present in the set.
fn remove(&mut self, value: &uint) -> bool
Removes a value from the set. Returns true if the value was
present in the set.