BoolExpr.cs source code in C# .NET

Source code for the .NET framework in C#

                        

Code:

/ 4.0 / 4.0 / untmp / DEVDIV_TFS / Dev10 / Releases / RTMRel / ndp / fx / src / DataEntity / System / Data / Common / Utils / Boolean / BoolExpr.cs / 1305376 / BoolExpr.cs

                            //---------------------------------------------------------------------- 
// 
//      Copyright (c) Microsoft Corporation.  All rights reserved.
// 
// 
// @owner [....]
// @backupOwner [....] 
//--------------------------------------------------------------------- 

using System; 
using System.Collections.Generic;
using System.Text;
using System.Globalization;
using System.Collections.ObjectModel; 
using System.Diagnostics;
using System.Linq; 
 
namespace System.Data.Common.Utils.Boolean
{ 
    /// 
    /// Base type for Boolean expressions. Boolean expressions are immutable,
    /// and value-comparable using Equals. Services include local simplification
    /// and normalization to Conjunctive and Disjunctive Normal Forms. 
    /// 
    ///  
    /// Comments use the following notation convention: 
    ///
    ///     "A . B" means "A and B" 
    ///     "A + B" means "A or B"
    ///     "!A" means "not A"
    /// 
    /// The type of leaf term identifiers in this expression. 
    internal abstract partial class BoolExpr : IEquatable>
    { 
        ///  
        /// Gets an enumeration value indicating the type of the expression node.
        ///  
        internal abstract ExprType ExprType { get; }

        /// 
        /// Standard accept method invoking the appropriate method overload 
        /// in the given visitor.
        ///  
        /// T_Return is the return type for the visitor. 
        /// Visitor implementation.
        /// Value computed for this node. 
        internal abstract T_Return Accept(Visitor visitor);

        /// 
        /// Invokes the Simplifier visitor on this expression tree. 
        /// Simplifications are purely local (see Simplifier class
        /// for details). 
        ///  
        internal BoolExpr Simplify()
        { 
            return IdentifierService.Instance.LocalSimplify(this);
        }

        ///  
        /// Expensive simplification that considers various permutations of the
        /// expression (including Decision Diagram, DNF, and CNF translations) 
        ///  
        internal BoolExpr ExpensiveSimplify(out Converter converter)
        { 
            var context = IdentifierService.Instance.CreateConversionContext();
            converter = new Converter(this, context);

            // Check for valid/unsat constraints 
            if (converter.Vertex.IsOne())
            { 
                return TrueExpr.Value; 
            }
            if (converter.Vertex.IsZero()) 
            {
                return FalseExpr.Value;
            }
 
            // Pick solution from the (unmodified) expression, its CNF and its DNF
            return ChooseCandidate(this, converter.Cnf.Expr, converter.Dnf.Expr); 
        } 

        private static BoolExpr ChooseCandidate(params BoolExpr[] candidates) 
        {
            Debug.Assert(null != candidates && 1 < candidates.Length, "must be at least one to pick");

            int resultUniqueTermCount = default(int); 
            int resultTermCount = default(int);
            BoolExpr result = null; 
 
            foreach (var candidate in candidates)
            { 
                // first do basic simplification
                var simplifiedCandidate = candidate.Simplify();

                // determine "interesting" properties of the expression 
                int candidateUniqueTermCount = simplifiedCandidate.GetTerms().Distinct().Count();
                int candidateTermCount = simplifiedCandidate.CountTerms(); 
 
                // see if it's better than the current result best result
                if (null == result || // bootstrap 
                    candidateUniqueTermCount < resultUniqueTermCount || // check if the candidate improves on # of terms
                    (candidateUniqueTermCount == resultUniqueTermCount && // in case of tie, choose based on total
                     candidateTermCount < resultTermCount))
                { 
                    result = simplifiedCandidate;
                    resultUniqueTermCount = candidateUniqueTermCount; 
                    resultTermCount = candidateTermCount; 
                }
            } 

            return result;
        }
 
        /// 
        /// Returns all term expressions below this node. 
        ///  
        internal List> GetTerms()
        { 
            return LeafVisitor.GetTerms(this);
        }

        ///  
        /// Counts terms in this expression.
        ///  
        internal int CountTerms() 
        {
            return TermCounter.CountTerms(this); 
        }

        /// 
        /// Implicit cast from a value of type T to a TermExpr where 
        /// TermExpr.Value is set to the given value.
        ///  
        /// Value to wrap in term expression 
        /// Term expression
        public static implicit operator BoolExpr(T_Identifier value) 
        {
            return new TermExpr(value);
        }
 
