Added dfs traversal of gates graph

3 files changed, 106 insertions, 65 deletions

diff --git a/src/circuit.rs b/src/circuit.rs
new file mode 100644
index 0000000..6882296
--- /dev/null
+++ b/src/circuit.rs
@@ -0,0 +1,25 @@
+use crate::{gate::Chip, types::*};
+
+#[derive(Debug, Clone)]
+struct Circuit {
+    chips: Chips,
+}
+
+impl Circuit {
+    fn new() -> Circuit {
+        Circuit { chips: Vec::new() }
+    }
+
+    fn add_chip(&mut self, chip: Chip) -> usize {
+        self.chips.push(chip);
+        0
+    }
+
+    fn connect_chip(&mut self, from: usize, to: usize) {
+        todo!()
+    }
+
+    fn simulate(&mut self) {
+        todo!();
+    }
+}
diff --git a/src/gate.rs b/src/gate.rs
index 87ae219..d88f729 100644
--- a/src/gate.rs
+++ b/src/gate.rs
@@ -1,6 +1,7 @@
 use crate::pin::*;
 use crate::types::*;
 use std::collections::HashMap;
+use std::collections::HashSet;
 
 #[derive(Debug)]
 pub enum GateType {
@@ -140,8 +141,8 @@ pub struct AndGate {
 impl AndGate {
     fn new(input: Vec<PinValue>, id: usize, kind: PinType) -> Self {
         if input.is_empty() {
-            let pin_1 = Pin::new(PinType::Undetermined, id, 42);
-            let pin_2 = Pin::new(PinType::Undetermined, id, 42);
+            let pin_1 = Pin::new(PinType::GateInput, id, 42);
+            let pin_2 = Pin::new(PinType::GateInput, id, 42);
             Self {
                 id,
                 input: vec![pin_1, pin_2],
@@ -169,6 +170,7 @@ impl AndGate {
         let res = (self.input[0].val.unwrap() & self.input[1].val.unwrap()) == 1;
         self.output.val = Some(res as u8);
         self.output.kind = PinType::GateOutput;
+        println!("{:?}", self);
         res
     }
 }
@@ -260,7 +262,7 @@ impl BufferGate {
 
 #[derive(Debug, Clone, PartialEq)]
 pub struct Chip {
-    gates: Gates,
+    pub gates: Gates,
     pub connections: Connections,
     input: Pins,
     output: Pins,
@@ -291,16 +293,11 @@ impl Chip {
     }
 
     pub fn connect_gate(&mut self, from: &mut Gate, to: &mut Gate, to_pin_idx: usize) {
+        to.input_mut()[to_pin_idx] = Pin::new(PinType::GateInput, to.id(), 42);
         self.connections
             .entry(to.input()[to_pin_idx])
             .and_modify(|val| val.push(*from.output()))
             .or_insert_with(|| vec![*from.output()]);
-        // self.connections
-        //     .entry(to.input()[to_pin_idx].id)
-        //     .or_insert(vec![from.output().id]);
-        from.evaluate();
-        to.input_mut()[to_pin_idx] =
-            Pin::new(PinType::GateInput, to.id(), from.output().val.unwrap());
         if !self.gates.contains(&from) {
             // TODO: Remove this clone
             self.add_gate(from.clone());
@@ -311,30 +308,75 @@ impl Chip {
         }
     }
 
-    pub fn pins(&self) -> Vec<&Pin> {
-        let mut pins = vec![];
+    pub fn pins(&self) -> HashMap<usize, Vec<&Pin>> {
+        let mut pins = HashMap::new();
         for gate in &self.gates {
             for pin in gate.input() {
-                pins.push(pin);
+                pins.entry(pin.id)
+                    .and_modify(|val: &mut Vec<&Pin>| val.push(pin))
+                    .or_insert_with(|| vec![pin]);
             }
-            pins.push(gate.output());
+            pins.entry(gate.output().id)
+                .and_modify(|val: &mut Vec<&Pin>| val.push(gate.output()))
+                .or_insert_with(|| vec![gate.output()]);
         }
         pins
     }
 
-    // fn gate_dag(&self) -> HashMap<&Pin, Vec<&Pin>> {
-    //     let mut dag = HashMap::new();
-    //     for connection in &self.connections {
-    //         for pin in *connection.1 {
-    //             dag.entry(*connection.0)
-    //                 .and_modify(|val: &mut Vec<&Pin>| val.push(pin))
-    //                 .or_insert_with(|| vec![pin]);
-    //         }
-    //     }
-    //     dag
-    // }
-
-    fn simulate(&self) -> bool {
-        todo!()
+    pub fn gate_dag(&self) -> HashMap<usize, Vec<usize>> {
+        let mut dag = HashMap::new();
+        for connection in &self.connections {
+            for pin in connection.1 {
+                dag.entry(connection.0.gate_id)
+                    .and_modify(|val: &mut Vec<usize>| val.push(pin.gate_id))
+                    .or_insert_with(|| vec![pin.gate_id]);
+            }
+        }
+        dag
+    }
+
+    pub fn pin_dag(&self) -> HashMap<usize, Vec<usize>> {
+        let mut gate_dag = self.gate_dag();
+        let mut dag = HashMap::new();
+        for (id, children) in gate_dag {
+            // dag.entry()
+            //     .and_modify(|val: &mut Vec<usize>| val.push(pin.gate_id))
+            //     .or_insert_with(|| vec![pin.gate_id]);
+        }
+        dag
+    }
+
+    fn simulate_helper(
+        &mut self,
+        gate: usize,
+        visited: &mut HashSet<usize>,
+        dag: &HashMap<usize, Vec<usize>>,
+    ) {
+        visited.insert(gate);
+        if dag.contains_key(&gate) {
+            for child in dag.get(&gate).unwrap() {
+                if !visited.contains(child) {
+                    self.simulate_helper(*child, visited, dag);
+                }
+            }
+            let pos = self.gates.iter().position(|g| g.id() == gate).unwrap();
+            self.gates[pos].evaluate();
+            println!("{}", gate);
+        } else {
+            println!("{}", gate);
+            let pos = self.gates.iter().position(|g| g.id() == gate).unwrap();
+            self.gates[pos].evaluate();
+        }
+    }
+
+    pub fn simulate(&mut self) -> bool {
+        let dag = self.gate_dag();
+        let mut visited = HashSet::new();
+        for child in dag.get(&8).unwrap() {
+            if !visited.contains(child) {
+                self.simulate_helper(*child, &mut visited, &dag);
+            }
+        }
+        false
     }
 }
diff --git a/src/main.rs b/src/main.rs
index a70ace9..9acda46 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -1,4 +1,5 @@
 #![allow(dead_code)]
+mod circuit;
 mod gate;
 mod pin;
 mod types;
@@ -7,34 +8,9 @@ use crate::pin::*;
 use crate::types::*;
 use std::vec;
 
-// Define a struct to represent the Circuit
-#[derive(Debug, Clone)]
-struct Circuit {
-    chips: Chips,
-}
-
-impl Circuit {
-    fn new() -> Circuit {
-        Circuit { chips: Vec::new() }
-    }
-
-    fn add_chip(&mut self, chip: Chip) -> usize {
-        self.chips.push(chip);
-        0
-    }
-
-    fn connect_chip(&mut self, from: usize, to: usize) {
-        todo!()
-    }
-
-    fn simulate(&mut self) {
-        todo!();
-    }
-}
-
 fn main() {
     let mut _chip = Chip::new();
-    let a: u8 = 1;
+    let a: u8 = 0;
     let b: u8 = 1;
     let input: Vec<PinValue> = vec![a, b];
     println!("input: {:?}", input);
@@ -58,18 +34,16 @@ fn main() {
     xor.connect_gate(&mut gate_6, &mut gate_7, 1);
     xor.connect_gate(&mut gate_7, &mut gate_8, 0);
 
-    // let dag = xor.gate_dag();
-    let mut sorted = xor.pins();
-    sorted.sort_by(|&x, &y| x.id.cmp(&y.id));
-
-    // println!("pins: {:#?}", sorted);
-    // println!("connections: {:#?}", xor.connections);
-    // println!("dag: {:#?}", dag);
-    println!(
-        "Gate: {:?}\n output = {:?}",
-        &mut gate_8.evaluate(),
-        gate_8.clone(),
-    );
+    let dag = xor.gate_dag();
+    // println!("pins: {:#?}", xor.pins());
+    println!("dag: {:#?}", dag);
+    // println!("dag: {:#?}", xor.gates);
+    // xor.simulate();
+    // println!(
+    //     "Output: {:?}\n Gate = {:?}",
+    //     &mut gate_8.evaluate(),
+    //     gate_8.clone(),
+    // );
 }
 
 // #[macroquad::main("lgsim")]