FEI Version of the Day
snl_fei_ArrayUtils.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 #ifndef _snl_fei_ArrayUtils_hpp_
00044 #define _snl_fei_ArrayUtils_hpp_
00045 
00046 
00047 #include "fei_fwd.hpp"
00048 
00049 #include <algorithm>
00050 
00051 namespace snl_fei {
00052 
00061   template<typename T>
00062     int binarySearch(const T& item,
00063          const T* list,
00064          int len)
00065     {
00066       if (len < 2) {
00067   if (len < 1) {
00068     return(-1);
00069   }
00070 
00071   if (list[0] != item) {
00072     return(-1);
00073   }
00074   else {
00075     return(0);
00076   }
00077       }
00078 
00079       unsigned start = 0;
00080       unsigned end = len - 1;
00081 
00082       while(end - start > 1) {
00083   unsigned mid = (start + end) >> 1;
00084   if (list[mid] < item) start = mid;
00085   else end = mid;
00086       }
00087 
00088       if (list[end] == item) return(end);
00089       if (list[start] == item) return(start);
00090 
00091       return(-1);
00092     }
00093 
00097   template<typename T>
00098     void insertion_sort_with_companions(int len, int* array, T* companions)
00099     {
00100       int i, j, index;
00101       T companion;
00102 
00103       for (i=1; i < len; i++) {
00104         index = array[i];
00105         companion = companions[i];
00106         j = i;
00107         while ((j > 0) && (array[j-1] > index))
00108         {
00109           array[j] = array[j-1];
00110           companions[j] = companions[j-1];
00111           j = j - 1;
00112         }
00113         array[j] = index;
00114         companions[j] = companion;
00115       }
00116     }
00117 
00121   template<typename T>
00122   int lowerBound(const T& item,
00123      const T* list,
00124      int len)
00125   {
00126     //The correctness of this function is tested in
00127     // fei/test_utils/test_misc.cpp, in test_misc::serialtest2().
00128 
00129     if (len < 1) return 0;
00130 
00131     unsigned start = 0;
00132     unsigned end = len - 1;
00133 
00134     while(end - start > 1) {
00135       unsigned mid = (start + end) >> 1;
00136       if (list[mid] < item) start = mid;
00137       else end = mid;
00138     }
00139 
00140     if (list[end] < item) {
00141       return(end+1);
00142     }
00143 
00144     if (list[start] < item) {
00145       return(end);
00146     }
00147 
00148     return(start);
00149   }
00150 
00162   template<typename T>
00163     int binarySearch(const T& item,
00164          const T* list,
00165          int len,
00166          int& insertPoint)
00167     {
00168       //The correctness of this function is tested in src/utils/test_Set.C,
00169       //in the function test_Set::test2.
00170 
00171       if (len < 2) {
00172   if (len < 1) {
00173     insertPoint = 0;
00174     return(-1);
00175   }
00176 
00177   if (list[0] < item) {
00178     insertPoint = 1;
00179     return(-1);
00180   }
00181   if (item < list[0]) {
00182     insertPoint = 0;
00183     return(-1);
00184   }
00185   else {
00186     return(0);
00187   }
00188       }
00189 
00190       unsigned start = 0;
00191       unsigned end = len - 1;
00192 
00193       while(end - start > 1) {
00194   unsigned mid = (start + end) >> 1;
00195   if (list[mid] < item) start = mid;
00196   else end = mid;
00197       }
00198 
00199       if (list[end] < item) {
00200   insertPoint = end+1;
00201   return(-1);
00202       }
00203 
00204       if (item < list[end]) {
00205   if (list[start] < item) {
00206     insertPoint = end;
00207     return(-1);
00208   }
00209 
00210   if (item < list[start]) {
00211     insertPoint = start;
00212     return(-1);
00213   }
00214   else {
00215     return(start);
00216   }
00217       }
00218       else {
00219   return(end);
00220       }
00221     }
00222 
00225   template<typename T>
00226     int binarySearch(const T& item, const std::vector<T>& list, int& insertPoint)
00227     {
00228       if (list.size() == 0) {
00229         insertPoint = 0;
00230         return(-1);
00231       }
00232       return( binarySearch(item, &list[0], list.size(), insertPoint) );
00233     }
00234 
00237   template<typename T>
00238     int binarySearch(const T& item, const std::vector<T>& list)
00239     {
00240       if (list.size() == 0) return(-1);
00241       return( binarySearch(item, &list[0], list.size()) );
00242     }
00243 
00255   template<typename T>
00256     int binarySearch(const T& item, const T* list, int /*listLength*/,
00257          int start, int end, int& insertPoint)
00258     {
00259       int length = end - start + 1;
00260 
00261       if (length < 2) {
00262   if (length < 1) {
00263     insertPoint = start;
00264     return(-1);
00265   }
00266 
00267   if (list[start] < item) {
00268     insertPoint = start+1;
00269     return(-1);
00270   }
00271   if (item < list[start]) {
00272     insertPoint = start;
00273     return(-1);
00274   }
00275   else {
00276     return(start);
00277   }
00278       }
00279 
00280       unsigned ustart = start;
00281       unsigned uend = end;
00282 
00283       while(uend - ustart > 1) {
00284   unsigned mid = (ustart + uend) >> 1;
00285   if (list[mid] < item) ustart = mid;
00286   else uend = mid;
00287       }
00288 
00289       //if list[uend] < item, then insertPoint = end+1
00290       if (list[uend] < item) {
00291   insertPoint = uend+1;
00292   return(-1);
00293       }
00294 
00295       if (item < list[uend]) {
00296   if (list[ustart] < item) {
00297     insertPoint = uend;
00298     return(-1);
00299   }
00300 
00301   if (item < list[ustart]) {
00302     insertPoint = ustart;
00303     return(-1);
00304   }
00305   else {
00306     //list[ustart] == item
00307     return(ustart);
00308   }
00309       }
00310 
00311       // list[uend] == item
00312       return(uend);
00313     }
00314 
00325   template<typename T>
00326     int binarySearch(int numItems, const T* items, int* offsets,
00327          const T* list, int listLength)
00328     {
00329       int i;
00330       if (numItems < 1 || listLength < 1) {
00331   if (listLength < 1) {
00332     for(i=0; i<numItems; ++i) offsets[i] = -1;
00333   }
00334       }
00335 
00336       int tmp, start = 0;
00337       int end = listLength -1;
00338       int insertPoint = -1;
00339       for(i=0; i<numItems; ++i) {
00340   tmp = binarySearch(items[i], list, listLength, start, end, insertPoint);
00341   start = tmp > -1 ? tmp : insertPoint;
00342   offsets[i] = tmp;
00343       }
00344 
00345       return(0);
00346     }
00347 
00352   template<class T>
00353     int sortedListInsert(const T& item, std::vector<T>& list)
00354     {
00355       typename std::vector<T>::iterator iter =
00356         std::lower_bound(list.begin(), list.end(), item);
00357 
00358       if (iter == list.end() || *iter != item) {
00359         iter = list.insert(iter, item);
00360         return( iter - list.begin() );
00361       }
00362 
00363       return(-1);
00364     }
00365 
00368   template<class T>
00369     int sortedListInsert(const T& item, T*& list, int& len, int& allocLen)
00370     {
00371       int i, insertPoint = -1;
00372       int index = binarySearch(item, list, len, insertPoint);
00373       if (index < 0) {
00374   if (len >= allocLen) {
00375     allocLen = len+2;
00376     T* newlist = new T[allocLen];
00377     for(i=0; i<insertPoint; ++i) newlist[i] = list[i];
00378     newlist[insertPoint] = item;
00379     for(i=insertPoint; i<len; ++i) newlist[i+1] = list[i];
00380     delete [] list;
00381     list = newlist;
00382   }
00383   else {
00384     for(i=len; i>insertPoint; --i) {
00385       list[i] = list[i-1];
00386     }
00387     list[insertPoint] = item;
00388   }
00389   ++len;
00390   return(insertPoint);
00391       }
00392 
00393       return(-1);
00394     }
00395 
00398   template<class T>
00399     int listInsert(const T& item, int offset, T*& list,
00400        int& usedLength, int& allocatedLength,
00401        int allocChunkSize=200)
00402     {
00403       if (offset < 0 || offset > usedLength) {
00404   return(-1);
00405       }
00406 
00407       if (usedLength < allocatedLength) {
00408   for(int i=usedLength; i>offset; --i) {
00409     list[i] = list[i-1];
00410   }
00411   list[offset] = item;
00412   ++usedLength;
00413   return(0);
00414       }
00415 
00416       T* newlist = new T[allocatedLength+allocChunkSize];
00417 
00418       allocatedLength += allocChunkSize;
00419       int i;
00420       for(i=0; i<offset; ++i) {
00421   newlist[i] = list[i];
00422       }
00423 
00424       newlist[offset] = item;
00425 
00426       for(i=offset+1; i<=usedLength; ++i) {
00427   newlist[i] = list[i-1];
00428       }
00429 
00430       ++usedLength;
00431       delete [] list;
00432       list = newlist;
00433       return(0);
00434     }
00435 
00439   template<class T>
00440     int searchList(const T& item, const T* list, int len)
00441     {
00442       for(int i=0; i<len; ++i) {
00443   if (list[i] == item) {
00444     return(i);
00445   }
00446       }
00447       return(-1);
00448     }
00449 
00450 } //namespace snl_fei
00451 
00452 #endif // _snl_fei_ArrayUtils_hpp_
00453 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Friends