        /// 
        /// Creates the negation of the current element. 
        ///  
        internal virtual BoolExpr MakeNegated()
        { 
            return new NotExpr(this);
        }

        public override string ToString() 
        {
            return ExprType.ToString(); 
        } 

        public bool Equals(BoolExpr other) 
        {
            return null != other && ExprType == other.ExprType &&
                EquivalentTypeEquals(other);
        } 

        protected abstract bool EquivalentTypeEquals(BoolExpr other); 
    } 

    ///  
    /// Boolean expression that evaluates to true.
    /// 
    /// The type of leaf term identifiers in this expression.
    internal sealed class TrueExpr : BoolExpr 
    {
        private static readonly TrueExpr s_value = new TrueExpr(); 
 
        // private constructor so that we control existence of True instance
        private TrueExpr() 
            : base()
        {
        }
 
        /// 
        /// Gets the one instance of TrueExpr 
        ///  
        internal static TrueExpr Value { get { return s_value; } }
 
        internal override ExprType ExprType { get { return ExprType.True; } }

        internal override T_Return Accept(Visitor visitor)
        { 
            return visitor.VisitTrue(this);
        } 
 
        internal override BoolExpr MakeNegated()
        { 
            return FalseExpr.Value;
        }

        protected override bool EquivalentTypeEquals(BoolExpr other) 
        {
            return object.ReferenceEquals(this, other); 
        } 
    }
 
    /// 
    /// Boolean expression that evaluates to false.
    /// 
    /// The type of leaf term identifiers in this expression. 
    internal sealed class FalseExpr : BoolExpr
    { 
        private static readonly FalseExpr s_value = new FalseExpr(); 

        // private constructor so that we control existence of False instance 
        private FalseExpr()
            : base()
        {
        } 

        ///  
        /// Gets the one instance of FalseExpr 
        /// 
        internal static FalseExpr Value { get { return s_value; } } 

        internal override ExprType ExprType { get { return ExprType.False; } }

        internal override T_Return Accept(Visitor visitor) 
        {
            return visitor.VisitFalse(this); 
        } 

        internal override BoolExpr MakeNegated() 
        {
            return TrueExpr.Value;
        }
 
        protected override bool EquivalentTypeEquals(BoolExpr other)
        { 
            return object.ReferenceEquals(this, other); 
        }
    } 

    /// 
    /// A term is a leaf node in a Boolean expression. Its value (T/F) is undefined.
    ///  
    /// The type of leaf term identifiers in this expression.
    internal sealed class TermExpr : BoolExpr, IEquatable> 
    { 
        private readonly T_Identifier _identifier;
        private readonly IEqualityComparer _comparer; 

        /// 
        /// Construct a term.
        ///  
        /// Value comparer to use when comparing two
        /// term expressions. 
        /// Identifier/tag for this term. 
        internal TermExpr(IEqualityComparer comparer, T_Identifier identifier)
            : base() 
        {
            Debug.Assert(null != (object)identifier);
            _identifier = identifier;
            if (null == comparer) { _comparer = EqualityComparer.Default; } 
            else { _comparer = comparer; }
        } 
        internal TermExpr(T_Identifier identifier) : this(null, identifier) { } 

        ///  
        /// Gets identifier for this term. This value is used to determine whether
        /// two terms as equivalent.
        /// 
        internal T_Identifier Identifier { get { return _identifier; } } 

        internal override ExprType ExprType { get { return ExprType.Term; } } 
 
        public override bool Equals(object obj)
        { 
            Debug.Fail("use only typed equals");
            return this.Equals(obj as TermExpr);
        }
 
        public bool Equals(TermExpr other)
        { 
            return _comparer.Equals(_identifier, other._identifier); 
        }
 
        protected override bool EquivalentTypeEquals(BoolExpr other)
        {
            return _comparer.Equals(_identifier, ((TermExpr)other)._identifier);
        } 

        public override int GetHashCode() 
        { 
            return _comparer.GetHashCode(_identifier);
        } 

        public override string ToString()
        {
            return StringUtil.FormatInvariant("{0}", _identifier); 
        }
 
        internal override T_Return Accept(Visitor visitor) 
        {
            return visitor.VisitTerm(this); 
        }

        internal override BoolExpr MakeNegated()
        { 
            Literal literal = new Literal(this, true);
            // leverage normalization code if it exists 
            Literal negatedLiteral = literal.MakeNegated(); 
            if (negatedLiteral.IsTermPositive)
            { 
                return negatedLiteral.Term;
            }
            else
            { 
                return new NotExpr(negatedLiteral.Term);
            } 
        } 
    }
 
