FEI Version of the Day
fei_ArrayUtils.hpp
00001 #ifndef _fei_ArrayUtils_hpp_
00002 #define _fei_ArrayUtils_hpp_
00003 
00004 /*--------------------------------------------------------------------*/
00005 /*    Copyright 2005 Sandia Corporation.                              */
00006 /*    Under the terms of Contract DE-AC04-94AL85000, there is a       */
00007 /*    non-exclusive license for use of this work by or on behalf      */
00008 /*    of the U.S. Government.  Export of this program may require     */
00009 /*    a license from the United States Government.                    */
00010 /*--------------------------------------------------------------------*/
00011 
00012 #include "fei_fwd.hpp"
00013 
00014 #include <algorithm>
00015 
00016 namespace fei {
00017 
00018 
00022   template<typename T>
00023   inline int lowerBound(const T& item,
00024      const T* list,
00025      int len)
00026   {
00027     //The correctness of this function is tested in
00028     // fei/test_utils/test_misc.cpp, in test_misc::serialtest2().
00029 
00030     if (len < 1) return 0;
00031 
00032     unsigned start = 0;
00033     unsigned end = len - 1;
00034 
00035     while(end - start > 23) {
00036       unsigned mid = (start + end) >> 1;
00037       if (list[mid] < item) start = mid;
00038       else end = mid;
00039     }
00040 
00041     while (start+7<=end ) {
00042       if ( item <= list[start+0] ) return start+0;
00043       if ( item <= list[start+1] ) return start+1;
00044       if ( item <= list[start+2] ) return start+2;
00045       if ( item <= list[start+3] ) return start+3;
00046       if ( item <= list[start+4] ) return start+4;
00047       if ( item <= list[start+5] ) return start+5;
00048       if ( item <= list[start+6] ) return start+6;
00049       if ( item <= list[start+7] ) return start+7;
00050       start+=8;
00051     }
00052 
00053     while (start<=end && item > list[start] ) 
00054       start++;
00055 
00056     return(start);
00057   }
00058 
00067   template<typename T>
00068   inline int binarySearch(const T& item,
00069         const T* list,
00070         int len)
00071     {
00072       int result = lowerBound(item,list,len);
00073       if ( result < len && item == list[result] )
00074   return result;
00075       return -1;
00076     }
00077 
00081   template<typename T>
00082   inline void insertion_sort_with_companions(int len, int* array, T* companions)
00083     {
00084       int i, j, index;
00085       T companion;
00086 
00087       for (i=1; i < len; i++) {
00088         index = array[i];
00089         companion = companions[i];
00090         j = i;
00091         while ((j > 0) && (array[j-1] > index))
00092         {
00093           array[j] = array[j-1];
00094           companions[j] = companions[j-1];
00095           j = j - 1;
00096         }
00097         array[j] = index;
00098         companions[j] = companion;
00099       }
00100     }
00101 
00102 
00114   template<typename T>
00115   inline int binarySearch(const T& item,
00116          const T* list,
00117          int len,
00118          int& insertPoint)
00119     {
00120       //The correctness of this function is tested in src/utils/test_Set.C,
00121       //in the function test_Set::test2.
00122       insertPoint = lowerBound(item,list,len);
00123       if ( insertPoint < len && item == list[insertPoint] )
00124   return insertPoint;
00125       return -1;
00126     }
00127 
00130   template<typename T>
00131   inline int binarySearch(const T& item, const std::vector<T>& list, int& insertPoint)
00132     {
00133       if (list.size() == 0) {
00134         insertPoint = 0;
00135         return(-1);
00136       }
00137       return( binarySearch(item, &list[0], list.size(), insertPoint) );
00138     }
00139 
00142   template<typename T>
00143   inline int binarySearch(const T& item, const std::vector<T>& list)
00144     {
00145       if (list.size() == 0) return(-1);
00146       return( binarySearch(item, &list[0], list.size()) );
00147     }
00148 
00160   template<typename T>
00161   inline int binarySearch(const T& item, const T* list, int /*listLength*/,
00162          int start, int end, int& insertPoint)
00163     {
00164       int result = binarySearch(item,list+start,end-start+1,insertPoint);
00165       if ( result >= 0 )
00166   return result+start;
00167       insertPoint+= start;
00168       return -1;
00169     }
00170 
00181   template<typename T>
00182   inline int binarySearch(int numItems, const T* items, int* offsets,
00183          const T* list, int listLength)
00184     {
00185       int i;
00186       if (numItems < 1 || listLength < 1) {
00187         if (listLength < 1) {
00188           for(i=0; i<numItems; ++i) offsets[i] = -1;
00189         }
00190       }
00191 
00192       int tmp, start = 0;
00193       int end = listLength -1;
00194       int insertPoint = -1;
00195       for(i=0; i<numItems; ++i) {
00196         tmp = binarySearch(items[i], list, listLength, start, end, insertPoint);
00197         start = tmp > -1 ? tmp : insertPoint;
00198         offsets[i] = tmp;
00199       }
00200 
00201       return(0);
00202     }
00203 
00208   template<class T>
00209   inline int sortedListInsert(const T& item, std::vector<T>& list)
00210     {
00211       typename std::vector<T>::iterator iter =
00212         std::lower_bound(list.begin(), list.end(), item);
00213 
00214       if (iter == list.end() || *iter != item) {
00215         iter = list.insert(iter, item);
00216         return( iter - list.begin() );
00217       }
00218 
00219       return(-1);
00220     }
00221 
00224   template<class T>
00225   inline int sortedListInsert(const T& item, T*& list, int& len, int& allocLen)
00226     {
00227       int i, insertPoint = -1;
00228       int index = binarySearch(item, list, len, insertPoint);
00229       if (index < 0) {
00230         if (len >= allocLen) {
00231           allocLen = len+2;
00232           T* newlist = new T[allocLen];
00233           for(i=0; i<insertPoint; ++i) newlist[i] = list[i];
00234           newlist[insertPoint] = item;
00235           for(i=insertPoint; i<len; ++i) newlist[i+1] = list[i];
00236           delete [] list;
00237           list = newlist;
00238         }
00239         else {
00240           for(i=len; i>insertPoint; --i) {
00241             list[i] = list[i-1];
00242           }
00243           list[insertPoint] = item;
00244         }
00245         ++len;
00246         return(insertPoint);
00247       }
00248 
00249       return(-1);
00250     }
00251 
00254   template<class T>
00255   inline int listInsert(const T& item, int offset, T*& list,
00256        int& usedLength, int& allocatedLength,
00257        int allocChunkSize=200)
00258     {
00259       if (offset < 0 || offset > usedLength) {
00260         return(-1);
00261       }
00262 
00263       if (usedLength < allocatedLength) {
00264         for(int i=usedLength; i>offset; --i) {
00265           list[i] = list[i-1];
00266         }
00267         list[offset] = item;
00268         ++usedLength;
00269         return(0);
00270       }
00271 
00272       T* newlist = new T[allocatedLength+allocChunkSize];
00273 
00274       allocatedLength += allocChunkSize;
00275       int i;
00276       for(i=0; i<offset; ++i) {
00277         newlist[i] = list[i];
00278       }
00279 
00280       newlist[offset] = item;
00281 
00282       for(i=offset+1; i<=usedLength; ++i) {
00283         newlist[i] = list[i-1];
00284       }
00285 
00286       ++usedLength;
00287       delete [] list;
00288       list = newlist;
00289       return(0);
00290     }
00291 
00295   template<class T>
00296   inline int searchList(const T& item, const T* list, int len)
00297     {
00298       for(int i=0; i<len; ++i) {
00299         if (list[i] == item) {
00300           return(i);
00301         }
00302       }
00303       return(-1);
00304     }
00305 
00306 } //namespace fei
00307 
00308 #endif // _fei_ArrayUtils_hpp_
00309 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Friends