neighbors_opt.rs

use std::collections::HashSet;
use std::hash::BuildHasherDefault;

use std::default::Default;
use std::hash::Hasher;

pub struct FnvHasher(u64);

impl Default for FnvHasher {
    #[inline]
    fn default() -> FnvHasher {
        FnvHasher(0xcbf29ce484222325)
    }
}

impl Hasher for FnvHasher {
    #[inline]
    fn finish(&self) -> u64 {
        self.0
    }

    #[inline]
    fn write(&mut self, bytes: &[u8]) {
        let FnvHasher(mut hash) = *self;

        for &byte in bytes.iter() {
            hash = hash ^ (byte as u64);
            hash = hash.wrapping_mul(0x100000001b3);
        }

        *self = FnvHasher(hash);
    }
}

type Set = HashSet<(i32, i32), BuildHasherDefault<FnvHasher>>;

fn new_set(size: usize) -> Set {
	let fnv = BuildHasherDefault::<FnvHasher>::default();
	HashSet::with_capacity_and_hasher(size, fnv)
}

const N_NEIGHBORS : usize = 4;

fn iterNeighbors<F>(mut f: F, (i, j): (i32, i32)) -> ()
    where F: FnMut((i32, i32)) -> ()
{
    f((i-1, j));
    f((i+1, j));
    f((i, j-1));
    f((i, j+1));
}

fn nthLoop(n: usize, mut s0: Set, s1: Set, mut s2: Set) -> Set {
    if n == 0 {
        return s1;
    } else {
        for &p in &s1 {
            let add = |p| {
                if !s2.contains(&p) && !s1.contains(&p) {
                    s0.insert(p);
                }
            };
            iterNeighbors(add, p);
        }
        s2.clear();
        return nthLoop(n-1, s2, s0, s1);
    }
}

fn nth(n: usize, p: (i32, i32)) -> Set {
    // Create the three sets, one will end up with
    // n*N_NEIGHBORS entries, but the other two will
    // end up with close to that many.
    let mut s1 = new_set(n*N_NEIGHBORS);
    let s2 = new_set(n*N_NEIGHBORS);
    let s0 = new_set(n*N_NEIGHBORS);

    s1.insert(p);
    nthLoop(n, s0, s1, s2)
}

fn main() {
    let s = nth(2000, (0, 0));
    println!("{}", s.len());
}