Bloom Filter implementation in Rust

bloom.rs

extern mod extra;
use std::num;
use extra::bitv::Bitv;

struct BloomFilter {m: uint, k: uint, buckets: Bitv}

impl BloomFilter {
  fn new(n: uint, p: float) -> BloomFilter {
    let m = ((-(n as float) * num::ln(p) / 0.48)) as uint + 1;
    let k = (0.7 * (m as float) / (n as float)) as uint;
    BloomFilter { m: m, k: k, buckets: Bitv::new(m, false) }
  }

  fn add(&mut self, elem: &str) {
    let hash = self.hash(elem);
    for i in hash.iter() { self.buckets.set(*i, true); }
  }

  fn query(&self, elem: &str) -> bool {
    let hash = self.hash(elem);
    hash.iter().all(|i| self.buckets.get(*i))
  }

  fn hash(&self, elem: &str) -> ~[uint] {
    let h1 = elem.hash();
    let h2 = elem.hash_keyed(0, h1);
    range(0, self.k).map(|i| ((h1 + (i as u64) * h2) % (self.m as u64)) as uint).collect()
  }
}

#[test]
fn bloom_filter_test() {
  let input = ["Lorem", "ipsum", "dolor", "sit", "amet", "consectetur", "adipisicing", "elit", "sed",
              "do", "eiusmod", "tempor", "incididunt", "ut", "labore", "et", "dolore", "magna", "aliqua"];

  let mut bf = BloomFilter::new(input.len(), 0.01);
  for word in input.iter() { bf.add(*word); }

  assert!(bf.query("eiusmod"));
  assert!(bf.query("labore"));
  assert!(bf.query("consectetur"));
  assert!(!bf.query("missing"));
  assert!(!bf.query("fizzbuzz"));
}

fn main() {
}