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
5 This file is part of libDAI.
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.
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.
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
23 #ifndef __defined_libdai_varset_h
24 #define __defined_libdai_varset_h
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.
47 /// The elements in this set
48 std::vector
<T
> _elements
;
51 /// Default constructor
52 small_set() : _elements() {}
54 /// Construct a small_set with one element
55 small_set( const T
&n
) : _elements() {
56 _elements
.push_back( n
);
59 /// Construct a small_set with two elements
60 small_set( const T
&n1
, const T
&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
);
68 _elements
.push_back( n1
);
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.
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() );
86 small_set( const small_set
&x
) : _elements( x
._elements
) {}
88 /// Assignment operator
89 small_set
& operator=( const small_set
&x
) {
91 _elements
= x
._elements
;
96 /// Setminus operator (result contains all elements in *this, except those in ns)
97 small_set
operator/ ( const small_set
& ns
) const {
99 std::set_difference( _elements
.begin(), _elements
.end(), ns
._elements
.begin(), ns
._elements
.end(), inserter( res
._elements
, res
._elements
.begin() ) );
103 /// Set-union operator (result contains all elements in *this, plus those in ns)
104 small_set
operator| ( const small_set
& ns
) const {
106 std::set_union( _elements
.begin(), _elements
.end(), ns
._elements
.begin(), ns
._elements
.end(), inserter( res
._elements
, res
._elements
.begin() ) );
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 {
113 std::set_intersection( _elements
.begin(), _elements
.end(), ns
._elements
.begin(), ns
._elements
.end(), inserter( res
._elements
, res
._elements
.begin() ) );
117 /// Erases from *this all elements in ns
118 small_set
& operator/= ( const small_set
& ns
) {
119 return (*this = (*this / ns
));
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
);
131 /// Adds to *this all elements in ns
132 small_set
& operator|= ( const small_set
& ns
) {
133 return( *this = (*this | ns
) );
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
);
144 /// Erases from *this all elements not in ns
145 small_set
& operator&= ( const small_set
& ns
) {
146 return (*this = (*this & ns
));
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() );
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() );
159 /// Returns true if *this and ns contain common elements
160 bool intersects( const small_set
& ns
) const {
161 return( (*this & ns
).size() > 0 );
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
);
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
;
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(); }
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(); }
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(); }
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(); }
198 /// Returns number of elements
199 typename
std::vector
<T
>::size_type
size() const { return _elements
.size(); }
201 /// Returns whether the small_set is empty
202 bool empty() const { return _elements
.size() == 0; }
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
);
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
);
214 /// Lexicographical comparison of element labels
215 friend bool operator<( const small_set
&a
, const small_set
&b
) {
216 return a
._elements
< b
._elements
;
221 /// A VarSet represents a set of variables.
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.
227 typedef small_set
<Var
> VarSet
;
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
) );
236 /// Calculates the product of number of states of all variables in vars
237 size_t nrStates( const VarSet
&vars
);
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
);
246 /// Sends a VarSet to an output stream
247 std::ostream
& operator<< (std::ostream
&os
, const VarSet
& ns
);
250 } // end of namespace dai