Code:
/ Dotnetfx_Vista_SP2 / Dotnetfx_Vista_SP2 / 8.0.50727.4016 / DEVDIV / depot / DevDiv / releases / Orcas / QFE / ndp / fx / src / DataEntity / System / Data / Common / Utils / Boolean / BoolExpr.cs / 2 / 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
- ProviderCollection.cs
- ArrayMergeHelper.cs
- HotCommands.cs
- OdbcConnectionString.cs
- XmlEntityReference.cs
- SqlCaseSimplifier.cs
- Rfc2898DeriveBytes.cs
- MimeParameter.cs
- XamlBrushSerializer.cs
- VerticalAlignConverter.cs
- HandlerFactoryWrapper.cs
- SelectedDatesCollection.cs
- _Rfc2616CacheValidators.cs
- RtfFormatStack.cs
- DataSourceViewSchemaConverter.cs
- UpDownEvent.cs
- ObjectStateManagerMetadata.cs
- DataMisalignedException.cs
- COM2Properties.cs
- TextEndOfSegment.cs
- TextElement.cs
- MessageDecoder.cs
- ProviderUtil.cs
- DataPagerFieldCommandEventArgs.cs
- HitTestWithPointDrawingContextWalker.cs
- ToolStripPanel.cs
- BamlBinaryReader.cs
- XmlSchemaAttribute.cs
- PrincipalPermission.cs
- XmlReaderDelegator.cs
- HTMLTagNameToTypeMapper.cs
- CompilerGlobalScopeAttribute.cs
- SafeNativeMethodsCLR.cs
- Ref.cs
- AsymmetricCryptoHandle.cs
- Codec.cs
- GraphicsContext.cs
- CompiledQueryCacheEntry.cs
- DbConnectionPoolIdentity.cs
- DefaultObjectMappingItemCollection.cs
- AdornerHitTestResult.cs
- UriTemplateTrieNode.cs
- GridViewRowCollection.cs
- CachedPathData.cs
- RegularExpressionValidator.cs
- ObjectViewFactory.cs
- WindowsIPAddress.cs
- ConfigurationCollectionAttribute.cs
- BinaryObjectReader.cs
- IPPacketInformation.cs
- SoapFault.cs
- ProtocolsConfigurationHandler.cs
- PageStatePersister.cs
- SqlMetaData.cs
- SqlWebEventProvider.cs
- HandoffBehavior.cs
- PrintDialog.cs
- ToolStripCustomTypeDescriptor.cs
- SocketPermission.cs
- indexingfiltermarshaler.cs
- TreeViewImageIndexConverter.cs
- DoubleStorage.cs
- XmlSchemaGroupRef.cs
- ExpressionConverter.cs
- ButtonBase.cs
- SHA1.cs
- RealizedColumnsBlock.cs
- MULTI_QI.cs
- DisplayInformation.cs
- Util.cs
- FloaterBaseParagraph.cs
- DataGridColumnEventArgs.cs
- Update.cs
- Attribute.cs
- unsafenativemethodstextservices.cs
- CqlErrorHelper.cs
- uribuilder.cs
- ResourcesChangeInfo.cs
- __Filters.cs
- XmlDataImplementation.cs
- BaseParaClient.cs
- _AuthenticationState.cs
- DocumentPageViewAutomationPeer.cs
- EntityDataSourceStatementEditor.cs
- Stylesheet.cs
- FileDialogCustomPlacesCollection.cs
- XPathNodeIterator.cs
- DesignerResources.cs
- NativeRightsManagementAPIsStructures.cs
- DocumentOrderComparer.cs
- XmlText.cs
- SchemaNotation.cs
- TextDecoration.cs
- CodeEventReferenceExpression.cs
- DataSourceCache.cs
- ResourceAssociationType.cs
- Blend.cs
- GatewayDefinition.cs
- FixedSOMContainer.cs
- DesignerCategoryAttribute.cs