BoolExpr.h

Go to the documentation of this file.
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 */

Generated on Thu May 10 04:13:20 2007 for BoolStuff by  doxygen 1.5.1