606c3f8506b3f1b74d848fa6422f2dd2e696bfe8
[libdai.git] / 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