FEI Version of the Day
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 _fei_ArrayUtils_hpp_
00044 #define _fei_ArrayUtils_hpp_
00045 
00046 
00047 #include "fei_fwd.hpp"
00048 
00049 #include <algorithm>
00050 
00051 namespace fei {
00052 
00053 
00057   template<typename T>
00058   inline int lowerBound(const T& item,
00059      const T* list,
00060      int len)
00061   {
00062     //The correctness of this function is tested in
00063     // fei/test_utils/test_misc.cpp, in test_misc::serialtest2().
00064 
00065     if (len < 1) return 0;
00066 
00067     unsigned start = 0;
00068     unsigned end = len - 1;
00069 
00070     while(end - start > 23) {
00071       unsigned mid = (start + end) >> 1;
00072       if (list[mid] < item) start = mid;
00073       else end = mid;
00074     }
00075 
00076     while (start+7<=end ) {
00077       if ( item <= list[start+0] ) return start+0;
00078       if ( item <= list[start+1] ) return start+1;
00079       if ( item <= list[start+2] ) return start+2;
00080       if ( item <= list[start+3] ) return start+3;
00081       if ( item <= list[start+4] ) return start+4;
00082       if ( item <= list[start+5] ) return start+5;
00083       if ( item <= list[start+6] ) return start+6;
00084       if ( item <= list[start+7] ) return start+7;
00085       start+=8;
00086     }
00087 
00088     while (start<=end && item > list[start] ) 
00089       start++;
00090 
00091     return(start);
00092   }
00093 
00102   template<typename T>
00103   inline int binarySearch(const T& item,
00104         const T* list,
00105         int len)
00106     {
00107       int result = lowerBound(item,list,len);
00108       if ( result < len && item == list[result] )
00109   return result;
00110       return -1;
00111     }
00112 
00116   template<typename T>
00117   inline void insertion_sort_with_companions(int len, int* array, T* companions)
00118     {
00119       int i, j, index;
00120       T companion;
00121 
00122       for (i=1; i < len; i++) {
00123         index = array[i];
00124         companion = companions[i];
00125         j = i;
00126         while ((j > 0) && (array[j-1] > index))
00127         {
00128           array[j] = array[j-1];
00129           companions[j] = companions[j-1];
00130           j = j - 1;
00131         }
00132         array[j] = index;
00133         companions[j] = companion;
00134       }
00135     }
00136 
00137 
00149   template<typename T>
00150   inline int binarySearch(const T& item,
00151          const T* list,
00152          int len,
00153          int& insertPoint)
00154     {
00155       //The correctness of this function is tested in src/utils/test_Set.C,
00156       //in the function test_Set::test2.
00157       insertPoint = lowerBound(item,list,len);
00158       if ( insertPoint < len && item == list[insertPoint] )
00159   return insertPoint;
00160       return -1;
00161     }
00162 
00165   template<typename T>
00166   inline int binarySearch(const T& item, const std::vector<T>& list, int& insertPoint)
00167     {
00168       if (list.size() == 0) {
00169         insertPoint = 0;
00170         return(-1);
00171       }
00172       return( binarySearch(item, &list[0], list.size(), insertPoint) );
00173     }
00174 
00177   template<typename T>
00178   inline int binarySearch(const T& item, const std::vector<T>& list)
00179     {
00180       if (list.size() == 0) return(-1);
00181       return( binarySearch(item, &list[0], list.size()) );
00182     }
00183 
00195   template<typename T>
00196   inline int binarySearch(const T& item, const T* list, int /*listLength*/,
00197          int start, int end, int& insertPoint)
00198     {
00199       int result = binarySearch(item,list+start,end-start+1,insertPoint);
00200       if ( result >= 0 )
00201   return result+start;
00202       insertPoint+= start;
00203       return -1;
00204     }
00205 
00216   template<typename T>
00217   inline int binarySearch(int numItems, const T* items, int* offsets,
00218          const T* list, int listLength)
00219     {
00220       int i;
00221       if (numItems < 1 || listLength < 1) {
00222         if (listLength < 1) {
00223           for(i=0; i<numItems; ++i) offsets[i] = -1;
00224         }
00225       }
00226 
00227       int tmp, start = 0;
00228       int end = listLength -1;
00229       int insertPoint = -1;
00230       for(i=0; i<numItems; ++i) {
00231         tmp = binarySearch(items[i], list, listLength, start, end, insertPoint);
00232         start = tmp > -1 ? tmp : insertPoint;
00233         offsets[i] = tmp;
00234       }
00235 
00236       return(0);
00237     }
00238 
00243   template<class T>
00244   inline int sortedListInsert(const T& item, std::vector<T>& list)
00245     {
00246       typename std::vector<T>::iterator iter =
00247         std::lower_bound(list.begin(), list.end(), item);
00248 
00249       if (iter == list.end() || *iter != item) {
00250         iter = list.insert(iter, item);
00251         return( iter - list.begin() );
00252       }
00253 
00254       return(-1);
00255     }
00256 
00259   template<class T>
00260   inline int sortedListInsert(const T& item, T*& list, int& len, int& allocLen)
00261     {
00262       int i, insertPoint = -1;
00263       int index = binarySearch(item, list, len, insertPoint);
00264       if (index < 0) {
00265         if (len >= allocLen) {
00266           allocLen = len+2;
00267           T* newlist = new T[allocLen];
00268           for(i=0; i<insertPoint; ++i) newlist[i] = list[i];
00269           newlist[insertPoint] = item;
00270           for(i=insertPoint; i<len; ++i) newlist[i+1] = list[i];
00271           delete [] list;
00272           list = newlist;
00273         }
00274         else {
00275           for(i=len; i>insertPoint; --i) {
00276             list[i] = list[i-1];
00277           }
00278           list[insertPoint] = item;
00279         }
00280         ++len;
00281         return(insertPoint);
00282       }
00283 
00284       return(-1);
00285     }
00286 
00289   template<class T>
00290   inline int listInsert(const T& item, int offset, T*& list,
00291        int& usedLength, int& allocatedLength,
00292        int allocChunkSize=200)
00293     {
00294       if (offset < 0 || offset > usedLength) {
00295         return(-1);
00296       }
00297 
00298       if (usedLength < allocatedLength) {
00299         for(int i=usedLength; i>offset; --i) {
00300           list[i] = list[i-1];
00301         }
00302         list[offset] = item;
00303         ++usedLength;
00304         return(0);
00305       }
00306 
00307       T* newlist = new T[allocatedLength+allocChunkSize];
00308 
00309       allocatedLength += allocChunkSize;
00310       int i;
00311       for(i=0; i<offset; ++i) {
00312         newlist[i] = list[i];
00313       }
00314 
00315       newlist[offset] = item;
00316 
00317       for(i=offset+1; i<=usedLength; ++i) {
00318         newlist[i] = list[i-1];
00319       }
00320 
00321       ++usedLength;
00322       delete [] list;
00323       list = newlist;
00324       return(0);
00325     }
00326 
00330   template<class T>
00331   inline int searchList(const T& item, const T* list, int len)
00332     {
00333       for(int i=0; i<len; ++i) {
00334         if (list[i] == item) {
00335           return(i);
00336         }
00337       }
00338       return(-1);
00339     }
00340 
00341 } //namespace fei
00342 
00343 #endif // _fei_ArrayUtils_hpp_
00344 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Friends