Improved index.h (merged from SVN head), which yields a 25% speedup.
[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 /// Copy constructor
82 VarSet( const VarSet &x ) : std::set<Var>( x ), _statespace( x._statespace ) {}
83
84 /// Assignment operator
85 VarSet & operator=( const VarSet &x ) {
86 if( this != &x ) {
87 std::set<Var>::operator=( x );
88 _statespace = x._statespace;
89 }
90 return *this;
91 }
92
93
94 /// Return statespace, i.e. the product of the number of states of each variable
95 size_t states() const {
96 #ifdef DAI_DEBUG
97 size_t x = 1;
98 for( const_iterator i = begin(); i != end(); ++i )
99 x *= i->states();
100 assert( x == _statespace );
101 #endif
102 return _statespace;
103 }
104
105
106 /// Erase one variable
107 VarSet& operator/= (const Var& n) {
108 erase( n );
109 calcStateSpace();
110 return *this;
111 }
112
113 /// Add one variable
114 VarSet& operator|= (const Var& n) {
115 insert( n );
116 calcStateSpace();
117 return *this;
118 }
119
120 /// Setminus operator (result contains all variables except those in ns)
121 VarSet operator/ (const VarSet& ns) const {
122 VarSet res;
123 std::set_difference( begin(), end(), ns.begin(), ns.end(), inserter( res, res.begin() ) );
124 res.calcStateSpace();
125 return res;
126 }
127
128 /// Set-union operator (result contains all variables plus those in ns)
129 VarSet operator| (const VarSet& ns) const {
130 VarSet res;
131 std::set_union( begin(), end(), ns.begin(), ns.end(), inserter( res, res.begin() ) );
132 res.calcStateSpace();
133 return res;
134 }
135
136 /// Set-intersection operator (result contains all variables that are also contained in ns)
137 VarSet operator& (const VarSet& ns) const {
138 VarSet res;
139 std::set_intersection( begin(), end(), ns.begin(), ns.end(), inserter( res, res.begin() ) );
140 res.calcStateSpace();
141 return res;
142 }
143
144 /// Erases from *this all variables in ns
145 VarSet& operator/= (const VarSet& ns) {
146 return (*this = (*this / ns));
147 }
148
149 /// Adds to *this all variables in ns
150 VarSet& operator|= (const VarSet& ns) {
151 return (*this = (*this | ns));
152 }
153
154 /// Erases from *this all variables not in ns
155 VarSet& operator&= (const VarSet& ns) {
156 return (*this = (*this & ns));
157 }
158
159
160 /// Returns false if both *this and ns are empty
161 bool operator|| (const VarSet& ns) const {
162 return !( this->empty() && ns.empty() );
163 }
164
165 /// Returns true if *this and ns contain common variables
166 bool operator&& (const VarSet& ns) const {
167 return !( (*this & ns).empty() );
168 }
169
170 /// Returns true if *this is a subset of ns
171 bool operator<< (const VarSet& ns) const {
172 return ns.includes( *this );
173 }
174
175 /// Returns true if ns is a subset of *this
176 bool operator>> (const VarSet& ns) const {
177 return includes( ns );
178 }
179
180 /// Returns true if *this contains the variable n
181 bool operator&& (const Var& n) const {
182 return( find( n ) == end() ? false : true );
183 }
184
185
186 /// Sends a VarSet to an output stream
187 friend std::ostream& operator<< (std::ostream & os, const VarSet& ns) {
188 for( VarSet::const_iterator n = ns.begin(); n != ns.end(); n++)
189 os << *n;
190 return( os );
191 }
192
193
194 /* The following makes part of the public interface of set<Var> available.
195 * It is important to note that insert functions have to be overloaded,
196 * because they have to recalculate the statespace. A different approach
197 * would be to publicly inherit from set<Var> and only overload the insert
198 * methods.
199 */
200
201 // Additional interface from set<Var> that has to be provided
202 using std::set<Var>::const_iterator;
203 using std::set<Var>::iterator;
204 using std::set<Var>::const_reference;
205 using std::set<Var>::begin;
206 using std::set<Var>::end;
207 using std::set<Var>::size;
208 using std::set<Var>::empty;
209
210 /// Copy of set<Var>::insert which additionally calculates the new statespace
211 std::pair<iterator, bool> insert( const Var& x ) {
212 std::pair<iterator, bool> result = std::set<Var>::insert( x );
213 calcStateSpace();
214 return result;
215 }
216
217 /// Copy of set<Var>::insert which additionally calculates the new statespace
218 iterator insert( iterator pos, const value_type& x ) {
219 iterator result = std::set<Var>::insert( pos, x );
220 calcStateSpace();
221 return result;
222 }
223
224 /// Test for equality (ignore _statespace member)
225 friend bool operator==( const VarSet &a, const VarSet &b ) {
226 return operator==( (std::set<Var>)a, (std::set<Var>)b );
227 }
228
229 /// Test for inequality (ignore _statespace member)
230 friend bool operator!=( const VarSet &a, const VarSet &b ) {
231 return operator!=( (std::set<Var>)a, (std::set<Var>)b );
232 }
233
234 friend bool operator<( const VarSet &a, const VarSet &b ) {
235 return operator<( (std::set<Var>)a, (std::set<Var>)b );
236 }
237 };
238
239
240 /// For two Vars n1 and n2, the expression n1 | n2 gives the Varset containing n1 and n2
241 inline VarSet operator| (const Var& n1, const Var& n2) {
242 return( VarSet(n1, n2) );
243 }
244
245
246 } // end of namespace dai
247
248
249 #endif