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

   1 //---------------------------------------------------------------------
   2 // <copyright file="Sentence.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.Globalization;
  14 using System.Collections.ObjectModel;
  15 using System.Diagnostics;
  16 using System.Linq;
  17
  18 namespace System.Data.Common.Utils.Boolean
  19 {
  20     /// <summary>
  21     /// Abstract base class for nodes in normal form expressions, e.g. Conjunctive Normal Form
  22     /// sentences.
  23     /// </summary>
  24     /// <typeparam name="T_Identifier">Type of expression leaf term identifiers.</typeparam>
  25     internal abstract class NormalFormNode<T_Identifier>
  26     {
  27         private readonly BoolExpr<T_Identifier> _expr;
  28
  29         /// <summary>
  30         /// Initialize a new normal form node representing the given expression. Caller must
  31         /// ensure the expression is logically equivalent to the node.
  32         /// </summary>
  33         /// <param name="expr">Expression logically equivalent to this node.</param>
  34         protected NormalFormNode(BoolExpr<T_Identifier> expr) { _expr = expr.Simplify(); }
  35
  36         /// <summary>
  37         /// Gets an expression that is logically equivalent to this node.
  38         /// </summary>
  39         internal BoolExpr<T_Identifier> Expr { get { return _expr; } }
  40
  41         /// <summary>
  42         /// Utility method for delegation that return the expression corresponding to a given
  43         /// normal form node.
  44         /// </summary>
  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>
  50         {
  51             return node._expr;
  52         }
  53     }
  54
  55     /// <summary>
  56     /// Abstract base class for normal form sentences (CNF and DNF)
  57     /// </summary>
  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>
  62     {
  63         private readonly Set<T_Clause> _clauses;
  64
  65         /// <summary>
  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.
  69         /// </summary>
  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))
  74         {
  75             _clauses = clauses.AsReadOnly();
  76         }
  77
  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)
  81         {
  82             bool isAnd = ExprType.And == treeType;
  83             Debug.Assert(isAnd || ExprType.Or == treeType);
  84
  85             IEnumerable<BoolExpr<T_Identifier>> clauseExpressions =
  86                 clauses.Select(new Func<T_Clause, BoolExpr<T_Identifier>>(ExprSelector));
  87
  88             if (isAnd)
  89             {
  90                 return new AndExpr<T_Identifier>(clauseExpressions);
  91             }
  92             else
  93             {
  94                 return new OrExpr<T_Identifier>(clauseExpressions);
  95             }
  96         }
  97
  98         public override string ToString()
  99         {
 100             StringBuilder builder = new StringBuilder();
 101             builder.Append("Sentence{");
 102             builder.Append(_clauses);
 103             return builder.Append("}").ToString();
 104         }
 105     }
 106
 107     /// <summary>
 108     /// Represents a sentence in disjunctive normal form, e.g.:
 109     ///
 110     ///     Clause1 + Clause2 . ...
 111     ///
 112     /// Where each DNF clause is of the form:
 113     ///
 114     ///     Literal1 . Literal2 . ...
 115     ///
 116     /// Each literal is of the form:
 117     ///
 118     ///     Term
 119     ///
 120     /// or
 121     ///
 122     ///     !Term
 123     /// </summary>
 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>>
 126     {
 127         // Initializes a new DNF sentence given its clauses.
 128         internal DnfSentence(Set<DnfClause<T_Identifier>> clauses)
 129             : base(clauses, ExprType.Or)
 130         {
 131         }
 132     }
 133
 134     /// <summary>
 135     /// Represents a sentence in conjunctive normal form, e.g.:
 136     ///
 137     ///     Clause1 . Clause2 . ...
 138     ///
 139     /// Where each DNF clause is of the form:
 140     ///
 141     ///     Literal1 + Literal2 + ...
 142     ///
 143     /// Each literal is of the form:
 144     ///
 145     ///     Term
 146     ///
 147     /// or
 148     ///
 149     ///     !Term
 150     /// </summary>
 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>>
 153     {
 154         // Initializes a new CNF sentence given its clauses.
 155         internal CnfSentence(Set<CnfClause<T_Identifier>> clauses)
 156             : base(clauses, ExprType.And)
 157         {
 158         }
 159     }
 160 }