Sierra Toolkit  Version of the Day
VecSet.hpp
Go to the documentation of this file.
1 /*--------------------------------------------------------------------*/
2 /* Copyright 2002 Sandia Corporation. */
3 /* Under the terms of Contract DE-AC04-94AL85000, there is a */
4 /* non-exclusive license for use of this work by or on behalf */
5 /* of the U.S. Government. Export of this program may require */
6 /* a license from the United States Government. */
7 /*--------------------------------------------------------------------*/
14 #ifndef STK_UTIL_UTIL_vecset_hpp
15 #define STK_UTIL_UTIL_vecset_hpp
16 
17 #include <utility>
18 #include <vector>
19 #include <functional>
20 
21 namespace sierra {
22 
58 template <class Key, class Compare = std::less<Key> >
59 class vecset {
60 private:
61  template <typename T>
62  struct const_key_type_meta_func
63  {
64  typedef const T type;
65  };
66 
67  template <typename T>
68  struct const_key_type_meta_func<T*>
69  {
70  typedef const T* const type;
71  };
72 
73 public:
74 
75  typedef Key key_type;
76  typedef Key value_type;
77  typedef Compare key_compare;
78  typedef Compare value_compare;
79  typedef typename const_key_type_meta_func<Key>::type const_key_type;
80 
81 private:
82 
83  typedef std::vector<key_type> storage ;
84 
85 public:
86 
87  typedef typename storage::allocator_type allocator_type ;
88  typedef typename allocator_type::reference reference ;
89  typedef typename allocator_type::const_reference const_reference ;
90  typedef typename allocator_type::pointer pointer ;
91  typedef typename allocator_type::const_pointer const_pointer ;
92  typedef typename storage::size_type size_type ;
93  typedef typename storage::difference_type difference_type ;
94  typedef typename storage::iterator iterator ;
95  typedef typename storage::const_iterator const_iterator ;
96  typedef typename storage::reverse_iterator reverse_iterator ;
97  typedef typename storage::const_reverse_iterator const_reverse_iterator ;
98 
99  //--------------------------------------------------------------------
100 private:
101 
102  key_compare KeyComp ;
103  storage Storage ;
104 
105 public:
106  //--------------------------------------------------------------------
107 
108  ~vecset()
109  {}
110 
111  vecset() : Storage()
112  {}
113 
114  vecset( const vecset<Key,Compare> & rhs ) : Storage(rhs.Storage)
115  {}
116 
117  vecset<Key,Compare> & operator = ( const vecset<Key,Compare> & rhs ) {
118  Storage = rhs.Storage ;
119  return *this ;
120  }
121 
122  void swap( vecset<Key,Compare> & v ) {
123  Storage.swap( v.Storage );
124  }
125 
126  iterator begin() { return Storage.begin(); }
127  iterator end() { return Storage.end(); }
128  const_iterator begin() const { return Storage.begin(); }
129  const_iterator end() const { return Storage.end(); }
130  reverse_iterator rbegin() { return Storage.rbegin(); }
131  reverse_iterator rend() { return Storage.rend(); }
132  const_reverse_iterator rbegin() const { return Storage.rbegin(); }
133  const_reverse_iterator rend() const { return Storage.rend(); }
134  bool empty() const { return Storage.empty(); }
135  size_type size() const { return Storage.size(); }
136  size_type max_size() const { return Storage.max_size(); }
137 
138  iterator lower_bound( const_key_type & k ) {
139  iterator __first = begin();
140  iterator __last = end();
141 
142  difference_type __len = __last - __first;
143  difference_type __half;
144  iterator __middle;
145 
146  while (__len > 0) {
147  __half = __len >> 1;
148  __middle = __first;
149  __middle += __half;
150  if (KeyComp(*__middle, k)) {
151  __first = __middle;
152  ++__first;
153  __len = __len - __half - 1;
154  }
155  else
156  __len = __half;
157  }
158  return __first;
159  }
160 
161  const_iterator lower_bound( const_key_type & k ) const {
162  const_iterator __first = begin();
163  const_iterator __last = end();
164 
165  difference_type __len = __last - __first;
166  difference_type __half;
167  const_iterator __middle;
168 
169  while (__len > 0) {
170  __half = __len >> 1;
171  __middle = __first;
172  __middle += __half;
173  if (KeyComp(*__middle, k)) {
174  __first = __middle;
175  ++__first;
176  __len = __len - __half - 1;
177  }
178  else
179  __len = __half;
180  }
181  return __first;
182  }
183 
184  iterator upper_bound( const_key_type & k ) {
185  iterator __first = begin();
186  iterator __last = end();
187 
188  difference_type __len = __last - __first;
189  difference_type __half;
190  iterator __middle;
191 
192  while (__len > 0) {
193  __half = __len >> 1;
194  __middle = __first;
195  __middle += __half;
196  if (__comp(k, *__middle))
197  __len = __half;
198  else {
199  __first = __middle;
200  ++__first;
201  __len = __len - __half - 1;
202  }
203  }
204  return __first;
205  }
206 
207 
208  const_iterator upper_bound( const_key_type & k ) const {
209  const_iterator __first = begin();
210  const_iterator __last = end();
211 
212  difference_type __len = __last - __first;
213  difference_type __half;
214  const_iterator __middle;
215 
216  while (__len > 0) {
217  __half = __len >> 1;
218  __middle = __first;
219  __middle += __half;
220  if (__comp(k, *__middle))
221  __len = __half;
222  else {
223  __first = __middle;
224  ++__first;
225  __len = __len - __half - 1;
226  }
227  }
228  return __first;
229  }
230 
231  std::pair<iterator,bool> insert( const value_type & v ) {
232  typename storage::iterator ip = lower_bound(v);
233  // (ip-1)->first < v <= ip->first
234  const bool b = Storage.end() == ip || KeyComp( v , *ip );
235  // b = v != *ip
236  if ( b ) ip = Storage.insert(ip,v);
237  return std::pair<iterator,bool>( ip, b );
238  }
239 
240  void erase( iterator i ) {
241  Storage.erase( Storage.begin() + ( i - begin() ) );
242  }
243 
244  void erase( iterator first , iterator last ) {
245  Storage.erase( Storage.begin() + ( first - begin() ) ,
246  Storage.begin() + ( last - begin() ) );
247  }
248 
249  size_type erase( const_key_type & k ) {
250  typename storage::iterator i = lower_bound(k );
251  return KeyComp( k , *i ) ? 0 : ( Storage.erase(i) , 1 );
252  }
253 
254  void clear() {
255  Storage.clear();
256  }
257 
258  key_compare key_comp() const { return KeyComp ; }
259  value_compare value_comp() const { return KeyComp ; }
260 
261  iterator find( const_key_type & k ) {
262  const iterator i = lower_bound(k);
263  return end() == i || KeyComp( k , *i ) ? end() : i ;
264  }
265 
266  const_iterator find( const_key_type & k ) const {
267  const const_iterator i = lower_bound(k);
268  return end() == i || KeyComp( k , *i ) ? end() : i ;
269  }
270 
271  size_type count( const_key_type & k ) const {
272  const const_iterator i = lower_bound(k);
273  return end() == i || KeyComp( k , *i ) ? 0 : 1 ;
274  }
275 
276  //--------------------------------------------------------------------
277  // Allow conversion to constant vector
278 
279  operator const storage & () const {
280  return Storage ;
281  }
282 
283  void reserve( size_type n ) {
284  Storage.reserve( n );
285  }
286 
287  bool operator == ( const vecset<Key,Compare> & rhs ) const {
288  return Storage == rhs.Storage ;
289  }
290 
291  bool operator != ( const vecset<Key,Compare> & rhs ) const {
292  return Storage != rhs.Storage ;
293  }
294 };
295 
296 }
297 
298 #endif // STK_UTIL_UTIL_vecset_hpp
Definition: Env.cpp:53
Part * find(const PartVector &parts, const std::string &name)
Find a part by name in a collection of parts.
Definition: Part.cpp:22
Vector-based std::set functionality.
Definition: VecSet.hpp:59
bool insert(PartVector &v, Part &part)
Insert a part into a properly ordered collection of parts. Returns true if this is a new insertion...
Definition: Part.cpp:85