Tpetra_Util.hpp

Go to the documentation of this file.

// @HEADER
// ***********************************************************************
//
//          Tpetra: Templated Linear Algebra Services Package
//                 Copyright (2008) Sandia Corporation
//
// Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
// the U.S. Government retains certain rights in this software.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
// 1. Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//
// 2. Redistributions in binary form must reproduce the above copyright
// notice, this list of conditions and the following disclaimer in the
// documentation and/or other materials provided with the distribution.
//
// 3. Neither the name of the Corporation nor the names of the
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
// Questions? Contact Michael A. Heroux (maherou@sandia.gov)
//
// ************************************************************************
// @HEADER

#ifndef TPETRA_UTIL_HPP
#define TPETRA_UTIL_HPP

#include "Tpetra_ConfigDefs.hpp" // for map, vector, string, and iostream
#include <iterator>
#include <algorithm>
#include <Teuchos_Utils.hpp>
#include <Teuchos_Assert.hpp>
#include <sstream>

#if defined(HAVE_TPETRA_THROW_EFFICIENCY_WARNINGS) || defined(HAVE_TPETRA_PRINT_EFFICIENCY_WARNINGS)

































#define TPETRA_EFFICIENCY_WARNING(throw_exception_test,Exception,msg)  \
{ \
  const bool tpetraEfficiencyWarningTest = (throw_exception_test); \
  if (tpetraEfficiencyWarningTest) { \
    std::ostringstream errStream; \
    errStream << Teuchos::typeName(*this) << ":" << std::endl; \
    errStream << "Efficiency warning: " << #throw_exception_test << std::endl; \
    errStream << msg; \
    std::string err = errStream.str(); \
    if (TPETRA_PRINTS_EFFICIENCY_WARNINGS && tpetraEfficiencyWarningTest) { \
      std::cerr << err << std::endl; \
    } \
    TEUCHOS_TEST_FOR_EXCEPTION(TPETRA_THROWS_EFFICIENCY_WARNINGS && tpetraEfficiencyWarningTest, Exception, err); \
  } \
}
#else

































#define TPETRA_EFFICIENCY_WARNING(throw_exception_test,Exception,msg)
#endif

// handle an abuse warning, according to HAVE_TPETRA_THROW_ABUSE_WARNINGS and HAVE_TPETRA_PRINT_ABUSE_WARNINGS
#if defined(HAVE_TPETRA_THROW_ABUSE_WARNINGS) || defined(HAVE_TPETRA_PRINT_ABUSE_WARNINGS)

#define TPETRA_ABUSE_WARNING(throw_exception_test,Exception,msg)                               \
{                                                                                              \
  std::ostringstream errStream;                                                                \
  errStream << Teuchos::typeName(*this) << msg;                                                \
  std::string err = errStream.str();                                                           \
  if (TPETRA_PRINTS_ABUSE_WARNINGS && (throw_exception_test)) {                                \
    std::cerr << err << std::endl;                                                             \
  }                                                                                            \
  TEUCHOS_TEST_FOR_EXCEPTION(TPETRA_THROWS_ABUSE_WARNINGS && (throw_exception_test), Exception, err);  \
}
#else

#define TPETRA_ABUSE_WARNING(throw_exception_test,Exception,msg)
#endif

#define SHARED_TEST_FOR_EXCEPTION(throw_exception_test,Exception,msg,comm) \
{ \
    using Teuchos::outArg; \
    const int lcl_throw_exception = (throw_exception_test) ? Teuchos::rank(comm)+1 : 0; \
    int gbl_throw; \
    Teuchos::reduceAll(comm,Teuchos::REDUCE_MAX,lcl_throw_exception,outArg(gbl_throw)); \
    TEUCHOS_TEST_FOR_EXCEPTION(gbl_throw,Exception,  \
      msg << " Failure on at least one process, including process " << gbl_throw-1 << "." << std::endl); \
}

#ifdef HAVE_TEUCHOS_DEBUG

#define SWITCHED_TEST_FOR_EXCEPTION(throw_exception_test,Exception,msg,comm) \
{ \
    SHARED_TEST_FOR_EXCEPTION(throw_exception_test,Exception,msg,comm); \
}
#else

#define SWITCHED_TEST_FOR_EXCEPTION(throw_exception_test,Exception,msg,comm) \
{ \
    TEUCHOS_TEST_FOR_EXCEPTION(throw_exception_test,Exception,msg); \
}
#endif

