1 //---------------------------------------------------------------------
2 // <copyright file="Sentence.cs" company="Microsoft">
3 // Copyright (c) Microsoft Corporation. All rights reserved.
7 // @backupOwner Microsoft
8 //---------------------------------------------------------------------
11 using System
.Collections
.Generic
;
13 using System
.Globalization
;
14 using System
.Collections
.ObjectModel
;
15 using System
.Diagnostics
;
18 namespace System
.Data
.Common
.Utils
.Boolean
21 /// Abstract base class for nodes in normal form expressions, e.g. Conjunctive Normal Form
24 /// <typeparam name="T_Identifier">Type of expression leaf term identifiers.</typeparam>
25 internal abstract class NormalFormNode
<T_Identifier
>
27 private readonly BoolExpr
<T_Identifier
> _expr
;
30 /// Initialize a new normal form node representing the given expression. Caller must
31 /// ensure the expression is logically equivalent to the node.
33 /// <param name="expr">Expression logically equivalent to this node.</param>
34 protected NormalFormNode(BoolExpr
<T_Identifier
> expr
) { _expr = expr.Simplify(); }
37 /// Gets an expression that is logically equivalent to this node.
39 internal BoolExpr
<T_Identifier
> Expr { get { return _expr; }
}
42 /// Utility method for delegation that return the expression corresponding to a given
45 /// <typeparam name="T_NormalFormNode">Type of node</typeparam>
46 /// <param name="node">Node to examine.</param>
47 /// <returns>Equivalent Boolean expression for the given node.</returns>
48 protected static BoolExpr
<T_Identifier
> ExprSelector
<T_NormalFormNode
>(T_NormalFormNode node
)
49 where T_NormalFormNode
: NormalFormNode
<T_Identifier
>
56 /// Abstract base class for normal form sentences (CNF and DNF)
58 /// <typeparam name="T_Identifier">Type of expression leaf term identifiers.</typeparam>
59 /// <typeparam name="T_Clause">Type of clauses in the sentence.</typeparam>
60 internal abstract class Sentence
<T_Identifier
, T_Clause
> : NormalFormNode
<T_Identifier
>
61 where T_Clause
: Clause
<T_Identifier
>, IEquatable
<T_Clause
>
63 private readonly Set
<T_Clause
> _clauses
;
66 /// Initialize a sentence given the appropriate sentence clauses. Produces
67 /// an equivalent expression by composing the clause expressions using
68 /// the given tree type.
70 /// <param name="clauses">Sentence clauses</param>
71 /// <param name="treeType">Tree type for sentence (and generated expression)</param>
72 protected Sentence(Set
<T_Clause
> clauses
, ExprType treeType
)
73 : base(ConvertClausesToExpr(clauses
, treeType
))
75 _clauses
= clauses
.AsReadOnly();
78 // Produces an expression equivalent to the given clauses by composing the clause
79 // expressions using the given tree type.
80 private static BoolExpr
<T_Identifier
> ConvertClausesToExpr(Set
<T_Clause
> clauses
, ExprType treeType
)
82 bool isAnd
= ExprType
.And
== treeType
;
83 Debug
.Assert(isAnd
|| ExprType
.Or
== treeType
);
85 IEnumerable
<BoolExpr
<T_Identifier
>> clauseExpressions
=
86 clauses
.Select(new Func
<T_Clause
, BoolExpr
<T_Identifier
>>(ExprSelector
));
90 return new AndExpr
<T_Identifier
>(clauseExpressions
);
94 return new OrExpr
<T_Identifier
>(clauseExpressions
);
98 public override string ToString()
100 StringBuilder builder
= new StringBuilder();
101 builder
.Append("Sentence{");
102 builder
.Append(_clauses
);
103 return builder
.Append("}").ToString();
108 /// Represents a sentence in disjunctive normal form, e.g.:
110 /// Clause1 + Clause2 . ...
112 /// Where each DNF clause is of the form:
114 /// Literal1 . Literal2 . ...
116 /// Each literal is of the form:
124 /// <typeparam name="T_Identifier">Type of expression leaf term identifiers.</typeparam>
125 internal sealed class DnfSentence
<T_Identifier
> : Sentence
<T_Identifier
, DnfClause
<T_Identifier
>>
127 // Initializes a new DNF sentence given its clauses.
128 internal DnfSentence(Set
<DnfClause
<T_Identifier
>> clauses
)
129 : base(clauses
, ExprType
.Or
)
135 /// Represents a sentence in conjunctive normal form, e.g.:
137 /// Clause1 . Clause2 . ...
139 /// Where each DNF clause is of the form:
141 /// Literal1 + Literal2 + ...
143 /// Each literal is of the form:
151 /// <typeparam name="T_Identifier">Type of expression leaf term identifiers.</typeparam>
152 internal sealed class CnfSentence
<T_Identifier
> : Sentence
<T_Identifier
, CnfClause
<T_Identifier
>>
154 // Initializes a new CNF sentence given its clauses.
155 internal CnfSentence(Set
<CnfClause
<T_Identifier
>> clauses
)
156 : base(clauses
, ExprType
.And
)