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
- Configuration.cs
- BoundPropertyEntry.cs
- AxHost.cs
- ExpressionTable.cs
- CreateUserWizardAutoFormat.cs
- DataGridCellEditEndingEventArgs.cs
- ToolStripItemRenderEventArgs.cs
- SmtpReplyReader.cs
- TextDecorations.cs
- InputScopeConverter.cs
- BinaryMessageFormatter.cs
- SettingsAttributes.cs
- PropertyStore.cs
- Int16Converter.cs
- FileLogRecordHeader.cs
- Int64Storage.cs
- PersonalizationState.cs
- IdlingCommunicationPool.cs
- LayoutTableCell.cs
- Rotation3D.cs
- ReaderOutput.cs
- HtmlShim.cs
- FileLogRecord.cs
- HybridDictionary.cs
- Vector3D.cs
- IntersectQueryOperator.cs
- TabletDevice.cs
- RequestCachePolicyConverter.cs
- InputReportEventArgs.cs
- SafeCoTaskMem.cs
- TextBox.cs
- XmlSchemaNotation.cs
- _TransmitFileOverlappedAsyncResult.cs
- StylusTip.cs
- ColumnBinding.cs
- XpsViewerException.cs
- SvcMapFileSerializer.cs
- XmlSchemaAnnotation.cs
- Permission.cs
- BrowsableAttribute.cs
- metadatamappinghashervisitor.hashsourcebuilder.cs
- CustomExpression.cs
- XPathPatternParser.cs
- IDataContractSurrogate.cs
- PointHitTestResult.cs
- WorkflowControlEndpoint.cs
- ListView.cs
- ValidationSummary.cs
- SpecialNameAttribute.cs
- BindingList.cs
- MethodRental.cs
- ProvidersHelper.cs
- ImageList.cs
- PackageRelationship.cs
- DataGridViewColumnConverter.cs
- DetailsViewPagerRow.cs
- XmlQueryOutput.cs
- PathSegment.cs
- PageCatalogPart.cs
- CheckBoxField.cs
- tibetanshape.cs
- NameSpaceExtractor.cs
- DesignTimeVisibleAttribute.cs
- DesignerTextBoxAdapter.cs
- LinkedDataMemberFieldEditor.cs
- XmlDownloadManager.cs
- SortedList.cs
- TdsEnums.cs
- DataGrid.cs
- ButtonFlatAdapter.cs
- SessionParameter.cs
- ScriptManagerProxy.cs
- Msmq.cs
- Cloud.cs
- TransformerInfo.cs
- SingleObjectCollection.cs
- SimpleWorkerRequest.cs
- RegexCompilationInfo.cs
- SqlConnectionString.cs
- HttpHandlerActionCollection.cs
- ExecutionEngineException.cs
- XmlPreloadedResolver.cs
- TableLayout.cs
- ArrayConverter.cs
- TextWriterEngine.cs
- ScrollContentPresenter.cs
- XmlNodeList.cs
- XPathSingletonIterator.cs
- AudioFormatConverter.cs
- TcpStreams.cs
- PageSettings.cs
- SqlUnionizer.cs
- SortQuery.cs
- Size3DConverter.cs
- ReadOnlyActivityGlyph.cs
- listitem.cs
- Icon.cs
- AliasGenerator.cs
- unitconverter.cs
- RsaSecurityToken.cs