namespace Tpetra {

  template<typename MapType, typename KeyArgType, typename ValueArgType>
  typename MapType::iterator efficientAddOrUpdate(MapType& m,
                          const KeyArgType & k,
                          const ValueArgType & v)
  {
    typename MapType::iterator lb = m.lower_bound(k);
    if(lb != m.end() && !(m.key_comp()(k, lb->first))) {
      lb->second = v;
      return(lb);
    }
    else {
      typedef typename MapType::value_type MVT;
      return(m.insert(lb, MVT(k, v)));
    }
  }

  namespace SortDetails {

  template<class IT1>
  bool isAlreadySorted(const IT1& first, const IT1& last){
    typedef typename std::iterator_traits<IT1>::difference_type DT;
    DT myit =OrdinalTraits<DT>::one();
    const DT sz  = last - first;
    for(;myit < sz; ++myit){
      if(first[myit] < first[myit-1]){
        return false;
      }
    }
    return true;
  }

  template<class IT>
  IT getPivot(const IT& first, const IT& last){
    IT pivot(first+(last-first)/2);
    if(*first<=*pivot && *(last-1)<=*first) pivot=first;
    else if(*(last-1)<=*pivot && *first<= *(last-1)) pivot = last-1;
    return pivot;
  }

  template<class IT1, class IT2>
  IT1 partition2(
    const IT1& first1,
    const IT1& last1,
    const IT2& first2,
    const IT2& last2,
    const IT1& pivot)
  {
    typename std::iterator_traits<IT1>::value_type piv(*pivot);
    std::swap(*pivot, *(last1-1));
    std::swap(first2[(pivot-first1)], *(last2-1));
    IT1 store1=first1;
    for(IT1 it=first1; it!=last1-1; ++it){
      if(*it<=piv){
        std::swap(*store1, *it);
        std::swap(first2[(store1-first1)], first2[(it-first1)]);
        ++store1;
      }
    }
    std::swap(*(last1-1), *store1);
    std::swap(*(last2-1), first2[store1-first1]);
    return store1;
  }

  template<class IT1, class IT2, class IT3>
  IT1 partition3(
    const IT1& first1,
    const IT1& last1,
    const IT2& first2,
    const IT2& last2,
    const IT3& first3,
    const IT3& last3,
    const IT1& pivot)
  {
    typename std::iterator_traits<IT1>::value_type piv(*pivot);
    std::swap(*pivot, *(last1-1));
    std::swap(first2[(pivot-first1)], *(last2-1));
    std::swap(first3[(pivot-first1)], *(last3-1));
    IT1 store1=first1;
    for(IT1 it=first1; it!=last1-1; ++it){
      if(*it<=piv){
        std::swap(*store1, *it);
        std::swap(first2[(store1-first1)], first2[(it-first1)]);
        std::swap(first3[(store1-first1)], first3[(it-first1)]);
        ++store1;
      }
    }
    std::swap(*(last1-1), *store1);
    std::swap(*(last2-1), first2[store1-first1]);
    std::swap(*(last3-1), first3[store1-first1]);
    return store1;
  }

  template<class IT1, class IT2>
  void quicksort2(
    const IT1& first1,
    const IT1& last1,
    const IT2& first2,
    const IT2& last2)
  {
    typedef typename std::iterator_traits<IT1>::difference_type DT;
    DT DT1 = OrdinalTraits<DT>::one();
    if(last1-first1 > DT1){
      IT1 pivot = getPivot(first1, last1);
      pivot = partition2(first1, last1, first2, last2, pivot);
      quicksort2(first1, pivot, first2, first2+(pivot-first1));
      quicksort2(pivot+1, last1, first2+(pivot-first1)+1, last2);
    }
  }

  template<class IT1, class IT2, class IT3>
  void quicksort3(
    const IT1& first1,
    const IT1& last1,
    const IT2& first2,
    const IT2& last2,
    const IT3& first3,
    const IT3& last3)
  {
    typedef typename std::iterator_traits<IT1>::difference_type DT;
    DT DT1 = OrdinalTraits<DT>::one();
    if(last1-first1 > DT1){
      IT1 pivot = getPivot(first1, last1);
      pivot = partition3(first1, last1, first2, last2, first3, last3, pivot);
      quicksort3(first1, pivot, first2, first2+(pivot-first1), first3, first3+(pivot-first1));
      quicksort3(pivot+1, last1, first2+(pivot-first1)+1, last2, first3+(pivot-first1)+1, last3);
    }
  }

