BoolStuff 0.1
|
00001 /* $Id: BoolExpr.h,v 1.19 2008/10/08 04:19:32 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 00054 template <class T> 00055 class BoolExpr 00056 { 00057 public: 00061 enum Type 00062 { 00065 VALUE, 00066 00069 AND, 00070 00073 OR, 00074 00077 NOT 00078 }; 00079 00088 BoolExpr(const T &initValue = T()); 00089 00106 BoolExpr(Type t, BoolExpr *l, BoolExpr *r); 00107 00114 ~BoolExpr(); 00115 00117 Type getType() const; 00118 00120 const BoolExpr *getLeft() const; 00121 00128 BoolExpr *getLeft(); 00129 00131 const BoolExpr *getRight() const; 00132 00139 BoolExpr *getRight(); 00140 00146 const T &getValue() const; 00147 00153 T &getValue(); 00154 00159 void setType(Type t); 00160 00167 void setLeft(BoolExpr *subtree); 00168 00175 void setRight(BoolExpr *subtree); 00176 00183 void setValue(const T &v); 00184 00196 static BoolExpr *cloneTree(const BoolExpr *root); 00197 00220 static BoolExpr *getDisjunctiveNormalForm(BoolExpr *root); 00221 00225 static BoolExpr *getRawDNF(BoolExpr *root); 00226 00231 bool isDisjunctiveNormalForm() const; 00232 00266 template <class OutputIter> 00267 OutputIter getDNFTermRoots(OutputIter dest) const; 00268 00289 void getTreeVariables(std::set<T> &positives, std::set<T> &negatives) const; 00290 00298 bool isDNFTermUseful() const; 00299 00311 void print(std::ostream &out) const; 00312 00321 std::string print() const; 00322 00323 private: 00324 Type type; 00325 T value; 00326 BoolExpr *left; 00327 BoolExpr *right; 00328 00329 friend class BoolExprParser; 00330 00331 static void simplifyXAndXTerms(std::vector<BoolExpr<T> *> &terms); 00332 static void destroyDNFOrNodes(BoolExpr<T> *root); 00333 static BoolExpr<T> *joinTreesWithOrNodes( 00334 const std::vector<BoolExpr<T> *> &trees); 00335 bool isDNFTermUseful(const std::set<T> &positives, 00336 const std::set<T> &negatives) const; 00337 static BoolExpr<T> *negateDNF(BoolExpr<T> *root); 00338 }; 00339 00340 00341 template <class T> 00342 inline 00343 std::ostream & 00344 operator << (std::ostream &out, const BoolExpr<T> *root) 00345 /* 00346 Prints nothing if 'root' is NULL. 00347 */ 00348 { 00349 if (root != NULL) 00350 root->print(out); 00351 return out; 00352 } 00353 00354 00355 #include <boolstuff/BoolExpr.cpp> 00356 00357 00358 } // namespace boolstuff 00359 00360 #endif /* _H_BoolExpr */