Significant improvement of documentation
[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
29
30 #ifndef __defined_libdai_smallset_h
31 #define __defined_libdai_smallset_h
32
33
34 #include <vector>
35 #include <algorithm>
36
37
38 namespace dai {
39
40
41 /// Represents a set (optimized for a small number of elements).
42 /** For sets consisting of a small number of elements, an implementation using
43 * an ordered std::vector<T> is faster than an implementation using std::set<T>.
44 * The elements should be less-than-comparable.
45 */
46 template <typename T>
47 class smallSet {
48 private:
49 /// The elements in this set
50 std::vector<T> _elements;
51
52 public:
53 /// Default constructor
54 smallSet() : _elements() {}
55
56 /// Construct a smallSet with one element
57 smallSet( const T &n ) : _elements() {
58 _elements.push_back( n );
59 }
60
61 /// Construct a smallSet with two elements
62 smallSet( const T &n1, const T &n2 ) {
63 if( n1 < n2 ) {
64 _elements.push_back( n1 );
65 _elements.push_back( n2 );
66 } else if( n2 < n1 ) {
67 _elements.push_back( n2 );
68 _elements.push_back( n1 );
69 } else
70 _elements.push_back( n1 );
71 }
72
73 /// Construct a smallSet from a range of iterators.
74 /** \tparam Iterator Iterator with value_type T.
75 * \param begin Points to first element to be added.
76 * \param end Points just beyond last element to be added.
77 * \param sizeHint For efficiency, the number of elements can be speficied by sizeHint.
78 */
79 template <typename Iterator>
80 smallSet( Iterator begin, Iterator end, size_t sizeHint=0 ) {
81 _elements.reserve( sizeHint );
82 _elements.insert( _elements.begin(), begin, end );
83 std::sort( _elements.begin(), _elements.end() );
84 typename std::vector<T>::iterator new_end = std::unique( _elements.begin(), _elements.end() );
85 _elements.erase( new_end, _elements.end() );
86 }
87
88 /// Copy constructor
89 smallSet( const smallSet &x ) : _elements( x._elements ) {}
90
91 /// Assignment operator
92 smallSet & operator=( const smallSet &x ) {
93 if( this != &x ) {
94 _elements = x._elements;
95 }
96 return *this;
97 }
98
99 /// Setminus operator: returns all elements in *this, except those in ns
100 smallSet operator/ ( const smallSet& ns ) const {
101 smallSet res;
102 std::set_difference( _elements.begin(), _elements.end(), ns._elements.begin(), ns._elements.end(), inserter( res._elements, res._elements.begin() ) );
103 return res;
104 }
105
106 /// Set-union operator: returns all elements in *this, plus those in ns
107 smallSet operator| ( const smallSet& ns ) const {
108 smallSet res;
109 std::set_union( _elements.begin(), _elements.end(), ns._elements.begin(), ns._elements.end(), inserter( res._elements, res._elements.begin() ) );
110 return res;
111 }
112
113 /// Set-intersection operator: returns all elements in *this that are also contained in ns
114 smallSet operator& ( const smallSet& ns ) const {
115 smallSet res;
116 std::set_intersection( _elements.begin(), _elements.end(), ns._elements.begin(), ns._elements.end(), inserter( res._elements, res._elements.begin() ) );
117 return res;
118 }
119
120 /// Erases from *this all elements in ns
121 smallSet& operator/= ( const smallSet& ns ) {
122 return (*this = (*this / ns));
123 }
124
125 /// Erases one element
126 smallSet& operator/= ( const T& n ) {
127 typename std::vector<T>::iterator pos = lower_bound( _elements.begin(), _elements.end(), n );
128 if( pos != _elements.end() )
129 if( *pos == n ) // found element, delete it
130 _elements.erase( pos );
131 return *this;
132 }
133
134 /// Adds to *this all elements in ns
135 smallSet& operator|= ( const smallSet& ns ) {
136 return( *this = (*this | ns) );
137 }
138
139 /// Adds one element
140 smallSet& operator|= ( const T& n ) {
141 typename std::vector<T>::iterator pos = lower_bound( _elements.begin(), _elements.end(), n );
142 if( pos == _elements.end() || *pos != n ) // insert it
143 _elements.insert( pos, n );
144 return *this;
145 }
146
147 /// Erases from *this all elements not in ns
148 smallSet& operator&= ( const smallSet& ns ) {
149 return (*this = (*this & ns));
150 }
151
152 /// Returns true if *this is a subset of ns
153 bool operator<< ( const smallSet& ns ) const {
154 return std::includes( ns._elements.begin(), ns._elements.end(), _elements.begin(), _elements.end() );
155 }
156
157 /// Returns true if ns is a subset of *this
158 bool operator>> ( const smallSet& ns ) const {
159 return std::includes( _elements.begin(), _elements.end(), ns._elements.begin(), ns._elements.end() );
160 }
161
162 /// Returns true if *this and ns contain common elements
163 bool intersects( const smallSet& ns ) const {
164 return( (*this & ns).size() > 0 );
165 }
166
167 /// Returns true if *this contains the element n
168 bool contains( const T& n ) const {
169 return std::binary_search( _elements.begin(), _elements.end(), n );
170 }
171
172 /// Constant iterator over the elements
173 typedef typename std::vector<T>::const_iterator const_iterator;
174 /// Iterator over the elements
175 typedef typename std::vector<T>::iterator iterator;
176 /// Constant reverse iterator over the elements
177 typedef typename std::vector<T>::const_reverse_iterator const_reverse_iterator;
178 /// Reverse iterator over the elements
179 typedef typename std::vector<T>::reverse_iterator reverse_iterator;
180
181 /// Returns iterator that points to the first element
182 iterator begin() { return _elements.begin(); }
183 /// Returns constant iterator that points to the first element
184 const_iterator begin() const { return _elements.begin(); }
185
186 /// Returns iterator that points beyond the last element
187 iterator end() { return _elements.end(); }
188 /// Returns constant iterator that points beyond the last element
189 const_iterator end() const { return _elements.end(); }
190
191 /// Returns reverse iterator that points to the last element
192 reverse_iterator rbegin() { return _elements.rbegin(); }
193 /// Returns constant reverse iterator that points to the last element
194 const_reverse_iterator rbegin() const { return _elements.rbegin(); }
195
196 /// Returns reverse iterator that points beyond the first element
197 reverse_iterator rend() { return _elements.rend(); }
198 /// Returns constant reverse iterator that points beyond the first element
199 const_reverse_iterator rend() const { return _elements.rend(); }
200
201 /// Returns number of elements
202 typename std::vector<T>::size_type size() const { return _elements.size(); }
203
204 /// Returns whether the smallSet is empty
205 bool empty() const { return _elements.size() == 0; }
206
207 /// Returns true if the two sets are identical
208 friend bool operator==( const smallSet &a, const smallSet &b ) {
209 return (a._elements == b._elements);
210 }
211
212 /// Returns true if the two sets are not identical
213 friend bool operator!=( const smallSet &a, const smallSet &b ) {
214 return !(a._elements == b._elements);
215 }
216
217 /// Lexicographical comparison of elements
218 friend bool operator<( const smallSet &a, const smallSet &b ) {
219 return a._elements < b._elements;
220 }
221 };
222
223
224 } // end of namespace dai
225
226
227 #endif