  template<class IT1, class IT2, class IT3>
  void sh_sort3(
    const IT1& first1,
    const IT1& last1,
    const IT2& first2,
    const IT2& last2,
    const IT3& first3,
    const IT3& last3)
   {
        typedef typename std::iterator_traits<IT1>::difference_type DT;
        DT n = last1 - first1;
        DT m = n / 2;
        DT z = OrdinalTraits<DT>::zero();
        while (m > z)
        {
            DT max = n - m;
            for (DT j = 0; j < max; j++)
            {
                for (DT k = j; k >= 0; k-=m)
                {
                    if (first1[k+m] >= first1[k])
                        break;
                    std::swap(first1[k+m], first1[k]);
                    std::swap(first2[k+m], first2[k]);
                    std::swap(first3[k+m], first3[k]);
                }
            }
            m = m/2;
        }
   }

  template<class IT1, class IT2>
  void sh_sort2(
    const IT1& first1,
    const IT1& last1,
    const IT2& first2,
    const IT2& last2)
   {
        typedef typename std::iterator_traits<IT1>::difference_type DT;
        DT n = last1 - first1;
        DT m = n / 2;
        DT z = OrdinalTraits<DT>::zero();
        while (m > z)
        {
            DT max = n - m;
            for (DT j = 0; j < max; j++)
            {
                for (DT k = j; k >= 0; k-=m)
                {
                    if (first1[k+m] >= first1[k])
                        break;
                    std::swap(first1[k+m], first1[k]);
                    std::swap(first2[k+m], first2[k]);
                }
            }
            m = m/2;
        }
   }

  } //end namespace SortDetails


  template<class IT1, class IT2>
  void sort2(const IT1 &first1, const IT1 &last1, const IT2 &first2) {
    // Quicksort uses best-case N log N time whether or not the input
    // data is sorted.  However, the common case in Tpetra is that the
    // input data are sorted, so we first check whether this is the
    // case before reverting to Quicksort.
    if(SortDetails::isAlreadySorted(first1, last1)){
      return;
    }
    SortDetails::sh_sort2(first1, last1, first2, first2+(last1-first1));
#ifdef HAVE_TPETRA_DEBUG
    if(!SortDetails::isAlreadySorted(first1, last1)){
      std::cout << "Trouble: sort() did not sort !!" << std::endl;
      return;
    }
#endif
  }


  template<class IT1, class IT2, class IT3>
  void sort3(const IT1 &first1, const IT1 &last1, const IT2 &first2,
    const IT3 &first3)
  {
    // Quicksort uses best-case N log N time whether or not the input
    // data is sorted.  However, the common case in Tpetra is that the
    // input data are sorted, so we first check whether this is the
    // case before reverting to Quicksort.
    if(SortDetails::isAlreadySorted(first1, last1)){
      return;
    }
    SortDetails::sh_sort3(first1, last1, first2, first2+(last1-first1), first3,
                    first3+(last1-first1));

#ifdef HAVE_TPETRA_DEBUG
    if(!SortDetails::isAlreadySorted(first1, last1)){
        std::cout << " Trouble sort did not actually sort... !!!!!!" <<
                        std::endl;
      return;
    }
#endif
  }

  template<class IT1, class IT2>
  void
  merge2 (IT1& indResultOut, IT2& valResultOut,
          IT1 indBeg, IT1 indEnd,
          IT2 valBeg, IT2 valEnd)
  {
    if (indBeg == indEnd) {
      indResultOut = indBeg; // It's allowed for indResultOut to alias indEnd
      valResultOut = valBeg; // It's allowed for valResultOut to alias valEnd
    }
    else {
      IT1 indResult = indBeg;
      IT2 valResult = valBeg;
      if (indBeg != indEnd) {
        ++indBeg;
        ++valBeg;
        while (indBeg != indEnd) {
          if (*indResult == *indBeg) { // adjacent column indices equal
            *valResult += *valBeg; // merge entries by adding their values together
          } else { // adjacent column indices not equal
            *(++indResult) = *indBeg; // shift over the index
            *(++valResult) = *valBeg; // shift over the value
          }
          ++indBeg;
          ++valBeg;
        }
        ++indResult; // exclusive end of merged result
        ++valResult; // exclusive end of merged result

        // mfh 24 Feb 2014: Setting these is technically correct, but
        // since the resulting variables aren't used after this point,
        // it may result in a build error.
        //
        // indEnd = indResult;
        // valEnd = valResult;
      }
      indResultOut = indResult;
      valResultOut = valResult;
    }
  }

