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