lib.rs

use std::hash::Hash;
use std::collections::{HashSet, VecDeque};
use std::marker::PhantomData;

pub trait Digraph {
    type Vertex: std::cmp::Eq;
    type Neighbors: IntoIterator<Item=Self::Vertex>;

    fn neighbors(&self, Self::Vertex) -> Self::Neighbors;

    fn fewest_steps<VSet, P>(&self, start: VSet, goal: P) -> Option<usize>
        where Self::Vertex: Hash + Clone + std::fmt::Debug,
              VSet: IntoIterator<Item=Self::Vertex>,
              P: Fn(Self::Vertex) -> bool
    {
        let mut seen = HashSet::new();
        let mut queue: VecDeque<(Self::Vertex, usize)> = VecDeque::new();

        for v in start {
            if seen.insert(v.clone()) {
                if goal(v.clone()) {
                    return Some(0);
                }
                queue.push_back((v, 0));
            }
        }

        while let Some((v, vd)) = queue.pop_front() {
            let wd = vd + 1;
            for w in self.neighbors(v) {
                if seen.insert(w.clone()) {
                    println!("{:?}, {}", w, wd);
                    if goal(w.clone()) {
                        return Some(wd);
                    }
                    queue.push_back((w, wd));
                }
            }
        }

        None
    }
}

pub struct SimpleDigraph<V, F, N>
    where V: Eq, F: Fn(V) -> N, N: IntoIterator<Item=V>
{
    f: F,
    phantom: PhantomData<(V, N)>
}

impl<V: Eq, F: Fn(V) -> N, N: IntoIterator<Item=V>> Digraph for SimpleDigraph<V, F, N> {
    type Vertex = V;
    type Neighbors = N;

    fn neighbors(&self, v: V) -> N { (self.f)(v) }
}

pub fn digraph<V, F, N>(neighbors: F) -> SimpleDigraph<V, F, N>
    where V: Eq,
          F: Fn(V) -> N,
          N: IntoIterator<Item=V>
{
    SimpleDigraph {
        f: neighbors,
        phantom: PhantomData
    }
}


#[test]
fn test_fewest_steps() {
    struct Hamming;

    impl Digraph for Hamming {
        type Vertex = u8;
        type Neighbors = Vec<u8>;

        fn neighbors(&self, n: u8) -> Vec<u8> {
            (0 .. 8).map(|i| n ^ (1 << i)).collect()
        }
    }

    assert_eq!(Hamming.fewest_steps(vec![0, 1], |v| v == 1), Some(0));
    assert_eq!(Hamming.fewest_steps(vec![0], |v| v == 1), Some(1));
    assert_eq!(Hamming.fewest_steps(vec![0, 1], |v| v == 255), Some(7));
    assert_eq!(Hamming.fewest_steps(Vec::<u8>::new(), |v| v == 1), None);
    assert_eq!(Hamming.fewest_steps(vec![0, 19], |v| v == !v), None);

    let hamming = digraph(|v| (0..8).map(move |i| v^(1<<i)));
    assert_eq!(hamming.fewest_steps(vec![0, 1],       |v| v == 1), Some(0));
    assert_eq!(hamming.fewest_steps(vec![0],          |v| v == 1), Some(1));
    assert_eq!(hamming.fewest_steps(vec![0, 1],       |v| v == 255), Some(7));
    assert_eq!(hamming.fewest_steps(Vec::<u8>::new(), |v| v == 1), None);
    assert_eq!(hamming.fewest_steps(vec![0, 19],      |v| v == !v), None);
}