diff options
| -rw-r--r-- | ' | 361 | ||||
| -rw-r--r-- | src/circuit.rs | 25 | ||||
| -rw-r--r-- | src/gate.rs | 96 | ||||
| -rw-r--r-- | src/main.rs | 50 |
4 files changed, 467 insertions, 65 deletions
@@ -0,0 +1,361 @@ +use crate::pin::*; +use crate::types::*; +use std::collections::HashMap; +use std::collections::HashSet; + +#[derive(Debug)] +pub enum GateType { + And, + Or, + Not, + Buffer, + Chip, +} + +#[derive(Debug, Clone, PartialEq)] +pub enum Gate { + And(AndGate), + Or(OrGate), + Not(NotGate), + Buffer(BufferGate), + Chip(Chip), +} + +impl Gate { + pub fn new(gate_type: GateType, input: Vec<PinValue>, kind: PinType) -> Self { + static mut ID: usize = 0; + unsafe { + ID += 1; + match gate_type { + GateType::And => Gate::And(AndGate::new(input, ID, kind)), + GateType::Or => Gate::Or(OrGate::new(input, ID)), + GateType::Not => Gate::Not(NotGate::new(input, ID)), + GateType::Buffer => Gate::Buffer(BufferGate::new(input, ID)), + GateType::Chip => Gate::Chip(Chip::new()), + } + } + } + + pub fn evaluate(&mut self) -> bool { + match self { + Gate::And(gate) => gate.evaluate(), + + Gate::Or(gate) => gate.evaluate(), + + Gate::Not(gate) => gate.evaluate(), + + Gate::Buffer(gate) => gate.evaluate(), + + Gate::Chip(chip) => chip.simulate(), + } + } + + fn input(&self) -> &Pins { + match self { + Gate::And(gate) => &gate.input, + + Gate::Or(gate) => &gate.input, + + Gate::Not(gate) => &gate.input, + + Gate::Buffer(gate) => &gate.input, + + Gate::Chip(chip) => &chip.input, + } + } + + fn input_mut(&mut self) -> &mut Pins { + match self { + Gate::And(gate) => &mut gate.input, + + Gate::Or(gate) => &mut gate.input, + + Gate::Not(gate) => &mut gate.input, + + Gate::Buffer(gate) => &mut gate.input, + + Gate::Chip(chip) => &mut chip.input, + } + } + + fn output(&self) -> &Pin { + match self { + Gate::And(gate) => &gate.output, + + Gate::Or(gate) => &gate.output, + + Gate::Not(gate) => &gate.output, + + Gate::Buffer(gate) => &gate.output, + + Gate::Chip(_) => todo!(), + } + } + + fn id(&self) -> usize { + match self { + Gate::And(gate) => gate.id, + + Gate::Or(gate) => gate.id, + + Gate::Not(gate) => gate.id, + + Gate::Buffer(gate) => gate.id, + + Gate::Chip(_) => 0, + } + } +} + +impl PartialEq for AndGate { + fn eq(&self, other: &Self) -> bool { + self.id == other.id + } +} + +impl PartialEq for OrGate { + fn eq(&self, other: &Self) -> bool { + self.id == other.id + } +} + +impl PartialEq for NotGate { + fn eq(&self, other: &Self) -> bool { + self.id == other.id + } +} + +impl PartialEq for BufferGate { + fn eq(&self, other: &Self) -> bool { + self.id == other.id + } +} + +#[derive(Debug, Clone)] +pub struct AndGate { + id: usize, + input: Pins, + output: Pin, +} + +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); + Self { + id, + input: vec![pin_1, pin_2], + output: Pin::new(PinType::Undetermined, id, 42), + } + } else if input.len() == 1 { + let pin_1 = Pin::new(kind, id, input[0]); + Self { + id, + input: vec![pin_1, Pin::new(PinType::Undetermined, id, 42)], + output: Pin::new(PinType::Undetermined, id, 42), + } + } else { + let pin_1 = Pin::new(kind, id, input[0]); + let pin_2 = Pin::new(kind, id, input[1]); + Self { + id, + input: vec![pin_1, pin_2], + output: Pin::new(PinType::Undetermined, id, 42), + } + } + } + + fn evaluate(&mut self) -> bool { + 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; + res + } +} + +#[derive(Debug, Clone)] +pub struct OrGate { + id: usize, + input: Pins, + output: Pin, +} + +impl OrGate { + fn new(input: Vec<PinValue>, id: usize) -> Self { + let pin_1 = Pin::new(PinType::ChipInput, id, input[0]); + let pin_2 = Pin::new(PinType::ChipInput, id, input[1]); + Self { + id, + input: vec![pin_1, pin_2], + output: Pin::new(PinType::Undetermined, id, 42), + } + } + + fn evaluate(&mut self) -> bool { + 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; + res + } +} + +#[derive(Debug, Clone)] +pub struct NotGate { + id: usize, + input: Pins, + output: Pin, +} + +impl NotGate { + fn new(input: Vec<PinValue>, id: usize) -> Self { + if input.is_empty() { + let pin_1 = Pin::new(PinType::Undetermined, id, 42); + Self { + id, + input: vec![pin_1], + output: Pin::new(PinType::Undetermined, id, 42), + } + } else { + let pin_1 = Pin::new(PinType::ChipInput, id, input[0]); + Self { + id, + input: vec![pin_1], + output: Pin::new(PinType::Undetermined, id, 42), + } + } + } + + fn evaluate(&mut self) -> bool { + let res = !(self.input[0].val.unwrap() == 1); + self.output.val = Some(res as u8); + self.output.kind = PinType::GateOutput; + res + } +} + +#[derive(Debug, Clone, Eq)] +pub struct BufferGate { + id: usize, + input: Pins, + output: Pin, +} + +impl BufferGate { + fn new(input: Vec<PinValue>, id: usize) -> Self { + let pin_1 = Pin::new(PinType::ChipInput, id, input[0]); + Self { + id, + input: vec![pin_1], + output: Pin::new(PinType::Undetermined, id, 42), + } + } + + fn evaluate(&mut self) -> bool { + let res = self.input[0].val.unwrap() == 1; + self.output.val = Some(res as u8); + self.output.kind = PinType::GateOutput; + res + } +} + +#[derive(Debug, Clone, PartialEq)] +pub struct Chip { + gates: Gates, + pub connections: Connections, + input: Pins, + output: Pins, +} + +impl Chip { + pub fn new() -> Chip { + Chip { + gates: Gates::new(), + connections: HashMap::new(), + input: Pins::new(), + output: Pins::new(), + } + } + + fn add_input(&mut self, pin: Pin) { + self.input.push(pin); + } + + fn add_output(&mut self, pin: Pin) { + self.output.push(pin); + } + + fn add_gate(&mut self, gate: Gate) -> usize { + let id = gate.id(); + self.gates.push(gate); + id + } + + pub fn connect_gate(&mut self, from: &mut Gate, to: &mut Gate, to_pin_idx: usize) { + from.evaluate(); + to.input_mut()[to_pin_idx] = + Pin::new(PinType::GateInput, to.id(), from.output().val.unwrap()); + self.connections + .entry(to.input()[to_pin_idx]) + .and_modify(|val| val.push(*from.output())) + .or_insert_with(|| vec![*from.output()]); + if !self.gates.contains(&from) { + // TODO: Remove this clone + self.add_gate(from.clone()); + } + if !self.gates.contains(&to) { + // TODO: Remove this clone + self.add_gate(to.clone()); + } + } + + pub fn pins(&self) -> Vec<&Pin> { + let mut pins = vec![]; + for gate in &self.gates { + for pin in gate.input() { + pins.push(pin); + } + pins.push(gate.output()); + } + pins + } + + 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 + } + + fn simulate_helper(&self, visited: &mut HashSet<usize>) { + let dag = self.gate_dag(); + for pair in dag { + for child in pair.1 { + if (visited.contains(&child)) { + println!(child); + } else { + todo!(); + } + } + println!(""); + return false; + } + todo!() + } + + fn simulate(&self) -> bool { + let dag = self.gate_dag(); + for pair in dag { + for child in pair.1 { + print!("{:?}", child); + } + println!(""); + } + todo!() + } +} 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")] |