Struct std::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

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

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

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

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

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

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

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 self) -> &'a Bitv

Returns a reference to the underlying bit vector.

Example

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

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 self) -> BitPositions<'a>

Iterator over each u32 stored in the BitvSet.

Example

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 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

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 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

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 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

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 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

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

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

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

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

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.

Trait Implementations

impl Default for BitvSet

fn default() -> BitvSet

impl FromIterator<bool> for BitvSet

fn from_iter<I: Iterator<bool>>(iterator: I) -> BitvSet

impl Extend<bool> for BitvSet

fn extend<I: Iterator<bool>>(&mut self, iterator: I)

impl PartialOrd for BitvSet

fn partial_cmp(&self, other: &BitvSet) -> Option<Ordering>

fn lt(&self, &BitvSet) -> bool

fn le(&self, &BitvSet) -> bool

fn gt(&self, &BitvSet) -> bool

fn ge(&self, &BitvSet) -> bool

impl Ord for BitvSet

fn cmp(&self, other: &BitvSet) -> Ordering

impl PartialEq for BitvSet

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

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

impl Eq for BitvSet

fn assert_receiver_is_total_eq(&self)

impl Show for BitvSet

fn fmt(&self, fmt: &mut Formatter) -> Result<(), Error>

impl<S: Writer> Hash<S> for BitvSet

fn hash(&self, state: &mut S)

Derived Implementations

impl Clone for BitvSet

fn clone(&self) -> BitvSet

fn clone_from(&mut self, &BitvSet)