1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
use std::collections::HashSet;
use itertools::Itertools;
use crate::{
gate::{GraphIterator, PostVisitIterator},
Gate, Operation,
};
/// A boolean circuit with named inputs and outputs.
/// Input variables are identified by their name.
/// The gates in the circuit are [`Gate`]s.
#[derive(Default)]
pub struct Circuit {
/// The output gates of the circuit. They contain their predecessors.
outputs: Vec<Gate>,
/// The names of the (non-constant) input gates, specifying their order.
/// If `None`, the input gates are in no particular order and identified
/// by their name only. If `Some(_)`, the list of names need to match
/// the names of the input gates.
input_names: Option<Vec<String>>,
/// The names of the output gates. Unnamed outputs use the empty string.
output_names: Vec<String>,
}
impl From<Gate> for Circuit {
fn from(gate: Gate) -> Self {
Circuit {
outputs: vec![gate],
input_names: None,
output_names: vec![String::new()],
}
}
}
impl Circuit {
/// Creates a circuit from unnamed outputs. Note that the [`Gate`]s can
/// share predecessors. Any two input gates in the circuit with the same
/// name are considered identical.
pub fn from_unnamed_outputs(outputs: impl IntoIterator<Item = Gate>) -> Self {
Self::from_named_outputs(outputs.into_iter().map(|n| (n, String::new())))
}
/// Adds the order of input gates to the circuit, or changes it.
pub fn with_input_order(
self,
input_names: impl IntoIterator<Item = impl ToString>,
) -> Result<Self, String> {
let input_names = input_names.into_iter().map(|n| n.to_string()).collect_vec();
let inputs_in_circuit = self.input_names_from_traversal().collect::<HashSet<_>>();
let input_names_set = input_names
.iter()
.map(|n| n.as_str())
.collect::<HashSet<_>>();
if input_names_set.len() != input_names.len() {
return Err("Duplicate input names in list.".to_string());
}
if inputs_in_circuit != input_names_set {
return Err(format!(
"Input names do not match circuit inputs:\n{}\n !=\n{}",
input_names.iter().sorted().format(", "),
inputs_in_circuit.iter().sorted().format(", ")
));
}
Ok(Circuit {
input_names: Some(input_names),
..self
})
}
/// Creates a circuit from (uniquely) named outputs. Note that the [`Gate`]s can
/// share predecessors. Any two input gates in the circuit with the same
/// name are considered identical.
///
/// The empty string can be used to not name outputs.
///
/// Panics if the output names are not unique.
pub fn from_named_outputs(items: impl IntoIterator<Item = (Gate, impl ToString)>) -> Self {
let mut seen_names: HashSet<_> = Default::default();
let mut circuit = Self::default();
for (gate, name) in items {
let name = name.to_string();
if !name.is_empty() && !seen_names.insert(name.clone()) {
panic!("Duplicate output name {name}");
}
circuit.outputs.push(gate);
circuit.output_names.push(name);
}
circuit
}
/// Returns the names of the input gates either in the order given by [`with_input_order`] or
/// otherwise from a circuit traversal.
pub fn input_names(&self) -> impl Iterator<Item = &str> + '_ {
if let Some(names) = &self.input_names {
Box::new(names.iter().map(|n| n.as_str())) as Box<dyn Iterator<Item = &str>>
} else {
Box::new(self.input_names_from_traversal())
}
}
/// Returns the output gates.
pub fn outputs(&self) -> &[Gate] {
&self.outputs
}
/// Returns the names of the output gates, where unnamed output gates use the empty String.
pub fn output_names(&self) -> &[String] {
&self.output_names
}
/// Returns an iterator over the output gates and their names, where unnamed output
/// gates use the empty string.
pub fn named_outputs(&self) -> impl Iterator<Item = (&Gate, &String)> {
self.outputs().iter().zip_eq(self.output_names())
}
/// Creates an iterator over the graph (the output gates and all their predecessors)
/// that returns each gate exactly once.
pub fn iter(&self) -> impl Iterator<Item = &Gate> {
GraphIterator::new(&self.outputs)
}
/// Creates an iterator over the graph (the output gates and all their predecessors)
/// with post-visit order, visiting each gate exactly once.
/// This means that the predecessors of each gate are always visited before the gate itself.
pub fn post_visit_iter(&self) -> impl Iterator<Item = &Gate> {
PostVisitIterator::new(self.outputs.iter())
}
/// Returns the names of the input gates from a traversal of the circuit,
/// not as potentially given by [`with_input_order`].
fn input_names_from_traversal(&self) -> impl Iterator<Item = &str> {
self.iter()
.filter_map(|gate| match gate.operation() {
Operation::Variable(name) => Some(name.as_str()),
_ => None,
})
.unique()
}
}
#[cfg(test)]
mod test {
use super::*;
#[test]
fn input_order() {
let c = Circuit::from(Gate::from("a") & Gate::from("b"));
assert_eq!(c.input_names().collect::<Vec<_>>(), vec!["a", "b"]);
let c = c.with_input_order(["b", "a"]).unwrap();
assert_eq!(
c.input_names().collect::<Vec<_>>(),
vec!["b".to_string(), "a".to_string()]
);
}
}