Tpetra Matrix/Vector Services Version of the Day
Tpetra_Util.hpp
Go to the documentation of this file.
00001 // HAVE_@HEADER
00002 // ***********************************************************************
00003 // 
00004 //          Tpetra: Templated Linear Algebra Services Package
00005 //                 Copyright (2008) Sandia Corporation
00006 // 
00007 // Under terms of Contract DE-AC04-94AL85000, there is a non-exclusive
00008 // license for use of this work by or on behalf of the U.S. Government.
00009 // 
00010 // This library is free software; you can redistribute it and/or modify
00011 // it under the terms of the GNU Lesser General Public License as
00012 // published by the Free Software Foundation; either version 2.1 of the
00013 // License, or (at your option) any later version.
00014 //  
00015 // This library is distributed in the hope that it will be useful, but
00016 // WITHOUT ANY WARRANTY; without even the implied warranty of
00017 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00018 // Lesser General Public License for more details.
00019 //  
00020 // You should have received a copy of the GNU Lesser General Public
00021 // License along with this library; if not, write to the Free Software
00022 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
00023 // USA
00024 // Questions? Contact Michael A. Heroux (maherou@sandia.gov) 
00025 // 
00026 // ***********************************************************************
00027 // @HEADER
00028 
00029 #ifndef TPETRA_UTIL_HPP
00030 #define TPETRA_UTIL_HPP
00031 
00032 #include "Tpetra_ConfigDefs.hpp" // for map, vector, string, and iostream 
00033 #include <iterator>
00034 #include <algorithm>
00035 #include <Teuchos_Utils.hpp>
00036 #include <Teuchos_TestForException.hpp>
00037 #include <sstream>
00038 
00039 #if defined(HAVE_TPETRA_THROW_EFFICIENCY_WARNINGS) || defined(HAVE_TPETRA_PRINT_EFFICIENCY_WARNINGS)
00040 
00041 #define TPETRA_EFFICIENCY_WARNING(throw_exception_test,Exception,msg)                                 \
00042 {                                                                                                     \
00043   std::ostringstream errStream;                                                                       \
00044   errStream << Teuchos::typeName(*this) << msg;                                                       \
00045   std::string err = errStream.str();                                                                  \
00046   if (TPETRA_PRINTS_EFFICIENCY_WARNINGS && (throw_exception_test)) {                                  \
00047     std::cerr << err << std::endl;                                                                    \
00048   }                                                                                                   \
00049   TEST_FOR_EXCEPTION(TPETRA_THROWS_EFFICIENCY_WARNINGS && (throw_exception_test), Exception, err);    \
00050 }
00051 #else
00052 
00053 #define TPETRA_EFFICIENCY_WARNING(throw_exception_test,Exception,msg)
00054 #endif
00055 
00056 // handle an abuse warning, according to HAVE_TPETRA_THROW_ABUSE_WARNINGS and HAVE_TPETRA_PRINT_ABUSE_WARNINGS
00057 #if defined(HAVE_TPETRA_THROW_ABUSE_WARNINGS) || defined(HAVE_TPETRA_PRINT_ABUSE_WARNINGS)
00058 
00059 #define TPETRA_ABUSE_WARNING(throw_exception_test,Exception,msg)                               \
00060 {                                                                                              \
00061   std::ostringstream errStream;                                                                \
00062   errStream << Teuchos::typeName(*this) << msg;                                                \
00063   std::string err = errStream.str();                                                           \
00064   if (TPETRA_PRINTS_ABUSE_WARNINGS && (throw_exception_test)) {                                \
00065     std::cerr << err << std::endl;                                                             \
00066   }                                                                                            \
00067   TEST_FOR_EXCEPTION(TPETRA_THROWS_ABUSE_WARNINGS && (throw_exception_test), Exception, err);  \
00068 }
00069 #else
00070 
00071 #define TPETRA_ABUSE_WARNING(throw_exception_test,Exception,msg)
00072 #endif
00073 
00074 
00078 #define SHARED_TEST_FOR_EXCEPTION(throw_exception_test,Exception,msg,comm) \
00079 { \
00080     using Teuchos::outArg; \
00081     const int lcl_throw_exception = (throw_exception_test) ? Teuchos::rank(comm)+1 : 0; \
00082     int gbl_throw; \
00083     Teuchos::reduceAll(comm,Teuchos::REDUCE_MAX,lcl_throw_exception,outArg(gbl_throw)); \
00084     TEST_FOR_EXCEPTION(gbl_throw,Exception,  \
00085                        msg << " Failure on node " << gbl_throw-1 << "." << std::endl); \
00086 }
00087 
00088 #ifdef HAVE_TEUCHOS_DEBUG
00089 
00090 #define SWITCHED_TEST_FOR_EXCEPTION(throw_exception_test,Exception,msg,comm) \
00091 { \
00092     SHARED_TEST_FOR_EXCEPTION(throw_exception_test,Exception,msg,comm); \
00093 }
00094 #else 
00095 
00096 #define SWITCHED_TEST_FOR_EXCEPTION(throw_exception_test,Exception,msg,comm) \
00097 { \
00098     TEST_FOR_EXCEPTION(throw_exception_test,Exception,msg); \
00099 }
00100 #endif
00101 
00102 namespace Tpetra {
00103 
00130   template<typename MapType, typename KeyArgType, typename ValueArgType>
00131   typename MapType::iterator efficientAddOrUpdate(MapType& m, 
00132                           const KeyArgType & k, 
00133                           const ValueArgType & v) 
00134   {
00135     typename MapType::iterator lb = m.lower_bound(k);
00136     if(lb != m.end() && !(m.key_comp()(k, lb->first))) {
00137       lb->second = v;
00138       return(lb);
00139     }
00140     else {
00141       typedef typename MapType::value_type MVT;
00142       return(m.insert(lb, MVT(k, v)));
00143     }
00144   }
00145 
00146 
00147   namespace SortDetails{
00148 
00149 
00158   template<class IT1>
00159   bool isAlreadySorted(const IT1& first, const IT1& last){
00160     typedef typename std::iterator_traits<IT1>::difference_type DT;
00161     DT myit =OrdinalTraits<DT>::one();
00162     const DT sz  = last - first;
00163     for(;myit < sz; ++myit){
00164       if(first[myit] < first[myit-1]){
00165         return false;
00166       }
00167     }
00168     return true;
00169   }
00170 
00180   template<class IT>
00181   IT getPivot(const IT& first, const IT& last){
00182     IT pivot(first+(last-first)/2);
00183     if(*first<=*pivot && *(last-1)<=*first) pivot=first;
00184     else if(*(last-1)<=*pivot && *first<= *(last-1)) pivot = last-1;
00185     return pivot; 
00186   }
00187 
00199   template<class IT1, class IT2>
00200   IT1 partition2(
00201     const IT1& first1,
00202     const IT1& last1,
00203     const IT2& first2,
00204     const IT2& last2,
00205     const IT1& pivot)
00206   {
00207     typename std::iterator_traits<IT1>::value_type piv(*pivot);
00208     std::swap(*pivot, *(last1-1));
00209     std::swap(first2[(pivot-first1)], *(last2-1));
00210     IT1 store1=first1;
00211     for(IT1 it=first1; it!=last1-1; ++it){
00212       if(*it<=piv){
00213         std::swap(*store1, *it);
00214         std::swap(first2[(store1-first1)], first2[(it-first1)]);
00215         ++store1;
00216       }
00217     }
00218     std::swap(*(last1-1), *store1);
00219     std::swap(*(last2-1), first2[store1-first1]);
00220     return store1;
00221   }
00222 
00236   template<class IT1, class IT2, class IT3>
00237   IT1 partition3(
00238     const IT1& first1,
00239     const IT1& last1,
00240     const IT2& first2,
00241     const IT2& last2,
00242     const IT3& first3,
00243     const IT3& last3,
00244     const IT1& pivot)
00245   {
00246     typename std::iterator_traits<IT1>::value_type piv(*pivot);
00247     std::swap(*pivot, *(last1-1));
00248     std::swap(first2[(pivot-first1)], *(last2-1));
00249     std::swap(first3[(pivot-first1)], *(last3-1));
00250     IT1 store1=first1;
00251     for(IT1 it=first1; it!=last1-1; ++it){
00252       if(*it<=piv){
00253         std::swap(*store1, *it);
00254         std::swap(first2[(store1-first1)], first2[(it-first1)]);
00255         std::swap(first3[(store1-first1)], first3[(it-first1)]);
00256         ++store1;
00257       }
00258     }
00259     std::swap(*(last1-1), *store1);
00260     std::swap(*(last2-1), first2[store1-first1]);
00261     std::swap(*(last3-1), first3[store1-first1]);
00262     return store1;
00263   }
00264 
00274   template<class IT1, class IT2>
00275   void quicksort2(
00276     const IT1& first1,
00277     const IT1& last1,
00278     const IT2& first2,
00279     const IT2& last2)
00280   {
00281     typedef typename std::iterator_traits<IT1>::difference_type DT;
00282     DT DT1 = OrdinalTraits<DT>::one();
00283     if(last1-first1 > DT1){
00284       IT1 pivot = getPivot(first1, last1);
00285       pivot = partition2(first1, last1, first2, last2, pivot);
00286       quicksort2(first1, pivot, first2, first2+(pivot-first1));
00287       quicksort2(pivot+1, last1, first2+(pivot-first1)+1, last2);
00288     }
00289   }
00290 
00302   template<class IT1, class IT2, class IT3>
00303   void quicksort3(
00304     const IT1& first1,
00305     const IT1& last1,
00306     const IT2& first2,
00307     const IT2& last2,
00308     const IT3& first3,
00309     const IT3& last3)
00310   {
00311     typedef typename std::iterator_traits<IT1>::difference_type DT;
00312     DT DT1 = OrdinalTraits<DT>::one();
00313     if(last1-first1 > DT1){
00314       IT1 pivot = getPivot(first1, last1);
00315       pivot = partition3(first1, last1, first2, last2, first3, last3, pivot);
00316       quicksort3(first1, pivot, first2, first2+(pivot-first1), first3, first3+(pivot-first1));
00317       quicksort3(pivot+1, last1, first2+(pivot-first1)+1, last2, first3+(pivot-first1)+1, last3);
00318     }
00319   }
00320 
00321 
00322   } //end namespace SortDetails
00323 
00324 
00336   template<class IT1, class IT2>
00337   void sort2(const IT1 &first1, const IT1 &last1, const IT2 &first2) {
00338     if(SortDetails::isAlreadySorted(first1, last1)){
00339       return;
00340     }
00341     SortDetails::quicksort2(first1, last1, first2, first2+(last1-first1));
00342   }
00343 
00344   
00357   template<class IT1, class IT2, class IT3>
00358   void sort3(const IT1 &first1, const IT1 &last1, const IT2 &first2, const IT3 &first3)
00359   {
00360     if(SortDetails::isAlreadySorted(first1, last1)){
00361       return;
00362     }
00363     SortDetails::quicksort3(first1, last1, first2, first2+(last1-first1), first3, first3+(last1-first1));
00364   }
00365 
00372   template<class IT1, class T>
00373   IT1 binary_serach(IT1 first, IT1 last, const T& value){
00374   first = std::lower_bound(first,last,value);
00375   if(first!=last && !(value<*first)){
00376     return first;
00377   }
00378   else{
00379     return last;
00380   }
00381   }
00382   
00383 } // namespace Tpetra
00384 
00385 
00386 #endif // TPETRA_UTIL_HPP
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines