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
5 This file is part of libDAI.
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.
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.
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
23 #ifndef __defined_libdai_varset_h
24 #define __defined_libdai_varset_h
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
> {
42 /// Product of number of states of all contained variables
45 /// Check whether ns is a subset
46 bool includes( const VarSet
& ns
) const {
47 return std::includes( begin(), end(), ns
.begin(), ns
.end() );
50 /// Calculate statespace
51 size_t calcStateSpace() {
53 for( const_iterator i
= begin(); i
!= end(); ++i
)
54 _statespace
*= i
->states();
60 /// Default constructor
61 VarSet() : _statespace(0) {};
63 /// Construct a VarSet with one variable
64 VarSet( const Var
&n
) : _statespace( n
.states() ) {
68 /// Construct a VarSet with two variables
69 VarSet( const Var
&n1
, const Var
&n2
) {
75 /// Construct from a set<Var>
76 VarSet( const std::set
<Var
> &ns
) {
77 std::set
<Var
>::operator=( ns
);
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
++ )
89 VarSet( const VarSet
&x
) : std::set
<Var
>( x
), _statespace( x
._statespace
) {}
91 /// Assignment operator
92 VarSet
& operator=( const VarSet
&x
) {
94 std::set
<Var
>::operator=( x
);
95 _statespace
= x
._statespace
;
101 /// Return statespace, i.e. the product of the number of states of each variable
102 size_t states() const {
105 for( const_iterator i
= begin(); i
!= end(); ++i
)
107 assert( x
== _statespace
);
113 /// Erase one variable
114 VarSet
& operator/= (const Var
& n
) {
121 VarSet
& operator|= (const Var
& n
) {
127 /// Setminus operator (result contains all variables except those in ns)
128 VarSet
operator/ (const VarSet
& ns
) const {
130 std::set_difference( begin(), end(), ns
.begin(), ns
.end(), inserter( res
, res
.begin() ) );
131 res
.calcStateSpace();
135 /// Set-union operator (result contains all variables plus those in ns)
136 VarSet
operator| (const VarSet
& ns
) const {
138 std::set_union( begin(), end(), ns
.begin(), ns
.end(), inserter( res
, res
.begin() ) );
139 res
.calcStateSpace();
143 /// Set-intersection operator (result contains all variables that are also contained in ns)
144 VarSet
operator& (const VarSet
& ns
) const {
146 std::set_intersection( begin(), end(), ns
.begin(), ns
.end(), inserter( res
, res
.begin() ) );
147 res
.calcStateSpace();
151 /// Erases from *this all variables in ns
152 VarSet
& operator/= (const VarSet
& ns
) {
153 return (*this = (*this / ns
));
156 /// Adds to *this all variables in ns
157 VarSet
& operator|= (const VarSet
& ns
) {
158 return (*this = (*this | ns
));
161 /// Erases from *this all variables not in ns
162 VarSet
& operator&= (const VarSet
& ns
) {
163 return (*this = (*this & ns
));
167 /// Returns false if both *this and ns are empty
168 bool operator|| (const VarSet
& ns
) const {
169 return !( this->empty() && ns
.empty() );
172 /// Returns true if *this and ns contain common variables
173 bool operator&& (const VarSet
& ns
) const {
174 return !( (*this & ns
).empty() );
177 /// Returns true if *this is a subset of ns
178 bool operator<< (const VarSet
& ns
) const {
179 return ns
.includes( *this );
182 /// Returns true if ns is a subset of *this
183 bool operator>> (const VarSet
& ns
) const {
184 return includes( ns
);
187 /// Returns true if *this contains the variable n
188 bool operator&& (const Var
& n
) const {
189 return( find( n
) == end() ? false : true );
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
++)
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
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
;
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
);
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
);
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
);
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
);
241 friend bool operator<( const VarSet
&a
, const VarSet
&b
) {
242 return operator<( (std::set
<Var
>)a
, (std::set
<Var
>)b
);
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
) );
253 } // end of namespace dai