Shared via Rust Playground

playground.rs

use std::collections::HashMap;
use std::collections::HashSet;
use std::hash::Hash;
use std::fmt::Debug;

#[derive(Debug, Clone)]
struct EdgeIndex<Ix>(Ix);

#[derive(Debug, Clone)]
struct NodeIndex<Ix>(Ix);

#[derive(Debug, Clone)]
struct Node<N, Ix> {
    value: N,
    incoming: Vec<EdgeIndex<Ix>>,
    outgoing: Vec<EdgeIndex<Ix>>
}

#[derive(Debug, Clone)]
struct Edge<E, Ix> {
    value: E,
    source: NodeIndex<Ix>,
    sink: NodeIndex<Ix>
}
#[derive(Debug)]
struct DAG<N, E, Ix> where Ix:Eq + Hash {
    inputs: Vec<Ix>,
    outputs: Vec<Ix>,
    nodes: HashMap<Ix, Node<N, Ix>>,
    edges: HashMap<Ix, Edge<E, Ix>>
}

impl<N, E, Ix: Debug + Eq + Hash> DAG<N, E, Ix> {
    fn relatives(
            &self, 
            ref ix: &Ix, 
            edge_fn: Box<Fn(&Node<N, Ix>) -> &Vec<EdgeIndex<Ix>>>,
            node_fn: Box<Fn(&Edge<E, Ix>) -> &NodeIndex<Ix>>
            ) -> Option<Vec<&Ix>> {
        match self.nodes.get(ix) {
            Some(node) => {
                Some(edge_fn(node).iter().map(|&EdgeIndex(ref edge_ix)| {
                    let &NodeIndex(ref node_ix) = node_fn(self.edges.get(edge_ix).unwrap());
                    node_ix
                }).collect())
            }
            _ => { None }
        }
    }
    
    fn children(&self, ref ix: &Ix) -> Option<Vec<&Ix>> {
        self.relatives(
            ix, 
            Box::new(move |node| &node.outgoing),
            Box::new(move |edge| &edge.sink)
        )
    }
    
    fn parents(&self, ref ix: &Ix) -> Option<Vec<&Ix>> {
        self.relatives(
            ix, 
            Box::new(move |node| &node.incoming),
            Box::new(move |edge| &edge.source)
        )
    }

    fn dfs(&self) -> (Vec<&Ix>, Vec<&Ix>) {
        let mut stack: Vec<&Ix> = self.inputs.iter().collect();
        let mut pre: Vec<&Ix> = Vec::new();
        let mut post: Vec<&Ix> = Vec::new();
        let mut visited: HashSet<&Ix> = HashSet::new();
        
        while !stack.is_empty() {
            let ix = stack.pop().unwrap();
            if visited.contains(ix) {
                post.push(ix);
            } else {
                visited.insert(ix);
                pre.push(ix);
                stack.push(ix);
                for target_ix in self.children(ix).unwrap() {
                    if !visited.contains(target_ix) {
                        stack.push(target_ix);
                    }
                }
            }
        }
        (pre, post)
    }
    
    fn topological_sort(&self) -> Vec<&Ix> {
        let (_, mut post) = self.dfs();
        post.reverse();
        post
    }
}

impl<Ix: Eq + Hash + Debug> DAG<Gate, Wire, Ix> {
    fn compute(&self, input_bits: &Vec<Bit>) -> Vec<Bit> {
        let mut value_map: HashMap<&Ix, Bit> = HashMap::new();
        for (node_ix, &input_bit) in self.inputs.iter().zip(input_bits.iter()) {
            value_map.insert(node_ix, input_bit);
        }
        let node_ixs: Vec<&Ix> = self.topological_sort();
        for &node_ix in &node_ixs {
            if let Node{value: Gate::Internal{ref op}, ..} = self.nodes[node_ix] {
                let parent_ixs = self.parents(node_ix).unwrap();
                let parent_bits: Vec<Bit> = parent_ixs.iter().map(|parent_ix| {
                    value_map[parent_ix]
                }).collect();
                if op.arity != (parent_bits.len() as u32) {
                    panic!("Logical operation arity {} does not match number of incoming wires {}.", op.arity, parent_bits.len());
                }
                value_map.insert(node_ix, (op.f)(parent_bits));
            }
        }
        self.outputs.iter().map(|output_ix| value_map[output_ix]).collect()
    }
}

