Crate bitvector

BitVector Module

BitVector uses one bit to represent a bool state. BitVector is useful for the programs that need fast set operation (intersection, union, difference), because that all these operations can be done with simple bitand, bitor, bitxor.

Usually, the length of a BitVector should not be changed after constructed, for example:

extern crate bitvector;
use bitvector::*;

fn main(){
  // a bitvector contains 30 elements
  let mut bitvec = BitVector::new(30);
  // add 10 elements
  for i in 0 .. 10 { bitvec.insert(i); }
  // you can use Iterator to iter over all the elements
  assert_eq!(bitvec.iter().collect::<Vec<_>>(), vec![0,1,2,3,4,5,6,7,8,9]);

  let mut bitvec2 = BitVector::new(30);
  for i in 5 .. 15 { bitvec2.insert(i); }

  // set union
  assert_eq!(bitvec.union(&bitvec2).iter().collect::<Vec<_>>(),
             vec![0,1,2,3,4,5,6,7,8,9,10,11,12,13,14]);
   
  // set intersection 
  assert_eq!(bitvec.intersection(&bitvec2).iter().collect::<Vec<_>>(),
             vec![5,6,7,8,9]);

  // set difference 
  assert_eq!(bitvec.difference(&bitvec2).iter().collect::<Vec<_>>(),
             vec![0,1,2,3,4]);

  // you can also use `&`(intersection) `|`(union) and `^`(difference) 
  // to do the set operations
  assert_eq!((&bitvec ^ &bitvec2).iter().collect::<Vec<_>>(),
             vec![0,1,2,3,4]);
}

Implementation Details

BitVector is realized with a Vec<u64>. Each bit of an u64 represent if a elements exists. BitVector always increases from the end to begin, it meats that if you add element 0 to an empty bitvector, then the Vec<u64> will change from 0x00 to 0x01.

Of course, if the real length of set can not be divided by 64, it will have a capacity() % 64 bit memory waste.

Structs

BitVector	Bitvector
BitVectorIter	Iterator for BitVector