fei_ctg_set.hpp

00001 
00002 #ifndef _fei_ctg_set_hpp_
00003 #define _fei_ctg_set_hpp_
00004 
00005 /*--------------------------------------------------------------------*/
00006 /*    Copyright 2006 Sandia Corporation.                              */
00007 /*    Under the terms of Contract DE-AC04-94AL85000, there is a       */
00008 /*    non-exclusive license for use of this work by or on behalf      */
00009 /*    of the U.S. Government.  Export of this program may require     */
00010 /*    a license from the United States Government.                    */
00011 /*--------------------------------------------------------------------*/
00012 
00013 #include <fei_macros.hpp>
00014 #include <fei_iostream.hpp>
00015 
00016 #include <cstring>
00017 #include <vector>
00018 #include <fei_ArrayUtils.hpp>
00019 
00020 namespace fei {
00021 
00022 const int Set_end_val = -99999999;
00023 
00038 template<typename T>
00039 class ctg_set {
00040   public:
00042   ctg_set(int alloc_incr=32)
00043     : dataptr_(0), len_(0), highwatermark_(0), alloc_incr_(alloc_incr) {}
00044 
00046   ctg_set(const ctg_set<T>& src)
00047     : dataptr_(0), len_(0),
00048       highwatermark_(src.highwatermark_), alloc_incr_(src.alloc_incr_)
00049     {
00050       if (highwatermark_>0) {
00051         expand_dataptr(highwatermark_);
00052         len_ = src.len_;
00053         for(int i=0; i<len_; ++i) dataptr_[i] = src.dataptr_[i];
00054       }
00055     }
00056 
00058   virtual ~ctg_set(){clear();}
00059 
00061   typedef T key_type;
00062 
00064   class const_iterator {
00065   public:
00067     const_iterator() : set_(0),
00068       val_(Set_end_val), limit_(Set_end_val), i_(0) {}
00069 
00071     const_iterator(const ctg_set<T>* _set,
00072        const T& val,
00073        int i)
00074       : set_(_set),
00075       val_(val), limit_(Set_end_val), i_(i)
00076       {
00077   if (set_ != 0) {
00078     if (set_->len_ > 0) {
00079       limit_ = set_->dataptr_[i+1]-1;
00080     }
00081   }
00082       }
00083 
00085     const_iterator(const const_iterator& src)
00086       : set_(src.set_),
00087        val_(src.val_), limit_(src.limit_), i_(src.i_) {}
00088 
00090     virtual ~const_iterator(){}
00091 
00093     const T& operator*() const { return(val_); }
00094 
00096     const_iterator& operator++()
00097       {
00098   if (val_ < limit_) {
00099     ++val_;
00100   }
00101   else {
00102     if (i_ < set_->len_-2) {
00103       i_ += 2;
00104       val_ = set_->dataptr_[i_];
00105       limit_ = set_->dataptr_[i_+1]-1;
00106     }
00107     else {
00108       val_ = Set_end_val;
00109       limit_ = Set_end_val;
00110     }
00111   }
00112   return(*this);
00113       }
00114 
00116     const_iterator& operator=(const const_iterator& src)
00117       {
00118   set_ = src.set_;
00119   i_ = src.i_;
00120   val_ = src.val_;
00121   limit_ = src.limit_;
00122   return(*this);
00123       }
00124 
00126     bool operator==(const const_iterator& rhs)
00127       {
00128   return(val_ == rhs.val_);
00129       }
00130 
00132     bool operator!=(const const_iterator& rhs)
00133       {
00134   return(val_ != rhs.val_);
00135       }
00136 
00137   private:
00138     const ctg_set<T>* set_;
00139     T val_;
00140     T limit_;
00141     int i_;
00142   };
00143 
00145   const_iterator begin() const
00146     {
00147       T val = Set_end_val;
00148       if (len_>0) {
00149   val = dataptr_[0];
00150       }
00151       return(const_iterator(this, val, 0));
00152     }
00153 
00155   static const_iterator end() { return(const_iterator(0, Set_end_val, 0)); }
00156 
00158   ctg_set<T>& operator=(const ctg_set<T>& src)
00159     {
00160       highwatermark_ = src.highwatermark_;
00161       expand_dataptr(highwatermark_);
00162       len_ = src.len_;
00163 
00164       return(*this);
00165     }
00166 
00168   bool operator!=(const ctg_set<T>& rhs)
00169   {
00170     if (len_ != rhs.len_) {
00171       return(true);
00172     }
00173 
00174     for(int i=0; i<len_; ++i) {
00175       if (dataptr_[i] != rhs.dataptr_[i]) {
00176         return(true);
00177       }
00178     }
00179 
00180     return(false);
00181   }
00182 
00185   int clear()
00186   {
00187     delete [] dataptr_;
00188     dataptr_ = 0;
00189     len_ = 0;
00190     highwatermark_ = 0;
00191     return(0);
00192   }
00193 
00198   std::pair<const_iterator,bool> insert(const T& item)
00199   {
00200     if (len_ > highwatermark_) {
00201       FEI_COUT << "error"<<FEI_ENDL;
00202     }
00203     if (len_ < 1) {
00204       highwatermark_ = alloc_incr_;
00205       expand_dataptr(highwatermark_);
00206       dataptr_[0] = item;
00207       dataptr_[1] = item+1;
00208       len_ = 2;
00209       return(std::pair<const_iterator,bool>(const_iterator(this, item, 0),true));
00210     }
00211 
00212     int insertPoint = fei::lowerBound(item, dataptr_, len_);
00213 
00214     if (insertPoint < len_) {
00215 
00216       //dataptr_[insertPoint] is the first entry in dataptr_ that is not
00217       //less than item.
00218       //The possibilities are:
00219       //
00220       //1. dataptr_[insertPoint] equals item, so:
00221       //
00222       //     if (insertPoint is an even number) {
00223       //       return since item is present
00224       //     }
00225       //     else {
00226       //       expand the range below item to include item
00227       //       (by incrementing dataptr_[insertPoint])
00228       //       check whether dataptr_[insertPoint] == dataptr_[insertPoint+1]
00229       //       if so, merge the range at insertPoint-1 with the
00230       //       range at insertPoint+1
00231       //       return
00232       //     }
00233       //
00234       //2. dataptr_[insertPoint] is greater than item, so:
00235       //
00236       //     if (insertPoint is an even number) {
00237       //       if (item == dataptr_[insertPoint]-1) {
00238       //         expand the range at insertPoint to include item, by
00239       //         simply decrementing dataptr_[insertPoint]
00240       //       }
00241       //       else {
00242       //         insert a new range at insertPoint
00243       //       }
00244       //     }
00245       //     else {
00246       //       return since item is already present in the range at
00247       //       dataptr_[insertPoint-1]
00248       //     }
00249       //
00250 
00251       if (dataptr_[insertPoint] == item) {
00252   if (insertPoint%2 == 0) {
00253     //insertPoint is an even number, so return since item is present
00254     return(std::pair<const_iterator,bool>(const_iterator(this, item, insertPoint),false));
00255   }
00256 
00257   //Since insertPoint is an odd number, item lies just outside an existing
00258   //range so we simply need to add item to the range by incrementing
00259   //dataptr_[insertPoint].
00260   ++dataptr_[insertPoint];
00261 
00262   //now check whether this newly expanded range should be merged
00263   //with the range above it
00264   if (insertPoint < len_-1) {
00265     if (dataptr_[insertPoint] == dataptr_[insertPoint+1]) {
00266       dataptr_[insertPoint] = dataptr_[insertPoint+2];
00267       len_ -= 2;
00268       int nmove=len_-insertPoint-1;
00269       if (nmove > 0) {
00270         T* dest = dataptr_+insertPoint+1;
00271         T* src =  dest+2;
00272         std::memmove(dest, src, nmove*sizeof(T));
00273       }
00274     }
00275   }
00276 
00277   return(std::pair<const_iterator,bool>(const_iterator(this, item, insertPoint-1),true));
00278       }
00279       else {
00280   //dataptr_[insertPoint] is greater than item.
00281 
00282   if (insertPoint%2 == 0) {
00283     if (item == dataptr_[insertPoint]-1) {
00284       --dataptr_[insertPoint];
00285       return(std::pair<const_iterator,bool>(const_iterator(this, item, insertPoint),true));
00286     }
00287     else {
00288       //insert a new range at insertPoint
00289       int nmove = len_-insertPoint;
00290       if (len_+2 > highwatermark_) {
00291         highwatermark_ += alloc_incr_;
00292         expand_dataptr(highwatermark_);
00293       }
00294       len_ += 2;
00295       if (nmove > 0) {
00296         T* dest = dataptr_+insertPoint+2;
00297         T* src = dest - 2;
00298         std::memmove(dest, src, nmove*sizeof(T));
00299       }
00300       dataptr_[insertPoint] = item;
00301       dataptr_[insertPoint+1] = item+1;
00302 
00303       return(std::pair<const_iterator,bool>(const_iterator(this, item, insertPoint),true));
00304     }
00305   }
00306   else {
00307     return(std::pair<const_iterator,bool>(const_iterator(this, item, insertPoint-1),false));
00308   }
00309       }
00310     }
00311 
00312     //If we get to here, insertPoint >= len_, meaning we need to append
00313     //a new range.
00314     if (len_+2 > highwatermark_) {
00315       highwatermark_ += alloc_incr_;
00316       expand_dataptr(highwatermark_);
00317     }
00318     len_ += 2;
00319     dataptr_[insertPoint] = item;
00320     dataptr_[insertPoint+1] = item+1;
00321 
00322     return(std::pair<const_iterator,bool>(const_iterator(this, item, insertPoint),true));
00323   }
00324 
00326   void insert2(const T& item)
00327   {
00328     if (len_ < 1) {
00329       highwatermark_ = alloc_incr_;
00330       expand_dataptr(highwatermark_);
00331       dataptr_[0] = item;
00332       dataptr_[1] = item+1;
00333       len_ = 2;
00334       return;
00335     }
00336 
00337     int insertPoint = fei::lowerBound(item, dataptr_, len_);
00338 
00339     if (insertPoint < len_) {
00340 
00341       //dataptr_[insertPoint] is the first entry in dataptr_ that is not
00342       //less than item.
00343       //The possibilities are:
00344       //
00345       //1. insertPoint is an even number:
00346       //   dataptr_[insertPoint] is the start of an existing range.
00347       //   diff = dataptr_[insertPoint] - item;
00348       //   switch(diff) {
00349       //    case 0 : //  item in range, so return
00350       //    case 1 : //  item just below range, so expand range and return
00351       //    default: //  insert new range for item
00352       //   }
00353       //
00354       //2. insertPoint is an odd number:
00355       //   dataptr_[insertPoint] is the end of an existing range
00356       //   diff = dataptr_[insertPoint] - item;
00357       //   switch(diff) {
00358       //    case 0 : {
00359       //      // item just above range, so expand range
00360       //      // check whether range should be merged with range above
00361       //    }
00362       //    default: // item in range, so return
00363       //   }
00364       //
00365 
00366       if (insertPoint%2==0) {
00367         switch(dataptr_[insertPoint]-item) {
00368           case 0: break; //item in range
00369           case 1: {//expand range downwards
00370             --dataptr_[insertPoint];
00371             break;
00372           }
00373           default: {// insert new range for item
00374             //insert a new range at insertPoint
00375             int nmove = len_-insertPoint;
00376             if (len_+2 > highwatermark_) {
00377               highwatermark_ += alloc_incr_;
00378               expand_dataptr(highwatermark_);
00379             }
00380             len_ += 2;
00381 
00382             T* dest = dataptr_+insertPoint+2;
00383             T* src = dest - 2;
00384             std::memmove(dest, src, nmove*sizeof(T));
00385 
00386             dataptr_[insertPoint] = item;
00387             dataptr_[insertPoint+1] = item+1;
00388           }
00389         }
00390       }
00391       else {//insertPoint is odd number
00392         if (dataptr_[insertPoint] == item) {
00393           // item just above range, so expand range
00394           ++dataptr_[insertPoint];
00395 
00396           // check whether range should be merged with range above
00397           if (insertPoint < len_-1 &&
00398               dataptr_[insertPoint] == dataptr_[insertPoint+1]) {
00399             dataptr_[insertPoint] = dataptr_[insertPoint+2];
00400             len_ -= 2;
00401             int nmove=len_-insertPoint-1;
00402             if (nmove > 0) {
00403               T* dest = dataptr_+insertPoint+1;
00404               T* src =  dest+2;
00405               std::memmove(dest, src, nmove*sizeof(T));
00406             }
00407           }
00408         }//end if (dataptr_[insertPoint]==item)...
00409         //     else do nothing, item is already in existing range
00410       }
00411 
00412       return;
00413     } // end if (insertPoint < len_)...
00414 
00415     //If we get to here, insertPoint >= len_, meaning we need to append
00416     //a new range.
00417     if (len_+2 > highwatermark_) {
00418       highwatermark_ += alloc_incr_;
00419       expand_dataptr(highwatermark_);
00420     }
00421     dataptr_[insertPoint] = item;
00422     dataptr_[insertPoint+1] = item+1;
00423     len_ += 2;
00424   }
00425 
00427   int insert2_dense_group(const T& starting_index, int group_size)
00428     {
00429       for(int i=0; i<group_size; ++i) {
00430   insert2(starting_index+i);
00431       }
00432 
00433       return(0);
00434     }
00435 
00437   const_iterator find(const T& item)
00438     {
00439       if (len_ < 1) {
00440   return(const_iterator(0, Set_end_val, 0));
00441       }
00442 
00443       int insertPoint = -1;
00444       int index = fei::binarySearch(item, dataptr_, len_, insertPoint);
00445 
00446       if (index < 0) {
00447   if (insertPoint%2==0) {
00448     return(end());
00449   }
00450   else {
00451     return(const_iterator(this, item, insertPoint-1));
00452   }
00453       }
00454 
00455       if (index%2==0) {
00456   return( const_iterator(this, item, index) );
00457       }
00458 
00459       return(const_iterator(0, Set_end_val, 0));
00460     }
00461 
00465   int copy_to_array(int len, T* items) const
00466     {
00467       const_iterator iter = begin(), iter_end = end();
00468       int offset = 0;
00469       for(; iter != iter_end; ++iter) {
00470   if (offset >= len) {
00471     break;
00472   }
00473 
00474   items[offset++] = *iter;
00475       }
00476 
00477       return(0);
00478     }
00479 
00481   int copy_to_vector(std::vector<T>& items) const
00482     {
00483       int sz = size();
00484       items.resize(sz);
00485       T* itemsPtr = &(items[0]);
00486       return(copy_to_array(sz, itemsPtr));
00487     }
00488 
00490   int size() const
00491     {
00492       int setsize = 0;
00493       int offset = 0;
00494       while(offset<(len_-1)) {
00495   setsize += dataptr_[offset+1]-dataptr_[offset];
00496   offset += 2;
00497       }
00498 
00499       return(setsize);
00500     }
00501 
00502  private:
00503   void expand_dataptr(int newlen)
00504   {
00505     //on entry to this function, dataptr_ has length 'len_'.
00506     //we assume newlen is greater than len_.
00507     //after we create newptr with length 'newlen', we copy
00508     //len_ positions from dataptr_ to newptr.
00509 
00510     T* newptr = new T[newlen];
00511     for(int i=0; i<len_; ++i) newptr[i] = dataptr_[i];
00512     delete [] dataptr_;
00513     dataptr_ = newptr;
00514   }
00515 
00516   friend class const_iterator;
00517   T* dataptr_;
00518   int len_;
00519   int highwatermark_;
00520   int alloc_incr_;
00521 };//class ctg_set
00522 
00523 }//namespace fei
00524 
00525 #endif
00526 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Friends
Generated on Wed Apr 13 10:08:23 2011 for FEI by  doxygen 1.6.3