Cleanup of BBP code
[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 /// Set-minus operator: returns all elements in *this, except those in x
89 SmallSet operator/ ( const SmallSet& x ) const {
90 SmallSet res;
91 std::set_difference( _elements.begin(), _elements.end(), x._elements.begin(), x._elements.end(), inserter( res._elements, res._elements.begin() ) );
92 return res;
93 }
94
95 /// Set-union operator: returns all elements in *this, plus those in x
96 SmallSet operator| ( const SmallSet& x ) const {
97 SmallSet res;
98 std::set_union( _elements.begin(), _elements.end(), x._elements.begin(), x._elements.end(), inserter( res._elements, res._elements.begin() ) );
99 return res;
100 }
101
102 /// Set-intersection operator: returns all elements in *this that are also contained in x
103 SmallSet operator& ( const SmallSet& x ) const {
104 SmallSet res;
105 std::set_intersection( _elements.begin(), _elements.end(), x._elements.begin(), x._elements.end(), inserter( res._elements, res._elements.begin() ) );
106 return res;
107 }
108
109 /// Erases from *this all elements in x
110 SmallSet& operator/= ( const SmallSet& x ) {
111 return (*this = (*this / x));
112 }
113
114 /// Erases one element
115 SmallSet& operator/= ( const T &t ) {
116 typename std::vector<T>::iterator pos = lower_bound( _elements.begin(), _elements.end(), t );
117 if( pos != _elements.end() )
118 if( *pos == t ) // found element, delete it
119 _elements.erase( pos );
120 return *this;
121 }
122
123 /// Adds to *this all elements in x
124 SmallSet& operator|= ( const SmallSet& x ) {
125 return( *this = (*this | x) );
126 }
127
128 /// Adds one element
129 SmallSet& operator|= ( const T& t ) {
130 typename std::vector<T>::iterator pos = lower_bound( _elements.begin(), _elements.end(), t );
131 if( pos == _elements.end() || *pos != t ) // insert it
132 _elements.insert( pos, t );
133 return *this;
134 }
135
136 /// Erases from *this all elements not in x
137 SmallSet& operator&= ( const SmallSet& x ) {
138 return (*this = (*this & x));
139 }
140
141 /// Returns true if *this is a subset of x
142 bool operator<< ( const SmallSet& x ) const {
143 return std::includes( x._elements.begin(), x._elements.end(), _elements.begin(), _elements.end() );
144 }
145
146 /// Returns true if x is a subset of *this
147 bool operator>> ( const SmallSet& x ) const {
148 return std::includes( _elements.begin(), _elements.end(), x._elements.begin(), x._elements.end() );
149 }
150
151 /// Returns true if *this and x have elements in common
152 bool intersects( const SmallSet& x ) const {
153 return( (*this & x).size() > 0 );
154 }
155
156 /// Returns true if *this contains the element t
157 bool contains( const T &t ) const {
158 return std::binary_search( _elements.begin(), _elements.end(), t );
159 }
160
161 /// Constant iterator over the elements
162 typedef typename std::vector<T>::const_iterator const_iterator;
163 /// Iterator over the elements
164 typedef typename std::vector<T>::iterator iterator;
165 /// Constant reverse iterator over the elements
166 typedef typename std::vector<T>::const_reverse_iterator const_reverse_iterator;
167 /// Reverse iterator over the elements
168 typedef typename std::vector<T>::reverse_iterator reverse_iterator;
169
170 /// Returns iterator that points to the first element
171 iterator begin() { return _elements.begin(); }
172 /// Returns constant iterator that points to the first element
173 const_iterator begin() const { return _elements.begin(); }
174
175 /// Returns iterator that points beyond the last element
176 iterator end() { return _elements.end(); }
177 /// Returns constant iterator that points beyond the last element
178 const_iterator end() const { return _elements.end(); }
179
180 /// Returns reverse iterator that points to the last element
181 reverse_iterator rbegin() { return _elements.rbegin(); }
182 /// Returns constant reverse iterator that points to the last element
183 const_reverse_iterator rbegin() const { return _elements.rbegin(); }
184
185 /// Returns reverse iterator that points beyond the first element
186 reverse_iterator rend() { return _elements.rend(); }
187 /// Returns constant reverse iterator that points beyond the first element
188 const_reverse_iterator rend() const { return _elements.rend(); }
189
190 /// Returns number of elements
191 typename std::vector<T>::size_type size() const { return _elements.size(); }
192
193 /// Returns whether the SmallSet is empty
194 bool empty() const { return _elements.size() == 0; }
195
196 /// Returns true if a and b are identical
197 friend bool operator==( const SmallSet &a, const SmallSet &b ) {
198 return (a._elements == b._elements);
199 }
200
201 /// Returns true if a and b are not identical
202 friend bool operator!=( const SmallSet &a, const SmallSet &b ) {
203 return !(a._elements == b._elements);
204 }
205
206 /// Lexicographical comparison of elements
207 friend bool operator<( const SmallSet &a, const SmallSet &b ) {
208 return a._elements < b._elements;
209 }
210 };
211
212
213 } // end of namespace dai
214
215
216 #endif