Code:
/ Net / Net / 3.5.50727.3053 / DEVDIV / depot / DevDiv / releases / Orcas / SP / ndp / fx / src / DataEntity / System / Data / Common / Utils / Boolean / BoolExpr.cs / 3 / 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
- ModelItemDictionary.cs
- XmlSchemaDocumentation.cs
- FloaterParaClient.cs
- SqlServices.cs
- ExpandCollapsePatternIdentifiers.cs
- DefaultShape.cs
- MessageAction.cs
- NavigationService.cs
- CompositeFontInfo.cs
- XpsFilter.cs
- BamlTreeMap.cs
- SmiEventStream.cs
- DSACryptoServiceProvider.cs
- InternalBufferManager.cs
- TabControlToolboxItem.cs
- EntityDataSourceView.cs
- SqlBuilder.cs
- KeyedCollection.cs
- BasicHttpMessageSecurityElement.cs
- BaseDataBoundControl.cs
- CngKeyCreationParameters.cs
- updatecommandorderer.cs
- XPathExpr.cs
- EntityProviderFactory.cs
- FileDetails.cs
- ListItemCollection.cs
- SchemaImporterExtensionElement.cs
- TypeConverter.cs
- HeaderCollection.cs
- ControlPaint.cs
- RequestCache.cs
- DocumentPage.cs
- HierarchicalDataBoundControlAdapter.cs
- RequestBringIntoViewEventArgs.cs
- WindowsIPAddress.cs
- MailAddressCollection.cs
- DesignerActionListCollection.cs
- ApplicationContext.cs
- PersonalizationAdministration.cs
- PathTooLongException.cs
- CustomWebEventKey.cs
- LayoutEditorPart.cs
- XmlNotation.cs
- TableMethodGenerator.cs
- GatewayIPAddressInformationCollection.cs
- CompileXomlTask.cs
- TimeSpanSecondsConverter.cs
- baseaxisquery.cs
- ObjectDataSourceSelectingEventArgs.cs
- Assign.cs
- DataControlFieldTypeEditor.cs
- ObjectListItemCollection.cs
- KeyBinding.cs
- ValueHandle.cs
- BinaryObjectInfo.cs
- InvalidEnumArgumentException.cs
- ValidatorCompatibilityHelper.cs
- LowerCaseStringConverter.cs
- AdCreatedEventArgs.cs
- ItemList.cs
- ItemsChangedEventArgs.cs
- VScrollProperties.cs
- CompilationLock.cs
- ProtocolsConfiguration.cs
- base64Transforms.cs
- ServiceChannelFactory.cs
- UpdatePanel.cs
- EntityDataSourceView.cs
- BmpBitmapDecoder.cs
- TableLayoutSettingsTypeConverter.cs
- ZoneButton.cs
- GroupDescription.cs
- CqlParserHelpers.cs
- TreeNodeStyleCollection.cs
- MetadataArtifactLoaderCompositeFile.cs
- SystemMulticastIPAddressInformation.cs
- XmlIlGenerator.cs
- PointAnimationBase.cs
- AdapterUtil.cs
- InvokePattern.cs
- FormatException.cs
- SortKey.cs
- ExpressionWriter.cs
- DoubleAnimation.cs
- SqlBuilder.cs
- XmlChildNodes.cs
- EnumValAlphaComparer.cs
- XsltInput.cs
- VirtualDirectoryMapping.cs
- GridViewRow.cs
- RegexBoyerMoore.cs
- ImmComposition.cs
- IgnorePropertiesAttribute.cs
- SqlInternalConnectionTds.cs
- StreamSecurityUpgradeInitiator.cs
- SecurityIdentifierElementCollection.cs
- EUCJPEncoding.cs
- CommandEventArgs.cs
- TransformDescriptor.cs
- DbMetaDataFactory.cs