Enum boolean_expression::Expr

pub enum Expr<T> where
    T: Clone + Debug + Eq + Ord + 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.

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.

Methods

impl<T> Expr<T> where     T: Clone + Debug + Eq + Ord + 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 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 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 + Ord + Hash,

Map terminal values using the specified mapping function.

Trait Implementations

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

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

Returns a copy of the value.

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

Performs copy-assignment from source.

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

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

Formats the value using the given formatter.

impl<T: PartialEq> PartialEq for Expr<T> where     T: Clone + Debug + Eq + Ord + 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: Eq> Eq for Expr<T> where     T: Clone + Debug + Eq + Ord + Hash,

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

fn partial_cmp(&self, other: &Expr<T>) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

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

This method tests less than (for self and other) and is used by the < operator.

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

This method tests less than or equal to (for self and other) and is used by the <= operator.

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

This method tests greater than (for self and other) and is used by the > operator.

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

This method tests greater than or equal to (for self and other) and is used by the >= operator.

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

fn cmp(&self, other: &Expr<T>) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

Compares and returns the minimum of two values.

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

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

Feeds this value into the given [Hasher].

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

Feeds a slice of this type into the given [Hasher].