  template<class IT1, class IT2, class BinaryFunction>
  void
  merge2 (IT1& indResultOut, IT2& valResultOut,
          IT1 indBeg, IT1 indEnd,
          IT2 valBeg, IT2 valEnd,
          BinaryFunction f)
  {
    if (indBeg == indEnd) {
      indResultOut = indBeg; // It's allowed for indResultOut to alias indEnd
      valResultOut = valBeg; // It's allowed for valResultOut to alias valEnd
    }
    else {
      IT1 indResult = indBeg;
      IT2 valResult = valBeg;
      if (indBeg != indEnd) {
        ++indBeg;
        ++valBeg;
        while (indBeg != indEnd) {
          if (*indResult == *indBeg) { // adjacent column indices equal
            *valResult = f (*valResult, *valBeg); // merge entries via values
          } else { // adjacent column indices not equal
            *(++indResult) = *indBeg; // shift over the index
            *(++valResult) = *valBeg; // shift over the value
          }
          ++indBeg;
          ++valBeg;
        }
        ++indResult; // exclusive end of merged result
        ++valResult; // exclusive end of merged result
        indEnd = indResult;
        valEnd = valResult;
      }
      indResultOut = indResult;
      valResultOut = valResult;
    }
  }


  template<class KeyInputIterType, class ValueInputIterType,
           class KeyOutputIterType, class ValueOutputIterType,
           class BinaryFunction>
  void
  keyValueMerge (KeyInputIterType keyBeg1, KeyInputIterType keyEnd1,
                 ValueInputIterType valBeg1, ValueInputIterType valEnd1,
                 KeyInputIterType keyBeg2, KeyInputIterType keyEnd2,
                 ValueInputIterType valBeg2, ValueInputIterType valEnd2,
                 KeyOutputIterType keyOut, ValueOutputIterType valOut,
                 BinaryFunction f)
  {
    while (keyBeg1 != keyEnd1 && keyBeg2 != keyEnd2) {
      if (*keyBeg1 < *keyBeg2) {
        *keyOut++ = *keyBeg1++;
        *valOut++ = *valBeg1++;
      } else if (*keyBeg1 > *keyBeg2) {
        *keyOut++ = *keyBeg2++;
        *valOut++ = *valBeg2++;
      } else { // *keyBeg1 == *keyBeg2
        *keyOut++ = *keyBeg1;
        *valOut++ = f (*valBeg1, *valBeg2);
        ++keyBeg1;
        ++valBeg1;
        ++keyBeg2;
        ++valBeg2;
      }
    }
    // At most one of the two sequences will be nonempty.
    std::copy (keyBeg1, keyEnd1, keyOut);
    std::copy (valBeg1, valEnd1, valOut);
    std::copy (keyBeg2, keyEnd2, keyOut);
    std::copy (valBeg2, valEnd2, valOut);
  }

  template<class KeyInputIterType>
  size_t
  keyMergeCount (KeyInputIterType keyBeg1, KeyInputIterType keyEnd1,
                 KeyInputIterType keyBeg2, KeyInputIterType keyEnd2)
  {
    size_t count = 0;
    while (keyBeg1 != keyEnd1 && keyBeg2 != keyEnd2) {
      if (*keyBeg1 < *keyBeg2) {
        ++keyBeg1;
      } else if (*keyBeg1 > *keyBeg2) {
        ++keyBeg2;
      } else { // *keyBeg1 == *keyBeg2
        ++keyBeg1;
        ++keyBeg2;
      }
      ++count;
    }
    // At most one of the two sequences will be nonempty.
    count += static_cast<size_t> (keyEnd1 - keyBeg1) +
      static_cast<size_t> (keyEnd2 - keyBeg2);
    return count;
  }

  namespace Details {
    bool
    congruent (const Teuchos::Comm<int>& comm1,
               const Teuchos::Comm<int>& comm2);
  } // namespace Details

} // namespace Tpetra

#endif // TPETRA_UTIL_HPP