include/dai/varset.h

   1 /*  Copyright (C) 2006-2008  Joris Mooij  [j dot mooij at science dot ru dot nl]
   2     Radboud University Nijmegen, The Netherlands
   3
   4     This file is part of libDAI.
   5
   6     libDAI is free software; you can redistribute it and/or modify
   7     it under the terms of the GNU General Public License as published by
   8     the Free Software Foundation; either version 2 of the License, or
   9     (at your option) any later version.
  10
  11     libDAI is distributed in the hope that it will be useful,
  12     but WITHOUT ANY WARRANTY; without even the implied warranty of
  13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14     GNU General Public License for more details.
  15
  16     You should have received a copy of the GNU General Public License
  17     along with libDAI; if not, write to the Free Software
  18     Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  19 */
  20
  21
  22 #ifndef __defined_libdai_varset_h
  23 #define __defined_libdai_varset_h
  24
  25
  26 #include <set>
  27 #include <algorithm>
  28 #include <iostream>
  29 #include <cassert>
  30 #include <dai/var.h>
  31
  32
  33 namespace dai {
  34
  35
  36 /// VarSet represents a set of variables and is a descendant of set<Var>.
  37 /// In addition, it provides an easy interface for set-theoretic operations
  38 /// by operator overloading.
  39 class VarSet : private std::set<Var> {
  40     protected:
  41         /// Product of number of states of all contained variables
  42         size_t _statespace;
  43
  44         /// Check whether ns is a subset
  45         bool includes( const VarSet& ns ) const {
  46             return std::includes( begin(), end(), ns.begin(), ns.end() );
  47         }
  48
  49         /// Calculate statespace
  50         size_t calcStateSpace() {
  51             _statespace = 1;
  52             for( const_iterator i = begin(); i != end(); ++i )
  53                 _statespace *= i->states();
  54             return _statespace;
  55         }
  56
  57
  58     public:
  59         /// Default constructor
  60         VarSet() : _statespace(0) {};
  61
  62         /// Construct a VarSet with one variable
  63         VarSet( const Var &n ) : _statespace( n.states() ) {
  64             insert( n );
  65         }
  66
  67         /// Construct a VarSet with two variables
  68         VarSet( const Var &n1, const Var &n2 ) {
  69             insert( n1 );
  70             insert( n2 );
  71             calcStateSpace();
  72         }
  73
  74         /// Construct from a set<Var>
  75         VarSet( const std::set<Var> &ns ) {
  76             std::set<Var>::operator=( ns );
  77             calcStateSpace();
  78         }
  79
  80         /// Copy constructor
  81         VarSet( const VarSet &x ) : std::set<Var>( x ), _statespace( x._statespace ) {}
  82
  83         /// Assignment operator
  84         VarSet & operator=( const VarSet &x ) {
  85             if( this != &x ) {
  86                 std::set<Var>::operator=( x );
  87                 _statespace = x._statespace;
  88             }
  89             return *this;
  90         }
  91
  92
  93         /// Return statespace, i.e. the product of the number of states of each variable
  94         size_t stateSpace() const {
  95 #ifdef DEBUG
  96             size_t x = 1;
  97             for( const_iterator i = begin(); i != end(); ++i )
  98                 x *= i->states();
  99             assert( x == _statespace );
 100 #endif
 101             return _statespace;
 102         }
 103
 104
 105         /// Erase one variable
 106         VarSet& operator/= (const Var& n) {
 107             erase( n );
 108             calcStateSpace();
 109             return *this;
 110         }
 111
 112         /// Add one variable
 113         VarSet& operator|= (const Var& n) {
 114             insert( n );
 115             calcStateSpace();
 116             return *this;
 117         }
 118
 119         /// Setminus operator (result contains all variables except those in ns)
 120         VarSet operator/ (const VarSet& ns) const {
 121             VarSet res;
 122             std::set_difference( begin(), end(), ns.begin(), ns.end(), inserter( res, res.begin() ) );
 123             res.calcStateSpace();
 124             return res;
 125         }
 126
 127         /// Set-union operator (result contains all variables plus those in ns)
 128         VarSet operator| (const VarSet& ns) const {
 129             VarSet res;
 130             std::set_union( begin(), end(), ns.begin(), ns.end(), inserter( res, res.begin() ) );
 131             res.calcStateSpace();
 132             return res;
 133         }
 134
 135         /// Set-intersection operator (result contains all variables that are also contained in ns)
 136         VarSet operator& (const VarSet& ns) const {
 137             VarSet res;
 138             std::set_intersection( begin(), end(), ns.begin(), ns.end(), inserter( res, res.begin() ) );
 139             res.calcStateSpace();
 140             return res;
 141         }
 142
 143         /// Erases from *this all variables in ns
 144         VarSet& operator/= (const VarSet& ns) {
 145             return (*this = (*this / ns));
 146         }
 147
 148         /// Adds to *this all variables in ns
 149         VarSet& operator|= (const VarSet& ns) {
 150             return (*this = (*this | ns));
 151         }
 152
 153         /// Erases from *this all variables not in ns
 154         VarSet& operator&= (const VarSet& ns) {
 155             return (*this = (*this & ns));
 156         }
 157
 158
 159         /// Returns false if both *this and ns are empty
 160         bool operator|| (const VarSet& ns) const {
 161             return !( this->empty() && ns.empty() );
 162         }
 163
 164         /// Returns true if *this and ns contain common variables
 165         bool operator&& (const VarSet& ns) const {
 166             return !( (*this & ns).empty() );
 167         }
 168
 169         /// Returns true if *this is a subset of ns
 170         bool operator<< (const VarSet& ns) const {
 171             return ns.includes( *this );
 172         }
 173
 174         /// Returns true if ns is a subset of *this
 175         bool operator>> (const VarSet& ns) const {
 176             return includes( ns );
 177         }
 178
 179         /// Returns true if *this contains the variable n
 180         bool operator&& (const Var& n) const {
 181             return( find( n ) == end() ? false : true );
 182         }
 183
 184
 185         /// Sends a VarSet to an output stream
 186         friend std::ostream& operator<< (std::ostream & os, const VarSet& ns) {
 187             for( VarSet::const_iterator n = ns.begin(); n != ns.end(); n++)
 188                 os << *n;
 189             return( os );
 190         }
 191
 192
 193 /*      The following makes part of the public interface of set<Var> available.
 194  *      It is important to note that insert functions have to be overloaded,
 195  *      because they have to recalculate the statespace. A different approach
 196  *      would be to publicly inherit from set<Var> and only overload the insert
 197  *      methods.
 198  */
 199
 200         // Additional interface from set<Var> that has to be provided
 201         using std::set<Var>::const_iterator;
 202         using std::set<Var>::iterator;
 203         using std::set<Var>::const_reference;
 204         using std::set<Var>::begin;
 205         using std::set<Var>::end;
 206         using std::set<Var>::size;
 207         using std::set<Var>::empty;
 208
 209         /// Copy of set<Var>::insert which additionally calculates the new statespace
 210         std::pair<iterator, bool> insert( const Var& x ) {
 211             std::pair<iterator, bool> result = std::set<Var>::insert( x );
 212             calcStateSpace();
 213             return result;
 214         }
 215
 216         /// Copy of set<Var>::insert which additionally calculates the new statespace
 217         iterator insert( iterator pos, const value_type& x ) {
 218             iterator result = std::set<Var>::insert( pos, x );
 219             calcStateSpace();
 220             return result;
 221         }
 222
 223         /// Test for equality (ignore _statespace member)
 224         friend bool operator==( const VarSet &a, const VarSet &b ) {
 225             return operator==( (std::set<Var>)a, (std::set<Var>)b );
 226         }
 227
 228         /// Test for inequality (ignore _statespace member)
 229         friend bool operator!=( const VarSet &a, const VarSet &b ) {
 230             return operator!=( (std::set<Var>)a, (std::set<Var>)b );
 231         }
 232
 233         friend bool operator<( const VarSet &a, const VarSet &b ) {
 234             return operator<( (std::set<Var>)a, (std::set<Var>)b );
 235         }
 236 };
 237
 238
 239 /// For two Vars n1 and n2, the expression n1 | n2 gives the Varset containing n1 and n2
 240 inline VarSet operator| (const Var& n1, const Var& n2) {
 241     return( VarSet(n1, n2) );
 242 }
 243
 244
 245 } // end of namespace dai
 246
 247
 248 #endif