Enum boolean_expression::Expr

pub enum Expr<T> where
    T: Clone + Debug + Eq + Hash,  {
    Terminal(T),
    Const(bool),
    Not(Box<Expr<T>>),
    And(Box<Expr<T>>, Box<Expr<T>>),
    Or(Box<Expr<T>>, Box<Expr<T>>),
}

An Expr is a simple Boolean logic expression. It may contain terminals (i.e., free variables), constants, and the following fundamental operations: AND, OR, NOT.

use std::collections::HashMap;
use boolean_expression::Expr;

#[derive(Clone, Hash, Eq, PartialEq, Debug)]
enum RiverCrossing { Chicken, Fox, Grain }

let chicken = Expr::Terminal(RiverCrossing::Chicken);
let fox_and_grain = Expr::Terminal(RiverCrossing::Fox) & Expr::Terminal(RiverCrossing::Grain);

let allowed = (!chicken.clone() & fox_and_grain.clone()) | (chicken & !fox_and_grain);
let items = [
   (RiverCrossing::Grain, true),
   (RiverCrossing::Fox, true),
].iter().cloned().collect();

// nobody gets eaten!
assert!(allowed.evaluate(&items));

Variants

Terminal(T)

A terminal (free variable). This expression node represents a value that is not known until evaluation time.

Const(bool)

A boolean constant: true or false.

Not(Box<Expr<T>>)

The logical complement of the contained expression argument.

And(Box<Expr<T>>, Box<Expr<T>>)

The logical AND of the two expression arguments.

Or(Box<Expr<T>>, Box<Expr<T>>)

The logical OR of the two expression arguments.

Implementations

impl<T> Expr<T> where
    T: Clone + Debug + Eq + Hash, 

pub fn is_terminal(&self) -> bool

Returns true if this Expr is a terminal.

pub fn is_const(&self) -> bool

Returns true if this Expr is a constant.

pub fn is_not(&self) -> bool

Returns true if this Expr is a NOT node.

pub fn is_and(&self) -> bool

Returns true if this Expr is an AND node.

pub fn is_or(&self) -> bool

Returns true if this Expr is an OR node.

pub fn not(e: Expr<T>) -> Expr<T>

Builds a NOT node around an argument, consuming the argument expression.

pub fn and(e1: Expr<T>, e2: Expr<T>) -> Expr<T>

Builds an AND node around two arguments, consuming the argument expressions.

pub fn or(e1: Expr<T>, e2: Expr<T>) -> Expr<T>

Builds an OR node around two arguments, consuming the argument expressions.

pub fn xor(e1: Expr<T>, e2: Expr<T>) -> Expr<T>

pub fn evaluate(&self, vals: &HashMap<T, bool>) -> bool

Evaluates the expression with a particular set of terminal assignments. If any terminals are not assigned, they default to false.

pub fn evaluate_with<F>(&self, f: F) -> bool where
    F: Fn(&T) -> bool, 

Evaluates the expression using the provided function to map terminals (variables) to boolean values. This is a generalization of Expr::evaluate, where the variable lookup in a hashmap is replaced with an arbitrary computation.

 use boolean_expression::Expr;

 let expression = Expr::Terminal(10) | Expr::Terminal(3);

 // check if the expression satisfies a predicate
 assert!(expression.evaluate_with(|&x| x > 5));

pub fn simplify_via_laws(self) -> Expr<T>

Simplify an expression in a relatively cheap way using well-known logic identities.

This function performs certain reductions using DeMorgan’s Law, distribution of ANDs over ORs, and certain identities involving constants, to simplify an expression. The result will always be in sum-of-products form: nodes will always appear in order (from expression tree root to leaves) OR -> AND -> NOT. In other words, AND nodes may only have NOT nodes (or terminals or constants) as children, and NOT nodes may only have terminals or constants as children.

This function explicitly does not perform any sort of minterm reduction. The terms may thus be redundant (i.e., And(a, b) may appear twice), and combinable terms may exist (i.e., And(a, b) and And(a, Not(b)) may appear in the OR’d list of terms, where these could be combined to simply a but are not). For example:

use boolean_expression::Expr;

// This simplifies using DeMorgan's Law:
let expr = Expr::not(Expr::or(Expr::Terminal(0), Expr::Terminal(1)));
let simplified = expr.simplify_via_laws();
assert_eq!(simplified,
    Expr::and(Expr::not(Expr::Terminal(0)),
              Expr::not(Expr::Terminal(1))));

