libDAI
smallset.h
Go to the documentation of this file.
1 /* This file is part of libDAI - http://www.libdai.org/
2  *
3  * Copyright (c) 2006-2011, The libDAI authors. All rights reserved.
4  *
5  * Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
6  */
7 
8 
11 
12 
13 #ifndef __defined_libdai_smallset_h
14 #define __defined_libdai_smallset_h
15 
16 
17 #include <vector>
18 #include <algorithm>
19 #include <iostream>
20 
21 
22 namespace dai {
23 
24 
26 
30 template <typename T>
31 class SmallSet {
32  private:
34  std::vector<T> _elements;
35 
36  public:
38 
39 
41 
43  SmallSet( const T &t ) : _elements() {
44  _elements.push_back( t );
45  }
46 
48  SmallSet( const T &t1, const T &t2 ) {
49  if( t1 < t2 ) {
50  _elements.push_back( t1 );
51  _elements.push_back( t2 );
52  } else if( t2 < t1 ) {
53  _elements.push_back( t2 );
54  _elements.push_back( t1 );
55  } else
56  _elements.push_back( t1 );
57  }
58 
60 
66  template <typename TIterator>
67  SmallSet( TIterator begin, TIterator end, size_t sizeHint ) {
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  }
75 
77 
78 
79  SmallSet& insert( const T& t ) {
80  typename SmallSet<T>::iterator it = std::lower_bound( _elements.begin(), _elements.end(), t );
81  if( (it == _elements.end()) || (*it != t) )
82  _elements.insert( it, t );
83  return *this;
84  }
85 
87  SmallSet& erase( const T& t ) {
88  return (*this /= t);
89  }
90 
92  SmallSet operator/ ( const SmallSet& x ) const {
93  SmallSet res;
94  std::set_difference( _elements.begin(), _elements.end(), x._elements.begin(), x._elements.end(), inserter( res._elements, res._elements.begin() ) );
95  return res;
96  }
97 
99  SmallSet operator| ( const SmallSet& x ) const {
100  SmallSet res;
101  std::set_union( _elements.begin(), _elements.end(), x._elements.begin(), x._elements.end(), inserter( res._elements, res._elements.begin() ) );
102  return res;
103  }
104 
106  SmallSet operator& ( const SmallSet& x ) const {
107  SmallSet res;
108  std::set_intersection( _elements.begin(), _elements.end(), x._elements.begin(), x._elements.end(), inserter( res._elements, res._elements.begin() ) );
109  return res;
110  }
111 
114  return (*this = (*this / x));
115  }
116 
118  SmallSet& operator/= ( const T &t ) {
119  typename std::vector<T>::iterator pos = lower_bound( _elements.begin(), _elements.end(), t );
120  if( pos != _elements.end() )
121  if( *pos == t ) // found element, delete it
122  _elements.erase( pos );
123  return *this;
124  }
125 
128  return( *this = (*this | x) );
129  }
130 
132  SmallSet& operator|= ( const T& t ) {
133  typename std::vector<T>::iterator pos = lower_bound( _elements.begin(), _elements.end(), t );
134  if( pos == _elements.end() || *pos != t ) // insert it
135  _elements.insert( pos, t );
136  return *this;
137  }
138 
141  return (*this = (*this & x));
142  }
143 
145  bool operator<< ( const SmallSet& x ) const {
146  return std::includes( x._elements.begin(), x._elements.end(), _elements.begin(), _elements.end() );
147  }
148 
150  bool operator>> ( const SmallSet& x ) const {
151  return std::includes( _elements.begin(), _elements.end(), x._elements.begin(), x._elements.end() );
152  }
154 
156 
157 
158  bool intersects( const SmallSet& x ) const {
159  return( (*this & x).size() > 0 );
160  }
161 
163  bool contains( const T &t ) const {
164  return std::binary_search( _elements.begin(), _elements.end(), t );
165  }
166 
168  typename std::vector<T>::size_type size() const { return _elements.size(); }
169 
171  bool empty() const { return _elements.size() == 0; }
172 
174  std::vector<T>& elements() { return _elements; }
175 
177  const std::vector<T>& elements() const { return _elements; }
179 
181  typedef typename std::vector<T>::const_iterator const_iterator;
183  typedef typename std::vector<T>::iterator iterator;
185  typedef typename std::vector<T>::const_reverse_iterator const_reverse_iterator;
187  typedef typename std::vector<T>::reverse_iterator reverse_iterator;
188 
190 
191 
192  iterator begin() { return _elements.begin(); }
194  const_iterator begin() const { return _elements.begin(); }
195 
197  iterator end() { return _elements.end(); }
199  const_iterator end() const { return _elements.end(); }
200 
202  reverse_iterator rbegin() { return _elements.rbegin(); }
204  const_reverse_iterator rbegin() const { return _elements.rbegin(); }
205 
207  reverse_iterator rend() { return _elements.rend(); }
209  const_reverse_iterator rend() const { return _elements.rend(); }
210 
212  T& front() { return _elements.front(); }
214  const T& front() const { return _elements.front(); }
215 
217  T& back() { return _elements.back(); }
219  const T& back() const { return _elements.back(); }
221 
223 
224 
225  friend bool operator==( const SmallSet &a, const SmallSet &b ) {
226  return (a._elements == b._elements);
227  }
228 
230  friend bool operator!=( const SmallSet &a, const SmallSet &b ) {
231  return !(a._elements == b._elements);
232  }
233 
235  friend bool operator<( const SmallSet &a, const SmallSet &b ) {
236  return a._elements < b._elements;
237  }
239 
241 
242 
243  friend std::ostream& operator << ( std::ostream& os, const SmallSet& x ) {
244  os << "{";
245  for( typename std::vector<T>::const_iterator it = x.begin(); it != x.end(); it++ )
246  os << (it != x.begin() ? ", " : "") << *it;
247  os << "}";
248  return os;
249  }
251 };
252 
253 
254 } // end of namespace dai
255 
256 
257 #endif