Finished a new release: libDAI 0.2.7.
[libdai.git] / include / dai / smallset.h
1 /* This file is part of libDAI - http://www.libdai.org/
2 *
3 * libDAI is licensed under the terms of the GNU General Public License version
4 * 2, or (at your option) any later version. libDAI is distributed without any
5 * warranty. See the file COPYING for more details.
6 *
7 * Copyright (C) 2002 Martijn Leisink [martijn@mbfys.kun.nl]
8 * Copyright (C) 2006-2009 Joris Mooij [joris dot mooij at libdai dot org]
9 * Copyright (C) 2002-2007 Radboud University Nijmegen, The Netherlands
10 */
11
12
13 /// \file
14 /// \brief Defines the SmallSet<> class, which represents a set (optimized for a small number of elements).
15
16
17 #ifndef __defined_libdai_smallset_h
18 #define __defined_libdai_smallset_h
19
20
21 #include <vector>
22 #include <algorithm>
23 #include <iostream>
24
25
26 namespace dai {
27
28
29 /// Represents a set; the implementation is optimized for a small number of elements.
30 /** SmallSet uses an ordered <tt>std::vector<</tt><em>T</em><tt>></tt> to represent a set; this is faster than
31 * using a <tt>std::set<</tt><em>T</em><tt>></tt> if the number of elements is small.
32 * \tparam T Should be less-than-comparable.
33 */
34 template <typename T>
35 class SmallSet {
36 private:
37 /// The elements in this set
38 std::vector<T> _elements;
39
40 public:
41 /// \name Constructors and destructors
42 //@{
43 /// Default constructor (constructs an empty set)
44 SmallSet() : _elements() {}
45
46 /// Construct a set consisting of one element
47 SmallSet( const T &t ) : _elements() {
48 _elements.push_back( t );
49 }
50
51 /// Construct a set consisting of two elements
52 SmallSet( const T &t1, const T &t2 ) {
53 if( t1 < t2 ) {
54 _elements.push_back( t1 );
55 _elements.push_back( t2 );
56 } else if( t2 < t1 ) {
57 _elements.push_back( t2 );
58 _elements.push_back( t1 );
59 } else
60 _elements.push_back( t1 );
61 }
62
63 /// Construct a SmallSet from a range of elements.
64 /** \tparam TIterator Iterates over instances of type \a T.
65 * \param begin Points to first element to be added.
66 * \param end Points just beyond last element to be added.
67 * \param sizeHint For efficiency, the number of elements can be speficied by \a sizeHint.
68 * \note The \a sizeHint parameter used to be optional in libDAI versions 0.2.4 and earlier.
69 */
70 template <typename TIterator>
71 SmallSet( TIterator begin, TIterator end, size_t sizeHint ) {
72 _elements.reserve( sizeHint );
73 _elements.insert( _elements.begin(), begin, end );
74 std::sort( _elements.begin(), _elements.end() );
75 typename std::vector<T>::iterator new_end = std::unique( _elements.begin(), _elements.end() );
76 _elements.erase( new_end, _elements.end() );
77 }
78 //@}
79
80 /// \name Operators for set-theoretic operations
81 //@{
82 /// Inserts \a t into \c *this
83 SmallSet& insert( const T& t ) {
84 typename SmallSet<T>::iterator it = std::lower_bound( _elements.begin(), _elements.end(), t );
85 if( (it == _elements.end()) || (*it != t) )
86 _elements.insert( it, t );
87 return *this;
88 }
89
90 /// Erases \a t from \c *this
91 SmallSet& erase( const T& t ) {
92 return (*this /= t);
93 }
94
95 /// Set-minus operator: returns all elements in \c *this, except those in \a x
96 SmallSet operator/ ( const SmallSet& x ) const {
97 SmallSet res;
98 std::set_difference( _elements.begin(), _elements.end(), x._elements.begin(), x._elements.end(), inserter( res._elements, res._elements.begin() ) );
99 return res;
100 }
101
102 /// Set-union operator: returns all elements in \c *this, plus those in \a x
103 SmallSet operator| ( const SmallSet& x ) const {
104 SmallSet res;
105 std::set_union( _elements.begin(), _elements.end(), x._elements.begin(), x._elements.end(), inserter( res._elements, res._elements.begin() ) );
106 return res;
107 }
108
109 /// Set-intersection operator: returns all elements in \c *this that are also contained in \a x
110 SmallSet operator& ( const SmallSet& x ) const {
111 SmallSet res;
112 std::set_intersection( _elements.begin(), _elements.end(), x._elements.begin(), x._elements.end(), inserter( res._elements, res._elements.begin() ) );
113 return res;
114 }
115
116 /// Erases from \c *this all elements in \a x
117 SmallSet& operator/= ( const SmallSet& x ) {
118 return (*this = (*this / x));
119 }
120
121 /// Erases one element
122 SmallSet& operator/= ( const T &t ) {
123 typename std::vector<T>::iterator pos = lower_bound( _elements.begin(), _elements.end(), t );
124 if( pos != _elements.end() )
125 if( *pos == t ) // found element, delete it
126 _elements.erase( pos );
127 return *this;
128 }
129
130 /// Adds to \c *this all elements in \a x
131 SmallSet& operator|= ( const SmallSet& x ) {
132 return( *this = (*this | x) );
133 }
134
135 /// Adds one element
136 SmallSet& operator|= ( const T& t ) {
137 typename std::vector<T>::iterator pos = lower_bound( _elements.begin(), _elements.end(), t );
138 if( pos == _elements.end() || *pos != t ) // insert it
139 _elements.insert( pos, t );
140 return *this;
141 }
142
143 /// Erases from \c *this all elements not in \a x
144 SmallSet& operator&= ( const SmallSet& x ) {
145 return (*this = (*this & x));
146 }
147
148 /// Returns \c true if \c *this is a subset of \a x
149 bool operator<< ( const SmallSet& x ) const {
150 return std::includes( x._elements.begin(), x._elements.end(), _elements.begin(), _elements.end() );
151 }
152
153 /// Returns \c true if \a x is a subset of \c *this
154 bool operator>> ( const SmallSet& x ) const {
155 return std::includes( _elements.begin(), _elements.end(), x._elements.begin(), x._elements.end() );
156 }
157 //@}
158
159 /// \name Queries
160 //@{
161 /// Returns \c true if \c *this and \a x have elements in common
162 bool intersects( const SmallSet& x ) const {
163 return( (*this & x).size() > 0 );
164 }
165
166 /// Returns \c true if \c *this contains the element \a t
167 bool contains( const T &t ) const {
168 return std::binary_search( _elements.begin(), _elements.end(), t );
169 }
170
171 /// Returns number of elements
172 typename std::vector<T>::size_type size() const { return _elements.size(); }
173
174 /// Returns whether \c *this is empty
175 bool empty() const { return _elements.size() == 0; }
176
177 /// Returns reference to the elements
178 std::vector<T>& elements() { return _elements; }
179
180 /// Returns constant reference to the elements
181 const std::vector<T>& elements() const { return _elements; }
182 //@}
183
184 /// Constant iterator over the elements
185 typedef typename std::vector<T>::const_iterator const_iterator;
186 /// Iterator over the elements
187 typedef typename std::vector<T>::iterator iterator;
188 /// Constant reverse iterator over the elements
189 typedef typename std::vector<T>::const_reverse_iterator const_reverse_iterator;
190 /// Reverse iterator over the elements
191 typedef typename std::vector<T>::reverse_iterator reverse_iterator;
192
193 /// \name Iterator interface
194 //@{
195 /// Returns iterator that points to the first element
196 iterator begin() { return _elements.begin(); }
197 /// Returns constant iterator that points to the first element
198 const_iterator begin() const { return _elements.begin(); }
199
200 /// Returns iterator that points beyond the last element
201 iterator end() { return _elements.end(); }
202 /// Returns constant iterator that points beyond the last element
203 const_iterator end() const { return _elements.end(); }
204
205 /// Returns reverse iterator that points to the last element
206 reverse_iterator rbegin() { return _elements.rbegin(); }
207 /// Returns constant reverse iterator that points to the last element
208 const_reverse_iterator rbegin() const { return _elements.rbegin(); }
209
210 /// Returns reverse iterator that points beyond the first element
211 reverse_iterator rend() { return _elements.rend(); }
212 /// Returns constant reverse iterator that points beyond the first element
213 const_reverse_iterator rend() const { return _elements.rend(); }
214
215 /// Returns reference to first element
216 T& front() { return _elements.front(); }
217 /// Returns constant reference to first element
218 const T& front() const { return _elements.front(); }
219
220 /// Returns reference to last element
221 T& back() { return _elements.back(); }
222 /// Returns constant reference to last element
223 const T& back() const { return _elements.back(); }
224 //@}
225
226 /// \name Comparison operators
227 //@{
228 /// Returns \c true if \a a and \a b are identical
229 friend bool operator==( const SmallSet &a, const SmallSet &b ) {
230 return (a._elements == b._elements);
231 }
232
233 /// Returns \c true if \a a and \a b are not identical
234 friend bool operator!=( const SmallSet &a, const SmallSet &b ) {
235 return !(a._elements == b._elements);
236 }
237
238 /// Lexicographical comparison of elements
239 friend bool operator<( const SmallSet &a, const SmallSet &b ) {
240 return a._elements < b._elements;
241 }
242 //@}
243
244 /// \name Streaming input/output
245 //@{
246 /// Writes a SmallSet to an output stream
247 friend std::ostream& operator << ( std::ostream& os, const SmallSet& x ) {
248 os << "{";
249 for( typename std::vector<T>::const_iterator it = x.begin(); it != x.end(); it++ )
250 os << (it != x.begin() ? ", " : "") << *it;
251 os << "}";
252 return os;
253 }
254 //@}
255 };
256
257
258 } // end of namespace dai
259
260
261 #endif