type DefaultIx = u32;
type Bit = bool;

#[derive(Debug, Clone)]
enum OpType {
    AND,
    OR,
    NOT
}

#[derive(Debug, Clone)]
struct LogicalOp {
    op_type: OpType,
    arity: u32,
    f: fn(Vec<Bit>) -> Bit 
}

const AND_OP: LogicalOp = LogicalOp {
    op_type: OpType::AND,
    arity: 2,
    f: logical_add
};

const OR_OP: LogicalOp = LogicalOp {
    op_type: OpType::OR, 
    arity: 2, 
    f: logical_or
};

const NOT_OP: LogicalOp = LogicalOp {
    op_type: OpType::NOT, 
    arity: 1,
    f: logical_not
};


fn logical_add(bits: Vec<Bit>) -> Bit { bits[0] & bits[1] }
fn logical_or(bits: Vec<Bit>) -> Bit { bits[0] || bits[1] }
fn logical_not(bits: Vec<Bit>) -> Bit { !bits[0] }

#[derive(Debug, Clone)]
enum Gate {
    Input,
    Internal {
        op: LogicalOp
    }
}

impl Gate {
    fn new_internal(logical_op: LogicalOp) -> Gate {
        Gate::Internal {op: logical_op}
    }
    
    fn new_input() -> Gate {
        Gate::Input {}
    }
}

#[derive(Debug, Clone)]
struct Wire {
}

impl Wire {
    fn new() -> Wire {
        Wire {}
    }
}

fn test() -> Vec<Bit> {
    let node0 = Node{value: Gate::new_input(), incoming: Vec::new(), outgoing: vec![EdgeIndex(0), EdgeIndex(1)]};
    let node1 = Node{value: Gate::new_input(), incoming: Vec::new(), outgoing: vec![EdgeIndex(2)]};
    let node2 = Node{value: Gate::new_internal(AND_OP), incoming: vec![EdgeIndex(0), EdgeIndex(2)], outgoing: vec![EdgeIndex(3)]};
    let node3 = Node{value: Gate::new_internal(OR_OP), incoming: vec![EdgeIndex(1), EdgeIndex(3)], outgoing: vec![EdgeIndex(4)]};
    let node4 = Node{value: Gate::new_internal(NOT_OP), incoming: vec![EdgeIndex(4)], outgoing: Vec::new()};
    let edge0 = Edge{value: Wire::new(), source: NodeIndex(0), sink: NodeIndex(2)};
    let edge1 = Edge{value: Wire::new(), source: NodeIndex(0), sink: NodeIndex(3)};
    let edge2 = Edge{value: Wire::new(), source: NodeIndex(1), sink: NodeIndex(2)};
    let edge3 = Edge{value: Wire::new(), source: NodeIndex(2), sink: NodeIndex(3)};
    let edge4 = Edge{value: Wire::new(), source: NodeIndex(3), sink: NodeIndex(4)};
    let dag: DAG<Gate, Wire, DefaultIx> = DAG {
        inputs: vec![0, 1],
        outputs: vec![4],
        nodes: [(0, node0), (1, node1), (2, node2), (3, node3), (4, node4)].iter().cloned().collect(), 
        edges: [(0, edge0), (1, edge1), (2, edge2), (3, edge3), (4, edge4)].iter().cloned().collect()
    };
    
    let inputs = vec![false, false];
    dag.compute(&inputs)
}

fn main() {
    println!("{:?}", test());
}