FEI Version of the Day
fei_ctg_set.hpp
00001 /*
00002 // @HEADER
00003 // ************************************************************************
00004 //             FEI: Finite Element Interface to Linear Solvers
00005 //                  Copyright (2005) Sandia Corporation.
00006 //
00007 // Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation, the
00008 // U.S. Government retains certain rights in this software.
00009 //
00010 // Redistribution and use in source and binary forms, with or without
00011 // modification, are permitted provided that the following conditions are
00012 // met:
00013 //
00014 // 1. Redistributions of source code must retain the above copyright
00015 // notice, this list of conditions and the following disclaimer.
00016 //
00017 // 2. Redistributions in binary form must reproduce the above copyright
00018 // notice, this list of conditions and the following disclaimer in the
00019 // documentation and/or other materials provided with the distribution.
00020 //
00021 // 3. Neither the name of the Corporation nor the names of the
00022 // contributors may be used to endorse or promote products derived from
00023 // this software without specific prior written permission.
00024 //
00025 // THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
00026 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00027 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
00028 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
00029 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
00030 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
00031 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
00032 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
00033 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00034 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00035 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00036 //
00037 // Questions? Contact Alan Williams (william@sandia.gov) 
00038 //
00039 // ************************************************************************
00040 // @HEADER
00041 */
00042 
00043 
00044 #ifndef _fei_ctg_set_hpp_
00045 #define _fei_ctg_set_hpp_
00046 
00047 
00048 #include <fei_macros.hpp>
00049 #include <fei_iostream.hpp>
00050 
00051 #include <cstring>
00052 #include <vector>
00053 #include <fei_ArrayUtils.hpp>
00054 
00055 namespace fei {
00056 
00057 const int Set_end_val = -99999999;
00058 
00073 template<typename T>
00074 class ctg_set {
00075   public:
00077   ctg_set(int alloc_incr=32)
00078     : dataptr_(0), len_(0), highwatermark_(0), alloc_incr_(alloc_incr) {}
00079 
00081   ctg_set(const ctg_set<T>& src)
00082     : dataptr_(0), len_(0),
00083       highwatermark_(src.highwatermark_), alloc_incr_(src.alloc_incr_)
00084     {
00085       if (highwatermark_>0) {
00086         expand_dataptr(highwatermark_);
00087         len_ = src.len_;
00088         for(int i=0; i<len_; ++i) dataptr_[i] = src.dataptr_[i];
00089       }
00090     }
00091 
00093   virtual ~ctg_set(){clear();}
00094 
00096   typedef T key_type;
00097 
00099   class const_iterator {
00100   public:
00102     const_iterator() : set_(0),
00103       val_(Set_end_val), limit_(Set_end_val), i_(0) {}
00104 
00106     const_iterator(const ctg_set<T>* _set,
00107        const T& val,
00108        int i)
00109       : set_(_set),
00110       val_(val), limit_(Set_end_val), i_(i)
00111       {
00112   if (set_ != 0) {
00113     if (set_->len_ > 0) {
00114       limit_ = set_->dataptr_[i+1]-1;
00115     }
00116   }
00117       }
00118 
00120     const_iterator(const const_iterator& src)
00121       : set_(src.set_),
00122        val_(src.val_), limit_(src.limit_), i_(src.i_) {}
00123 
00125     virtual ~const_iterator(){}
00126 
00128     const T& operator*() const { return(val_); }
00129 
00131     const_iterator& operator++()
00132       {
00133   if (val_ < limit_) {
00134     ++val_;
00135   }
00136   else {
00137     if (i_ < set_->len_-2) {
00138       i_ += 2;
00139       val_ = set_->dataptr_[i_];
00140       limit_ = set_->dataptr_[i_+1]-1;
00141     }
00142     else {
00143       val_ = Set_end_val;
00144       limit_ = Set_end_val;
00145     }
00146   }
00147   return(*this);
00148       }
00149 
00151     const_iterator& operator=(const const_iterator& src)
00152       {
00153   set_ = src.set_;
00154   i_ = src.i_;
00155   val_ = src.val_;
00156   limit_ = src.limit_;
00157   return(*this);
00158       }
00159 
00161     bool operator==(const const_iterator& rhs)
00162       {
00163   return(val_ == rhs.val_);
00164       }
00165 
00167     bool operator!=(const const_iterator& rhs)
00168       {
00169   return(val_ != rhs.val_);
00170       }
00171 
00172   private:
00173     const ctg_set<T>* set_;
00174     T val_;
00175     T limit_;
00176     int i_;
00177   };
00178 
00180   const_iterator begin() const
00181     {
00182       T val = Set_end_val;
00183       if (len_>0) {
00184   val = dataptr_[0];
00185       }
00186       return(const_iterator(this, val, 0));
00187     }
00188 
00190   static const_iterator end() { return(const_iterator(0, Set_end_val, 0)); }
00191 
00193   ctg_set<T>& operator=(const ctg_set<T>& src)
00194     {
00195       highwatermark_ = src.highwatermark_;
00196       expand_dataptr(highwatermark_);
00197       len_ = src.len_;
00198 
00199       return(*this);
00200     }
00201 
00203   bool operator!=(const ctg_set<T>& rhs)
00204   {
00205     if (len_ != rhs.len_) {
00206       return(true);
00207     }
00208 
00209     for(int i=0; i<len_; ++i) {
00210       if (dataptr_[i] != rhs.dataptr_[i]) {
00211         return(true);
00212       }
00213     }
00214 
00215     return(false);
00216   }
00217 
00220   int clear()
00221   {
00222     delete [] dataptr_;
00223     dataptr_ = 0;
00224     len_ = 0;
00225     highwatermark_ = 0;
00226     return(0);
00227   }
00228 
00233   std::pair<const_iterator,bool> insert(const T& item)
00234   {
00235     if (len_ > highwatermark_) {
00236       FEI_COUT << "error"<<FEI_ENDL;
00237     }
00238     if (len_ < 1) {
00239       highwatermark_ = alloc_incr_;
00240       expand_dataptr(highwatermark_);
00241       dataptr_[0] = item;
00242       dataptr_[1] = item+1;
00243       len_ = 2;
00244       return(std::pair<const_iterator,bool>(const_iterator(this, item, 0),true));
00245     }
00246 
00247     int insertPoint = fei::lowerBound(item, dataptr_, len_);
00248 
00249     if (insertPoint < len_) {
00250 
00251       //dataptr_[insertPoint] is the first entry in dataptr_ that is not
00252       //less than item.
00253       //The possibilities are:
00254       //
00255       //1. dataptr_[insertPoint] equals item, so:
00256       //
00257       //     if (insertPoint is an even number) {
00258       //       return since item is present
00259       //     }
00260       //     else {
00261       //       expand the range below item to include item
00262       //       (by incrementing dataptr_[insertPoint])
00263       //       check whether dataptr_[insertPoint] == dataptr_[insertPoint+1]
00264       //       if so, merge the range at insertPoint-1 with the
00265       //       range at insertPoint+1
00266       //       return
00267       //     }
00268       //
00269       //2. dataptr_[insertPoint] is greater than item, so:
00270       //
00271       //     if (insertPoint is an even number) {
00272       //       if (item == dataptr_[insertPoint]-1) {
00273       //         expand the range at insertPoint to include item, by
00274       //         simply decrementing dataptr_[insertPoint]
00275       //       }
00276       //       else {
00277       //         insert a new range at insertPoint
00278       //       }
00279       //     }
00280       //     else {
00281       //       return since item is already present in the range at
00282       //       dataptr_[insertPoint-1]
00283       //     }
00284       //
00285 
00286       if (dataptr_[insertPoint] == item) {
00287   if (insertPoint%2 == 0) {
00288     //insertPoint is an even number, so return since item is present
00289     return(std::pair<const_iterator,bool>(const_iterator(this, item, insertPoint),false));
00290   }
00291 
00292   //Since insertPoint is an odd number, item lies just outside an existing
00293   //range so we simply need to add item to the range by incrementing
00294   //dataptr_[insertPoint].
00295   ++dataptr_[insertPoint];
00296 
00297   //now check whether this newly expanded range should be merged
00298   //with the range above it
00299   if (insertPoint < len_-1) {
00300     if (dataptr_[insertPoint] == dataptr_[insertPoint+1]) {
00301       dataptr_[insertPoint] = dataptr_[insertPoint+2];
00302       len_ -= 2;
00303       int nmove=len_-insertPoint-1;
00304       if (nmove > 0) {
00305         T* dest = dataptr_+insertPoint+1;
00306         T* src =  dest+2;
00307         std::memmove(dest, src, nmove*sizeof(T));
00308       }
00309     }
00310   }
00311 
00312   return(std::pair<const_iterator,bool>(const_iterator(this, item, insertPoint-1),true));
00313       }
00314       else {
00315   //dataptr_[insertPoint] is greater than item.
00316 
00317   if (insertPoint%2 == 0) {
00318     if (item == dataptr_[insertPoint]-1) {
00319       --dataptr_[insertPoint];
00320       return(std::pair<const_iterator,bool>(const_iterator(this, item, insertPoint),true));
00321     }
00322     else {
00323       //insert a new range at insertPoint
00324       int nmove = len_-insertPoint;
00325       if (len_+2 > highwatermark_) {
00326         highwatermark_ += alloc_incr_;
00327         expand_dataptr(highwatermark_);
00328       }
00329       len_ += 2;
00330       if (nmove > 0) {
00331         T* dest = dataptr_+insertPoint+2;
00332         T* src = dest - 2;
00333         std::memmove(dest, src, nmove*sizeof(T));
00334       }
00335       dataptr_[insertPoint] = item;
00336       dataptr_[insertPoint+1] = item+1;
00337 
00338       return(std::pair<const_iterator,bool>(const_iterator(this, item, insertPoint),true));
00339     }
00340   }
00341   else {
00342     return(std::pair<const_iterator,bool>(const_iterator(this, item, insertPoint-1),false));
00343   }
00344       }
00345     }
00346 
00347     //If we get to here, insertPoint >= len_, meaning we need to append
00348     //a new range.
00349     if (len_+2 > highwatermark_) {
00350       highwatermark_ += alloc_incr_;
00351       expand_dataptr(highwatermark_);
00352     }
00353     len_ += 2;
00354     dataptr_[insertPoint] = item;
00355     dataptr_[insertPoint+1] = item+1;
00356 
00357     return(std::pair<const_iterator,bool>(const_iterator(this, item, insertPoint),true));
00358   }
00359 
00361   void insert2(const T& item)
00362   {
00363     if (len_ < 1) {
00364       highwatermark_ = alloc_incr_;
00365       expand_dataptr(highwatermark_);
00366       dataptr_[0] = item;
00367       dataptr_[1] = item+1;
00368       len_ = 2;
00369       return;
00370     }
00371 
00372     int insertPoint = fei::lowerBound(item, dataptr_, len_);
00373 
00374     if (insertPoint < len_) {
00375 
00376       //dataptr_[insertPoint] is the first entry in dataptr_ that is not
00377       //less than item.
00378       //The possibilities are:
00379       //
00380       //1. insertPoint is an even number:
00381       //   dataptr_[insertPoint] is the start of an existing range.
00382       //   diff = dataptr_[insertPoint] - item;
00383       //   switch(diff) {
00384       //    case 0 : //  item in range, so return
00385       //    case 1 : //  item just below range, so expand range and return
00386       //    default: //  insert new range for item
00387       //   }
00388       //
00389       //2. insertPoint is an odd number:
00390       //   dataptr_[insertPoint] is the end of an existing range
00391       //   diff = dataptr_[insertPoint] - item;
00392       //   switch(diff) {
00393       //    case 0 : {
00394       //      // item just above range, so expand range
00395       //      // check whether range should be merged with range above
00396       //    }
00397       //    default: // item in range, so return
00398       //   }
00399       //
00400 
00401       if (insertPoint%2==0) {
00402         switch(dataptr_[insertPoint]-item) {
00403           case 0: break; //item in range
00404           case 1: {//expand range downwards
00405             --dataptr_[insertPoint];
00406             break;
00407           }
00408           default: {// insert new range for item
00409             //insert a new range at insertPoint
00410             int nmove = len_-insertPoint;
00411             if (len_+2 > highwatermark_) {
00412               highwatermark_ += alloc_incr_;
00413               expand_dataptr(highwatermark_);
00414             }
00415             len_ += 2;
00416 
00417             T* dest = dataptr_+insertPoint+2;
00418             T* src = dest - 2;
00419             std::memmove(dest, src, nmove*sizeof(T));
00420 
00421             dataptr_[insertPoint] = item;
00422             dataptr_[insertPoint+1] = item+1;
00423           }
00424         }
00425       }
00426       else {//insertPoint is odd number
00427         if (dataptr_[insertPoint] == item) {
00428           // item just above range, so expand range
00429           ++dataptr_[insertPoint];
00430 
00431           // check whether range should be merged with range above
00432           if (insertPoint < len_-1 &&
00433               dataptr_[insertPoint] == dataptr_[insertPoint+1]) {
00434             dataptr_[insertPoint] = dataptr_[insertPoint+2];
00435             len_ -= 2;
00436             int nmove=len_-insertPoint-1;
00437             if (nmove > 0) {
00438               T* dest = dataptr_+insertPoint+1;
00439               T* src =  dest+2;
00440               std::memmove(dest, src, nmove*sizeof(T));
00441             }
00442           }
00443         }//end if (dataptr_[insertPoint]==item)...
00444         //     else do nothing, item is already in existing range
00445       }
00446 
00447       return;
00448     } // end if (insertPoint < len_)...
00449 
00450     //If we get to here, insertPoint >= len_, meaning we need to append
00451     //a new range.
00452     if (len_+2 > highwatermark_) {
00453       highwatermark_ += alloc_incr_;
00454       expand_dataptr(highwatermark_);
00455     }
00456     dataptr_[insertPoint] = item;
00457     dataptr_[insertPoint+1] = item+1;
00458     len_ += 2;
00459   }
00460 
00462   int insert2_dense_group(const T& starting_index, int group_size)
00463     {
00464       for(int i=0; i<group_size; ++i) {
00465   insert2(starting_index+i);
00466       }
00467 
00468       return(0);
00469     }
00470 
00472   const_iterator find(const T& item)
00473     {
00474       if (len_ < 1) {
00475   return(const_iterator(0, Set_end_val, 0));
00476       }
00477 
00478       int insertPoint = -1;
00479       int index = fei::binarySearch(item, dataptr_, len_, insertPoint);
00480 
00481       if (index < 0) {
00482   if (insertPoint%2==0) {
00483     return(end());
00484   }
00485   else {
00486     return(const_iterator(this, item, insertPoint-1));
00487   }
00488       }
00489 
00490       if (index%2==0) {
00491   return( const_iterator(this, item, index) );
00492       }
00493 
00494       return(const_iterator(0, Set_end_val, 0));
00495     }
00496 
00500   int copy_to_array(int len, T* items) const
00501     {
00502       const_iterator iter = begin(), iter_end = end();
00503       int offset = 0;
00504       for(; iter != iter_end; ++iter) {
00505   if (offset >= len) {
00506     break;
00507   }
00508 
00509   items[offset++] = *iter;
00510       }
00511 
00512       return(0);
00513     }
00514 
00516   int copy_to_vector(std::vector<T>& items) const
00517     {
00518       int sz = size();
00519       items.resize(sz);
00520       T* itemsPtr = &(items[0]);
00521       return(copy_to_array(sz, itemsPtr));
00522     }
00523 
00525   int size() const
00526     {
00527       int setsize = 0;
00528       int offset = 0;
00529       while(offset<(len_-1)) {
00530   setsize += dataptr_[offset+1]-dataptr_[offset];
00531   offset += 2;
00532       }
00533 
00534       return(setsize);
00535     }
00536 
00537  private:
00538   void expand_dataptr(int newlen)
00539   {
00540     //on entry to this function, dataptr_ has length 'len_'.
00541     //we assume newlen is greater than len_.
00542     //after we create newptr with length 'newlen', we copy
00543     //len_ positions from dataptr_ to newptr.
00544 
00545     T* newptr = new T[newlen];
00546     for(int i=0; i<len_; ++i) newptr[i] = dataptr_[i];
00547     delete [] dataptr_;
00548     dataptr_ = newptr;
00549   }
00550 
00551   friend class const_iterator;
00552   T* dataptr_;
00553   int len_;
00554   int highwatermark_;
00555   int alloc_incr_;
00556 };//class ctg_set
00557 
00558 }//namespace fei
00559 
00560 #endif
00561 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Friends