00001 /* $Id: BoolExpr.h,v 1.17 2006/02/05 03:26:11 sarrazip Exp $ 00002 BoolExpr.h - Boolean expression binary tree node 00003 00004 boolstuff - Disjunctive Normal Form boolean expression library 00005 Copyright (C) 2002-2005 Pierre Sarrazin <http://sarrazip.com/> 00006 00007 This program is free software; you can redistribute it and/or 00008 modify it under the terms of the GNU General Public License 00009 as published by the Free Software Foundation; either version 2 00010 of the License, or (at your option) any later version. 00011 00012 This program is distributed in the hope that it will be useful, 00013 but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 GNU General Public License for more details. 00016 00017 You should have received a copy of the GNU General Public License 00018 along with this program; if not, write to the Free Software 00019 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 00020 02111-1307, USA. 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 Prints the boolean expression tree rooted at this node in a string. 00300 00301 If this method is called, there must be a method 00302 of the form operator << (ostream &, const T &). 00303 00304 @returns the string representation of this tree 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 Prints nothing if 'root' is NULL. 00331 */ 00332 { 00333 if (root != NULL) 00334 root->print(out); 00335 return out; 00336 } 00337 00338 00339 #include <boolstuff/BoolExpr.cpp> 00340 00341 00342 } // namespace boolstuff 00343 00344 #endif /* _H_BoolExpr */