include/dai/varset.h

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