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