BoolStuff 0.1

BoolExpr.h

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 */

Generated for BoolStuff by doxygen 1.7.3