1 /* Copyright (C) 2006-2008 Joris Mooij [j dot mooij at science dot ru dot nl]
2 Radboud University Nijmegen, The Netherlands
4 This file is part of libDAI.
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.
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.
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
22 #ifndef __defined_libdai_varset_h
23 #define __defined_libdai_varset_h
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
> {
41 /// Product of number of states of all contained variables
44 /// Check whether ns is a subset
45 bool includes( const VarSet
& ns
) const {
46 return std::includes( begin(), end(), ns
.begin(), ns
.end() );
49 /// Calculate statespace
50 size_t calcStateSpace() {
52 for( const_iterator i
= begin(); i
!= end(); ++i
)
53 _statespace
*= i
->states();
59 /// Default constructor
60 VarSet() : _statespace(0) {};
62 /// Construct a VarSet with one variable
63 VarSet( const Var
&n
) : _statespace( n
.states() ) {
67 /// Construct a VarSet with two variables
68 VarSet( const Var
&n1
, const Var
&n2
) {
74 /// Construct from a set<Var>
75 VarSet( const std::set
<Var
> &ns
) {
76 std::set
<Var
>::operator=( ns
);
81 VarSet( const VarSet
&x
) : std::set
<Var
>( x
), _statespace( x
._statespace
) {}
83 /// Assignment operator
84 VarSet
& operator=( const VarSet
&x
) {
86 std::set
<Var
>::operator=( x
);
87 _statespace
= x
._statespace
;
93 /// Return statespace, i.e. the product of the number of states of each variable
94 size_t stateSpace() const {
97 for( const_iterator i
= begin(); i
!= end(); ++i
)
99 assert( x
== _statespace
);
105 /// Erase one variable
106 VarSet
& operator/= (const Var
& n
) {
113 VarSet
& operator|= (const Var
& n
) {
119 /// Setminus operator (result contains all variables except those in ns)
120 VarSet
operator/ (const VarSet
& ns
) const {
122 std::set_difference( begin(), end(), ns
.begin(), ns
.end(), inserter( res
, res
.begin() ) );
123 res
.calcStateSpace();
127 /// Set-union operator (result contains all variables plus those in ns)
128 VarSet
operator| (const VarSet
& ns
) const {
130 std::set_union( begin(), end(), ns
.begin(), ns
.end(), inserter( res
, res
.begin() ) );
131 res
.calcStateSpace();
135 /// Set-intersection operator (result contains all variables that are also contained in ns)
136 VarSet
operator& (const VarSet
& ns
) const {
138 std::set_intersection( begin(), end(), ns
.begin(), ns
.end(), inserter( res
, res
.begin() ) );
139 res
.calcStateSpace();
143 /// Erases from *this all variables in ns
144 VarSet
& operator/= (const VarSet
& ns
) {
145 return (*this = (*this / ns
));
148 /// Adds to *this all variables in ns
149 VarSet
& operator|= (const VarSet
& ns
) {
150 return (*this = (*this | ns
));
153 /// Erases from *this all variables not in ns
154 VarSet
& operator&= (const VarSet
& ns
) {
155 return (*this = (*this & ns
));
159 /// Returns false if both *this and ns are empty
160 bool operator|| (const VarSet
& ns
) const {
161 return !( this->empty() && ns
.empty() );
164 /// Returns true if *this and ns contain common variables
165 bool operator&& (const VarSet
& ns
) const {
166 return !( (*this & ns
).empty() );
169 /// Returns true if *this is a subset of ns
170 bool operator<< (const VarSet
& ns
) const {
171 return ns
.includes( *this );
174 /// Returns true if ns is a subset of *this
175 bool operator>> (const VarSet
& ns
) const {
176 return includes( ns
);
179 /// Returns true if *this contains the variable n
180 bool operator&& (const Var
& n
) const {
181 return( find( n
) == end() ? false : true );
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
++)
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
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
;
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
);
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
);
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
);
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
);
233 friend bool operator<( const VarSet
&a
, const VarSet
&b
) {
234 return operator<( (std::set
<Var
>)a
, (std::set
<Var
>)b
);
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
) );
245 } // end of namespace dai