Skip to content

Instantly share code, notes, and snippets.

@userqq

userqq/vp_tree_hamming.rs

Created December 12, 2017 04:29
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save userqq/6d3578d8e33fcee55ae852f8c37ea40d to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save userqq/6d3578d8e33fcee55ae852f8c37ea40d to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. userqq created this gist Dec 12, 2017.
    39 changes: 39 additions & 0 deletions vp_tree_hamming.rs
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,39 @@
    extern crate bk_tree;

    use bk_tree::{BKTree, Metric};

    pub struct Hamming;

    impl Metric<i64> for Hamming
    {
    fn distance(&self, a: &i64, b: &i64) -> u64 {
    let mut dh = 0u64;

    for i in 0..64 {
    let mut k = (1 << i);
    if (a & k) != (b & k) {
    dh += 1;
    }
    }

    dh
    }
    }

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

    tree.add(-3572687289547480823i64);
    tree.add(-8197022089740803831i64);
    tree.add(-4132236144266432247i64);
    tree.add(-3717382884479454973i64);
    tree.add(-2969170184338595071i64);
    tree.add(853075759859001988i64);
    tree.add(-4079676741827119093i64);
    tree.add(-7591000451928546551i64);
    tree.add(-3571016074831056637i64);

    for i in tree.find(&-3572687289547480823i64, 10) {
    println!("{:?}", i);
    }
    }