Enum boolean_expression::Expr
[−]
[src]
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,
[src]
T: Clone + Debug + Eq + Ord + Hash,
pub fn is_terminal(&self) -> bool
[src]
Returns true
if this Expr
is a terminal.
pub fn is_const(&self) -> bool
[src]
Returns true
if this Expr
is a constant.
pub fn is_not(&self) -> bool
[src]
Returns true
if this Expr
is a NOT node.
pub fn is_and(&self) -> bool
[src]
Returns true
if this Expr
is an AND node.
pub fn is_or(&self) -> bool
[src]
Returns true
if this Expr
is an OR node.
pub fn not(e: Expr<T>) -> Expr<T>
[src]
Builds a NOT node around an argument, consuming the argument expression.
pub fn and(e1: Expr<T>, e2: Expr<T>) -> Expr<T>
[src]
Builds an AND node around two arguments, consuming the argument expressions.
pub fn or(e1: Expr<T>, e2: Expr<T>) -> Expr<T>
[src]
Builds an OR node around two arguments, consuming the argument expressions.
pub fn evaluate(&self, vals: &HashMap<T, bool>) -> bool
[src]
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>
[src]
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>
[src]
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,
[src]
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,
[src]
T: Clone + Debug + Eq + Ord + Hash,
fn clone(&self) -> Expr<T>
[src]
Returns a copy of the value. Read more
fn clone_from(&mut self, source: &Self)
1.0.0[src]
Performs copy-assignment from source
. Read more
impl<T: Debug> Debug for Expr<T> where
T: Clone + Debug + Eq + Ord + Hash,
[src]
T: Clone + Debug + Eq + Ord + Hash,
fn fmt(&self, __arg_0: &mut Formatter) -> Result
[src]
Formats the value using the given formatter. Read more
impl<T: PartialEq> PartialEq for Expr<T> where
T: Clone + Debug + Eq + Ord + Hash,
[src]
T: Clone + Debug + Eq + Ord + Hash,
fn eq(&self, __arg_0: &Expr<T>) -> bool
[src]
This method tests for self
and other
values to be equal, and is used by ==
. Read more
fn ne(&self, __arg_0: &Expr<T>) -> bool
[src]
This method tests for !=
.
impl<T: Eq> Eq for Expr<T> where
T: Clone + Debug + Eq + Ord + Hash,
[src]
T: Clone + Debug + Eq + Ord + Hash,
impl<T: PartialOrd> PartialOrd for Expr<T> where
T: Clone + Debug + Eq + Ord + Hash,
[src]
T: Clone + Debug + Eq + Ord + Hash,
fn partial_cmp(&self, __arg_0: &Expr<T>) -> Option<Ordering>
[src]
This method returns an ordering between self
and other
values if one exists. Read more
fn lt(&self, __arg_0: &Expr<T>) -> bool
[src]
This method tests less than (for self
and other
) and is used by the <
operator. Read more
fn le(&self, __arg_0: &Expr<T>) -> bool
[src]
This method tests less than or equal to (for self
and other
) and is used by the <=
operator. Read more
fn gt(&self, __arg_0: &Expr<T>) -> bool
[src]
This method tests greater than (for self
and other
) and is used by the >
operator. Read more
fn ge(&self, __arg_0: &Expr<T>) -> bool
[src]
This method tests greater than or equal to (for self
and other
) and is used by the >=
operator. Read more
impl<T: Ord> Ord for Expr<T> where
T: Clone + Debug + Eq + Ord + Hash,
[src]
T: Clone + Debug + Eq + Ord + Hash,
fn cmp(&self, __arg_0: &Expr<T>) -> Ordering
[src]
This method returns an Ordering
between self
and other
. Read more
fn max(self, other: Self) -> Self
1.21.0[src]
Compares and returns the maximum of two values. Read more
fn min(self, other: Self) -> Self
1.21.0[src]
Compares and returns the minimum of two values. Read more
impl<T: Hash> Hash for Expr<T> where
T: Clone + Debug + Eq + Ord + Hash,
[src]
T: Clone + Debug + Eq + Ord + Hash,