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 <vector>
  28 #include <map>
  29 #include <algorithm>
  30 #include <iostream>
  31 #include <cassert>
  32 #include <dai/var.h>
  33 #include <dai/util.h>
  34
  35
  36 namespace dai {
  37
  38
  39 /// A small_set<T> represents a set, optimized for a small number of elements.
  40 /** For sets consisting of a small number of elements, an implementation using
  41  *  an ordered std::vector<T> is faster than an implementation using std::set<T>.
  42  *  The elements should be less-than-comparable.
  43  */
  44 template <typename T>
  45 class small_set {
  46     private:
  47         /// The elements in this set
  48         std::vector<T> _elements;
  49
  50     public:
  51         /// Default constructor
  52         small_set() : _elements() {}
  53
  54         /// Construct a small_set with one element
  55         small_set( const T &n ) : _elements() {
  56             _elements.push_back( n );
  57         }
  58
  59         /// Construct a small_set with two elements
  60         small_set( const T &n1, const T &n2 ) {
  61             if( n1 < n2 ) {
  62                 _elements.push_back( n1 );
  63                 _elements.push_back( n2 );
  64             } else if( n2 < n1 ) {
  65                 _elements.push_back( n2 );
  66                 _elements.push_back( n1 );
  67             } else
  68                 _elements.push_back( n1 );
  69         }
  70
  71         /// Construct a small_set from a range of iterators.
  72         /** The value_type of the Iterator should be T.
  73          *  For efficiency, the number of elements can be
  74          *  speficied by sizeHint.
  75          */
  76         template <typename Iterator>
  77         small_set( Iterator begin, Iterator end, size_t sizeHint=0 ) {
  78             _elements.reserve( sizeHint );
  79             _elements.insert( _elements.begin(), begin, end );
  80             std::sort( _elements.begin(), _elements.end() );
  81             typename std::vector<T>::iterator new_end = std::unique( _elements.begin(), _elements.end() );
  82             _elements.erase( new_end, _elements.end() );
  83         }
  84
  85         /// Copy constructor
  86         small_set( const small_set &x ) : _elements( x._elements ) {}
  87
  88         /// Assignment operator
  89         small_set & operator=( const small_set &x ) {
  90             if( this != &x ) {
  91                 _elements = x._elements;
  92             }
  93             return *this;
  94         }
  95
  96         /// Setminus operator (result contains all elements in *this, except those in ns)
  97         small_set operator/ ( const small_set& ns ) const {
  98             small_set res;
  99             std::set_difference( _elements.begin(), _elements.end(), ns._elements.begin(), ns._elements.end(), inserter( res._elements, res._elements.begin() ) );
 100             return res;
 101         }
 102
 103         /// Set-union operator (result contains all elements in *this, plus those in ns)
 104         small_set operator| ( const small_set& ns ) const {
 105             small_set res;
 106             std::set_union( _elements.begin(), _elements.end(), ns._elements.begin(), ns._elements.end(), inserter( res._elements, res._elements.begin() ) );
 107             return res;
 108         }
 109
 110         /// Set-intersection operator (result contains all elements in *this that are also contained in ns)
 111         small_set operator& ( const small_set& ns ) const {
 112             small_set res;
 113             std::set_intersection( _elements.begin(), _elements.end(), ns._elements.begin(), ns._elements.end(), inserter( res._elements, res._elements.begin() ) );
 114             return res;
 115         }
 116
 117         /// Erases from *this all elements in ns
 118         small_set& operator/= ( const small_set& ns ) {
 119             return (*this = (*this / ns));
 120         }
 121
 122         /// Erase one element
 123         small_set& operator/= ( const T& n ) {
 124             typename std::vector<T>::iterator pos = lower_bound( _elements.begin(), _elements.end(), n );
 125             if( pos != _elements.end() )
 126                 if( *pos == n ) // found element, delete it
 127                     _elements.erase( pos );
 128             return *this;
 129         }
 130
 131         /// Adds to *this all elements in ns
 132         small_set& operator|= ( const small_set& ns ) {
 133             return( *this = (*this | ns) );
 134         }
 135
 136         /// Add one element
 137         small_set& operator|= ( const T& n ) {
 138             typename std::vector<T>::iterator pos = lower_bound( _elements.begin(), _elements.end(), n );
 139             if( pos == _elements.end() || *pos != n ) // insert it
 140                 _elements.insert( pos, n );
 141             return *this;
 142         }
 143
 144         /// Erases from *this all elements not in ns
 145         small_set& operator&= ( const small_set& ns ) {
 146             return (*this = (*this & ns));
 147         }
 148
 149         /// Returns true if *this is a subset of ns
 150         bool operator<< ( const small_set& ns ) const {
 151             return std::includes( ns._elements.begin(), ns._elements.end(), _elements.begin(), _elements.end() );
 152         }
 153
 154         /// Returns true if ns is a subset of *this
 155         bool operator>> ( const small_set& ns ) const {
 156             return std::includes( _elements.begin(), _elements.end(), ns._elements.begin(), ns._elements.end() );
 157         }
 158
 159         /// Returns true if *this and ns contain common elements
 160         bool intersects( const small_set& ns ) const {
 161             return( (*this & ns).size() > 0 );
 162         }
 163
 164         /// Returns true if *this contains the element n
 165         bool contains( const T& n ) const {
 166             return std::binary_search( _elements.begin(), _elements.end(), n );
 167         }
 168
 169         /// Constant iterator over the elements
 170         typedef typename std::vector<T>::const_iterator const_iterator;
 171         /// Iterator over the elements
 172         typedef typename std::vector<T>::iterator iterator;
 173         /// Constant reverse iterator over the elements
 174         typedef typename std::vector<T>::const_reverse_iterator const_reverse_iterator;
 175         /// Reverse iterator over the elements
 176         typedef typename std::vector<T>::reverse_iterator reverse_iterator;
 177
 178         /// Returns iterator that points to the first element
 179         iterator begin() { return _elements.begin(); }
 180         /// Returns constant iterator that points to the first element
 181         const_iterator begin() const { return _elements.begin(); }
 182
 183         /// Returns iterator that points beyond the last element
 184         iterator end() { return _elements.end(); }
 185         /// Returns constant iterator that points beyond the last element
 186         const_iterator end() const { return _elements.end(); }
 187
 188         /// Returns reverse iterator that points to the last element
 189         reverse_iterator rbegin() { return _elements.rbegin(); }
 190         /// Returns constant reverse iterator that points to the last element
 191         const_reverse_iterator rbegin() const { return _elements.rbegin(); }
 192
 193         /// Returns reverse iterator that points beyond the first element
 194         reverse_iterator rend() { return _elements.rend(); }
 195         /// Returns constant reverse iterator that points beyond the first element
 196         const_reverse_iterator rend() const { return _elements.rend(); }
 197
 198         /// Returns number of elements
 199         typename std::vector<T>::size_type size() const { return _elements.size(); }
 200
 201         /// Returns whether the small_set is empty
 202         bool empty() const { return _elements.size() == 0; }
 203
 204         /// Test for equality of element labels
 205         friend bool operator==( const small_set &a, const small_set &b ) {
 206             return (a._elements == b._elements);
 207         }
 208
 209         /// Test for inequality of element labels
 210         friend bool operator!=( const small_set &a, const small_set &b ) {
 211             return !(a._elements == b._elements);
 212         }
 213
 214         /// Lexicographical comparison of element labels
 215         friend bool operator<( const small_set &a, const small_set &b ) {
 216             return a._elements < b._elements;
 217         }
 218 };
 219
 220
 221 /// A VarSet represents a set of variables.
 222 /**
 223  *  It is implemented as an ordered std::vector<Var> for efficiency reasons
 224  *  (indeed, it was found that a std::set<Var> usually has more overhead).
 225  *  In addition, it provides an interface for common set-theoretic operations.
 226  */
 227 typedef small_set<Var> VarSet;
 228
 229
 230 /// For two Vars n1 and n2, the expression n1 | n2 gives the Varset containing n1 and n2
 231 inline VarSet operator| (const Var& n1, const Var& n2) {
 232     return( VarSet(n1, n2) );
 233 }
 234
 235
 236 /// Calculates the product of number of states of all variables in vars
 237 size_t nrStates( const VarSet &vars );
 238
 239
 240 /// calcState calculates the linear index of vars that corresponds
 241 /// to the states of the variables given in states, implicitly assuming
 242 /// states[m] = 0 for all m in this VarSet which are not in states.
 243 size_t calcState( const VarSet &vars, const std::map<Var, size_t> &states );
 244
 245
 246 /// Sends a VarSet to an output stream
 247 std::ostream& operator<< (std::ostream &os, const VarSet& ns);
 248
 249
 250 } // end of namespace dai
 251
 252
 253 #endif