FEI Package Browser (Single Doxygen Collection)  Version of the Day
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
fei_ctg_set.hpp
Go to the documentation of this file.
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 
20 namespace fei {
21 
22 const int Set_end_val = -99999999;
23 
38 template<typename T>
39 class 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),
49  {
50  if (highwatermark_>0) {
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:
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;
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_;
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  {
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) {
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_) {
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_) {
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) {
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_) {
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_) {
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;
518  int len_;
521 };//class ctg_set
522 
523 }//namespace fei
524 
525 #endif
526 
#define FEI_COUT
int size() const
int insert2_dense_group(const T &starting_index, int group_size)
int copy_to_vector(std::vector< T > &items) const
ctg_set(int alloc_incr=32)
Definition: fei_ctg_set.hpp:42
const_iterator find(const T &item)
const_iterator(const ctg_set< T > *_set, const T &val, int i)
Definition: fei_ctg_set.hpp:71
int binarySearch(const T &item, const T *list, int len)
int lowerBound(const T &item, const T *list, int len)
const_iterator begin() const
bool operator!=(const ctg_set< T > &rhs)
void insert2(const T &item)
ctg_set(const ctg_set< T > &src)
Definition: fei_ctg_set.hpp:46
const_iterator & operator=(const const_iterator &src)
const_iterator(const const_iterator &src)
Definition: fei_ctg_set.hpp:85
int copy_to_array(int len, T *items) const
#define FEI_ENDL
bool operator!=(const const_iterator &rhs)
const T & operator*() const
Definition: fei_ctg_set.hpp:93
static const_iterator end()
std::pair< const_iterator, bool > insert(const T &item)
bool operator==(const const_iterator &rhs)
void expand_dataptr(int newlen)
const_iterator & operator++()
Definition: fei_ctg_set.hpp:96
friend class const_iterator
const int Set_end_val
Definition: fei_ctg_set.hpp:22
const ctg_set< T > * set_
virtual ~ctg_set()
Definition: fei_ctg_set.hpp:58
ctg_set< T > & operator=(const ctg_set< T > &src)