tree.rs

extern crate bk_tree;

use bk_tree::{BKTree, metrics};
use bk_tree::Metric;

use std::cmp::min;

pub struct Hamming;

impl<K: AsRef<str> + ?Sized> Metric<K> for Hamming
{
    fn distance(&self, a: &K, b: &K) -> u64 {
        let str_a: &str = a.as_ref();
        let str_b: &str = b.as_ref();

        let len_a = str_a.chars().count();
        let len_b = str_b.chars().count();
        if len_a == 0 {
            return len_b as u64;
        }
        if len_b == 0 {
            return len_a as u64;
        }

        // This is a case-insensitive algorithm
        let a_lower = str_a.to_lowercase();
        let b_lower = str_b.to_lowercase();

        // Initialize the array
        let mut d: Vec<Vec<usize>> = Vec::new();
        for j in 0..(len_b + 1) {
            let mut cur_vec = Vec::new();
            for i in 0..(len_a + 1) {
                if j == 0 {
                    cur_vec.push(i);
                } else if i == 0 {
                    cur_vec.push(j);
                } else {
                    cur_vec.push(0);
                }
            }
            d.push(cur_vec);
        }

        for (j, chr_b) in b_lower.chars().enumerate() {
            for (i, chr_a) in a_lower.chars().enumerate() {
                if chr_a == chr_b {
                    // If they're the same, then don't modify the value
                    d[j + 1][i + 1] = d[j][i];
                } else {
                    // Otherwise, pick the lowest cost option for an error
                    let deletion = d[j + 1][i] + 1;
                    let insertion = d[j][i + 1] + 1;
                    let substitution = d[j][i] + 1;
                    d[j + 1][i + 1] = min(min(deletion, insertion), substitution);
                }
            }
        }

        d[len_b][len_a] as u64
    }
}

fn main() {
    let mut tree: BKTree<&str> = BKTree::new(Hamming);

    /*
    tree.add("foo");
    tree.add("bar");
    tree.add("baz");
    tree.add("bup");

    for i in tree.find("bar", 1) {
        println!("{:?}", i);
    }
    //println!("{:?}", tree.find("bar", 0)[0]); // returns vec!["bar"]
    //println!("{:?}", tree.find("bar", 1)); // returns vec!["bar", "baz"]
    //println!("{:?}", tree.find("bup", 2)); // returns vec!["bar", "baz", "bup"]
    */
    println!("Hello, world!");
}