Updated copyright headers
[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 SmallSet<T> class
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 std::vector<T> to represent a set; this is faster than
30 * using a std::set<T> 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 /// Default constructor (construct an empty set)
41 SmallSet() : _elements() {}
42
43 /// Construct a set with one element
44 SmallSet( const T &t ) : _elements() {
45 _elements.push_back( t );
46 }
47
48 /// Construct a set with two elements
49 SmallSet( const T &t1, const T &t2 ) {
50 if( t1 < t2 ) {
51 _elements.push_back( t1 );
52 _elements.push_back( t2 );
53 } else if( t2 < t1 ) {
54 _elements.push_back( t2 );
55 _elements.push_back( t1 );
56 } else
57 _elements.push_back( t1 );
58 }
59
60 /// Construct a SmallSet from a range of elements.
61 /** \tparam TIterator Iterates over instances of type T.
62 * \param begin Points to first element to be added.
63 * \param end Points just beyond last element to be added.
64 * \param sizeHint For efficiency, the number of elements can be speficied by sizeHint.
65 */
66 template <typename TIterator>
67 SmallSet( TIterator begin, TIterator end, size_t sizeHint=0 ) {
68 _elements.reserve( sizeHint );
69 _elements.insert( _elements.begin(), begin, end );
70 std::sort( _elements.begin(), _elements.end() );
71 typename std::vector<T>::iterator new_end = std::unique( _elements.begin(), _elements.end() );
72 _elements.erase( new_end, _elements.end() );
73 }
74
75 /// Set-minus operator: returns all elements in *this, except those in x
76 SmallSet operator/ ( const SmallSet& x ) const {
77 SmallSet res;
78 std::set_difference( _elements.begin(), _elements.end(), x._elements.begin(), x._elements.end(), inserter( res._elements, res._elements.begin() ) );
79 return res;
80 }
81
82 /// Set-union operator: returns all elements in *this, plus those in x
83 SmallSet operator| ( const SmallSet& x ) const {
84 SmallSet res;
85 std::set_union( _elements.begin(), _elements.end(), x._elements.begin(), x._elements.end(), inserter( res._elements, res._elements.begin() ) );
86 return res;
87 }
88
89 /// Set-intersection operator: returns all elements in *this that are also contained in x
90 SmallSet operator& ( const SmallSet& x ) const {
91 SmallSet res;
92 std::set_intersection( _elements.begin(), _elements.end(), x._elements.begin(), x._elements.end(), inserter( res._elements, res._elements.begin() ) );
93 return res;
94 }
95
96 /// Erases from *this all elements in x
97 SmallSet& operator/= ( const SmallSet& x ) {
98 return (*this = (*this / x));
99 }
100
101 /// Erases one element
102 SmallSet& operator/= ( const T &t ) {
103 typename std::vector<T>::iterator pos = lower_bound( _elements.begin(), _elements.end(), t );
104 if( pos != _elements.end() )
105 if( *pos == t ) // found element, delete it
106 _elements.erase( pos );
107 return *this;
108 }
109
110 /// Adds to *this all elements in x
111 SmallSet& operator|= ( const SmallSet& x ) {
112 return( *this = (*this | x) );
113 }
114
115 /// Adds one element
116 SmallSet& operator|= ( const T& t ) {
117 typename std::vector<T>::iterator pos = lower_bound( _elements.begin(), _elements.end(), t );
118 if( pos == _elements.end() || *pos != t ) // insert it
119 _elements.insert( pos, t );
120 return *this;
121 }
122
123 /// Erases from *this all elements not in x
124 SmallSet& operator&= ( const SmallSet& x ) {
125 return (*this = (*this & x));
126 }
127
128 /// Returns true if *this is a subset of x
129 bool operator<< ( const SmallSet& x ) const {
130 return std::includes( x._elements.begin(), x._elements.end(), _elements.begin(), _elements.end() );
131 }
132
133 /// Returns true if x is a subset of *this
134 bool operator>> ( const SmallSet& x ) const {
135 return std::includes( _elements.begin(), _elements.end(), x._elements.begin(), x._elements.end() );
136 }
137
138 /// Returns true if *this and x have elements in common
139 bool intersects( const SmallSet& x ) const {
140 return( (*this & x).size() > 0 );
141 }
142
143 /// Returns true if *this contains the element t
144 bool contains( const T &t ) const {
145 return std::binary_search( _elements.begin(), _elements.end(), t );
146 }
147
148 /// Constant iterator over the elements
149 typedef typename std::vector<T>::const_iterator const_iterator;
150 /// Iterator over the elements
151 typedef typename std::vector<T>::iterator iterator;
152 /// Constant reverse iterator over the elements
153 typedef typename std::vector<T>::const_reverse_iterator const_reverse_iterator;
154 /// Reverse iterator over the elements
155 typedef typename std::vector<T>::reverse_iterator reverse_iterator;
156
157 /// Returns iterator that points to the first element
158 iterator begin() { return _elements.begin(); }
159 /// Returns constant iterator that points to the first element
160 const_iterator begin() const { return _elements.begin(); }
161
162 /// Returns iterator that points beyond the last element
163 iterator end() { return _elements.end(); }
164 /// Returns constant iterator that points beyond the last element
165 const_iterator end() const { return _elements.end(); }
166
167 /// Returns reverse iterator that points to the last element
168 reverse_iterator rbegin() { return _elements.rbegin(); }
169 /// Returns constant reverse iterator that points to the last element
170 const_reverse_iterator rbegin() const { return _elements.rbegin(); }
171
172 /// Returns reverse iterator that points beyond the first element
173 reverse_iterator rend() { return _elements.rend(); }
174 /// Returns constant reverse iterator that points beyond the first element
175 const_reverse_iterator rend() const { return _elements.rend(); }
176
177 /// Returns number of elements
178 typename std::vector<T>::size_type size() const { return _elements.size(); }
179
180 /// Returns whether the SmallSet is empty
181 bool empty() const { return _elements.size() == 0; }
182
183 /// Returns true if a and b are identical
184 friend bool operator==( const SmallSet &a, const SmallSet &b ) {
185 return (a._elements == b._elements);
186 }
187
188 /// Returns true if a and b are not identical
189 friend bool operator!=( const SmallSet &a, const SmallSet &b ) {
190 return !(a._elements == b._elements);
191 }
192
193 /// Lexicographical comparison of elements
194 friend bool operator<( const SmallSet &a, const SmallSet &b ) {
195 return a._elements < b._elements;
196 }
197 };
198
199
200 } // end of namespace dai
201
202
203 #endif