snl_fei_ArrayUtils.hpp

#ifndef _snl_fei_ArrayUtils_hpp_
#define _snl_fei_ArrayUtils_hpp_

/*--------------------------------------------------------------------*/
/*    Copyright 2005 Sandia Corporation.                              */
/*    Under the terms of Contract DE-AC04-94AL85000, there is a       */
/*    non-exclusive license for use of this work by or on behalf      */
/*    of the U.S. Government.  Export of this program may require     */
/*    a license from the United States Government.                    */
/*--------------------------------------------------------------------*/

#include "fei_fwd.hpp"

#include <algorithm>

namespace snl_fei {

  template<typename T>
    int binarySearch(const T& item,
         const T* list,
         int len)
    {
      if (len < 2) {
  if (len < 1) {
    return(-1);
  }

  if (list[0] != item) {
    return(-1);
  }
  else {
    return(0);
  }
      }

      unsigned start = 0;
      unsigned end = len - 1;

      while(end - start > 1) {
  unsigned mid = (start + end) >> 1;
  if (list[mid] < item) start = mid;
  else end = mid;
      }

      if (list[end] == item) return(end);
      if (list[start] == item) return(start);

      return(-1);
    }

  template<typename T>
    void insertion_sort_with_companions(int len, int* array, T* companions)
    {
      int i, j, index;
      T companion;

      for (i=1; i < len; i++) {
        index = array[i];
        companion = companions[i];
        j = i;
        while ((j > 0) && (array[j-1] > index))
        {
          array[j] = array[j-1];
          companions[j] = companions[j-1];
          j = j - 1;
        }
        array[j] = index;
        companions[j] = companion;
      }
    }

  template<typename T>
  int lowerBound(const T& item,
     const T* list,
     int len)
  {
    //The correctness of this function is tested in
    // fei/test_utils/test_misc.cpp, in test_misc::serialtest2().

    if (len < 1) return 0;

    unsigned start = 0;
    unsigned end = len - 1;

    while(end - start > 1) {
      unsigned mid = (start + end) >> 1;
      if (list[mid] < item) start = mid;
      else end = mid;
    }

    if (list[end] < item) {
      return(end+1);
    }

    if (list[start] < item) {
      return(end);
    }

    return(start);
  }

  template<typename T>
    int binarySearch(const T& item,
         const T* list,
         int len,
         int& insertPoint)
    {
      //The correctness of this function is tested in src/utils/test_Set.C,
      //in the function test_Set::test2.

      if (len < 2) {
  if (len < 1) {
    insertPoint = 0;
    return(-1);
  }

  if (list[0] < item) {
    insertPoint = 1;
    return(-1);
  }
  if (item < list[0]) {
    insertPoint = 0;
    return(-1);
  }
  else {
    return(0);
  }
      }

      unsigned start = 0;
      unsigned end = len - 1;

      while(end - start > 1) {
  unsigned mid = (start + end) >> 1;
  if (list[mid] < item) start = mid;
  else end = mid;
      }

      if (list[end] < item) {
  insertPoint = end+1;
  return(-1);
      }

      if (item < list[end]) {
  if (list[start] < item) {
    insertPoint = end;
    return(-1);
  }

  if (item < list[start]) {
    insertPoint = start;
    return(-1);
  }
  else {
    return(start);
  }
      }
      else {
  return(end);
      }
    }

  template<typename T>
    int binarySearch(const T& item, const std::vector<T>& list, int& insertPoint)
    {
      if (list.size() == 0) {
        insertPoint = 0;
        return(-1);
      }
      return( binarySearch(item, &list[0], list.size(), insertPoint) );
    }

  template<typename T>
    int binarySearch(const T& item, const std::vector<T>& list)
    {
      if (list.size() == 0) return(-1);
      return( binarySearch(item, &list[0], list.size()) );
    }

