433b7fc18907e10e15fc34ba76675be4c7294113
[libdai.git] / include / dai / smallset.h
1 /* This file is part of libDAI - http://www.libdai.org/
2 *
3 * libDAI is licensed under the terms of the GNU General Public License version
4 * 2, or (at your option) any later version. libDAI is distributed without any
5 * warranty. See the file COPYING for more details.
6 *
7 * Copyright (C) 2002 Martijn Leisink [martijn@mbfys.kun.nl]
8 * Copyright (C) 2006-2009 Joris Mooij [joris dot mooij at libdai dot org]
9 * Copyright (C) 2002-2007 Radboud University Nijmegen, The Netherlands
10 */
11
12
13 /// \file
14 /// \brief Defines the SmallSet<T> class, which represents a set; the implementation is optimized for a small number of elements.
15 /// \todo Check documentation
16
17
18 #ifndef __defined_libdai_smallset_h
19 #define __defined_libdai_smallset_h
20
21
22 #include <vector>
23 #include <algorithm>
24
25
26 namespace dai {
27
28
29 /// Represents a set; the implementation is optimized for a small number of elements.
30 /** SmallSet uses an ordered std::vector<T> to represent a set; this is faster than
31 * using a std::set<T> if the number of elements is small.
32 * \tparam T Should be less-than-comparable.
33 */
34 template <typename T>
35 class SmallSet {
36 private:
37 /// The elements in this set
38 std::vector<T> _elements;
39
40 public:
41 /// @name Constructors and destructors
42 //@{
43 /// Default constructor (construct an empty set)
44 SmallSet() : _elements() {}
45
46 /// Construct a set with one element
47 SmallSet( const T &t ) : _elements() {
48 _elements.push_back( t );
49 }
50
51 /// Construct a set with two elements
52 SmallSet( const T &t1, const T &t2 ) {
53 if( t1 < t2 ) {
54 _elements.push_back( t1 );
55 _elements.push_back( t2 );
56 } else if( t2 < t1 ) {
57 _elements.push_back( t2 );
58 _elements.push_back( t1 );
59 } else
60 _elements.push_back( t1 );
61 }
62
63 /// Construct a SmallSet from a range of elements.
64 /** \tparam TIterator Iterates over instances of type T.
65 * \param begin Points to first element to be added.
66 * \param end Points just beyond last element to be added.
67 * \param sizeHint For efficiency, the number of elements can be speficied by sizeHint.
68 */
69 template <typename TIterator>
70 SmallSet( TIterator begin, TIterator end, size_t sizeHint=0 ) {
71 _elements.reserve( sizeHint );
72 _elements.insert( _elements.begin(), begin, end );
73 std::sort( _elements.begin(), _elements.end() );
74 typename std::vector<T>::iterator new_end = std::unique( _elements.begin(), _elements.end() );
75 _elements.erase( new_end, _elements.end() );
76 }
77 //@}
78
79 /// @name Operators for set-theoretic operations
80 //@{
81 /// Set-minus operator: returns all elements in *this, except those in x
82 SmallSet operator/ ( const SmallSet& x ) const {
83 SmallSet res;
84 std::set_difference( _elements.begin(), _elements.end(), x._elements.begin(), x._elements.end(), inserter( res._elements, res._elements.begin() ) );
85 return res;
86 }
87
88 /// Set-union operator: returns all elements in *this, plus those in x
89 SmallSet operator| ( const SmallSet& x ) const {
90 SmallSet res;
91 std::set_union( _elements.begin(), _elements.end(), x._elements.begin(), x._elements.end(), inserter( res._elements, res._elements.begin() ) );
92 return res;
93 }
94
95 /// Set-intersection operator: returns all elements in *this that are also contained in x
96 SmallSet operator& ( const SmallSet& x ) const {
97 SmallSet res;
98 std::set_intersection( _elements.begin(), _elements.end(), x._elements.begin(), x._elements.end(), inserter( res._elements, res._elements.begin() ) );
99 return res;
100 }
101
102 /// Erases from *this all elements in x
103 SmallSet& operator/= ( const SmallSet& x ) {
104 return (*this = (*this / x));
105 }
106
107 /// Erases one element
108 SmallSet& operator/= ( const T &t ) {
109 typename std::vector<T>::iterator pos = lower_bound( _elements.begin(), _elements.end(), t );
110 if( pos != _elements.end() )
111 if( *pos == t ) // found element, delete it
112 _elements.erase( pos );
113 return *this;
114 }
115
116 /// Adds to *this all elements in x
117 SmallSet& operator|= ( const SmallSet& x ) {
118 return( *this = (*this | x) );
119 }
120
121 /// Adds one element
122 SmallSet& operator|= ( const T& t ) {
123 typename std::vector<T>::iterator pos = lower_bound( _elements.begin(), _elements.end(), t );
124 if( pos == _elements.end() || *pos != t ) // insert it
125 _elements.insert( pos, t );
126 return *this;
127 }
128
129 /// Erases from *this all elements not in x
130 SmallSet& operator&= ( const SmallSet& x ) {
131 return (*this = (*this & x));
132 }
133
134 /// Returns true if *this is a subset of x
135 bool operator<< ( const SmallSet& x ) const {
136 return std::includes( x._elements.begin(), x._elements.end(), _elements.begin(), _elements.end() );
137 }
138
139 /// Returns true if x is a subset of *this
140 bool operator>> ( const SmallSet& x ) const {
141 return std::includes( _elements.begin(), _elements.end(), x._elements.begin(), x._elements.end() );
142 }
143 //@}
144
145 /// @name Queries
146 //@{
147 /// Returns true if *this and x have elements in common
148 bool intersects( const SmallSet& x ) const {
149 return( (*this & x).size() > 0 );
150 }
151
152 /// Returns true if *this contains the element t
153 bool contains( const T &t ) const {
154 return std::binary_search( _elements.begin(), _elements.end(), t );
155 }
156
157 /// Returns number of elements
158 typename std::vector<T>::size_type size() const { return _elements.size(); }
159
160 /// Returns whether the SmallSet is empty
161 bool empty() const { return _elements.size() == 0; }
162 //@}
163
164 /// Constant iterator over the elements
165 typedef typename std::vector<T>::const_iterator const_iterator;
166 /// Iterator over the elements
167 typedef typename std::vector<T>::iterator iterator;
168 /// Constant reverse iterator over the elements
169 typedef typename std::vector<T>::const_reverse_iterator const_reverse_iterator;
170 /// Reverse iterator over the elements
171 typedef typename std::vector<T>::reverse_iterator reverse_iterator;
172
173 /// @name Iterator interface
174 //@{
175 /// Returns iterator that points to the first element
176 iterator begin() { return _elements.begin(); }
177 /// Returns constant iterator that points to the first element
178 const_iterator begin() const { return _elements.begin(); }
179
180 /// Returns iterator that points beyond the last element
181 iterator end() { return _elements.end(); }
182 /// Returns constant iterator that points beyond the last element
183 const_iterator end() const { return _elements.end(); }
184
185 /// Returns reverse iterator that points to the last element
186 reverse_iterator rbegin() { return _elements.rbegin(); }
187 /// Returns constant reverse iterator that points to the last element
188 const_reverse_iterator rbegin() const { return _elements.rbegin(); }
189
190 /// Returns reverse iterator that points beyond the first element
191 reverse_iterator rend() { return _elements.rend(); }
192 /// Returns constant reverse iterator that points beyond the first element
193 const_reverse_iterator rend() const { return _elements.rend(); }
194 //@}
195
196 /// @name Comparison operators
197 //@{
198 /// Returns true if a and b are identical
199 friend bool operator==( const SmallSet &a, const SmallSet &b ) {
200 return (a._elements == b._elements);
201 }
202
203 /// Returns true if a and b are not identical
204 friend bool operator!=( const SmallSet &a, const SmallSet &b ) {
205 return !(a._elements == b._elements);
206 }
207
208 /// Lexicographical comparison of elements
209 friend bool operator<( const SmallSet &a, const SmallSet &b ) {
210 return a._elements < b._elements;
211 }
212 //@}
213 };
214
215
216 } // end of namespace dai
217
218
219 #endif