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