boolean_circuit/
builder.rs

1use crate::Node;
2
3/// Constructs a node that evaluates to `true` if and only if `x` and `y`
4/// evaluate to the same value.
5pub fn eq(x: &Node, y: &Node) -> Node {
6    !(x ^ y)
7}
8
9/// Constructs a node that evaluates to `true` if and only if all of the
10/// nodes returned by `i` evaulate to `true`.
11///
12/// The construction has logarithmic depth in the length if `i`.
13pub fn reduce_conjunction(i: impl IntoIterator<Item = Node>) -> Node {
14    reduce_associative(i.into_iter().collect::<Vec<_>>().as_slice(), |x, y| x & y)
15        .unwrap_or_else(|| true.into())
16}
17
18/// Constructs a node that evaluates to `true` if and only if at least one of the
19/// nodes returned by `i` evaulates to `true`.
20///
21/// The construction has logarithmic depth in the length if `i`.
22pub fn reduce_disjunction(i: impl IntoIterator<Item = Node>) -> Node {
23    reduce_associative(i.into_iter().collect::<Vec<_>>().as_slice(), |x, y| x | y)
24        .unwrap_or_else(|| false.into())
25}
26
27/// Constructs a node that evaluates to `true` if and only if an odd number of the
28/// nodes returned by `i` evaulate to `true`.
29///
30/// The construction has logarithmic depth in the length if `i`.
31pub fn reduce_xor(i: impl IntoIterator<Item = Node>) -> Node {
32    reduce_associative(i.into_iter().collect::<Vec<_>>().as_slice(), |x, y| x ^ y).unwrap()
33}
34
35fn reduce_associative<T: Clone>(i: &[T], op: fn(&T, &T) -> T) -> Option<T> {
36    match i.len() {
37        0 => None,
38        1 => Some(i[0].clone()),
39        _ => {
40            let mid = i.len() / 2;
41            Some(op(
42                &reduce_associative(&i[..mid], op).unwrap(),
43                &reduce_associative(&i[mid..], op).unwrap(),
44            ))
45        }
46    }
47}
boolean_circuit/builder.rs

boolean_circuit/
builder.rs
