dict.rs

/* A simple dictionary implementation in Rust, using a hash table with
 * chaining and table doubling.
 *
 * Tested with Rust nightly 2014-06-27
 */
extern crate collections;

use std::hash;
use std::hash::Hash;

pub struct Dict<K,V> {
    table: Box<Vec<Vec<(K, V)>>>,
    nelem: uint,
}

impl<K: Eq + Hash + Clone, V: Clone> Dict<K, V> {
    pub fn new() -> Dict<K, V> {
        Dict {
            table: box Vec::from_fn(4, |_| Vec::new()),
            nelem: 0
        }
    }

    pub fn num_items(&self) -> uint {
        self.nelem
    }

    pub fn insert(&mut self, key: K, val: V) {
        let table_len = self.table.len();

        // Double the table size if the load factor gets above 1.0
        if self.nelem >= table_len {
            self.resize_table(table_len * 2);
        }

        let bucket = self.hash(&key, self.table.len());
        self.table.get_mut(bucket).push((key, val));
        self.nelem += 1;
    }

    pub fn remove(&mut self, key: &K) {
        let table_len = self.table.len();

        // Half the table size if the load factor gets below 0.25
        if self.nelem <= table_len / 4  && table_len > 4 {
            self.resize_table(table_len / 2);
        }

        let bucket = self.hash(key, self.table.len());
        let chain = self.table.get_mut(bucket);
        let mut to_remove  = None;
        for i in range(0, chain.len()) {
            let &(ref k,_) = chain.get(i);
            if *k == *key {
                to_remove = Some(i);
                break;
            }
        }

        match to_remove {
            Some(i) => {
                chain.remove(i);
                self.nelem -= 1;
            },
            None => ()
        }
    }

    pub fn get(&self, key: &K) -> Option<V> {
        let bucket = self.hash(key, self.table.len());
        let chain = self.table.get(bucket);

        for &(ref k, ref v) in chain.iter() {
            if *k == *key {
                return Some(v.clone())
            }
        }

        None
    }

    pub fn iter<'a>(&'a self) -> DictIter<'a, K, V> {
        DictIter {
            bucket_index: 0,
            chain_index: 0,
            dict: self
        }
    }

    fn hash(&self, key: &K, table_size: uint) -> uint{
        let hash_val = hash::hash(&key);
        (hash_val % table_size as u64) as uint
    }

    fn resize_table(&mut self, new_size: uint) {
        let mut new = box Vec::from_fn(new_size, |_| Vec::new());

        for chain in self.table.iter() {
            for &(ref k, ref v) in chain.iter() {
                let index = self.hash(k, new_size);
                new.get_mut(index).push((k.clone(), v.clone()));
            }
        }

        self.table = new;
    }
}

struct DictIter<'a, K, V> {
    bucket_index: uint,
    chain_index: uint,
    dict: &'a Dict<K,V>,
}

impl<'a, K: Hash + Clone, V: Clone> Iterator<(K, V)> for DictIter<'a, K, V> {
    fn next(&mut self) -> Option<(K, V)> {
        loop {
            if self.bucket_index >= self.dict.table.len() {
                return None;
            } else {
                let chain = self.dict.table.get(self.bucket_index);

                if self.chain_index < chain.len() {
                    self.chain_index += 1;
                    let kv_pair = chain.get(self.chain_index - 1);
                    return Some(kv_pair.clone());
                } else {
                    self.chain_index = 0;
                    self.bucket_index += 1;
                }
            }
        }
    }
}