Updated copyrights
[libdai.git] / include / dai / varset.h
1 /* Copyright (C) 2006-2008 Joris Mooij [joris dot mooij at tuebingen dot mpg dot de]
2 Radboud University Nijmegen, The Netherlands /
3 Max Planck Institute for Biological Cybernetics, Germany
4
5 Copyright (C) 2002 Martijn Leisink [martijn@mbfys.kun.nl]
6 Radboud University Nijmegen, The Netherlands
7
8 This file is part of libDAI.
9
10 libDAI is free software; you can redistribute it and/or modify
11 it under the terms of the GNU General Public License as published by
12 the Free Software Foundation; either version 2 of the License, or
13 (at your option) any later version.
14
15 libDAI is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 GNU General Public License for more details.
19
20 You should have received a copy of the GNU General Public License
21 along with libDAI; if not, write to the Free Software
22 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
23 */
24
25
26 #ifndef __defined_libdai_varset_h
27 #define __defined_libdai_varset_h
28
29
30 #include <vector>
31 #include <map>
32 #include <algorithm>
33 #include <iostream>
34 #include <cassert>
35 #include <dai/var.h>
36 #include <dai/util.h>
37
38
39 namespace dai {
40
41
42 /// A small_set<T> represents a set, optimized for a small number of elements.
43 /** For sets consisting of a small number of elements, an implementation using
44 * an ordered std::vector<T> is faster than an implementation using std::set<T>.
45 * The elements should be less-than-comparable.
46 */
47 template <typename T>
48 class small_set {
49 private:
50 /// The elements in this set
51 std::vector<T> _elements;
52
53 public:
54 /// Default constructor
55 small_set() : _elements() {}
56
57 /// Construct a small_set with one element
58 small_set( const T &n ) : _elements() {
59 _elements.push_back( n );
60 }
61
62 /// Construct a small_set with two elements
63 small_set( const T &n1, const T &n2 ) {
64 if( n1 < n2 ) {
65 _elements.push_back( n1 );
66 _elements.push_back( n2 );
67 } else if( n2 < n1 ) {
68 _elements.push_back( n2 );
69 _elements.push_back( n1 );
70 } else
71 _elements.push_back( n1 );
72 }
73
74 /// Construct a small_set from a range of iterators.
75 /** The value_type of the Iterator should be T.
76 * For efficiency, the number of elements can be
77 * speficied by sizeHint.
78 */
79 template <typename Iterator>
80 small_set( Iterator begin, Iterator end, size_t sizeHint=0 ) {
81 _elements.reserve( sizeHint );
82 _elements.insert( _elements.begin(), begin, end );
83 std::sort( _elements.begin(), _elements.end() );
84 typename std::vector<T>::iterator new_end = std::unique( _elements.begin(), _elements.end() );
85 _elements.erase( new_end, _elements.end() );
86 }
87
88 /// Copy constructor
89 small_set( const small_set &x ) : _elements( x._elements ) {}
90
91 /// Assignment operator
92 small_set & operator=( const small_set &x ) {
93 if( this != &x ) {
94 _elements = x._elements;
95 }
96 return *this;
97 }
98
99 /// Setminus operator (result contains all elements in *this, except those in ns)
100 small_set operator/ ( const small_set& ns ) const {
101 small_set res;
102 std::set_difference( _elements.begin(), _elements.end(), ns._elements.begin(), ns._elements.end(), inserter( res._elements, res._elements.begin() ) );
103 return res;
104 }
105
106 /// Set-union operator (result contains all elements in *this, plus those in ns)
107 small_set operator| ( const small_set& ns ) const {
108 small_set res;
109 std::set_union( _elements.begin(), _elements.end(), ns._elements.begin(), ns._elements.end(), inserter( res._elements, res._elements.begin() ) );
110 return res;
111 }
112
113 /// Set-intersection operator (result contains all elements in *this that are also contained in ns)
114 small_set operator& ( const small_set& ns ) const {
115 small_set res;
116 std::set_intersection( _elements.begin(), _elements.end(), ns._elements.begin(), ns._elements.end(), inserter( res._elements, res._elements.begin() ) );
117 return res;
118 }
119
120 /// Erases from *this all elements in ns
121 small_set& operator/= ( const small_set& ns ) {
122 return (*this = (*this / ns));
123 }
124
125 /// Erase one element
126 small_set& operator/= ( const T& n ) {
127 typename std::vector<T>::iterator pos = lower_bound( _elements.begin(), _elements.end(), n );
128 if( pos != _elements.end() )
129 if( *pos == n ) // found element, delete it
130 _elements.erase( pos );
131 return *this;
132 }
133
134 /// Adds to *this all elements in ns
135 small_set& operator|= ( const small_set& ns ) {
136 return( *this = (*this | ns) );
137 }
138
139 /// Add one element
140 small_set& operator|= ( const T& n ) {
141 typename std::vector<T>::iterator pos = lower_bound( _elements.begin(), _elements.end(), n );
142 if( pos == _elements.end() || *pos != n ) // insert it
143 _elements.insert( pos, n );
144 return *this;
145 }
146
147 /// Erases from *this all elements not in ns
148 small_set& operator&= ( const small_set& ns ) {
149 return (*this = (*this & ns));
150 }
151
152 /// Returns true if *this is a subset of ns
153 bool operator<< ( const small_set& ns ) const {
154 return std::includes( ns._elements.begin(), ns._elements.end(), _elements.begin(), _elements.end() );
155 }
156
157 /// Returns true if ns is a subset of *this
158 bool operator>> ( const small_set& ns ) const {
159 return std::includes( _elements.begin(), _elements.end(), ns._elements.begin(), ns._elements.end() );
160 }
161
162 /// Returns true if *this and ns contain common elements
163 bool intersects( const small_set& ns ) const {
164 return( (*this & ns).size() > 0 );
165 }
166
167 /// Returns true if *this contains the element n
168 bool contains( const T& n ) const {
169 return std::binary_search( _elements.begin(), _elements.end(), n );
170 }
171
172 /// Constant iterator over the elements
173 typedef typename std::vector<T>::const_iterator const_iterator;
174 /// Iterator over the elements
175 typedef typename std::vector<T>::iterator iterator;
176 /// Constant reverse iterator over the elements
177 typedef typename std::vector<T>::const_reverse_iterator const_reverse_iterator;
178 /// Reverse iterator over the elements
179 typedef typename std::vector<T>::reverse_iterator reverse_iterator;
180
181 /// Returns iterator that points to the first element
182 iterator begin() { return _elements.begin(); }
183 /// Returns constant iterator that points to the first element
184 const_iterator begin() const { return _elements.begin(); }
185
186 /// Returns iterator that points beyond the last element
187 iterator end() { return _elements.end(); }
188 /// Returns constant iterator that points beyond the last element
189 const_iterator end() const { return _elements.end(); }
190
191 /// Returns reverse iterator that points to the last element
192 reverse_iterator rbegin() { return _elements.rbegin(); }
193 /// Returns constant reverse iterator that points to the last element
194 const_reverse_iterator rbegin() const { return _elements.rbegin(); }
195
196 /// Returns reverse iterator that points beyond the first element
197 reverse_iterator rend() { return _elements.rend(); }
198 /// Returns constant reverse iterator that points beyond the first element
199 const_reverse_iterator rend() const { return _elements.rend(); }
200
201 /// Returns number of elements
202 typename std::vector<T>::size_type size() const { return _elements.size(); }
203
204 /// Returns whether the small_set is empty
205 bool empty() const { return _elements.size() == 0; }
206
207 /// Test for equality of element labels
208 friend bool operator==( const small_set &a, const small_set &b ) {
209 return (a._elements == b._elements);
210 }
211
212 /// Test for inequality of element labels
213 friend bool operator!=( const small_set &a, const small_set &b ) {
214 return !(a._elements == b._elements);
215 }
216
217 /// Lexicographical comparison of element labels
218 friend bool operator<( const small_set &a, const small_set &b ) {
219 return a._elements < b._elements;
220 }
221 };
222
223
224 /// A VarSet represents a set of variables.
225 /**
226 * It is implemented as an ordered std::vector<Var> for efficiency reasons
227 * (indeed, it was found that a std::set<Var> usually has more overhead).
228 * In addition, it provides an interface for common set-theoretic operations.
229 */
230 typedef small_set<Var> VarSet;
231
232
233 /// For two Vars n1 and n2, the expression n1 | n2 gives the Varset containing n1 and n2
234 inline VarSet operator| (const Var& n1, const Var& n2) {
235 return( VarSet(n1, n2) );
236 }
237
238
239 /// Calculates the product of number of states of all variables in vars
240 size_t nrStates( const VarSet &vars );
241
242
243 /// calcState calculates the linear index of vars that corresponds
244 /// to the states of the variables given in states, implicitly assuming
245 /// states[m] = 0 for all m in this VarSet which are not in states.
246 size_t calcState( const VarSet &vars, const std::map<Var, size_t> &states );
247
248
249 /// Sends a VarSet to an output stream
250 std::ostream& operator<< (std::ostream &os, const VarSet& ns);
251
252
253 } // end of namespace dai
254
255
256 #endif