Code:
/ 4.0 / 4.0 / 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 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
- FormClosedEvent.cs
- _SslSessionsCache.cs
- SecuritySessionServerSettings.cs
- SymmetricAlgorithm.cs
- ToggleButtonAutomationPeer.cs
- SmtpLoginAuthenticationModule.cs
- StorageSetMapping.cs
- _UncName.cs
- WebBrowserEvent.cs
- UpDownBase.cs
- TemplateParser.cs
- ProtocolsConfiguration.cs
- CommonRemoteMemoryBlock.cs
- WindowsHyperlink.cs
- ConstraintConverter.cs
- EventRecord.cs
- BrushMappingModeValidation.cs
- HtmlElementErrorEventArgs.cs
- BitmapInitialize.cs
- XmlSchemaComplexContentExtension.cs
- mansign.cs
- UnaryQueryOperator.cs
- AnnotationHelper.cs
- TextStore.cs
- AggregatePushdown.cs
- TextDecorationCollection.cs
- PathSegmentCollection.cs
- RemotingService.cs
- Point3DConverter.cs
- PartialCachingAttribute.cs
- RoutedUICommand.cs
- MetadataPropertyAttribute.cs
- SubMenuStyleCollectionEditor.cs
- documentsequencetextview.cs
- EncodingTable.cs
- DataGridViewButtonCell.cs
- HttpProcessUtility.cs
- ControlAdapter.cs
- FreezableDefaultValueFactory.cs
- Endpoint.cs
- WebPartManager.cs
- ListViewItemEventArgs.cs
- ThaiBuddhistCalendar.cs
- SnapLine.cs
- ToolStripOverflow.cs
- FillBehavior.cs
- DateTimeOffset.cs
- ManipulationBoundaryFeedbackEventArgs.cs
- GeneralTransform3DGroup.cs
- SelectionHighlightInfo.cs
- PolygonHotSpot.cs
- XmlSchemaRedefine.cs
- XslTransform.cs
- BitmapEffectInputData.cs
- FontStretchConverter.cs
- ObjectReferenceStack.cs
- RefType.cs
- BmpBitmapEncoder.cs
- TypeFieldSchema.cs
- OpCodes.cs
- SqlSelectStatement.cs
- CommonObjectSecurity.cs
- TemplateBindingExtensionConverter.cs
- InvalidDataException.cs
- ProxyHelper.cs
- TemplateControlCodeDomTreeGenerator.cs
- PerspectiveCamera.cs
- TextServicesDisplayAttributePropertyRanges.cs
- MouseEvent.cs
- ActiveXMessageFormatter.cs
- XmlSchemaExporter.cs
- ConsoleTraceListener.cs
- ComponentGlyph.cs
- CustomWebEventKey.cs
- XmlConvert.cs
- NameValuePermission.cs
- Internal.cs
- Base64Decoder.cs
- Lease.cs
- RoleGroup.cs
- CharacterMetrics.cs
- DomainUpDown.cs
- WeakHashtable.cs
- RegexGroup.cs
- DefaultValueTypeConverter.cs
- PlatformCulture.cs
- MarkupCompiler.cs
- DataGridState.cs
- HttpResponseInternalWrapper.cs
- NativeMethods.cs
- GenericsInstances.cs
- PackageRelationship.cs
- OutputScope.cs
- UpDownBase.cs
- StringCollection.cs
- HScrollBar.cs
- IntegerValidator.cs
- XmlSerializerNamespaces.cs
- CachedFontFace.cs
- NavigatorInput.cs