Small misc changes
[libdai.git] / include / dai / varset.h
1 /* Copyright (C) 2006-2008 Joris Mooij [j dot mooij at science dot ru dot nl]
2 Radboud University Nijmegen, The Netherlands
3
4 This file is part of libDAI.
5
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.
10
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.
15
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
19 */
20
21
22 #ifndef __defined_libdai_varset_h
23 #define __defined_libdai_varset_h
24
25
26 #include <set>
27 #include <algorithm>
28 #include <iostream>
29 #include <cassert>
30 #include <dai/var.h>
31
32
33 namespace dai {
34
35
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> {
40 protected:
41 /// Product of number of states of all contained variables
42 size_t _statespace;
43
44 /// Check whether ns is a subset
45 bool includes( const VarSet& ns ) const {
46 return std::includes( begin(), end(), ns.begin(), ns.end() );
47 }
48
49 /// Calculate statespace
50 size_t calcStateSpace() {
51 _statespace = 1;
52 for( const_iterator i = begin(); i != end(); ++i )
53 _statespace *= i->states();
54 return _statespace;
55 }
56
57
58 public:
59 /// Default constructor
60 VarSet() : _statespace(0) {};
61
62 /// Construct a VarSet with one variable
63 VarSet( const Var &n ) : _statespace( n.states() ) {
64 insert( n );
65 }
66
67 /// Construct a VarSet with two variables
68 VarSet( const Var &n1, const Var &n2 ) {
69 insert( n1 );
70 insert( n2 );
71 calcStateSpace();
72 }
73
74 /// Construct from a set<Var>
75 VarSet( const std::set<Var> &ns ) {
76 std::set<Var>::operator=( ns );
77 calcStateSpace();
78 }
79
80 /// Copy constructor
81 VarSet( const VarSet &x ) : std::set<Var>( x ), _statespace( x._statespace ) {}
82
83 /// Assignment operator
84 VarSet & operator=( const VarSet &x ) {
85 if( this != &x ) {
86 std::set<Var>::operator=( x );
87 _statespace = x._statespace;
88 }
89 return *this;
90 }
91
92
93 /// Return statespace, i.e. the product of the number of states of each variable
94 size_t states() const {
95 #ifdef DAI_DEBUG
96 size_t x = 1;
97 for( const_iterator i = begin(); i != end(); ++i )
98 x *= i->states();
99 assert( x == _statespace );
100 #endif
101 return _statespace;
102 }
103
104
105 /// Erase one variable
106 VarSet& operator/= (const Var& n) {
107 erase( n );
108 calcStateSpace();
109 return *this;
110 }
111
112 /// Add one variable
113 VarSet& operator|= (const Var& n) {
114 insert( n );
115 calcStateSpace();
116 return *this;
117 }
118
119 /// Setminus operator (result contains all variables except those in ns)
120 VarSet operator/ (const VarSet& ns) const {
121 VarSet res;
122 std::set_difference( begin(), end(), ns.begin(), ns.end(), inserter( res, res.begin() ) );
123 res.calcStateSpace();
124 return res;
125 }
126
127 /// Set-union operator (result contains all variables plus those in ns)
128 VarSet operator| (const VarSet& ns) const {
129 VarSet res;
130 std::set_union( begin(), end(), ns.begin(), ns.end(), inserter( res, res.begin() ) );
131 res.calcStateSpace();
132 return res;
133 }
134
135 /// Set-intersection operator (result contains all variables that are also contained in ns)
136 VarSet operator& (const VarSet& ns) const {
137 VarSet res;
138 std::set_intersection( begin(), end(), ns.begin(), ns.end(), inserter( res, res.begin() ) );
139 res.calcStateSpace();
140 return res;
141 }
142
143 /// Erases from *this all variables in ns
144 VarSet& operator/= (const VarSet& ns) {
145 return (*this = (*this / ns));
146 }
147
148 /// Adds to *this all variables in ns
149 VarSet& operator|= (const VarSet& ns) {
150 return (*this = (*this | ns));
151 }
152
153 /// Erases from *this all variables not in ns
154 VarSet& operator&= (const VarSet& ns) {
155 return (*this = (*this & ns));
156 }
157
158
159 /// Returns false if both *this and ns are empty
160 bool operator|| (const VarSet& ns) const {
161 return !( this->empty() && ns.empty() );
162 }
163
164 /// Returns true if *this and ns contain common variables
165 bool operator&& (const VarSet& ns) const {
166 return !( (*this & ns).empty() );
167 }
168
169 /// Returns true if *this is a subset of ns
170 bool operator<< (const VarSet& ns) const {
171 return ns.includes( *this );
172 }
173
174 /// Returns true if ns is a subset of *this
175 bool operator>> (const VarSet& ns) const {
176 return includes( ns );
177 }
178
179 /// Returns true if *this contains the variable n
180 bool operator&& (const Var& n) const {
181 return( find( n ) == end() ? false : true );
182 }
183
184
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++)
188 os << *n;
189 return( os );
190 }
191
192
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
197 * methods.
198 */
199
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;
208
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 );
212 calcStateSpace();
213 return result;
214 }
215
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 );
219 calcStateSpace();
220 return result;
221 }
222
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 );
226 }
227
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 );
231 }
232
233 friend bool operator<( const VarSet &a, const VarSet &b ) {
234 return operator<( (std::set<Var>)a, (std::set<Var>)b );
235 }
236 };
237
238
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) );
242 }
243
244
245 } // end of namespace dai
246
247
248 #endif