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 / Simplifier.cs / 2 / Simplifier.cs
//---------------------------------------------------------------------- //// Copyright (c) Microsoft Corporation. All rights reserved. // // // @owner [....] // @backupOwner [....] //--------------------------------------------------------------------- using System; using System.Collections.Generic; using System.Text; using System.Diagnostics; namespace System.Data.Common.Utils.Boolean { // Simplifier visitor for Boolean expressions. Performs the following // simplifications bottom-up: // - Eliminate True and False (A Or False iff. A, A And True iff. A) // - Resolve tautology (A Or !A iff. True, True Or A iff. True) and // contradiction (A And !A iff. False, False And A iff. False) // - Flatten nested negations (!!A iff. A) // - Evaluate bound literals (!True iff. False, etc.) // - Flatten unary/empty And/Or expressions internal class Simplifier: BasicVisitor { internal static readonly Simplifier Instance = new Simplifier (); protected Simplifier() { } internal override BoolExpr VisitNot(NotExpr expression) { BoolExpr child = expression.Child.Accept(this); switch (child.ExprType) { case ExprType.Not: return ((NotExpr )child).Child; case ExprType.True: return FalseExpr .Value; case ExprType.False: return TrueExpr .Value; default: return base.VisitNot(expression); } } internal override BoolExpr VisitAnd(AndExpr expression) { return SimplifyTree(expression); } internal override BoolExpr VisitOr(OrExpr expression) { return SimplifyTree(expression); } private BoolExpr SimplifyTree(TreeExpr tree) { bool isAnd = ExprType.And == tree.ExprType; Debug.Assert(isAnd || ExprType.Or == tree.ExprType); // Get list of simplified children, flattening nested And/Or expressions List > simplifiedChildren = new List >(tree.Children.Count); foreach (BoolExpr child in tree.Children) { BoolExpr simplifiedChild = child.Accept(this); // And(And(A, B), C) iff. And(A, B, C) // Or(Or(A, B), C) iff. Or(A, B, C) if (simplifiedChild.ExprType == tree.ExprType) { simplifiedChildren.AddRange(((TreeExpr )simplifiedChild).Children); } else { simplifiedChildren.Add(simplifiedChild); } } // Track negated children separately to identify tautologies and contradictions Dictionary , bool> negatedChildren = new Dictionary , bool>(tree.Children.Count); List > otherChildren = new List >(tree.Children.Count); foreach (BoolExpr simplifiedChild in simplifiedChildren) { switch (simplifiedChild.ExprType) { case ExprType.Not: negatedChildren[((NotExpr )simplifiedChild).Child] = true; break; case ExprType.False: // False And A --> False if (isAnd) { return FalseExpr .Value; } // False || A --> A (omit False from child collections) break; case ExprType.True: // True Or A --> True if (!isAnd) { return TrueExpr .Value; } // True And A --> A (omit True from child collections) break; default: otherChildren.Add(simplifiedChild); break; } } List > children = new List >(); foreach (BoolExpr child in otherChildren) { if (negatedChildren.ContainsKey(child)) { // A && !A --> False, A || !A --> True if (isAnd) { return FalseExpr .Value; } else { return TrueExpr .Value; } } children.Add(child); } foreach (BoolExpr child in negatedChildren.Keys) { children.Add(child.MakeNegated()); } if (0 == children.Count) { // And() iff. True if (isAnd) { return TrueExpr .Value; } // Or() iff. False else { return FalseExpr .Value; } } else if (1 == children.Count) { // Or(A) iff. A, And(A) iff. A return children[0]; } else { // Construct simplified And/Or expression TreeExpr result; if (isAnd) { result = new AndExpr (children); } else { result = new OrExpr (children); } return result; } } } } // 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.Diagnostics; namespace System.Data.Common.Utils.Boolean { // Simplifier visitor for Boolean expressions. Performs the following // simplifications bottom-up: // - Eliminate True and False (A Or False iff. A, A And True iff. A) // - Resolve tautology (A Or !A iff. True, True Or A iff. True) and // contradiction (A And !A iff. False, False And A iff. False) // - Flatten nested negations (!!A iff. A) // - Evaluate bound literals (!True iff. False, etc.) // - Flatten unary/empty And/Or expressions internal class Simplifier: BasicVisitor { internal static readonly Simplifier Instance = new Simplifier (); protected Simplifier() { } internal override BoolExpr VisitNot(NotExpr expression) { BoolExpr child = expression.Child.Accept(this); switch (child.ExprType) { case ExprType.Not: return ((NotExpr )child).Child; case ExprType.True: return FalseExpr .Value; case ExprType.False: return TrueExpr .Value; default: return base.VisitNot(expression); } } internal override BoolExpr VisitAnd(AndExpr expression) { return SimplifyTree(expression); } internal override BoolExpr VisitOr(OrExpr expression) { return SimplifyTree(expression); } private BoolExpr SimplifyTree(TreeExpr tree) { bool isAnd = ExprType.And == tree.ExprType; Debug.Assert(isAnd || ExprType.Or == tree.ExprType); // Get list of simplified children, flattening nested And/Or expressions List > simplifiedChildren = new List >(tree.Children.Count); foreach (BoolExpr child in tree.Children) { BoolExpr simplifiedChild = child.Accept(this); // And(And(A, B), C) iff. And(A, B, C) // Or(Or(A, B), C) iff. Or(A, B, C) if (simplifiedChild.ExprType == tree.ExprType) { simplifiedChildren.AddRange(((TreeExpr )simplifiedChild).Children); } else { simplifiedChildren.Add(simplifiedChild); } } // Track negated children separately to identify tautologies and contradictions Dictionary , bool> negatedChildren = new Dictionary , bool>(tree.Children.Count); List > otherChildren = new List >(tree.Children.Count); foreach (BoolExpr simplifiedChild in simplifiedChildren) { switch (simplifiedChild.ExprType) { case ExprType.Not: negatedChildren[((NotExpr )simplifiedChild).Child] = true; break; case ExprType.False: // False And A --> False if (isAnd) { return FalseExpr .Value; } // False || A --> A (omit False from child collections) break; case ExprType.True: // True Or A --> True if (!isAnd) { return TrueExpr .Value; } // True And A --> A (omit True from child collections) break; default: otherChildren.Add(simplifiedChild); break; } } List > children = new List >(); foreach (BoolExpr child in otherChildren) { if (negatedChildren.ContainsKey(child)) { // A && !A --> False, A || !A --> True if (isAnd) { return FalseExpr .Value; } else { return TrueExpr .Value; } } children.Add(child); } foreach (BoolExpr child in negatedChildren.Keys) { children.Add(child.MakeNegated()); } if (0 == children.Count) { // And() iff. True if (isAnd) { return TrueExpr .Value; } // Or() iff. False else { return FalseExpr .Value; } } else if (1 == children.Count) { // Or(A) iff. A, And(A) iff. A return children[0]; } else { // Construct simplified And/Or expression TreeExpr result; if (isAnd) { result = new AndExpr (children); } else { result = new OrExpr (children); } return result; } } } } // 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
- NativeMethods.cs
- ColumnMapProcessor.cs
- ConnectionStringsExpressionBuilder.cs
- ActiveDocumentEvent.cs
- SuppressMergeCheckAttribute.cs
- BamlTreeNode.cs
- Sentence.cs
- TextHintingModeValidation.cs
- PenCursorManager.cs
- Expander.cs
- CharConverter.cs
- FormatterServices.cs
- FormsAuthenticationUserCollection.cs
- AudioFormatConverter.cs
- diagnosticsswitches.cs
- PingOptions.cs
- DataException.cs
- _BufferOffsetSize.cs
- DispatcherHooks.cs
- RevocationPoint.cs
- ReplacementText.cs
- WindowsFormsHostPropertyMap.cs
- ArraySegment.cs
- Encoder.cs
- OptimalBreakSession.cs
- PerformanceCountersElement.cs
- ParseChildrenAsPropertiesAttribute.cs
- EFDataModelProvider.cs
- EntityWithKeyStrategy.cs
- ProgressPage.cs
- ButtonChrome.cs
- ExtendedPropertiesHandler.cs
- DiscoveryMessageSequence.cs
- wgx_commands.cs
- Events.cs
- WebScriptEnablingElement.cs
- SafeNativeMethods.cs
- ChannelAcceptor.cs
- EncoderNLS.cs
- HttpRuntimeSection.cs
- HelpProvider.cs
- storepermissionattribute.cs
- HashCodeCombiner.cs
- PersonalizationEntry.cs
- CompilationSection.cs
- ListItemCollection.cs
- HwndTarget.cs
- DrawingDrawingContext.cs
- FontWeightConverter.cs
- MemberAssignmentAnalysis.cs
- COM2PropertyPageUITypeConverter.cs
- DataServiceException.cs
- JsonReaderDelegator.cs
- ToolBarOverflowPanel.cs
- HttpModuleActionCollection.cs
- DataGridViewCellErrorTextNeededEventArgs.cs
- MarkupCompilePass2.cs
- UrlMapping.cs
- ExpressionNode.cs
- PieceNameHelper.cs
- ListItem.cs
- InheritedPropertyChangedEventArgs.cs
- RequestQueryParser.cs
- SvcMapFile.cs
- IfJoinedCondition.cs
- PackageDigitalSignatureManager.cs
- ScrollEvent.cs
- CodeTypeDeclarationCollection.cs
- ServiceObjectContainer.cs
- SqlUtils.cs
- BinaryMessageFormatter.cs
- Variant.cs
- DerivedKeySecurityToken.cs
- SqlFacetAttribute.cs
- FixedTextView.cs
- MULTI_QI.cs
- Grant.cs
- NopReturnReader.cs
- AdornedElementPlaceholder.cs
- ObjectSerializerFactory.cs
- DtcInterfaces.cs
- Pair.cs
- MemberInfoSerializationHolder.cs
- MediaContext.cs
- UIElementParaClient.cs
- WizardStepBase.cs
- DataSourceXmlTextReader.cs
- ListViewGroupConverter.cs
- RegisteredHiddenField.cs
- TextEditorLists.cs
- LinearGradientBrush.cs
- SecurityRuntime.cs
- BindingNavigator.cs
- WebPartActionVerb.cs
- SvcMapFileSerializer.cs
- Function.cs
- QueryableDataSource.cs
- ImportCatalogPart.cs
- XmlHierarchyData.cs
- DispatcherExceptionFilterEventArgs.cs