snl_fei_ArrayUtils.hpp

00001 #ifndef _snl_fei_ArrayUtils_hpp_
00002 #define _snl_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 snl_fei {
00017 
00026   template<typename T>
00027     int binarySearch(const T& item,
00028          const T* list,
00029          int len)
00030     {
00031       if (len < 2) {
00032   if (len < 1) {
00033     return(-1);
00034   }
00035 
00036   if (list[0] != item) {
00037     return(-1);
00038   }
00039   else {
00040     return(0);
00041   }
00042       }
00043 
00044       unsigned start = 0;
00045       unsigned end = len - 1;
00046 
00047       while(end - start > 1) {
00048   unsigned mid = (start + end) >> 1;
00049   if (list[mid] < item) start = mid;
00050   else end = mid;
00051       }
00052 
00053       if (list[end] == item) return(end);
00054       if (list[start] == item) return(start);
00055 
00056       return(-1);
00057     }
00058 
00062   template<typename T>
00063     void insertion_sort_with_companions(int len, int* array, T* companions)
00064     {
00065       int i, j, index;
00066       T companion;
00067 
00068       for (i=1; i < len; i++) {
00069         index = array[i];
00070         companion = companions[i];
00071         j = i;
00072         while ((j > 0) && (array[j-1] > index))
00073         {
00074           array[j] = array[j-1];
00075           companions[j] = companions[j-1];
00076           j = j - 1;
00077         }
00078         array[j] = index;
00079         companions[j] = companion;
00080       }
00081     }
00082 
00086   template<typename T>
00087   int lowerBound(const T& item,
00088      const T* list,
00089      int len)
00090   {
00091     //The correctness of this function is tested in
00092     // fei/test_utils/test_misc.cpp, in test_misc::serialtest2().
00093 
00094     if (len < 1) return 0;
00095 
00096     unsigned start = 0;
00097     unsigned end = len - 1;
00098 
00099     while(end - start > 1) {
00100       unsigned mid = (start + end) >> 1;
00101       if (list[mid] < item) start = mid;
00102       else end = mid;
00103     }
00104 
00105     if (list[end] < item) {
00106       return(end+1);
00107     }
00108 
00109     if (list[start] < item) {
00110       return(end);
00111     }
00112 
00113     return(start);
00114   }
00115 
00127   template<typename T>
00128     int binarySearch(const T& item,
00129          const T* list,
00130          int len,
00131          int& insertPoint)
00132     {
00133       //The correctness of this function is tested in src/utils/test_Set.C,
00134       //in the function test_Set::test2.
00135 
00136       if (len < 2) {
00137   if (len < 1) {
00138     insertPoint = 0;
00139     return(-1);
00140   }
00141 
00142   if (list[0] < item) {
00143     insertPoint = 1;
00144     return(-1);
00145   }
00146   if (item < list[0]) {
00147     insertPoint = 0;
00148     return(-1);
00149   }
00150   else {
00151     return(0);
00152   }
00153       }
00154 
00155       unsigned start = 0;
00156       unsigned end = len - 1;
00157 
00158       while(end - start > 1) {
00159   unsigned mid = (start + end) >> 1;
00160   if (list[mid] < item) start = mid;
00161   else end = mid;
00162       }
00163 
00164       if (list[end] < item) {
00165   insertPoint = end+1;
00166   return(-1);
00167       }
00168 
00169       if (item < list[end]) {
00170   if (list[start] < item) {
00171     insertPoint = end;
00172     return(-1);
00173   }
00174 
00175   if (item < list[start]) {
00176     insertPoint = start;
00177     return(-1);
00178   }
00179   else {
00180     return(start);
00181   }
00182       }
00183       else {
00184   return(end);
00185       }
00186     }
00187 
00190   template<typename T>
00191     int binarySearch(const T& item, const std::vector<T>& list, int& insertPoint)
00192     {
00193       if (list.size() == 0) {
00194         insertPoint = 0;
00195         return(-1);
00196       }
00197       return( binarySearch(item, &list[0], list.size(), insertPoint) );
00198     }
00199 
00202   template<typename T>
00203     int binarySearch(const T& item, const std::vector<T>& list)
00204     {
00205       if (list.size() == 0) return(-1);
00206       return( binarySearch(item, &list[0], list.size()) );
00207     }
00208 
00220   template<typename T>
00221     int binarySearch(const T& item, const T* list, int /*listLength*/,
00222          int start, int end, int& insertPoint)
00223     {
00224       int length = end - start + 1;
00225 
00226       if (length < 2) {
00227   if (length < 1) {
00228     insertPoint = start;
00229     return(-1);
00230   }
00231 
00232   if (list[start] < item) {
00233     insertPoint = start+1;
00234     return(-1);
00235   }
00236   if (item < list[start]) {
00237     insertPoint = start;
00238     return(-1);
00239   }
00240   else {
00241     return(start);
00242   }
00243       }
00244 
00245       unsigned ustart = start;
00246       unsigned uend = end;
00247 
00248       while(uend - ustart > 1) {
00249   unsigned mid = (ustart + uend) >> 1;
00250   if (list[mid] < item) ustart = mid;
00251   else uend = mid;
00252       }
00253 
00254       //if list[uend] < item, then insertPoint = end+1
00255       if (list[uend] < item) {
00256   insertPoint = uend+1;
00257   return(-1);
00258       }
00259 
00260       if (item < list[uend]) {
00261   if (list[ustart] < item) {
00262     insertPoint = uend;
00263     return(-1);
00264   }
00265 
00266   if (item < list[ustart]) {
00267     insertPoint = ustart;
00268     return(-1);
00269   }
00270   else {
00271     //list[ustart] == item
00272     return(ustart);
00273   }
00274       }
00275 
00276       // list[uend] == item
00277       return(uend);
00278     }
00279 
00290   template<typename T>
00291     int binarySearch(int numItems, const T* items, int* offsets,
00292          const T* list, int listLength)
00293     {
00294       int i;
00295       if (numItems < 1 || listLength < 1) {
00296   if (listLength < 1) {
00297     for(i=0; i<numItems; ++i) offsets[i] = -1;
00298   }
00299       }
00300 
00301       int tmp, start = 0;
00302       int end = listLength -1;
00303       int insertPoint = -1;
00304       for(i=0; i<numItems; ++i) {
00305   tmp = binarySearch(items[i], list, listLength, start, end, insertPoint);
00306   start = tmp > -1 ? tmp : insertPoint;
00307   offsets[i] = tmp;
00308       }
00309 
00310       return(0);
00311     }
00312 
00317   template<class T>
00318     int sortedListInsert(const T& item, std::vector<T>& list)
00319     {
00320       typename std::vector<T>::iterator iter =
00321         std::lower_bound(list.begin(), list.end(), item);
00322 
00323       if (iter == list.end() || *iter != item) {
00324         iter = list.insert(iter, item);
00325         return( iter - list.begin() );
00326       }
00327 
00328       return(-1);
00329     }
00330 
00333   template<class T>
00334     int sortedListInsert(const T& item, T*& list, int& len, int& allocLen)
00335     {
00336       int i, insertPoint = -1;
00337       int index = binarySearch(item, list, len, insertPoint);
00338       if (index < 0) {
00339   if (len >= allocLen) {
00340     allocLen = len+2;
00341     T* newlist = new T[allocLen];
00342     for(i=0; i<insertPoint; ++i) newlist[i] = list[i];
00343     newlist[insertPoint] = item;
00344     for(i=insertPoint; i<len; ++i) newlist[i+1] = list[i];
00345     delete [] list;
00346     list = newlist;
00347   }
00348   else {
00349     for(i=len; i>insertPoint; --i) {
00350       list[i] = list[i-1];
00351     }
00352     list[insertPoint] = item;
00353   }
00354   ++len;
00355   return(insertPoint);
00356       }
00357 
00358       return(-1);
00359     }
00360 
00363   template<class T>
00364     int listInsert(const T& item, int offset, T*& list,
00365        int& usedLength, int& allocatedLength,
00366        int allocChunkSize=200)
00367     {
00368       if (offset < 0 || offset > usedLength) {
00369   return(-1);
00370       }
00371 
00372       if (usedLength < allocatedLength) {
00373   for(int i=usedLength; i>offset; --i) {
00374     list[i] = list[i-1];
00375   }
00376   list[offset] = item;
00377   ++usedLength;
00378   return(0);
00379       }
00380 
00381       T* newlist = new T[allocatedLength+allocChunkSize];
00382 
00383       allocatedLength += allocChunkSize;
00384       int i;
00385       for(i=0; i<offset; ++i) {
00386   newlist[i] = list[i];
00387       }
00388 
00389       newlist[offset] = item;
00390 
00391       for(i=offset+1; i<=usedLength; ++i) {
00392   newlist[i] = list[i-1];
00393       }
00394 
00395       ++usedLength;
00396       delete [] list;
00397       list = newlist;
00398       return(0);
00399     }
00400 
00404   template<class T>
00405     int searchList(const T& item, const T* list, int len)
00406     {
00407       for(int i=0; i<len; ++i) {
00408   if (list[i] == item) {
00409     return(i);
00410   }
00411       }
00412       return(-1);
00413     }
00414 
00415 } //namespace snl_fei
00416 
00417 #endif // _snl_fei_ArrayUtils_hpp_
00418 

Generated on Wed May 12 21:30:42 2010 for FEI by  doxygen 1.4.7