mcs/class/referencesource/System.Data.Entity/System/Data/Common/Utils/Boolean/NegationPusher.cs

   1 //---------------------------------------------------------------------
   2 // <copyright file="NegationPusher.cs" company="Microsoft">
   3 //      Copyright (c) Microsoft Corporation.  All rights reserved.
   4 // </copyright>
   5 //
   6 // @owner Microsoft
   7 // @backupOwner Microsoft
   8 //---------------------------------------------------------------------
   9
  10 using System;
  11 using System.Collections.Generic;
  12 using System.Text;
  13 using System.Diagnostics;
  14 using System.Linq;
  15
  16 namespace System.Data.Common.Utils.Boolean
  17 {
  18     // Top-down push-down of negation in Boolean expressions.
  19     // - !(A or B) iff. !A and !B
  20     // - !(A and B) iff. !A or !B
  21     // - !!A iff. A
  22     // Uses two visitor classes: one to handle negated subtrees (essentially creates
  23     // an inverted tree) and one to handle non-negated subtrees (replicates until it
  24     // encounters NotExpr)
  25     internal static class NegationPusher
  26     {
  27         internal static BoolExpr<DomainConstraint<T_Variable, T_Element>> EliminateNot<T_Variable, T_Element>(BoolExpr<DomainConstraint<T_Variable, T_Element>> expression)
  28         {
  29             return expression.Accept(NonNegatedDomainConstraintTreeVisitor<T_Variable, T_Element>.Instance);
  30         }
  31
  32         private class NonNegatedTreeVisitor<T_Identifier> : BasicVisitor<T_Identifier>
  33         {
  34             internal static readonly NonNegatedTreeVisitor<T_Identifier> Instance = new NonNegatedTreeVisitor<T_Identifier>();
  35
  36             protected NonNegatedTreeVisitor()
  37             {
  38             }
  39
  40             internal override BoolExpr<T_Identifier> VisitNot(NotExpr<T_Identifier> expression)
  41             {
  42                 return expression.Child.Accept(NegatedTreeVisitor<T_Identifier>.Instance);
  43             }
  44         }
  45
  46         private class NegatedTreeVisitor<T_Identifier> : Visitor<T_Identifier, BoolExpr<T_Identifier>>
  47         {
  48             internal static readonly NegatedTreeVisitor<T_Identifier> Instance = new NegatedTreeVisitor<T_Identifier>();
  49
  50             protected NegatedTreeVisitor()
  51             {
  52             }
  53
  54             internal override BoolExpr<T_Identifier> VisitTrue(TrueExpr<T_Identifier> expression)
  55             {
  56                 return FalseExpr<T_Identifier>.Value;
  57             }
  58
  59             internal override BoolExpr<T_Identifier> VisitFalse(FalseExpr<T_Identifier> expression)
  60             {
  61                 return TrueExpr<T_Identifier>.Value;
  62             }
  63
  64             internal override BoolExpr<T_Identifier> VisitTerm(TermExpr<T_Identifier> expression)
  65             {
  66                 return new NotExpr<T_Identifier>(expression);
  67             }
  68
  69             internal override BoolExpr<T_Identifier> VisitNot(NotExpr<T_Identifier> expression)
  70             {
  71                 return expression.Child.Accept(NonNegatedTreeVisitor<T_Identifier>.Instance);
  72             }
  73
  74             internal override BoolExpr<T_Identifier> VisitAnd(AndExpr<T_Identifier> expression)
  75             {
  76                 return new OrExpr<T_Identifier>(expression.Children.Select(child => child.Accept(this)));
  77             }
  78
  79             internal override BoolExpr<T_Identifier> VisitOr(OrExpr<T_Identifier> expression)
  80             {
  81                 return new AndExpr<T_Identifier>(expression.Children.Select(child => child.Accept(this)));
  82             }
  83         }
  84
  85         private class NonNegatedDomainConstraintTreeVisitor<T_Variable, T_Element> : NonNegatedTreeVisitor<DomainConstraint<T_Variable, T_Element>>
  86         {
  87             internal new static readonly NonNegatedDomainConstraintTreeVisitor<T_Variable, T_Element> Instance = new NonNegatedDomainConstraintTreeVisitor<T_Variable, T_Element>();
  88
  89             private NonNegatedDomainConstraintTreeVisitor()
  90             {
  91             }
  92
  93             internal override BoolExpr<DomainConstraint<T_Variable, T_Element>> VisitNot(NotExpr<DomainConstraint<T_Variable, T_Element>> expression)
  94             {
  95                 return expression.Child.Accept(NegatedDomainConstraintTreeVisitor<T_Variable, T_Element>.Instance);
  96             }
  97         }
  98
  99         private class NegatedDomainConstraintTreeVisitor<T_Variable, T_Element> : NegatedTreeVisitor<DomainConstraint<T_Variable, T_Element>>
 100         {
 101             internal new static readonly NegatedDomainConstraintTreeVisitor<T_Variable, T_Element> Instance = new NegatedDomainConstraintTreeVisitor<T_Variable, T_Element>();
 102
 103             private NegatedDomainConstraintTreeVisitor()
 104             {
 105             }
 106
 107             internal override BoolExpr<DomainConstraint<T_Variable, T_Element>> VisitNot(NotExpr<DomainConstraint<T_Variable, T_Element>> expression)
 108             {
 109                 return expression.Child.Accept(NonNegatedDomainConstraintTreeVisitor<T_Variable, T_Element>.Instance);
 110             }
 111
 112             internal override BoolExpr<DomainConstraint<T_Variable, T_Element>> VisitTerm(TermExpr<DomainConstraint<T_Variable, T_Element>> expression)
 113             {
 114                 return new TermExpr<DomainConstraint<T_Variable, T_Element>>(expression.Identifier.InvertDomainConstraint());
 115             }
 116         }
 117     }
 118 }