Oops, correct previous partial commit.
[libdai.git] / include / dai / smallset.h
1 /* Copyright (C) 2006-2008 Joris Mooij [joris dot mooij at tuebingen dot mpg dot de]
2 Radboud University Nijmegen, The Netherlands /
3 Max Planck Institute for Biological Cybernetics, Germany
4
5 Copyright (C) 2002 Martijn Leisink [martijn@mbfys.kun.nl]
6 Radboud University Nijmegen, The Netherlands
7
8 This file is part of libDAI.
9
10 libDAI is free software; you can redistribute it and/or modify
11 it under the terms of the GNU General Public License as published by
12 the Free Software Foundation; either version 2 of the License, or
13 (at your option) any later version.
14
15 libDAI is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 GNU General Public License for more details.
19
20 You should have received a copy of the GNU General Public License
21 along with libDAI; if not, write to the Free Software
22 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
23 */
24
25
26 /// \file
27 /// \brief Defines smallSet<T> class
28 /// \todo Improve documentation
29
30
31 #ifndef __defined_libdai_smallset_h
32 #define __defined_libdai_smallset_h
33
34
35 #include <vector>
36 #include <algorithm>
37
38
39 namespace dai {
40
41
42 /// Represents a set (optimized for a small number of elements).
43 /** For sets consisting of a small number of elements, an implementation using
44 * an ordered std::vector<T> is faster than an implementation using std::set<T>.
45 * The elements should be less-than-comparable.
46 */
47 template <typename T>
48 class smallSet {
49 private:
50 /// The elements in this set
51 std::vector<T> _elements;
52
53 public:
54 /// Default constructor
55 smallSet() : _elements() {}
56
57 /// Construct a smallSet with one element
58 smallSet( const T &n ) : _elements() {
59 _elements.push_back( n );
60 }
61
62 /// Construct a smallSet with two elements
63 smallSet( const T &n1, const T &n2 ) {
64 if( n1 < n2 ) {
65 _elements.push_back( n1 );
66 _elements.push_back( n2 );
67 } else if( n2 < n1 ) {
68 _elements.push_back( n2 );
69 _elements.push_back( n1 );
70 } else
71 _elements.push_back( n1 );
72 }
73
74 /// Construct a smallSet from a range of iterators.
75 /** \tparam Iterator Iterator with value_type T.
76 * \param begin Points to first element to be added.
77 * \param end Points just beyond last element to be added.
78 * \param sizeHint For efficiency, the number of elements can be speficied by sizeHint.
79 */
80 template <typename Iterator>
81 smallSet( Iterator begin, Iterator end, size_t sizeHint=0 ) {
82 _elements.reserve( sizeHint );
83 _elements.insert( _elements.begin(), begin, end );
84 std::sort( _elements.begin(), _elements.end() );
85 typename std::vector<T>::iterator new_end = std::unique( _elements.begin(), _elements.end() );
86 _elements.erase( new_end, _elements.end() );
87 }
88
89 /// Copy constructor
90 smallSet( const smallSet &x ) : _elements( x._elements ) {}
91
92 /// Assignment operator
93 smallSet & operator=( const smallSet &x ) {
94 if( this != &x ) {
95 _elements = x._elements;
96 }
97 return *this;
98 }
99
100 /// Setminus operator: returns all elements in *this, except those in ns
101 smallSet operator/ ( const smallSet& ns ) const {
102 smallSet res;
103 std::set_difference( _elements.begin(), _elements.end(), ns._elements.begin(), ns._elements.end(), inserter( res._elements, res._elements.begin() ) );
104 return res;
105 }
106
107 /// Set-union operator: returns all elements in *this, plus those in ns
108 smallSet operator| ( const smallSet& ns ) const {
109 smallSet res;
110 std::set_union( _elements.begin(), _elements.end(), ns._elements.begin(), ns._elements.end(), inserter( res._elements, res._elements.begin() ) );
111 return res;
112 }
113
114 /// Set-intersection operator: returns all elements in *this that are also contained in ns
115 smallSet operator& ( const smallSet& ns ) const {
116 smallSet res;
117 std::set_intersection( _elements.begin(), _elements.end(), ns._elements.begin(), ns._elements.end(), inserter( res._elements, res._elements.begin() ) );
118 return res;
119 }
120
121 /// Erases from *this all elements in ns
122 smallSet& operator/= ( const smallSet& ns ) {
123 return (*this = (*this / ns));
124 }
125
126 /// Erases one element
127 smallSet& operator/= ( const T& n ) {
128 typename std::vector<T>::iterator pos = lower_bound( _elements.begin(), _elements.end(), n );
129 if( pos != _elements.end() )
130 if( *pos == n ) // found element, delete it
131 _elements.erase( pos );
132 return *this;
133 }
134
135 /// Adds to *this all elements in ns
136 smallSet& operator|= ( const smallSet& ns ) {
137 return( *this = (*this | ns) );
138 }
139
140 /// Adds one element
141 smallSet& operator|= ( const T& n ) {
142 typename std::vector<T>::iterator pos = lower_bound( _elements.begin(), _elements.end(), n );
143 if( pos == _elements.end() || *pos != n ) // insert it
144 _elements.insert( pos, n );
145 return *this;
146 }
147
148 /// Erases from *this all elements not in ns
149 smallSet& operator&= ( const smallSet& ns ) {
150 return (*this = (*this & ns));
151 }
152
153 /// Returns true if *this is a subset of ns
154 bool operator<< ( const smallSet& ns ) const {
155 return std::includes( ns._elements.begin(), ns._elements.end(), _elements.begin(), _elements.end() );
156 }
157
158 /// Returns true if ns is a subset of *this
159 bool operator>> ( const smallSet& ns ) const {
160 return std::includes( _elements.begin(), _elements.end(), ns._elements.begin(), ns._elements.end() );
161 }
162
163 /// Returns true if *this and ns contain common elements
164 bool intersects( const smallSet& ns ) const {
165 return( (*this & ns).size() > 0 );
166 }
167
168 /// Returns true if *this contains the element n
169 bool contains( const T& n ) const {
170 return std::binary_search( _elements.begin(), _elements.end(), n );
171 }
172
173 /// Constant iterator over the elements
174 typedef typename std::vector<T>::const_iterator const_iterator;
175 /// Iterator over the elements
176 typedef typename std::vector<T>::iterator iterator;
177 /// Constant reverse iterator over the elements
178 typedef typename std::vector<T>::const_reverse_iterator const_reverse_iterator;
179 /// Reverse iterator over the elements
180 typedef typename std::vector<T>::reverse_iterator reverse_iterator;
181
182 /// Returns iterator that points to the first element
183 iterator begin() { return _elements.begin(); }
184 /// Returns constant iterator that points to the first element
185 const_iterator begin() const { return _elements.begin(); }
186
187 /// Returns iterator that points beyond the last element
188 iterator end() { return _elements.end(); }
189 /// Returns constant iterator that points beyond the last element
190 const_iterator end() const { return _elements.end(); }
191
192 /// Returns reverse iterator that points to the last element
193 reverse_iterator rbegin() { return _elements.rbegin(); }
194 /// Returns constant reverse iterator that points to the last element
195 const_reverse_iterator rbegin() const { return _elements.rbegin(); }
196
197 /// Returns reverse iterator that points beyond the first element
198 reverse_iterator rend() { return _elements.rend(); }
199 /// Returns constant reverse iterator that points beyond the first element
200 const_reverse_iterator rend() const { return _elements.rend(); }
201
202 /// Returns number of elements
203 typename std::vector<T>::size_type size() const { return _elements.size(); }
204
205 /// Returns whether the smallSet is empty
206 bool empty() const { return _elements.size() == 0; }
207
208 /// Returns true if the two sets are identical
209 friend bool operator==( const smallSet &a, const smallSet &b ) {
210 return (a._elements == b._elements);
211 }
212
213 /// Returns true if the two sets are not identical
214 friend bool operator!=( const smallSet &a, const smallSet &b ) {
215 return !(a._elements == b._elements);
216 }
217
218 /// Lexicographical comparison of elements
219 friend bool operator<( const smallSet &a, const smallSet &b ) {
220 return a._elements < b._elements;
221 }
222 };
223
224
225 } // end of namespace dai
226
227
228 #endif