42 #ifndef TPETRA_UTIL_HPP 43 #define TPETRA_UTIL_HPP 71 #include "Tpetra_ConfigDefs.hpp" 74 #include <Teuchos_Utils.hpp> 75 #include <Teuchos_Assert.hpp> 78 #if defined(HAVE_TPETRA_THROW_EFFICIENCY_WARNINGS) || defined(HAVE_TPETRA_PRINT_EFFICIENCY_WARNINGS) 79 #define TPETRA_EFFICIENCY_WARNING(throw_exception_test,Exception,msg) \ 114 const bool tpetraEfficiencyWarningTest = (throw_exception_test); \ 115 if (tpetraEfficiencyWarningTest) { \ 116 std::ostringstream errStream; \ 117 errStream << Teuchos::typeName(*this) << ":" << std::endl; \ 118 errStream << "Efficiency warning: " << #throw_exception_test << std::endl; \ 120 std::string err = errStream.str(); \ 121 if (TPETRA_PRINTS_EFFICIENCY_WARNINGS && tpetraEfficiencyWarningTest) { \ 122 std::cerr << err << std::endl; \ 124 TEUCHOS_TEST_FOR_EXCEPTION(TPETRA_THROWS_EFFICIENCY_WARNINGS && tpetraEfficiencyWarningTest, Exception, err); \ 128 #define TPETRA_EFFICIENCY_WARNING(throw_exception_test,Exception,msg) 165 #if defined(HAVE_TPETRA_THROW_ABUSE_WARNINGS) || defined(HAVE_TPETRA_PRINT_ABUSE_WARNINGS) 166 #define TPETRA_ABUSE_WARNING(throw_exception_test,Exception,msg) \ 169 std::ostringstream errStream; \ 170 errStream << Teuchos::typeName(*this) << msg; \ 171 std::string err = errStream.str(); \ 172 if (TPETRA_PRINTS_ABUSE_WARNINGS && (throw_exception_test)) { \ 173 std::cerr << err << std::endl; \ 175 TEUCHOS_TEST_FOR_EXCEPTION(TPETRA_THROWS_ABUSE_WARNINGS && (throw_exception_test), Exception, err); \ 178 #define TPETRA_ABUSE_WARNING(throw_exception_test,Exception,msg) 211 #define SHARED_TEST_FOR_EXCEPTION(throw_exception_test,Exception,msg,comm) \ 213 using Teuchos::outArg; \ 214 const int lcl_throw_exception = (throw_exception_test) ? Teuchos::rank(comm)+1 : 0; \ 216 Teuchos::reduceAll(comm,Teuchos::REDUCE_MAX,lcl_throw_exception,outArg(gbl_throw)); \ 217 TEUCHOS_TEST_FOR_EXCEPTION(gbl_throw,Exception, \ 218 msg << " Failure on at least one process, including process " << gbl_throw-1 << "." << std::endl); \ 221 #ifdef HAVE_TEUCHOS_DEBUG 222 #define SWITCHED_TEST_FOR_EXCEPTION(throw_exception_test,Exception,msg,comm) \ 225 SHARED_TEST_FOR_EXCEPTION(throw_exception_test,Exception,msg,comm); \ 228 #define SWITCHED_TEST_FOR_EXCEPTION(throw_exception_test,Exception,msg,comm) \ 231 TEUCHOS_TEST_FOR_EXCEPTION(throw_exception_test,Exception,msg); \ 248 template<
typename MapType,
typename KeyArgType,
typename ValueArgType>
250 const KeyArgType & k,
251 const ValueArgType & v)
253 typename MapType::iterator lb = m.lower_bound(k);
254 if(lb != m.end() && !(m.key_comp()(k, lb->first))) {
259 typedef typename MapType::value_type MVT;
260 return(m.insert(lb, MVT(k, v)));
283 typedef typename std::iterator_traits<IT1>::difference_type DT;
284 DT myit =OrdinalTraits<DT>::one();
285 const DT sz = last - first;
286 for(;myit < sz; ++myit){
287 if(first[myit] < first[myit-1]){
305 IT pivot(first+(last-first)/2);
306 if(*first<=*pivot && *(last-1)<=*first) pivot=first;
307 else if(*(last-1)<=*pivot && *first<= *(last-1)) pivot = last-1;
325 template<
class IT1,
class IT2>
333 typename std::iterator_traits<IT1>::value_type piv(*pivot);
334 std::swap(*pivot, *(last1-1));
335 std::swap(first2[(pivot-first1)], *(last2-1));
337 for(IT1 it=first1; it!=last1-1; ++it){
339 std::swap(*store1, *it);
340 std::swap(first2[(store1-first1)], first2[(it-first1)]);
344 std::swap(*(last1-1), *store1);
345 std::swap(*(last2-1), first2[store1-first1]);
365 template<
class IT1,
class IT2,
class IT3>
375 typename std::iterator_traits<IT1>::value_type piv(*pivot);
376 std::swap(*pivot, *(last1-1));
377 std::swap(first2[(pivot-first1)], *(last2-1));
378 std::swap(first3[(pivot-first1)], *(last3-1));
380 for(IT1 it=first1; it!=last1-1; ++it){
382 std::swap(*store1, *it);
383 std::swap(first2[(store1-first1)], first2[(it-first1)]);
384 std::swap(first3[(store1-first1)], first3[(it-first1)]);
388 std::swap(*(last1-1), *store1);
389 std::swap(*(last2-1), first2[store1-first1]);
390 std::swap(*(last3-1), first3[store1-first1]);
404 template<
class IT1,
class IT2>
411 typedef typename std::iterator_traits<IT1>::difference_type DT;
412 DT DT1 = OrdinalTraits<DT>::one();
413 if(last1-first1 > DT1){
414 IT1 pivot =
getPivot(first1, last1);
415 pivot =
partition2(first1, last1, first2, last2, pivot);
416 quicksort2(first1, pivot, first2, first2+(pivot-first1));
417 quicksort2(pivot+1, last1, first2+(pivot-first1)+1, last2);
433 template<
class IT1,
class IT2,
class IT3>
442 typedef typename std::iterator_traits<IT1>::difference_type DT;
443 DT DT1 = OrdinalTraits<DT>::one();
444 if(last1-first1 > DT1){
445 IT1 pivot =
getPivot(first1, last1);
446 pivot =
partition3(first1, last1, first2, last2, first3, last3, pivot);
447 quicksort3(first1, pivot, first2, first2+(pivot-first1), first3, first3+(pivot-first1));
448 quicksort3(pivot+1, last1, first2+(pivot-first1)+1, last2, first3+(pivot-first1)+1, last3);
458 template<
class IT1,
class IT2,
class IT3>
467 typedef typename std::iterator_traits<IT1>::difference_type DT;
468 DT n = last1 - first1;
470 DT z = OrdinalTraits<DT>::zero();
474 for (DT j = 0; j < max; j++)
476 for (DT k = j; k >= 0; k-=m)
478 if (first1[k+m] >= first1[k])
480 std::swap(first1[k+m], first1[k]);
481 std::swap(first2[k+m], first2[k]);
482 std::swap(first3[k+m], first3[k]);
495 template<
class IT1,
class IT2>
502 typedef typename std::iterator_traits<IT1>::difference_type DT;
503 DT n = last1 - first1;
505 DT z = OrdinalTraits<DT>::zero();
509 for (DT j = 0; j < max; j++)
511 for (DT k = j; k >= 0; k-=m)
513 if (first1[k+m] >= first1[k])
515 std::swap(first1[k+m], first1[k]);
516 std::swap(first2[k+m], first2[k]);
544 template<
class IT1,
class IT2>
545 void sort2(
const IT1 &first1,
const IT1 &last1,
const IT2 &first2) {
550 if(SortDetails::isAlreadySorted(first1, last1)){
553 SortDetails::sh_sort2(first1, last1, first2, first2+(last1-first1));
554 #ifdef HAVE_TPETRA_DEBUG 555 if(!SortDetails::isAlreadySorted(first1, last1)){
556 std::cout <<
"Trouble: sort() did not sort !!" << std::endl;
578 template<
class IT1,
class IT2,
class IT3>
579 void sort3(
const IT1 &first1,
const IT1 &last1,
const IT2 &first2,
586 if(SortDetails::isAlreadySorted(first1, last1)){
589 SortDetails::sh_sort3(first1, last1, first2, first2+(last1-first1), first3,
590 first3+(last1-first1));
592 #ifdef HAVE_TPETRA_DEBUG 593 if(!SortDetails::isAlreadySorted(first1, last1)){
594 std::cout <<
" Trouble sort did not actually sort... !!!!!!" <<
644 template<
class IT1,
class IT2>
646 merge2 (IT1& indResultOut, IT2& valResultOut,
647 IT1 indBeg, IT1 indEnd,
648 IT2 valBeg, IT2 valEnd)
650 if (indBeg == indEnd) {
651 indResultOut = indBeg;
652 valResultOut = valBeg;
655 IT1 indResult = indBeg;
656 IT2 valResult = valBeg;
657 if (indBeg != indEnd) {
660 while (indBeg != indEnd) {
661 if (*indResult == *indBeg) {
662 *valResult += *valBeg;
664 *(++indResult) = *indBeg;
665 *(++valResult) = *valBeg;
680 indResultOut = indResult;
681 valResultOut = valResult;
733 template<
class IT1,
class IT2,
class BinaryFunction>
735 merge2 (IT1& indResultOut, IT2& valResultOut,
736 IT1 indBeg, IT1 indEnd,
737 IT2 valBeg, IT2 valEnd,
740 if (indBeg == indEnd) {
741 indResultOut = indBeg;
742 valResultOut = valBeg;
745 IT1 indResult = indBeg;
746 IT2 valResult = valBeg;
747 if (indBeg != indEnd) {
750 while (indBeg != indEnd) {
751 if (*indResult == *indBeg) {
752 *valResult = f (*valResult, *valBeg);
754 *(++indResult) = *indBeg;
755 *(++valResult) = *valBeg;
765 indResultOut = indResult;
766 valResultOut = valResult;
799 template<
class KeyInputIterType,
class ValueInputIterType,
800 class KeyOutputIterType,
class ValueOutputIterType,
801 class BinaryFunction>
804 ValueInputIterType valBeg1, ValueInputIterType valEnd1,
805 KeyInputIterType keyBeg2, KeyInputIterType keyEnd2,
806 ValueInputIterType valBeg2, ValueInputIterType valEnd2,
807 KeyOutputIterType keyOut, ValueOutputIterType valOut,
810 while (keyBeg1 != keyEnd1 && keyBeg2 != keyEnd2) {
811 if (*keyBeg1 < *keyBeg2) {
812 *keyOut++ = *keyBeg1++;
813 *valOut++ = *valBeg1++;
814 }
else if (*keyBeg1 > *keyBeg2) {
815 *keyOut++ = *keyBeg2++;
816 *valOut++ = *valBeg2++;
818 *keyOut++ = *keyBeg1;
819 *valOut++ = f (*valBeg1, *valBeg2);
827 std::copy (keyBeg1, keyEnd1, keyOut);
828 std::copy (valBeg1, valEnd1, valOut);
829 std::copy (keyBeg2, keyEnd2, keyOut);
830 std::copy (valBeg2, valEnd2, valOut);
833 template<
class KeyInputIterType>
835 keyMergeCount (KeyInputIterType keyBeg1, KeyInputIterType keyEnd1,
836 KeyInputIterType keyBeg2, KeyInputIterType keyEnd2)
839 while (keyBeg1 != keyEnd1 && keyBeg2 != keyEnd2) {
840 if (*keyBeg1 < *keyBeg2) {
842 }
else if (*keyBeg1 > *keyBeg2) {
851 count +=
static_cast<size_t> (keyEnd1 - keyBeg1) +
852 static_cast<size_t> (keyEnd2 - keyBeg2);
877 congruent (
const Teuchos::Comm<int>& comm1,
878 const Teuchos::Comm<int>& comm2);
883 #endif // TPETRA_UTIL_HPP Namespace Tpetra contains the class and methods constituting the Tpetra library.
void quicksort3(const IT1 &first1, const IT1 &last1, const IT2 &first2, const IT2 &last2, const IT3 &first3, const IT3 &last3)
Sort the first array using Quicksort, and apply the resulting permutation to the second and third arr...
void sort3(const IT1 &first1, const IT1 &last1, const IT2 &first2, const IT3 &first3)
Sort the first array, and apply the same permutation to the second and third arrays.
IT1 partition2(const IT1 &first1, const IT1 &last1, const IT2 &first2, const IT2 &last2, const IT1 &pivot)
Partition operation for quicksort2().
void quicksort2(const IT1 &first1, const IT1 &last1, const IT2 &first2, const IT2 &last2)
Sort the first array using Quicksort, and apply the resulting permutation to the second array...
Implementation details of Tpetra.
void sh_sort3(const IT1 &first1, const IT1 &last1, const IT2 &first2, const IT2 &last2, const IT3 &first3, const IT3 &last3)
Sort the first array using shell sort, and apply the resulting permutation to the second and third ar...
void merge2(IT1 &indResultOut, IT2 &valResultOut, IT1 indBeg, IT1 indEnd, IT2 valBeg, IT2 valEnd)
Merge values in place, additively, with the same index.
void keyValueMerge(KeyInputIterType keyBeg1, KeyInputIterType keyEnd1, ValueInputIterType valBeg1, ValueInputIterType valEnd1, KeyInputIterType keyBeg2, KeyInputIterType keyEnd2, ValueInputIterType valBeg2, ValueInputIterType valEnd2, KeyOutputIterType keyOut, ValueOutputIterType valOut, BinaryFunction f)
Merge two sorted (by keys) sequences of unique (key,value) pairs by combining pairs with equal keys...
IT getPivot(const IT &first, const IT &last)
Determines the pivot point as part of the quicksort routine.
MapType::iterator efficientAddOrUpdate(MapType &m, const KeyArgType &k, const ValueArgType &v)
Efficiently insert or replace an entry in an std::map.
void sort2(const IT1 &first1, const IT1 &last1, const IT2 &first2)
Sort the first array, and apply the resulting permutation to the second array.
Implementation details of sort routines used by Tpetra.
IT1 partition3(const IT1 &first1, const IT1 &last1, const IT2 &first2, const IT2 &last2, const IT3 &first3, const IT3 &last3, const IT1 &pivot)
Partition operation for quicksort3().
bool isAlreadySorted(const IT1 &first, const IT1 &last)
Determines whether or not a random access sequence is already sorted.
void sh_sort2(const IT1 &first1, const IT1 &last1, const IT2 &first2, const IT2 &last2)
Sort the first array using shell sort, and apply the resulting permutation to the second array...