    /// 
    /// Abstract base class for tree expressions (unary as in Not, n-ary
    /// as in And or Or). Duplicate elements are trimmed at construction
    /// time (algorithms applied to these trees rely on the assumption 
    /// of uniform children).
    ///  
    /// The type of leaf term identifiers in this expression. 
    internal abstract class TreeExpr : BoolExpr
    { 
        private readonly Set> _children;
        private readonly int _hashCode;

        ///  
        /// Initialize a new tree expression with the given children.
        ///  
        /// Child expressions 
        protected TreeExpr(IEnumerable> children)
            : base() 
        {
            Debug.Assert(null != children);
            _children = new Set>(children);
            _children.MakeReadOnly(); 
            _hashCode = _children.GetElementsHashCode();
        } 
 
        /// 
        /// Gets the children of this expression node. 
        /// 
        internal Set> Children { get { return _children; } }

        public override bool Equals(object obj) 
        {
            Debug.Fail("use only typed Equals"); 
            return base.Equals(obj as BoolExpr); 
        }
 
        public override int GetHashCode()
        {
            return _hashCode;
        } 

        public override string ToString() 
        { 
            return StringUtil.FormatInvariant("{0}({1})", ExprType, _children);
        } 

        protected override bool EquivalentTypeEquals(BoolExpr other)
        {
            return ((TreeExpr)other).Children.SetEquals(Children); 
        }
    } 
 
    /// 
    /// A tree expression that evaluates to true iff. none of its children 
    /// evaluate to false.
    /// 
    /// 
    /// An And expression with no children is equivalent to True (this is an 
    /// operational convenience because we assume an implicit True is along
    /// for the ride in every And expression) 
    /// 
    ///     A . True iff. A
    ///  
    /// The type of leaf term identifiers in this expression.
    internal class AndExpr : TreeExpr
    {
        ///  
        /// Initialize a new And expression with the given children.
        ///  
        /// Child expressions 
        internal AndExpr(params BoolExpr[] children)
            : this((IEnumerable>)children) 
        {
        }

        ///  
        /// Initialize a new And expression with the given children.
        ///  
        /// Child expressions 
        internal AndExpr(IEnumerable> children)
            : base(children) 
        {
        }

        internal override ExprType ExprType { get { return ExprType.And; } } 

        internal override T_Return Accept(Visitor visitor) 
        { 
            return visitor.VisitAnd(this);
        } 
    }

    /// 
    /// A tree expression that evaluates to true iff. any of its children 
    /// evaluates to true.
    ///  
    ///  
    /// An Or expression with no children is equivalent to False (this is an
    /// operational convenience because we assume an implicit False is along 
    /// for the ride in every Or expression)
    ///
    ///     A + False iff. A
    ///  
    /// The type of leaf term identifiers in this expression.
    internal class OrExpr : TreeExpr 
    { 
        /// 
        /// Initialize a new Or expression with the given children. 
        /// 
        /// Child expressions
        internal OrExpr(params BoolExpr[] children)
            : this((IEnumerable>)children) 
        {
        } 
 
        /// 
        /// Initialize a new Or expression with the given children. 
        /// 
        /// Child expressions
        internal OrExpr(IEnumerable> children)
            : base(children) 
        {
        } 
 
        internal override ExprType ExprType { get { return ExprType.Or; } }
 
        internal override T_Return Accept(Visitor visitor)
        {
            return visitor.VisitOr(this);
        } 
    }
 
    ///  
    /// A tree expression that evaluates to true iff. its (single) child evaluates to false.
    ///  
    /// The type of leaf term identifiers in this expression.
    internal sealed class NotExpr : TreeExpr
    {
        ///  
        /// Initialize a new Not expression with the given child.
        ///  
        ///  
        internal NotExpr(BoolExpr child)
            : base(new BoolExpr[] { child }) 
        {
        }

        internal override ExprType ExprType { get { return ExprType.Not; } } 

        internal BoolExpr Child { get { return Children.First(); } } 
 
        internal override T_Return Accept(Visitor visitor)
        { 
            return visitor.VisitNot(this);
        }

        public override string ToString() 
        {
            return String.Format(CultureInfo.InvariantCulture, "!{0}", Child); 
        } 

        internal override BoolExpr MakeNegated() 
        {
            return this.Child;
        }
    } 

    ///  
    /// Enumeration of Boolean expression node types. 
    /// 
    internal enum ExprType 
    {
        And, Not, Or, Term, True, False,
    }
} 

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
                        

Link Menu

Network programming in C#, Network Programming in VB.NET, Network Programming in .NET
This book is available now!
Buy at Amazon US or
Buy at Amazon UK