00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023 #ifndef _H_BoolExpr
00024 #define _H_BoolExpr
00025
00026 #include <iostream>
00027 #include <string>
00028 #include <vector>
00029 #include <set>
00030 #include <algorithm>
00031 #include <cassert>
00032 #include <sstream>
00033
00034
00038 namespace boolstuff {
00039
00040
00051 template <class T>
00052 class BoolExpr
00053 {
00054 public:
00060 enum Type { VALUE, AND, OR, NOT };
00061
00073 BoolExpr(const T &initValue = T());
00074
00091 BoolExpr(Type t, BoolExpr *l, BoolExpr *r);
00092
00099 ~BoolExpr();
00100
00102 Type getType() const;
00103
00105 const BoolExpr *getLeft() const;
00106
00113 BoolExpr *getLeft();
00114
00116 const BoolExpr *getRight() const;
00117
00124 BoolExpr *getRight();
00125
00131 const T &getValue() const;
00132
00138 T &getValue();
00139
00144 void setType(Type t);
00145
00152 void setLeft(BoolExpr *subtree);
00153
00160 void setRight(BoolExpr *subtree);
00161
00168 void setValue(const T &v);
00169
00181 static BoolExpr *cloneTree(const BoolExpr *root);
00182
00205 static BoolExpr *getDisjunctiveNormalForm(BoolExpr *root);
00206
00210 static BoolExpr *getRawDNF(BoolExpr *root);
00211
00216 bool isDisjunctiveNormalForm() const;
00217
00251 template <class OutputIter>
00252 OutputIter getDNFTermRoots(OutputIter dest) const;
00253
00274 void getTreeVariables(std::set<T> &positives, std::set<T> &negatives) const;
00275
00283 bool isDNFTermUseful() const;
00284
00296 void print(std::ostream &out) const;
00297
00298
00299
00300
00301
00302
00303
00304
00305
00306 std::string print() const;
00307
00308 private:
00309 Type type;
00310 T value;
00311 BoolExpr *left;
00312 BoolExpr *right;
00313
00314 friend class BoolExprParser;
00315
00316 static void destroyDNFOrNodes(BoolExpr<T> *root);
00317 static BoolExpr<T> *joinTreesWithOrNodes(
00318 const std::vector<BoolExpr<T> *> &trees);
00319 bool isDNFTermUseful(const std::set<T> &positives,
00320 const std::set<T> &negatives) const;
00321 static BoolExpr<T> *negateDNF(BoolExpr<T> *root);
00322 };
00323
00324
00325 template <class T>
00326 inline
00327 std::ostream &
00328 operator << (std::ostream &out, const BoolExpr<T> *root)
00329
00330
00331
00332 {
00333 if (root != NULL)
00334 root->print(out);
00335 return out;
00336 }
00337
00338
00339 #include <boolstuff/BoolExpr.cpp>
00340
00341
00342 }
00343
00344 #endif