Code:
/ Dotnetfx_Win7_3.5.1 / Dotnetfx_Win7_3.5.1 / 3.5.1 / DEVDIV / depot / DevDiv / releases / Orcas / NetFXw7 / ndp / fx / src / DataEntity / System / Data / Common / Utils / Boolean / BoolExpr.cs / 1 / 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 BoolExprSimplify() { return IdentifierService .Instance.LocalSimplify(this); } /// /// Expensive simplification that considers various permutations of the /// expression (including Decision Diagram, DNF, and CNF translations) /// internal BoolExprExpensiveSimplify(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 BoolExprMakeNegated() { 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 TrueExprValue { 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 FalseExprValue { 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(IEqualityComparercomparer, 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(BoolExprchild) : 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. //---------------------------------------------------------------------- //// 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 BoolExprSimplify() { return IdentifierService .Instance.LocalSimplify(this); } /// /// Expensive simplification that considers various permutations of the /// expression (including Decision Diagram, DNF, and CNF translations) /// internal BoolExprExpensiveSimplify(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 BoolExprMakeNegated() { 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 TrueExprValue { 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 FalseExprValue { 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(IEqualityComparercomparer, 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(BoolExprchild) : 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
This book is available now!
Buy at Amazon US or
Buy at Amazon UK
- ThemeDirectoryCompiler.cs
- CommunicationException.cs
- _FixedSizeReader.cs
- BufferModesCollection.cs
- WindowsIPAddress.cs
- BinaryFormatterWriter.cs
- unsafenativemethodstextservices.cs
- ErrorStyle.cs
- DSACryptoServiceProvider.cs
- odbcmetadatacolumnnames.cs
- NamespaceDecl.cs
- EventLogPermissionAttribute.cs
- WorkflowInlining.cs
- TreeNodeCollection.cs
- PackUriHelper.cs
- BuildResultCache.cs
- XmlnsCache.cs
- Comparer.cs
- _ReceiveMessageOverlappedAsyncResult.cs
- X509Certificate2.cs
- XPathArrayIterator.cs
- ContentDisposition.cs
- PolicyException.cs
- RSAPKCS1KeyExchangeDeformatter.cs
- ClientCultureInfo.cs
- SqlCommand.cs
- MemberHolder.cs
- SpoolingTaskBase.cs
- PointLight.cs
- SmtpNegotiateAuthenticationModule.cs
- MonthCalendar.cs
- XmlUnspecifiedAttribute.cs
- UpDownEvent.cs
- DynamicMethod.cs
- RequestSecurityToken.cs
- Bezier.cs
- AutomationPropertyInfo.cs
- ProtocolsSection.cs
- WebPartChrome.cs
- InheritanceAttribute.cs
- PeerContact.cs
- FixedDSBuilder.cs
- LayoutEditorPart.cs
- SqlServices.cs
- EnumBuilder.cs
- AsyncWaitHandle.cs
- Buffer.cs
- DataStreamFromComStream.cs
- WebPartConnection.cs
- XPathAncestorIterator.cs
- ProfileSettings.cs
- RegistrationServices.cs
- ExtractedStateEntry.cs
- DataGridViewRowHeightInfoPushedEventArgs.cs
- CodeTypeReference.cs
- ComboBoxHelper.cs
- BaseParser.cs
- OutputWindow.cs
- SrgsRule.cs
- SafeNativeMethodsOther.cs
- CommonDialog.cs
- MarshalDirectiveException.cs
- NumberFormatInfo.cs
- XmlSchemaIdentityConstraint.cs
- LookupNode.cs
- ReflectionUtil.cs
- String.cs
- _SpnDictionary.cs
- COM2ExtendedBrowsingHandler.cs
- HttpModuleCollection.cs
- SafeCryptoHandles.cs
- BinaryObjectInfo.cs
- ButtonRenderer.cs
- DbConnectionPool.cs
- LogicalTreeHelper.cs
- PathData.cs
- ConversionContext.cs
- DesignerExtenders.cs
- ThrowOnMultipleAssignment.cs
- Geometry3D.cs
- FileInfo.cs
- RadioButtonList.cs
- RouteParser.cs
- DesignerSerializationOptionsAttribute.cs
- ADMembershipProvider.cs
- QilTernary.cs
- SchemaInfo.cs
- SocketElement.cs
- ComplexPropertyEntry.cs
- SmtpDigestAuthenticationModule.cs
- ErrorFormatterPage.cs
- BitmapPalette.cs
- CharacterHit.cs
- LinearGradientBrush.cs
- RsaSecurityToken.cs
- RoleGroupCollection.cs
- TypeSource.cs
- ConcurrentStack.cs
- BinaryConverter.cs
- GlyphRunDrawing.cs