Merge branch 'joris'
[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; the implementation is optimized for a small number of elements.
42 /** SmallSet uses an ordered std::vector<T> to represent a set; this is faster than
43 * using a std::set<T> if the number of elements is small.
44 * \tparam T 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 (construct an empty set)
54 SmallSet() : _elements() {}
55
56 /// Construct a set with one element
57 SmallSet( const T &t ) : _elements() {
58 _elements.push_back( t );
59 }
60
61 /// Construct a set with two elements
62 SmallSet( const T &t1, const T &t2 ) {
63 if( t1 < t2 ) {
64 _elements.push_back( t1 );
65 _elements.push_back( t2 );
66 } else if( t2 < t1 ) {
67 _elements.push_back( t2 );
68 _elements.push_back( t1 );
69 } else
70 _elements.push_back( t1 );
71 }
72
73 /// Construct a SmallSet from a range of elements.
74 /** \tparam TIterator Iterates over instances of 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 TIterator>
80 SmallSet( TIterator begin, TIterator 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 /// Set-minus operator: returns all elements in *this, except those in x
100 SmallSet operator/ ( const SmallSet& x ) const {
101 SmallSet res;
102 std::set_difference( _elements.begin(), _elements.end(), x._elements.begin(), x._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 x
107 SmallSet operator| ( const SmallSet& x ) const {
108 SmallSet res;
109 std::set_union( _elements.begin(), _elements.end(), x._elements.begin(), x._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 x
114 SmallSet operator& ( const SmallSet& x ) const {
115 SmallSet res;
116 std::set_intersection( _elements.begin(), _elements.end(), x._elements.begin(), x._elements.end(), inserter( res._elements, res._elements.begin() ) );
117 return res;
118 }
119
120 /// Erases from *this all elements in x
121 SmallSet& operator/= ( const SmallSet& x ) {
122 return (*this = (*this / x));
123 }
124
125 /// Erases one element
126 SmallSet& operator/= ( const T &t ) {
127 typename std::vector<T>::iterator pos = lower_bound( _elements.begin(), _elements.end(), t );
128 if( pos != _elements.end() )
129 if( *pos == t ) // found element, delete it
130 _elements.erase( pos );
131 return *this;
132 }
133
134 /// Adds to *this all elements in x
135 SmallSet& operator|= ( const SmallSet& x ) {
136 return( *this = (*this | x) );
137 }
138
139 /// Adds one element
140 SmallSet& operator|= ( const T& t ) {
141 typename std::vector<T>::iterator pos = lower_bound( _elements.begin(), _elements.end(), t );
142 if( pos == _elements.end() || *pos != t ) // insert it
143 _elements.insert( pos, t );
144 return *this;
145 }
146
147 /// Erases from *this all elements not in x
148 SmallSet& operator&= ( const SmallSet& x ) {
149 return (*this = (*this & x));
150 }
151
152 /// Returns true if *this is a subset of x
153 bool operator<< ( const SmallSet& x ) const {
154 return std::includes( x._elements.begin(), x._elements.end(), _elements.begin(), _elements.end() );
155 }
156
157 /// Returns true if x is a subset of *this
158 bool operator>> ( const SmallSet& x ) const {
159 return std::includes( _elements.begin(), _elements.end(), x._elements.begin(), x._elements.end() );
160 }
161
162 /// Returns true if *this and x have elements in common
163 bool intersects( const SmallSet& x ) const {
164 return( (*this & x).size() > 0 );
165 }
166
167 /// Returns true if *this contains the element t
168 bool contains( const T &t ) const {
169 return std::binary_search( _elements.begin(), _elements.end(), t );
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 a and b are identical
208 friend bool operator==( const SmallSet &a, const SmallSet &b ) {
209 return (a._elements == b._elements);
210 }
211
212 /// Returns true if a and b 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