Removed obsolete/deprecated stuff
[libdai.git] / include / dai / varset.h
index 30ff83e..361ef7f 100644 (file)
@@ -1,23 +1,17 @@
-/*  Copyright (C) 2006-2008  Joris Mooij  [j dot mooij at science dot ru dot nl]
-    Copyright (C) 2002  Martijn Leisink  [martijn@mbfys.kun.nl]
-    Radboud University Nijmegen, The Netherlands
-    
   This file is part of libDAI.
-
-    libDAI is free software; you can redistribute it and/or modify
-    it under the terms of the GNU General Public License as published by
-    the Free Software Foundation; either version 2 of the License, or
-    (at your option) any later version.
+/*  This file is part of libDAI - http://www.libdai.org/
+ *
+ *  libDAI is licensed under the terms of the GNU General Public License version
+ *  2, or (at your option) any later version. libDAI is distributed without any
*  warranty. See the file COPYING for more details.
+ *
+ *  Copyright (C) 2002       Martijn Leisink  [martijn@mbfys.kun.nl]
+ *  Copyright (C) 2006-2009  Joris Mooij      [joris dot mooij at libdai dot org]
+ *  Copyright (C) 2002-2007  Radboud University Nijmegen, The Netherlands
+ */
 
-    libDAI is distributed in the hope that it will be useful,
-    but WITHOUT ANY WARRANTY; without even the implied warranty of
-    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-    GNU General Public License for more details.
 
-    You should have received a copy of the GNU General Public License
-    along with libDAI; if not, write to the Free Software
-    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
-*/
+/// \file
+/// \brief Defines the VarSet class, which represents a set of random variables.
 
 
 #ifndef __defined_libdai_varset_h
 
 #include <vector>
 #include <map>
-#include <algorithm>
-#include <iostream>
-#include <cassert>
+#include <ostream>
 #include <dai/var.h>
 #include <dai/util.h>
