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