FEI Version of the Day
Loading...
Searching...
No Matches
fei_ctg_set.hpp
1
2#ifndef _fei_ctg_set_hpp_
3#define _fei_ctg_set_hpp_
4
5/*--------------------------------------------------------------------*/
6/* Copyright 2006 Sandia Corporation. */
7/* Under the terms of Contract DE-AC04-94AL85000, there is a */
8/* non-exclusive license for use of this work by or on behalf */
9/* of the U.S. Government. Export of this program may require */
10/* a license from the United States Government. */
11/*--------------------------------------------------------------------*/
12
13#include <fei_macros.hpp>
14#include <fei_iostream.hpp>
15
16#include <cstring>
17#include <vector>
18#include <fei_ArrayUtils.hpp>
19
20namespace fei {
21
22const int Set_end_val = -99999999;
23
38template<typename T>
39class ctg_set {
40 public:
42 ctg_set(int alloc_incr=32)
43 : dataptr_(0), len_(0), highwatermark_(0), alloc_incr_(alloc_incr) {}
44
46 ctg_set(const ctg_set<T>& src)
47 : dataptr_(0), len_(0),
48 highwatermark_(src.highwatermark_), alloc_incr_(src.alloc_incr_)
49 {
50 if (highwatermark_>0) {
51 expand_dataptr(highwatermark_);
52 len_ = src.len_;
53 for(int i=0; i<len_; ++i) dataptr_[i] = src.dataptr_[i];
54 }
55 }
56
58 virtual ~ctg_set(){clear();}
59
61 typedef T key_type;
62
65 public:
67 const_iterator() : set_(0),
68 val_(Set_end_val), limit_(Set_end_val), i_(0) {}
69
72 const T& val,
73 int i)
74 : set_(_set),
75 val_(val), limit_(Set_end_val), i_(i)
76 {
77 if (set_ != 0) {
78 if (set_->len_ > 0) {
79 limit_ = set_->dataptr_[i+1]-1;
80 }
81 }
82 }
83
86 : set_(src.set_),
87 val_(src.val_), limit_(src.limit_), i_(src.i_) {}
88
90 virtual ~const_iterator(){}
91
93 const T& operator*() const { return(val_); }
94
97 {
98 if (val_ < limit_) {
99 ++val_;
100 }
101 else {
102 if (i_ < set_->len_-2) {
103 i_ += 2;
104 val_ = set_->dataptr_[i_];
105 limit_ = set_->dataptr_[i_+1]-1;
106 }
107 else {
108 val_ = Set_end_val;
109 limit_ = Set_end_val;
110 }
111 }
112 return(*this);
113 }
114
117 {
118 set_ = src.set_;
119 i_ = src.i_;
120 val_ = src.val_;
121 limit_ = src.limit_;
122 return(*this);
123 }
124
126 bool operator==(const const_iterator& rhs)
127 {
128 return(val_ == rhs.val_);
129 }
130
132 bool operator!=(const const_iterator& rhs)
133 {
134 return(val_ != rhs.val_);
135 }
136
137 private:
138 const ctg_set<T>* set_;
139 T val_;
140 T limit_;
141 int i_;
142 };
143
146 {
147 T val = Set_end_val;
148 if (len_>0) {
149 val = dataptr_[0];
150 }
151 return(const_iterator(this, val, 0));
152 }
153
155 static const_iterator end() { return(const_iterator(0, Set_end_val, 0)); }
156
159 {
160 highwatermark_ = src.highwatermark_;
161 expand_dataptr(highwatermark_);
162 len_ = src.len_;
163
164 return(*this);
165 }
166
168 bool operator!=(const ctg_set<T>& rhs)
169 {
170 if (len_ != rhs.len_) {
171 return(true);
172 }
173
174 for(int i=0; i<len_; ++i) {
175 if (dataptr_[i] != rhs.dataptr_[i]) {
176 return(true);
177 }
178 }
179
180 return(false);
181 }
182
185 int clear()
186 {
187 delete [] dataptr_;
188 dataptr_ = 0;
189 len_ = 0;
190 highwatermark_ = 0;
191 return(0);
192 }
193
198 std::pair<const_iterator,bool> insert(const T& item)
199 {
200 if (len_ > highwatermark_) {
201 FEI_COUT << "error"<<FEI_ENDL;
202 }
203 if (len_ < 1) {
204 highwatermark_ = alloc_incr_;
205 expand_dataptr(highwatermark_);
206 dataptr_[0] = item;
207 dataptr_[1] = item+1;
208 len_ = 2;
209 return(std::pair<const_iterator,bool>(const_iterator(this, item, 0),true));
210 }
211
212 int insertPoint = fei::lowerBound(item, dataptr_, len_);
213
214 if (insertPoint < len_) {
215
216 //dataptr_[insertPoint] is the first entry in dataptr_ that is not
217 //less than item.
218 //The possibilities are:
219 //
220 //1. dataptr_[insertPoint] equals item, so:
221 //
222 // if (insertPoint is an even number) {
223 // return since item is present
224 // }
225 // else {
226 // expand the range below item to include item
227 // (by incrementing dataptr_[insertPoint])
228 // check whether dataptr_[insertPoint] == dataptr_[insertPoint+1]
229 // if so, merge the range at insertPoint-1 with the
230 // range at insertPoint+1
231 // return
232 // }
233 //
234 //2. dataptr_[insertPoint] is greater than item, so:
235 //
236 // if (insertPoint is an even number) {
237 // if (item == dataptr_[insertPoint]-1) {
238 // expand the range at insertPoint to include item, by
239 // simply decrementing dataptr_[insertPoint]
240 // }
241 // else {
242 // insert a new range at insertPoint
243 // }
244 // }
245 // else {
246 // return since item is already present in the range at
247 // dataptr_[insertPoint-1]
248 // }
249 //
250
251 if (dataptr_[insertPoint] == item) {
252 if (insertPoint%2 == 0) {
253 //insertPoint is an even number, so return since item is present
254 return(std::pair<const_iterator,bool>(const_iterator(this, item, insertPoint),false));
255 }
256
257 //Since insertPoint is an odd number, item lies just outside an existing
258 //range so we simply need to add item to the range by incrementing
259 //dataptr_[insertPoint].
260 ++dataptr_[insertPoint];
261
262 //now check whether this newly expanded range should be merged
263 //with the range above it
264 if (insertPoint < len_-1) {
265 if (dataptr_[insertPoint] == dataptr_[insertPoint+1]) {
266 dataptr_[insertPoint] = dataptr_[insertPoint+2];
267 len_ -= 2;
268 int nmove=len_-insertPoint-1;
269 if (nmove > 0) {
270 T* dest = dataptr_+insertPoint+1;
271 T* src = dest+2;
272 std::memmove(dest, src, nmove*sizeof(T));
273 }
274 }
275 }
276
277 return(std::pair<const_iterator,bool>(const_iterator(this, item, insertPoint-1),true));
278 }
279 else {
280 //dataptr_[insertPoint] is greater than item.
281
282 if (insertPoint%2 == 0) {
283 if (item == dataptr_[insertPoint]-1) {
284 --dataptr_[insertPoint];
285 return(std::pair<const_iterator,bool>(const_iterator(this, item, insertPoint),true));
286 }
287 else {
288 //insert a new range at insertPoint
289 int nmove = len_-insertPoint;
290 if (len_+2 > highwatermark_) {
291 highwatermark_ += alloc_incr_;
292 expand_dataptr(highwatermark_);
293 }
294 len_ += 2;
295 if (nmove > 0) {
296 T* dest = dataptr_+insertPoint+2;
297 T* src = dest - 2;
298 std::memmove(dest, src, nmove*sizeof(T));
299 }
300 dataptr_[insertPoint] = item;
301 dataptr_[insertPoint+1] = item+1;
302
303 return(std::pair<const_iterator,bool>(const_iterator(this, item, insertPoint),true));
304 }
305 }
306 else {
307 return(std::pair<const_iterator,bool>(const_iterator(this, item, insertPoint-1),false));
308 }
309 }
310 }
311
312 //If we get to here, insertPoint >= len_, meaning we need to append
313 //a new range.
314 if (len_+2 > highwatermark_) {
315 highwatermark_ += alloc_incr_;
316 expand_dataptr(highwatermark_);
317 }
318 len_ += 2;
319 dataptr_[insertPoint] = item;
320 dataptr_[insertPoint+1] = item+1;
321
322 return(std::pair<const_iterator,bool>(const_iterator(this, item, insertPoint),true));
323 }
324
326 void insert2(const T& item)
327 {
328 if (len_ < 1) {
329 highwatermark_ = alloc_incr_;
330 expand_dataptr(highwatermark_);
331 dataptr_[0] = item;
332 dataptr_[1] = item+1;
333 len_ = 2;
334 return;
335 }
336
337 int insertPoint = fei::lowerBound(item, dataptr_, len_);
338
339 if (insertPoint < len_) {
340
341 //dataptr_[insertPoint] is the first entry in dataptr_ that is not
342 //less than item.
343 //The possibilities are:
344 //
345 //1. insertPoint is an even number:
346 // dataptr_[insertPoint] is the start of an existing range.
347 // diff = dataptr_[insertPoint] - item;
348 // switch(diff) {
349 // case 0 : // item in range, so return
350 // case 1 : // item just below range, so expand range and return
351 // default: // insert new range for item
352 // }
353 //
354 //2. insertPoint is an odd number:
355 // dataptr_[insertPoint] is the end of an existing range
356 // diff = dataptr_[insertPoint] - item;
357 // switch(diff) {
358 // case 0 : {
359 // // item just above range, so expand range
360 // // check whether range should be merged with range above
361 // }
362 // default: // item in range, so return
363 // }
364 //
365
366 if (insertPoint%2==0) {
367 switch(dataptr_[insertPoint]-item) {
368 case 0: break; //item in range
369 case 1: {//expand range downwards
370 --dataptr_[insertPoint];
371 break;
372 }
373 default: {// insert new range for item
374 //insert a new range at insertPoint
375 int nmove = len_-insertPoint;
376 if (len_+2 > highwatermark_) {
377 highwatermark_ += alloc_incr_;
378 expand_dataptr(highwatermark_);
379 }
380 len_ += 2;
381
382 T* dest = dataptr_+insertPoint+2;
383 T* src = dest - 2;
384 std::memmove(dest, src, nmove*sizeof(T));
385
386 dataptr_[insertPoint] = item;
387 dataptr_[insertPoint+1] = item+1;
388 }
389 }
390 }
391 else {//insertPoint is odd number
392 if (dataptr_[insertPoint] == item) {
393 // item just above range, so expand range
394 ++dataptr_[insertPoint];
395
396 // check whether range should be merged with range above
397 if (insertPoint < len_-1 &&
398 dataptr_[insertPoint] == dataptr_[insertPoint+1]) {
399 dataptr_[insertPoint] = dataptr_[insertPoint+2];
400 len_ -= 2;
401 int nmove=len_-insertPoint-1;
402 if (nmove > 0) {
403 T* dest = dataptr_+insertPoint+1;
404 T* src = dest+2;
405 std::memmove(dest, src, nmove*sizeof(T));
406 }
407 }
408 }//end if (dataptr_[insertPoint]==item)...
409 // else do nothing, item is already in existing range
410 }
411
412 return;
413 } // end if (insertPoint < len_)...
414
415 //If we get to here, insertPoint >= len_, meaning we need to append
416 //a new range.
417 if (len_+2 > highwatermark_) {
418 highwatermark_ += alloc_incr_;
419 expand_dataptr(highwatermark_);
420 }
421 dataptr_[insertPoint] = item;
422 dataptr_[insertPoint+1] = item+1;
423 len_ += 2;
424 }
425
427 int insert2_dense_group(const T& starting_index, int group_size)
428 {
429 for(int i=0; i<group_size; ++i) {
430 insert2(starting_index+i);
431 }
432
433 return(0);
434 }
435
437 const_iterator find(const T& item)
438 {
439 if (len_ < 1) {
440 return(const_iterator(0, Set_end_val, 0));
441 }
442
443 int insertPoint = -1;
444 int index = fei::binarySearch(item, dataptr_, len_, insertPoint);
445
446 if (index < 0) {
447 if (insertPoint%2==0) {
448 return(end());
449 }
450 else {
451 return(const_iterator(this, item, insertPoint-1));
452 }
453 }
454
455 if (index%2==0) {
456 return( const_iterator(this, item, index) );
457 }
458
459 return(const_iterator(0, Set_end_val, 0));
460 }
461
465 int copy_to_array(int len, T* items) const
466 {
467 const_iterator iter = begin(), iter_end = end();
468 int offset = 0;
469 for(; iter != iter_end; ++iter) {
470 if (offset >= len) {
471 break;
472 }
473
474 items[offset++] = *iter;
475 }
476
477 return(0);
478 }
479
481 int copy_to_vector(std::vector<T>& items) const
482 {
483 int sz = size();
484 items.resize(sz);
485 T* itemsPtr = &(items[0]);
486 return(copy_to_array(sz, itemsPtr));
487 }
488
490 int size() const
491 {
492 int setsize = 0;
493 int offset = 0;
494 while(offset<(len_-1)) {
495 setsize += dataptr_[offset+1]-dataptr_[offset];
496 offset += 2;
497 }
498
499 return(setsize);
500 }
501
502 private:
503 void expand_dataptr(int newlen)
504 {
505 //on entry to this function, dataptr_ has length 'len_'.
506 //we assume newlen is greater than len_.
507 //after we create newptr with length 'newlen', we copy
508 //len_ positions from dataptr_ to newptr.
509
510 T* newptr = new T[newlen];
511 for(int i=0; i<len_; ++i) newptr[i] = dataptr_[i];
512 delete [] dataptr_;
513 dataptr_ = newptr;
514 }
515
516 friend class const_iterator;
517 T* dataptr_;
518 int len_;
519 int highwatermark_;
520 int alloc_incr_;
521};//class ctg_set
522
523}//namespace fei
524
525#endif
526
const T & operator*() const
Definition: fei_ctg_set.hpp:93
const_iterator & operator=(const const_iterator &src)
const_iterator(const const_iterator &src)
Definition: fei_ctg_set.hpp:85
bool operator==(const const_iterator &rhs)
const_iterator(const ctg_set< T > *_set, const T &val, int i)
Definition: fei_ctg_set.hpp:71
bool operator!=(const const_iterator &rhs)
const_iterator & operator++()
Definition: fei_ctg_set.hpp:96
bool operator!=(const ctg_set< T > &rhs)
int copy_to_vector(std::vector< T > &items) const
ctg_set(const ctg_set< T > &src)
Definition: fei_ctg_set.hpp:46
int insert2_dense_group(const T &starting_index, int group_size)
ctg_set< T > & operator=(const ctg_set< T > &src)
int size() const
ctg_set(int alloc_incr=32)
Definition: fei_ctg_set.hpp:42
static const_iterator end()
std::pair< const_iterator, bool > insert(const T &item)
const_iterator find(const T &item)
int copy_to_array(int len, T *items) const
virtual ~ctg_set()
Definition: fei_ctg_set.hpp:58
void insert2(const T &item)
const_iterator begin() const
int lowerBound(const T &item, const T *list, int len)
int binarySearch(const T &item, const T *list, int len)