Shared via Rust Playground

playground.rs

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

pub struct Dag<'a, L: 'a, N: 'a> {
    leaves: HashSet<L>,
    // Might be better as an arena but that isn't available the playpen
    nodes: Vec<Node<'a, L, N>>
}

impl<'a, L: 'a + Eq + Hash, N: 'a> Dag<'a, L, N> {
    pub fn new() -> Self {
        Dag {
            leaves: HashSet::new(),
            nodes: Vec::new()
        }
    }
    
    pub fn new_leaf_node(&'a mut self, datum: N, leaves: &'a [L])
        -> &'a Node<L, N>
    {
        let leaf_refs = leaves.iter().collect(); // TODO: Insert into self.leaves
        
        self.nodes.push(Node {
            datum: datum,
            children: Children::Leaves(leaf_refs),
        });
        self.nodes.last().unwrap()
    }
    
    pub fn new_node(&'a mut self, datum: N, children: &'a [&'a Node<L, N>])
        -> &'a Node<L, N>
    {
        self.nodes.push(Node {
           datum: datum,
           children: Children::Nodes(children.iter().cloned().collect()),
        });
        self.nodes.last().unwrap()
    }
}

pub enum Children<'a, L: 'a, N: 'a> {
    Leaves(HashSet<&'a L>),
    // I'd like to use HashSet here but doesn't work because HashSet isn't Hash or Eq
    Nodes(Vec<&'a Node<'a, L, N>>),
}

pub struct Node<'a, L: 'a, N: 'a> {
    datum: N,
    children: Children<'a, L, N>
}

fn main() {
    let a_data = vec![1, 2];
    let b_data = vec![3, 4];
    let mut x: Dag<u8, &str> = Dag::new();
    let a = x.new_leaf_node("a", &a_data);
    let b = x.new_leaf_node("b", &b_data);
    let root_data = [a, b];
    let root = x.new_node("root", &root_data);
}