  template<typename T>
    int binarySearch(const T& item, const T* list, int /*listLength*/,
         int start, int end, int& insertPoint)
    {
      int length = end - start + 1;

      if (length < 2) {
  if (length < 1) {
    insertPoint = start;
    return(-1);
  }

  if (list[start] < item) {
    insertPoint = start+1;
    return(-1);
  }
  if (item < list[start]) {
    insertPoint = start;
    return(-1);
  }
  else {
    return(start);
  }
      }

      unsigned ustart = start;
      unsigned uend = end;

      while(uend - ustart > 1) {
  unsigned mid = (ustart + uend) >> 1;
  if (list[mid] < item) ustart = mid;
  else uend = mid;
      }

      //if list[uend] < item, then insertPoint = end+1
      if (list[uend] < item) {
  insertPoint = uend+1;
  return(-1);
      }

      if (item < list[uend]) {
  if (list[ustart] < item) {
    insertPoint = uend;
    return(-1);
  }

  if (item < list[ustart]) {
    insertPoint = ustart;
    return(-1);
  }
  else {
    //list[ustart] == item
    return(ustart);
  }
      }

      // list[uend] == item
      return(uend);
    }

  template<typename T>
    int binarySearch(int numItems, const T* items, int* offsets,
         const T* list, int listLength)
    {
      int i;
      if (numItems < 1 || listLength < 1) {
  if (listLength < 1) {
    for(i=0; i<numItems; ++i) offsets[i] = -1;
  }
      }

      int tmp, start = 0;
      int end = listLength -1;
      int insertPoint = -1;
      for(i=0; i<numItems; ++i) {
  tmp = binarySearch(items[i], list, listLength, start, end, insertPoint);
  start = tmp > -1 ? tmp : insertPoint;
  offsets[i] = tmp;
      }

      return(0);
    }

  template<class T>
    int sortedListInsert(const T& item, std::vector<T>& list)
    {
      typename std::vector<T>::iterator iter =
        std::lower_bound(list.begin(), list.end(), item);

      if (iter == list.end() || *iter != item) {
        iter = list.insert(iter, item);
        return( iter - list.begin() );
      }

      return(-1);
    }

  template<class T>
    int sortedListInsert(const T& item, T*& list, int& len, int& allocLen)
    {
      int i, insertPoint = -1;
      int index = binarySearch(item, list, len, insertPoint);
      if (index < 0) {
  if (len >= allocLen) {
    allocLen = len+2;
    T* newlist = new T[allocLen];
    for(i=0; i<insertPoint; ++i) newlist[i] = list[i];
    newlist[insertPoint] = item;
    for(i=insertPoint; i<len; ++i) newlist[i+1] = list[i];
    delete [] list;
    list = newlist;
  }
  else {
    for(i=len; i>insertPoint; --i) {
      list[i] = list[i-1];
    }
    list[insertPoint] = item;
  }
  ++len;
  return(insertPoint);
      }

      return(-1);
    }

  template<class T>
    int listInsert(const T& item, int offset, T*& list,
       int& usedLength, int& allocatedLength,
       int allocChunkSize=200)
    {
      if (offset < 0 || offset > usedLength) {
  return(-1);
      }

      if (usedLength < allocatedLength) {
  for(int i=usedLength; i>offset; --i) {
    list[i] = list[i-1];
  }
  list[offset] = item;
  ++usedLength;
  return(0);
      }

      T* newlist = new T[allocatedLength+allocChunkSize];

      allocatedLength += allocChunkSize;
      int i;
      for(i=0; i<offset; ++i) {
  newlist[i] = list[i];
      }

      newlist[offset] = item;

      for(i=offset+1; i<=usedLength; ++i) {
  newlist[i] = list[i-1];
      }

      ++usedLength;
      delete [] list;
      list = newlist;
      return(0);
    }

  template<class T>
    int searchList(const T& item, const T* list, int len)
    {
      for(int i=0; i<len; ++i) {
  if (list[i] == item) {
    return(i);
  }
      }
      return(-1);
    }

} //namespace snl_fei

#endif // _snl_fei_ArrayUtils_hpp_