// This doesn't simplify, though:
let expr = Expr::or(
            Expr::and(Expr::Terminal(0), Expr::Terminal(1)),
            Expr::and(Expr::Terminal(0), Expr::not(Expr::Terminal(1))));
let simplified = expr.clone().simplify_via_laws();
assert_eq!(simplified, expr);

For better (but more expensive) simplification, see simplify_via_bdd().

pub fn simplify_via_bdd(self) -> Expr<T>

Simplify an expression via a roundtrip through a BDD. This procedure is more effective than Expr::simplify_via_laws(), but more expensive. This roundtrip will implicitly simplify an arbitrarily complicated function (by construction, as the BDD is built), and then find a quasi-minimal set of terms using cubelist-based reduction. For example:

use boolean_expression::Expr;

// `simplify_via_laws()` cannot combine these terms, but
// `simplify_via_bdd()` will:
let expr = Expr::or(
            Expr::and(Expr::Terminal(0), Expr::Terminal(1)),
            Expr::and(Expr::Terminal(0), Expr::not(Expr::Terminal(1))));
let simplified = expr.simplify_via_bdd();
assert_eq!(simplified, Expr::Terminal(0));

pub fn map<F, R>(&self, f: F) -> Expr<R> where
    F: Fn(&T) -> R,
    R: Clone + Debug + Eq + Hash, 

Map terminal values using the specified mapping function.

Trait Implementations

impl<T> BitAnd<Expr<T>> for Expr<T> where
    T: Clone + Debug + Eq + Hash, 

type Output = Self

The resulting type after applying the & operator.

fn bitand(self, rhs: Expr<T>) -> Self::Output

Performs the & operation.

impl<T> BitAndAssign<Expr<T>> for Expr<T> where
    T: Clone + Debug + Eq + Hash, 

fn bitand_assign(&mut self, rhs: Expr<T>)

Performs the &= operation.

impl<T> BitOr<Expr<T>> for Expr<T> where
    T: Clone + Debug + Eq + Hash, 

type Output = Self

The resulting type after applying the | operator.

fn bitor(self, rhs: Expr<T>) -> Self::Output

Performs the | operation.

impl<T> BitOrAssign<Expr<T>> for Expr<T> where
    T: Clone + Debug + Eq + Hash, 

fn bitor_assign(&mut self, rhs: Expr<T>)

Performs the |= operation.

impl<T> BitXor<Expr<T>> for Expr<T> where
    T: Clone + Debug + Eq + Hash, 

type Output = Self

The resulting type after applying the ^ operator.

fn bitxor(self, rhs: Expr<T>) -> Self::Output

Performs the ^ operation.

impl<T> BitXorAssign<Expr<T>> for Expr<T> where
    T: Clone + Debug + Eq + Hash, 

fn bitxor_assign(&mut self, rhs: Expr<T>)

Performs the ^= operation.

impl<T: Clone> Clone for Expr<T> where
    T: Clone + Debug + Eq + Hash, 

fn clone(&self) -> Expr<T>

Returns a copy of the value.

pub fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug> Debug for Expr<T> where
    T: Clone + Debug + Eq + Hash, 

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: Eq> Eq for Expr<T> where
    T: Clone + Debug + Eq + Hash, 

impl<T: Hash> Hash for Expr<T> where
    T: Clone + Debug + Eq + Hash, 

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

pub fn hash_slice<H>(data: &[Self], state: &mut H) where
    H: Hasher, 

Feeds a slice of this type into the given Hasher.

impl<T> Not for Expr<T> where
    T: Clone + Debug + Eq + Hash, 

type Output = Self

The resulting type after applying the ! operator.

fn not(self) -> Self::Output

Performs the unary ! operation.

impl<T: PartialEq> PartialEq<Expr<T>> for Expr<T> where
    T: Clone + Debug + Eq + Hash, 

fn eq(&self, other: &Expr<T>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Expr<T>) -> bool

This method tests for !=.

impl<T> StructuralEq for Expr<T> where
    T: Clone + Debug + Eq + Hash, 

impl<T> StructuralPartialEq for Expr<T> where
    T: Clone + Debug + Eq + Hash,