Generalized VarSet to "template<typename T> small_set<T>"
[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 <vector>
28 #include <map>
29 #include <algorithm>
30 #include <iostream>
31 #include <cassert>
32 #include <dai/var.h>
33 #include <dai/util.h>
34
35
36 namespace dai {
37
38
39 /// A small_set<T> represents a set, optimized for a small number of elements.
40 /** For sets consisting of a small number of elements, an implementation using
41 * an ordered std::vector<T> is faster than an implementation using std::set<T>.
42 * The elements should be less-than-comparable.
43 */
44 template <typename T>
45 class small_set {
46 private:
47 /// The elements in this set
48 std::vector<T> _elements;
49
50 public:
51 /// Default constructor
52 small_set() : _elements() {}
53
54 /// Construct a small_set with one element
55 small_set( const T &n ) : _elements() {
56 _elements.push_back( n );
57 }
58
59 /// Construct a small_set with two elements
60 small_set( const T &n1, const T &n2 ) {
61 if( n1 < n2 ) {
62 _elements.push_back( n1 );
63 _elements.push_back( n2 );
64 } else if( n2 < n1 ) {
65 _elements.push_back( n2 );
66 _elements.push_back( n1 );
67 } else
68 _elements.push_back( n1 );
69 }
70
71 /// Construct a small_set from a range of iterators.
72 /** The value_type of the Iterator should be T.
73 * For efficiency, the number of elements can be
74 * speficied by sizeHint.
75 */
76 template <typename Iterator>
77 small_set( Iterator begin, Iterator end, size_t sizeHint=0 ) {
78 _elements.reserve( sizeHint );
79 _elements.insert( _elements.begin(), begin, end );
80 std::sort( _elements.begin(), _elements.end() );
81 typename std::vector<T>::iterator new_end = std::unique( _elements.begin(), _elements.end() );
82 _elements.erase( new_end, _elements.end() );
83 }
84
85 /// Copy constructor
86 small_set( const small_set &x ) : _elements( x._elements ) {}
87
88 /// Assignment operator
89 small_set & operator=( const small_set &x ) {
90 if( this != &x ) {
91 _elements = x._elements;
92 }
93 return *this;
94 }
95
96 /// Setminus operator (result contains all elements in *this, except those in ns)
97 small_set operator/ ( const small_set& ns ) const {
98 small_set res;
99 std::set_difference( _elements.begin(), _elements.end(), ns._elements.begin(), ns._elements.end(), inserter( res._elements, res._elements.begin() ) );
100 return res;
101 }
102
103 /// Set-union operator (result contains all elements in *this, plus those in ns)
104 small_set operator| ( const small_set& ns ) const {
105 small_set res;
106 std::set_union( _elements.begin(), _elements.end(), ns._elements.begin(), ns._elements.end(), inserter( res._elements, res._elements.begin() ) );
107 return res;
108 }
109
110 /// Set-intersection operator (result contains all elements in *this that are also contained in ns)
111 small_set operator& ( const small_set& ns ) const {
112 small_set res;
113 std::set_intersection( _elements.begin(), _elements.end(), ns._elements.begin(), ns._elements.end(), inserter( res._elements, res._elements.begin() ) );
114 return res;
115 }
116
117 /// Erases from *this all elements in ns
118 small_set& operator/= ( const small_set& ns ) {
119 return (*this = (*this / ns));
120 }
121
122 /// Erase one element
123 small_set& operator/= ( const T& n ) {
124 typename std::vector<T>::iterator pos = lower_bound( _elements.begin(), _elements.end(), n );
125 if( pos != _elements.end() )
126 if( *pos == n ) // found element, delete it
127 _elements.erase( pos );
128 return *this;
129 }
130
131 /// Adds to *this all elements in ns
132 small_set& operator|= ( const small_set& ns ) {
133 return( *this = (*this | ns) );
134 }
135
136 /// Add one element
137 small_set& operator|= ( const T& n ) {
138 typename std::vector<T>::iterator pos = lower_bound( _elements.begin(), _elements.end(), n );
139 if( pos == _elements.end() || *pos != n ) // insert it
140 _elements.insert( pos, n );
141 return *this;
142 }
143
144 /// Erases from *this all elements not in ns
145 small_set& operator&= ( const small_set& ns ) {
146 return (*this = (*this & ns));
147 }
148
149 /// Returns true if *this is a subset of ns
150 bool operator<< ( const small_set& ns ) const {
151 return std::includes( ns._elements.begin(), ns._elements.end(), _elements.begin(), _elements.end() );
152 }
153
154 /// Returns true if ns is a subset of *this
155 bool operator>> ( const small_set& ns ) const {
156 return std::includes( _elements.begin(), _elements.end(), ns._elements.begin(), ns._elements.end() );
157 }
158
159 /// Returns true if *this and ns contain common elements
160 bool intersects( const small_set& ns ) const {
161 return( (*this & ns).size() > 0 );
162 }
163
164 /// Returns true if *this contains the element n
165 bool contains( const T& n ) const {
166 return std::binary_search( _elements.begin(), _elements.end(), n );
167 }
168
169 /// Constant iterator over the elements
170 typedef typename std::vector<T>::const_iterator const_iterator;
171 /// Iterator over the elements
172 typedef typename std::vector<T>::iterator iterator;
173 /// Constant reverse iterator over the elements
174 typedef typename std::vector<T>::const_reverse_iterator const_reverse_iterator;
175 /// Reverse iterator over the elements
176 typedef typename std::vector<T>::reverse_iterator reverse_iterator;
177
178 /// Returns iterator that points to the first element
179 iterator begin() { return _elements.begin(); }
180 /// Returns constant iterator that points to the first element
181 const_iterator begin() const { return _elements.begin(); }
182
183 /// Returns iterator that points beyond the last element
184 iterator end() { return _elements.end(); }
185 /// Returns constant iterator that points beyond the last element
186 const_iterator end() const { return _elements.end(); }
187
188 /// Returns reverse iterator that points to the last element
189 reverse_iterator rbegin() { return _elements.rbegin(); }
190 /// Returns constant reverse iterator that points to the last element
191 const_reverse_iterator rbegin() const { return _elements.rbegin(); }
192
193 /// Returns reverse iterator that points beyond the first element
194 reverse_iterator rend() { return _elements.rend(); }
195 /// Returns constant reverse iterator that points beyond the first element
196 const_reverse_iterator rend() const { return _elements.rend(); }
197
198 /// Returns number of elements
199 typename std::vector<T>::size_type size() const { return _elements.size(); }
200
201 /// Returns whether the small_set is empty
202 bool empty() const { return _elements.size() == 0; }
203
204 /// Test for equality of element labels
205 friend bool operator==( const small_set &a, const small_set &b ) {
206 return (a._elements == b._elements);
207 }
208
209 /// Test for inequality of element labels
210 friend bool operator!=( const small_set &a, const small_set &b ) {
211 return !(a._elements == b._elements);
212 }
213
214 /// Lexicographical comparison of element labels
215 friend bool operator<( const small_set &a, const small_set &b ) {
216 return a._elements < b._elements;
217 }
218 };
219
220
221 /// A VarSet represents a set of variables.
222 /**
223 * It is implemented as an ordered std::vector<Var> for efficiency reasons
224 * (indeed, it was found that a std::set<Var> usually has more overhead).
225 * In addition, it provides an interface for common set-theoretic operations.
226 */
227 typedef small_set<Var> VarSet;
228
229
230 /// For two Vars n1 and n2, the expression n1 | n2 gives the Varset containing n1 and n2
231 inline VarSet operator| (const Var& n1, const Var& n2) {
232 return( VarSet(n1, n2) );
233 }
234
235
236 /// Calculates the product of number of states of all variables in vars
237 size_t nrStates( const VarSet &vars );
238
239
240 /// calcState calculates the linear index of vars that corresponds
241 /// to the states of the variables given in states, implicitly assuming
242 /// states[m] = 0 for all m in this VarSet which are not in states.
243 size_t calcState( const VarSet &vars, const std::map<Var, size_t> &states );
244
245
246 /// Sends a VarSet to an output stream
247 std::ostream& operator<< (std::ostream &os, const VarSet& ns);
248
249
250 } // end of namespace dai
251
252
253 #endif