+#include <dai/smallset.h>
 
 
 namespace dai {
 
 
-/// A small_set<T> represents a set, optimized for a small number of elements.
-/** For sets consisting of a small number of elements, an implementation using
- *  an ordered std::vector<T> is faster than an implementation using std::set<T>.
- *  The elements should be less-than-comparable.
+// Predefine for definitions of calcLinearState() and calcState()
+class VarSet;
+
+
+/// Calculates the linear index in the Cartesian product of the variables in \a vs that corresponds to a particular joint assignment of the variables, specified by \a state.
+/** \param vs Set of variables for which the linear state should be calculated;
+ *  \param state Specifies the states of some variables.
+ *  \return The linear index in the Cartesian product of the variables in \a vs
+ *  corresponding with the joint assignment specified by \a state, where variables
+ *  for which no state is specified are assumed to be in state 0.
+ *
+ *  The linear index is calculated as follows. The variables in \a vs are
+ *  ordered according to their label (in ascending order); say \a vs corresponds with
+ *  the set \f$\{x_{l(0)},x_{l(1)},\dots,x_{l(n-1)}\}\f$ with \f$l(0) < l(1) < \dots < l(n-1)\f$,
+ *  where variable \f$x_l\f$ has label \a l. Denote by \f$S_l\f$ the number of possible values
+ *  ("states") of variable \f$x_l\f$. The argument \a state corresponds
+ *  with a mapping \a s that assigns to each variable \f$x_l\f$ a state \f$s(x_l) \in \{0,1,\dots,S_l-1\}\f$,
+ *  where \f$s(x_l)=0\f$ if \f$x_l\f$ is not specified in \a state. The linear index \f$S\f$ corresponding
+ *  with \a state is now calculated by:
+ *  \f{eqnarray*}
+ *    S &:=& \sum_{i=0}^{n-1} s(x_{l(i)}) \prod_{j=0}^{i-1} S_{l(j)} \\
+ *      &= & s(x_{l(0)}) + s(x_{l(1)}) S_{l(0)} + s(x_{l(2)}) S_{l(0)} S_{l(1)} + \dots + s(x_{l(n-1)}) S_{l(0)} \cdots S_{l(n-2)}.
+ *  \f}
+ *
+ *  \note If \a vs corresponds with \f$\{x_l\}_{l\in L}\f$, and \a state specifies a state
+ *  for each variable \f$x_l\f$ for \f$l\in L\f$, calcLinearState() induces a mapping
+ *  \f$\sigma : \prod_{l\in L} X_l \to \{0,1,\dots,\prod_{l\in L} S_l-1\}\f$ that
+ *  maps a joint state to a linear index; this is the inverse of the mapping
+ *  \f$\sigma^{-1}\f$ induced by calcState().
+ *
+ *  \see calcState()
  */
-template <typename T>
-class small_set {
-    private:
-        /// The elements in this set
-        std::vector<T> _elements;
-
-    public:
-        /// Default constructor
-        small_set() : _elements() {}
-
-        /// Construct a small_set with one element
-        small_set( const T &n ) : _elements() { 
-            _elements.push_back( n );
-        }
-
-        /// Construct a small_set with two elements
-        small_set( const T &n1, const T &n2 ) { 
-            if( n1 < n2 ) {
-                _elements.push_back( n1 );
-                _elements.push_back( n2 );
-            } else if( n2 < n1 ) {
-                _elements.push_back( n2 );
-                _elements.push_back( n1 );
-            } else
-                _elements.push_back( n1 );
-        }
-
-        /// Construct a small_set from a range of iterators.
-        /** The value_type of the Iterator should be T.
-         *  For efficiency, the number of elements can be
-         *  speficied by sizeHint.
-         */
-        template <typename Iterator>
-        small_set( Iterator begin, Iterator end, size_t sizeHint=0 ) {
-            _elements.reserve( sizeHint );
-            _elements.insert( _elements.begin(), begin, end );
-            std::sort( _elements.begin(), _elements.end() );
-            typename std::vector<T>::iterator new_end = std::unique( _elements.begin(), _elements.end() );
-            _elements.erase( new_end, _elements.end() );
-        }
-
-        /// Copy constructor
-        small_set( const small_set &x ) : _elements( x._elements ) {}
-
-        /// Assignment operator
-        small_set & operator=( const small_set &x ) {
-            if( this != &x ) {
-                _elements = x._elements;
-            }
-            return *this;
-        }
-        
-        /// Setminus operator (result contains all elements in *this, except those in ns)
-        small_set operator/ ( const small_set& ns ) const {
-            small_set res;
-            std::set_difference( _elements.begin(), _elements.end(), ns._elements.begin(), ns._elements.end(), inserter( res._elements, res._elements.begin() ) );
-            return res;
-        }
-
-        /// Set-union operator (result contains all elements in *this, plus those in ns)
-        small_set operator| ( const small_set& ns ) const {
-            small_set res;
-            std::set_union( _elements.begin(), _elements.end(), ns._elements.begin(), ns._elements.end(), inserter( res._elements, res._elements.begin() ) );
-            return res;
-        }
-
-        /// Set-intersection operator (result contains all elements in *this that are also contained in ns)
-        small_set operator& ( const small_set& ns ) const {
-            small_set res;
-            std::set_intersection( _elements.begin(), _elements.end(), ns._elements.begin(), ns._elements.end(), inserter( res._elements, res._elements.begin() ) );
-            return res;
-        }
-        
-        /// Erases from *this all elements in ns
-        small_set& operator/= ( const small_set& ns ) {
-            return (*this = (*this / ns));
-        }
-
-        /// Erase one element
-        small_set& operator/= ( const T& n ) { 
-            typename std::vector<T>::iterator pos = lower_bound( _elements.begin(), _elements.end(), n );
-            if( pos != _elements.end() )
-                if( *pos == n ) // found element, delete it
-                    _elements.erase( pos ); 
-            return *this; 
-        }
-
-        /// Adds to *this all elements in ns
-        small_set& operator|= ( const small_set& ns ) {
-            return( *this = (*this | ns) );
-        }
-
-        /// Add one element
-        small_set& operator|= ( const T& n ) {
-            typename std::vector<T>::iterator pos = lower_bound( _elements.begin(), _elements.end(), n );
-            if( pos == _elements.end() || *pos != n ) // insert it
-                _elements.insert( pos, n );
-            return *this;
-        }
-
-        /// Erases from *this all elements not in ns
-        small_set& operator&= ( const small_set& ns ) { 
-            return (*this = (*this & ns));
-        }
-
-        /// Returns true if *this is a subset of ns
-        bool operator<< ( const small_set& ns ) const { 
-            return std::includes( ns._elements.begin(), ns._elements.end(), _elements.begin(), _elements.end() );
-        }
-
-        /// Returns true if ns is a subset of *this
-        bool operator>> ( const small_set& ns ) const { 
-            return std::includes( _elements.begin(), _elements.end(), ns._elements.begin(), ns._elements.end() );
-        }
-
-        /// Returns true if *this and ns contain common elements
-        bool intersects( const small_set& ns ) const { 
-            return( (*this & ns).size() > 0 ); 
-        }
-
-        /// Returns true if *this contains the element n
-        bool contains( const T& n ) const { 
-            return std::binary_search( _elements.begin(), _elements.end(), n );
-        }
-
-        /// Constant iterator over the elements
-        typedef typename std::vector<T>::const_iterator const_iterator;
-        /// Iterator over the elements
-        typedef typename std::vector<T>::iterator iterator;
-        /// Constant reverse iterator over the elements
-        typedef typename std::vector<T>::const_reverse_iterator const_reverse_iterator;
-        /// Reverse iterator over the elements
-        typedef typename std::vector<T>::reverse_iterator reverse_iterator;
-        
-        /// Returns iterator that points to the first element
-        iterator begin() { return _elements.begin(); }
-        /// Returns constant iterator that points to the first element
-        const_iterator begin() const { return _elements.begin(); }
-
-        /// Returns iterator that points beyond the last element
-        iterator end() { return _elements.end(); }
-        /// Returns constant iterator that points beyond the last element
-        const_iterator end() const { return _elements.end(); }
-
-        /// Returns reverse iterator that points to the last element
-        reverse_iterator rbegin() { return _elements.rbegin(); }
-        /// Returns constant reverse iterator that points to the last element
-        const_reverse_iterator rbegin() const { return _elements.rbegin(); }
-
-        /// Returns reverse iterator that points beyond the first element
-        reverse_iterator rend() { return _elements.rend(); }
-        /// Returns constant reverse iterator that points beyond the first element
-        const_reverse_iterator rend() const { return _elements.rend(); }
-
-        /// Returns number of elements
-        typename std::vector<T>::size_type size() const { return _elements.size(); }
-
-        /// Returns whether the small_set is empty
-        bool empty() const { return _elements.size() == 0; }
-
-        /// Test for equality of element labels
-        friend bool operator==( const small_set &a, const small_set &b ) {
-            return (a._elements == b._elements);
-        }
-
-        /// Test for inequality of element labels
-        friend bool operator!=( const small_set &a, const small_set &b ) {
-            return !(a._elements == b._elements);
-        }
-
-        /// Lexicographical comparison of element labels
-        friend bool operator<( const small_set &a, const small_set &b ) {
-            return a._elements < b._elements;
-        }
-};
-
-
-/// A VarSet represents a set of variables.
-/**
- *  It is implemented as an ordered std::vector<Var> for efficiency reasons
- *  (indeed, it was found that a std::set<Var> usually has more overhead). 
- *  In addition, it provides an interface for common set-theoretic operations.
+size_t calcLinearState( const VarSet &vs, const std::map<Var, size_t> &state );
+
+
+/// Calculates the joint assignment of the variables in \a vs corresponding to the linear index \a linearState.
+/** \param vs Set of variables to which \a linearState refers
+ *  \param linearState should be smaller than vs.nrStates().
+ *  \return A mapping \f$s\f$ that maps each Var \f$x_l\f$ in \a vs to its state \f$s(x_l)\f$, as specified by \a linearState.
+ *
+ *  The variables in \a vs are ordered according to their label (in ascending order); say \a vs corresponds with
+ *  the set \f$\{x_{l(0)},x_{l(1)},\dots,x_{l(n-1)}\}\f$ with \f$l(0) < l(1) < \dots < l(n-1)\f$,
+ *  where variable \f$x_l\f$ has label \a l. Denote by \f$S_l\f$ the number of possible values
+ *  ("states") of variable \f$x_l\f$ with label \a l.
+ *  The mapping \f$s\f$ returned by this function is defined as:
+ *  \f{eqnarray*}
+ *    s(x_{l(i)}) = \left\lfloor\frac{S \mbox { mod } \prod_{j=0}^{i} S_{l(j)}}{\prod_{j=0}^{i-1} S_{l(j)}}\right\rfloor \qquad \mbox{for all $i=0,\dots,n-1$}.
+ *  \f}
+ *  where \f$S\f$ denotes the value of \a linearState.
+ *
+ *  \note If \a vs corresponds with \f$\{x_l\}_{l\in L}\f$, calcState() induces a mapping
+ *  \f$\sigma^{-1} : \{0,1,\dots,\prod_{l\in L} S_l-1\} \to \prod_{l\in L} X_l\f$ that
+ *  maps a linear index to a joint state; this is the inverse of the mapping \f$\sigma\f$
+ *  induced by calcLinearState().
+ *
+ *  \see calcLinearState()
  */
-typedef small_set<Var> VarSet;
+std::map<Var, size_t> calcState( const VarSet &vs, size_t linearState );
 
 
-/// For two Vars n1 and n2, the expression n1 | n2 gives the Varset containing n1 and n2
-inline VarSet operator| (const Var& n1, const Var& n2) {
-    return( VarSet(n1, n2) );
-}
+/// Represents a set of variables.
+/** \note A VarSet is implemented using a SmallSet<Var> instead
+ *  of the more natural std::set<Var> because of efficiency reasons.
+ *  That is, internally, the variables in the set are sorted ascendingly
+ *  according to their labels.
+ */
+class VarSet : public SmallSet<Var> {
+    public:
+    /// \name Constructors and destructors
+    //@{
+        /// Default constructor (constructs an empty set)
+        VarSet() : SmallSet<Var>() {}
 
+        /// Construct from \link SmallSet \endlink<\link Var \endlink> \a x
+        VarSet( const SmallSet<Var> &x ) : SmallSet<Var>(x) {}
 
-/// Calculates the product of number of states of all variables in vars
-size_t nrStates( const VarSet &vars );
+        /// Construct a VarSet with one element, \a v
+        VarSet( const Var &v ) : SmallSet<Var>(v) {}
 
+        /// Construct a VarSet with two elements, \a v1 and \a v2
+        VarSet( const Var &v1, const Var &v2 ) : SmallSet<Var>(v1,v2) {}
 
-/// calcState calculates the linear index of vars that corresponds
-/// to the states of the variables given in states, implicitly assuming
-/// states[m] = 0 for all m in this VarSet which are not in states.
-size_t calcState( const VarSet &vars, const std::map<Var, size_t> &states );
+        /// Construct a VarSet from the range between \a begin and \a end.
+        /** \tparam VarIterator Iterates over instances of type Var.
+         *  \param begin Points to first Var to be added.
+         *  \param end Points just beyond last Var to be added.
+         *  \param sizeHint For efficiency, the number of elements can be speficied by \a sizeHint.
+         */
+        template <typename VarIterator>
+        VarSet( VarIterator begin, VarIterator end, size_t sizeHint=0 ) : SmallSet<Var>(begin,end,sizeHint) {}
+    //@}
+
+    /// \name Queries
+    //@{
+        /// Calculates the number of states of this VarSet, which is simply the number of possible joint states of the variables in \c *this.
+        /** The number of states of the Cartesian product of the variables in this VarSet
+         *  is simply the product of the number of states of each variable in this VarSet.
+         *  If \c *this corresponds with the set \f$\{x_l\}_{l\in L}\f$,
+         *  where variable \f$x_l\f$ has label \f$l\f$, and denoting by \f$S_l\f$ the
+         *  number of possible values ("states") of variable \f$x_l\f$, the number of
+         *  joint configurations of the variables in \f$\{x_l\}_{l\in L}\f$ is given by \f$\prod_{l\in L} S_l\f$.
+         */
+        size_t nrStates() const {
+            size_t states = 1;
+            for( VarSet::const_iterator n = begin(); n != end(); n++ )
+                states *= n->states();
+            return states;
+        }
+    //@}
+
+    /// \name Input and output
+    //@{
+        /// Writes a VarSet to an output stream
+        friend std::ostream& operator<<( std::ostream &os, const VarSet &vs )  {
+            os << "{";
+            for( VarSet::const_iterator v = vs.begin(); v != vs.end(); v++ )
+                os << (v != vs.begin() ? ", " : "") << *v;
+            os << "}";
+            return( os );
+        }
+    //@}
+};
 
 
-/// Sends a VarSet to an output stream
-std::ostream& operator<< (std::ostream &os, const VarSet& ns);
+} // end of namespace dai
 
 
-} // end of namespace dai
+/** \example example_varset.cpp
+ *  This example shows how to use the Var, VarSet and State classes. It also explains the concept of "states" for VarSets.
+ *
+ *  \section Output
+ *  \verbinclude examples/example_varset.out
+ *
+ *  \section Source
+ */
 
 
 #endif