DAG implementation

gistfile1.rs

use std::collections::HashSet;
use std::hash::Hash;

use typed_arena::Arena;

#[derive(Clone)]
pub enum Edges<'a, L: 'a, N: 'a + Hash> {
    Leaves(Vec<&'a L>),
    Children(Vec<&'a Node<'a, L, N>>)
}

#[derive(Clone)]
pub struct Node<'a, L: 'a, N: 'a + Hash> {
    datum: &'a N,
    edges: Edges<'a, L, N>,
}

impl<'a, L, N: Hash> Node<'a, L, N> {
    pub fn new<'b>(datum: &'a N, edges: Edges<'a, L, N>, arena: &'b Arena<Node<'a, L, N>>) -> &'b Node<'a, L, N> {
        arena.alloc(Node {
            datum: datum,
            edges: edges,
        })
    }

    pub fn traverse<F>(&self, f: &F, seen: &mut HashSet<&'a N>)
        where F: Fn(&'a L)
    {
        /* I get the error:
        src/directed_acyclic_graph.rs:29:17: 29:37 error: no method named `contains` found for type `&mut std::collections::hash::set::HashSet<&'a N>` in the current scope
src/directed_acyclic_graph.rs:29         if seen.contains(self.datum) {
                                                 ^~~~~~~~~~~~~~~~~~~~
src/directed_acyclic_graph.rs:33:14: 33:32 error: no method named `insert` found for type `&mut std::collections::hash::set::HashSet<&'a N>` in the current scope
src/directed_acyclic_graph.rs:33         seen.insert(self.datum);
                                              ^~~~~~~~~~~~~~~~~~

        */
        if seen.contains(self.datum) {
            return;
        }

        seen.insert(self.datum);
        match self.edges {
            Edges::Leaves(leaves) => {
                for leaf in leaves {
                    f(leaf);
                }
            },
            Edges::Children(children) => {
                for child in children {
                    child.traverse(f, seen);
                }
            }
        }
    }
}

#[cfg(test)]
mod test {
    use super::*;
    use typed_arena::Arena;
    use std::collections::HashSet;

    #[test]
    fn smoke() {
        let root_names = vec!["root1", "root2"];
        let names = vec!["a", "b", "c", "d", "e"];
        let data: Vec<u8> = (0..10).collect();
        let arena = Arena::new();
        let a = Node::new(&names[0], Edges::Leaves(vec![&data[0], &data[1]]), &arena);
        let b = Node::new(&names[1], Edges::Leaves(vec![&data[2], &data[3]]), &arena);
        let c = Node::new(&names[2], Edges::Leaves(vec![&data[4], &data[5]]), &arena);
        let d = Node::new(&names[3], Edges::Leaves(vec![&data[6], &data[7]]), &arena);
        let e = Node::new(&names[4], Edges::Leaves(vec![&data[8], &data[9]]), &arena);

        let root1 = Node::new(&root_names[0], Edges::Children(vec![a, b]), &arena);
        let root2 = Node::new(&root_names[1], Edges::Children(vec![root1, c, d, e]), &arena);
        root2.traverse(&|d| println!("{}", d), &mut HashSet::new());
    }
}