Tpetra parallel linear algebra Version of the Day
Loading...
Searching...
No Matches
Tpetra_Util.hpp
Go to the documentation of this file.
1// @HEADER
2// ***********************************************************************
3//
4// Tpetra: Templated Linear Algebra Services Package
5// Copyright (2008) Sandia Corporation
6//
7// Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
8// the U.S. Government retains certain rights in this software.
9//
10// Redistribution and use in source and binary forms, with or without
11// modification, are permitted provided that the following conditions are
12// met:
13//
14// 1. Redistributions of source code must retain the above copyright
15// notice, this list of conditions and the following disclaimer.
16//
17// 2. Redistributions in binary form must reproduce the above copyright
18// notice, this list of conditions and the following disclaimer in the
19// documentation and/or other materials provided with the distribution.
20//
21// 3. Neither the name of the Corporation nor the names of the
22// contributors may be used to endorse or promote products derived from
23// this software without specific prior written permission.
24//
25// THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
26// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
28// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
29// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
30// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
31// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
32// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
33// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
34// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
35// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36//
37// ************************************************************************
38// @HEADER
39
40#ifndef TPETRA_UTIL_HPP
41#define TPETRA_UTIL_HPP
42
52#include "Tpetra_ConfigDefs.hpp"
53#include "Kokkos_DualView.hpp"
54#include "KokkosCompat_View.hpp"
55#include "Teuchos_Assert.hpp"
56#include "Teuchos_CommHelpers.hpp"
57#include "Teuchos_OrdinalTraits.hpp"
58#include "Teuchos_TypeNameTraits.hpp"
59#include "Teuchos_Utils.hpp"
60#include <algorithm>
61#include <iterator>
62#include <memory>
63#include <ostream>
64#include <sstream>
65
66#if defined(HAVE_TPETRA_PRINT_EFFICIENCY_WARNINGS)
91#define TPETRA_EFFICIENCY_WARNING(throw_exception_test,msg) \
92{ \
93 const bool tpetraEfficiencyWarningTest = (throw_exception_test); \
94 if (tpetraEfficiencyWarningTest) { \
95 std::ostringstream errStream; \
96 errStream << Teuchos::typeName(*this) << ":" << std::endl; \
97 errStream << "Efficiency warning: " << #throw_exception_test << std::endl; \
98 errStream << msg; \
99 std::string err = errStream.str(); \
100 if (TPETRA_PRINTS_EFFICIENCY_WARNINGS && tpetraEfficiencyWarningTest) { \
101 std::cerr << err << std::endl; \
102 } \
103 } \
104}
105#else
130#define TPETRA_EFFICIENCY_WARNING(throw_exception_test,msg)
131#endif
132
133// handle an abuse warning, according to HAVE_TPETRA_THROW_ABUSE_WARNINGS and HAVE_TPETRA_PRINT_ABUSE_WARNINGS
134#if defined(HAVE_TPETRA_THROW_ABUSE_WARNINGS) || defined(HAVE_TPETRA_PRINT_ABUSE_WARNINGS)
136#define TPETRA_ABUSE_WARNING(throw_exception_test,Exception,msg) \
137{ \
138 std::ostringstream errStream; \
139 errStream << Teuchos::typeName(*this) << msg; \
140 std::string err = errStream.str(); \
141 if (TPETRA_PRINTS_ABUSE_WARNINGS && (throw_exception_test)) { \
142 std::cerr << err << std::endl; \
143 } \
144 TEUCHOS_TEST_FOR_EXCEPTION(TPETRA_THROWS_ABUSE_WARNINGS && (throw_exception_test), Exception, err); \
145}
146#else
148#define TPETRA_ABUSE_WARNING(throw_exception_test,Exception,msg)
149#endif
150
180#define SHARED_TEST_FOR_EXCEPTION(throw_exception_test,Exception,msg,comm) \
181{ \
182 using Teuchos::outArg; \
183 const int lcl_throw_exception = (throw_exception_test) ? Teuchos::rank(comm)+1 : 0; \
184 int gbl_throw; \
185 Teuchos::reduceAll(comm,Teuchos::REDUCE_MAX,lcl_throw_exception,outArg(gbl_throw)); \
186 TEUCHOS_TEST_FOR_EXCEPTION(gbl_throw,Exception, \
187 msg << " Failure on at least one process, including process " << gbl_throw-1 << "." << std::endl); \
188}
189
190namespace Tpetra {
191
203 template<typename MapType, typename KeyArgType, typename ValueArgType>
204 typename MapType::iterator efficientAddOrUpdate(MapType& m,
205 const KeyArgType & k,
206 const ValueArgType & v)
207 {
208 typename MapType::iterator lb = m.lower_bound(k);
209 if(lb != m.end() && !(m.key_comp()(k, lb->first))) {
210 lb->second = v;
211 return(lb);
212 }
213 else {
214 typedef typename MapType::value_type MVT;
215 return(m.insert(lb, MVT(k, v)));
216 }
217 }
218
226 namespace SortDetails {
227
236 template<class IT1>
237 bool isAlreadySorted(const IT1& first, const IT1& last){
238 typedef typename std::iterator_traits<IT1>::difference_type DT;
239 DT myit = Teuchos::OrdinalTraits<DT>::one();
240 const DT sz = last - first;
241 for(;myit < sz; ++myit){
242 if(first[myit] < first[myit-1]){
243 return false;
244 }
245 }
246 return true;
247 }
248
258 template<class IT>
259 IT getPivot(const IT& first, const IT& last){
260 IT pivot(first+(last-first)/2);
261 if(*first<=*pivot && *(last-1)<=*first) pivot=first;
262 else if(*(last-1)<=*pivot && *first<= *(last-1)) pivot = last-1;
263 return pivot;
264 }
265
280 template<class IT1, class IT2>
282 const IT1& first1,
283 const IT1& last1,
284 const IT2& first2,
285 const IT2& last2,
286 const IT1& pivot)
287 {
288 typename std::iterator_traits<IT1>::value_type piv(*pivot);
289 std::swap(*pivot, *(last1-1));
290 std::swap(first2[(pivot-first1)], *(last2-1));
291 IT1 store1=first1;
292 for(IT1 it=first1; it!=last1-1; ++it){
293 if(*it<=piv){
294 std::swap(*store1, *it);
295 std::swap(first2[(store1-first1)], first2[(it-first1)]);
296 ++store1;
297 }
298 }
299 std::swap(*(last1-1), *store1);
300 std::swap(*(last2-1), first2[store1-first1]);
301 return store1;
302 }
303
320 template<class IT1, class IT2, class IT3>
322 const IT1& first1,
323 const IT1& last1,
324 const IT2& first2,
325 const IT2& last2,
326 const IT3& first3,
327 const IT3& last3,
328 const IT1& pivot)
329 {
330 typename std::iterator_traits<IT1>::value_type piv(*pivot);
331 std::swap(*pivot, *(last1-1));
332 std::swap(first2[(pivot-first1)], *(last2-1));
333 std::swap(first3[(pivot-first1)], *(last3-1));
334 IT1 store1=first1;
335 for(IT1 it=first1; it!=last1-1; ++it){
336 if(*it<=piv){
337 std::swap(*store1, *it);
338 std::swap(first2[(store1-first1)], first2[(it-first1)]);
339 std::swap(first3[(store1-first1)], first3[(it-first1)]);
340 ++store1;
341 }
342 }
343 std::swap(*(last1-1), *store1);
344 std::swap(*(last2-1), first2[store1-first1]);
345 std::swap(*(last3-1), first3[store1-first1]);
346 return store1;
347 }
348
359 template<class IT1, class IT2>
361 const IT1& first1,
362 const IT1& last1,
363 const IT2& first2,
364 const IT2& last2)
365 {
366 typedef typename std::iterator_traits<IT1>::difference_type DT;
367 DT DT1 = Teuchos::OrdinalTraits<DT>::one();
368 if(last1-first1 > DT1){
369 IT1 pivot = getPivot(first1, last1);
370 pivot = partition2(first1, last1, first2, last2, pivot);
371 quicksort2(first1, pivot, first2, first2+(pivot-first1));
372 quicksort2(pivot+1, last1, first2+(pivot-first1)+1, last2);
373 }
374 }
375
388 template<class IT1, class IT2, class IT3>
390 const IT1& first1,
391 const IT1& last1,
392 const IT2& first2,
393 const IT2& last2,
394 const IT3& first3,
395 const IT3& last3)
396 {
397 typedef typename std::iterator_traits<IT1>::difference_type DT;
398 DT DT1 = Teuchos::OrdinalTraits<DT>::one();
399 if(last1-first1 > DT1){
400 IT1 pivot = getPivot(first1, last1);
401 pivot = partition3(first1, last1, first2, last2, first3, last3, pivot);
402 quicksort3(first1, pivot, first2, first2+(pivot-first1), first3, first3+(pivot-first1));
403 quicksort3(pivot+1, last1, first2+(pivot-first1)+1, last2, first3+(pivot-first1)+1, last3);
404 }
405 }
406
413 template<class IT1, class IT2, class IT3>
415 const IT1& first1,
416 const IT1& last1,
417 const IT2& first2,
418 const IT2& /* last2 */,
419 const IT3& first3,
420 const IT3& /* last3 */)
421 {
422 typedef typename std::iterator_traits<IT1>::difference_type DT;
423 DT n = last1 - first1;
424 DT m = n / 2;
425 DT z = Teuchos::OrdinalTraits<DT>::zero();
426 while (m > z)
427 {
428 DT max = n - m;
429 for (DT j = 0; j < max; j++)
430 {
431 for (DT k = j; k >= 0; k-=m)
432 {
433 if (first1[k+m] >= first1[k])
434 break;
435 std::swap(first1[k+m], first1[k]);
436 std::swap(first2[k+m], first2[k]);
437 std::swap(first3[k+m], first3[k]);
438 }
439 }
440 m = m/2;
441 }
442 }
443
450 template<class IT1, class IT2>
452 const IT1& first1,
453 const IT1& last1,
454 const IT2& first2,
455 const IT2& /* last2 */)
456 {
457 typedef typename std::iterator_traits<IT1>::difference_type DT;
458 DT n = last1 - first1;
459 DT m = n / 2;
460 DT z = Teuchos::OrdinalTraits<DT>::zero();
461 while (m > z)
462 {
463 DT max = n - m;
464 for (DT j = 0; j < max; j++)
465 {
466 for (DT k = j; k >= 0; k-=m)
467 {
468 if (first1[k+m] >= first1[k])
469 break;
470 std::swap(first1[k+m], first1[k]);
471 std::swap(first2[k+m], first2[k]);
472 }
473 }
474 m = m/2;
475 }
476 }
477
478 } //end namespace SortDetails
479
480
499 template<class IT1, class IT2>
500 void sort2(const IT1 &first1, const IT1 &last1, const IT2 &first2) {
501 // Quicksort uses best-case N log N time whether or not the input
502 // data is sorted. However, the common case in Tpetra is that the
503 // input data are sorted, so we first check whether this is the
504 // case before reverting to Quicksort.
505 if(SortDetails::isAlreadySorted(first1, last1)){
506 return;
507 }
508 SortDetails::sh_sort2(first1, last1, first2, first2+(last1-first1));
509#ifdef HAVE_TPETRA_DEBUG
510 if(!SortDetails::isAlreadySorted(first1, last1)){
511 std::cout << "Trouble: sort() did not sort !!" << std::endl;
512 return;
513 }
514#endif
515 }
516
517
534 template<class View1, class View2>
535 void sort2(View1 &view1, const size_t &size, View2 &view2) {
536 // NOTE: This assumes the view is host-accessible.
537
538 // Wrap the views as rcps (this happens to preserve the reference counting, but that doesn't really matter here)
539 Teuchos::ArrayRCP<typename View1::non_const_value_type> view1_rcp = Kokkos::Compat::persistingView(view1, 0, size);
540 Teuchos::ArrayRCP<typename View2::non_const_value_type> view2_rcp = Kokkos::Compat::persistingView(view2, 0, size);
541
542 sort2(view1_rcp.begin(),view1_rcp.end(),view2_rcp.begin());
543 }
544
553 template<class View>
554 void sort(View &view, const size_t &size) {
555 // NOTE: This assumes the view is host-accessible.
556
557 // Wrap the view as rcps (this happens to preserve the reference counting, but that doesn't really matter here)
558 Teuchos::ArrayRCP<typename View::non_const_value_type> view_rcp = Kokkos::Compat::persistingView(view, 0, size);
559
560 std::sort(view_rcp.begin(),view_rcp.end());
561 }
562
571 template<class View>
572 void reverse_sort(View &view, const size_t &size) {
573 // NOTE: This assumes the view is host-accessible.
574 // Wrap the view as rcps (this happens to preserve the reference counting, but that doesn't really matter here)
575 Teuchos::ArrayRCP<typename View::non_const_value_type> view_rcp = Kokkos::Compat::persistingView(view, 0, size);
576
577 std::sort(view_rcp.rbegin(),view_rcp.rend());
578 }
579
580
581
582
598 template<class IT1, class IT2, class IT3>
599 void sort3(const IT1 &first1, const IT1 &last1, const IT2 &first2,
600 const IT3 &first3)
601 {
602 // Quicksort uses best-case N log N time whether or not the input
603 // data is sorted. However, the common case in Tpetra is that the
604 // input data are sorted, so we first check whether this is the
605 // case before reverting to Quicksort.
606 if(SortDetails::isAlreadySorted(first1, last1)){
607 return;
608 }
609 SortDetails::sh_sort3(first1, last1, first2, first2+(last1-first1), first3,
610 first3+(last1-first1));
611
612#ifdef HAVE_TPETRA_DEBUG
613 if(!SortDetails::isAlreadySorted(first1, last1)){
614 std::cout << " Trouble sort did not actually sort... !!!!!!" <<
615 std::endl;
616 return;
617 }
618#endif
619 }
620
664 template<class IT1, class IT2>
665 void
666 merge2 (IT1& indResultOut, IT2& valResultOut,
667 IT1 indBeg, IT1 indEnd,
668 IT2 valBeg, IT2 /* valEnd */)
669 {
670 if (indBeg == indEnd) {
671 indResultOut = indBeg; // It's allowed for indResultOut to alias indEnd
672 valResultOut = valBeg; // It's allowed for valResultOut to alias valEnd
673 }
674 else {
675 IT1 indResult = indBeg;
676 IT2 valResult = valBeg;
677 if (indBeg != indEnd) {
678 ++indBeg;
679 ++valBeg;
680 while (indBeg != indEnd) {
681 if (*indResult == *indBeg) { // adjacent column indices equal
682 *valResult += *valBeg; // merge entries by adding their values together
683 } else { // adjacent column indices not equal
684 *(++indResult) = *indBeg; // shift over the index
685 *(++valResult) = *valBeg; // shift over the value
686 }
687 ++indBeg;
688 ++valBeg;
689 }
690 ++indResult; // exclusive end of merged result
691 ++valResult; // exclusive end of merged result
692
693 // mfh 24 Feb 2014: Setting these is technically correct, but
694 // since the resulting variables aren't used after this point,
695 // it may result in a build error.
696 //
697 // indEnd = indResult;
698 // valEnd = valResult;
699 }
700 indResultOut = indResult;
701 valResultOut = valResult;
702 }
703 }
704
753 template<class IT1, class IT2, class BinaryFunction>
754 void
755 merge2 (IT1& indResultOut, IT2& valResultOut,
756 IT1 indBeg, IT1 indEnd,
757 IT2 valBeg, IT2 valEnd,
758 BinaryFunction f)
759 {
760 if (indBeg == indEnd) {
761 indResultOut = indBeg; // It's allowed for indResultOut to alias indEnd
762 valResultOut = valBeg; // It's allowed for valResultOut to alias valEnd
763 }
764 else {
765 IT1 indResult = indBeg;
766 IT2 valResult = valBeg;
767 if (indBeg != indEnd) {
768 ++indBeg;
769 ++valBeg;
770 while (indBeg != indEnd) {
771 if (*indResult == *indBeg) { // adjacent column indices equal
772 *valResult = f (*valResult, *valBeg); // merge entries via values
773 } else { // adjacent column indices not equal
774 *(++indResult) = *indBeg; // shift over the index
775 *(++valResult) = *valBeg; // shift over the value
776 }
777 ++indBeg;
778 ++valBeg;
779 }
780 ++indResult; // exclusive end of merged result
781 ++valResult; // exclusive end of merged result
782 indEnd = indResult;
783 valEnd = valResult;
784 }
785 indResultOut = indResult;
786 valResultOut = valResult;
787 }
788 }
789
790
819 template<class KeyInputIterType, class ValueInputIterType,
820 class KeyOutputIterType, class ValueOutputIterType,
821 class BinaryFunction>
822 void
823 keyValueMerge (KeyInputIterType keyBeg1, KeyInputIterType keyEnd1,
824 ValueInputIterType valBeg1, ValueInputIterType valEnd1,
825 KeyInputIterType keyBeg2, KeyInputIterType keyEnd2,
826 ValueInputIterType valBeg2, ValueInputIterType valEnd2,
827 KeyOutputIterType keyOut, ValueOutputIterType valOut,
828 BinaryFunction f)
829 {
830 while (keyBeg1 != keyEnd1 && keyBeg2 != keyEnd2) {
831 if (*keyBeg1 < *keyBeg2) {
832 *keyOut++ = *keyBeg1++;
833 *valOut++ = *valBeg1++;
834 } else if (*keyBeg1 > *keyBeg2) {
835 *keyOut++ = *keyBeg2++;
836 *valOut++ = *valBeg2++;
837 } else { // *keyBeg1 == *keyBeg2
838 *keyOut++ = *keyBeg1;
839 *valOut++ = f (*valBeg1, *valBeg2);
840 ++keyBeg1;
841 ++valBeg1;
842 ++keyBeg2;
843 ++valBeg2;
844 }
845 }
846 // At most one of the two sequences will be nonempty.
847 std::copy (keyBeg1, keyEnd1, keyOut);
848 std::copy (valBeg1, valEnd1, valOut);
849 std::copy (keyBeg2, keyEnd2, keyOut);
850 std::copy (valBeg2, valEnd2, valOut);
851 }
852
853 template<class KeyInputIterType>
854 size_t
855 keyMergeCount (KeyInputIterType keyBeg1, KeyInputIterType keyEnd1,
856 KeyInputIterType keyBeg2, KeyInputIterType keyEnd2)
857 {
858 size_t count = 0;
859 while (keyBeg1 != keyEnd1 && keyBeg2 != keyEnd2) {
860 if (*keyBeg1 < *keyBeg2) {
861 ++keyBeg1;
862 } else if (*keyBeg1 > *keyBeg2) {
863 ++keyBeg2;
864 } else { // *keyBeg1 == *keyBeg2
865 ++keyBeg1;
866 ++keyBeg2;
867 }
868 ++count;
869 }
870 // At most one of the two sequences will be nonempty.
871 count += static_cast<size_t> (keyEnd1 - keyBeg1) +
872 static_cast<size_t> (keyEnd2 - keyBeg2);
873 return count;
874 }
875
876 namespace Details {
896 bool
897 congruent (const Teuchos::Comm<int>& comm1,
898 const Teuchos::Comm<int>& comm2);
899
909 template<class DualViewType>
910 Teuchos::ArrayView<typename DualViewType::t_dev::value_type>
911 getArrayViewFromDualView (const DualViewType& x)
912 {
913 static_assert (static_cast<int> (DualViewType::t_dev::rank) == 1,
914 "The input DualView must have rank 1.");
915 TEUCHOS_TEST_FOR_EXCEPTION
916 (x.need_sync_host (), std::logic_error, "The "
917 "input Kokkos::DualView was most recently modified on device, but this "
918 "function needs the host view of the data to be the most recently "
919 "modified.");
920
921 auto x_host = x.view_host ();
922 typedef typename DualViewType::t_dev::value_type value_type;
923 // mfh 15 Jan 2019: In debug mode, Teuchos::ArrayView's
924 // constructor throws if the pointer is nonnull but the length
925 // is nonpositive.
926 const auto len = x_host.extent (0);
927 return Teuchos::ArrayView<value_type> (len != 0 ? x_host.data () : nullptr,
928 len);
929 }
930
947 template<class T, class DT>
948 Kokkos::DualView<T*, DT>
949 getDualViewCopyFromArrayView (const Teuchos::ArrayView<const T>& x_av,
950 const char label[],
951 const bool leaveOnHost)
952 {
953 using Kokkos::MemoryUnmanaged;
954 typedef typename DT::memory_space DMS;
955 typedef typename DT::execution_space execution_space;
956 typedef Kokkos::HostSpace HMS;
957
958 const size_t len = static_cast<size_t> (x_av.size ());
959 Kokkos::View<const T*, HMS, MemoryUnmanaged> x_in (x_av.getRawPtr (), len);
960 Kokkos::DualView<T*, DT> x_out (label, len);
961 if (leaveOnHost) {
962 x_out.modify_host ();
963 // DEEP_COPY REVIEW - NOT TESTED FOR CUDA BUILD
964 Kokkos::deep_copy (x_out.view_host (), x_in);
965 }
966 else {
967 x_out.template modify<DMS> ();
968 // DEEP_COPY REVIEW - HOST-TO-DEVICE
969 Kokkos::deep_copy (execution_space(), x_out.template view<DMS> (), x_in);
970 }
971 return x_out;
972 }
973
981 template<class DualViewType>
982 std::string dualViewStatusToString (const DualViewType& dv, const char name[])
983 {
984 const auto host = dv.need_sync_device();
985 const auto dev = dv.need_sync_host();
986
987 std::ostringstream os;
988 os << name << ": {size: " << dv.extent (0)
989 << ", sync: {host: " << host << ", dev: " << dev << "}";
990 return os.str ();
991 }
992
997 template<class ArrayType>
998 void
999 verbosePrintArray(std::ostream& out,
1000 const ArrayType& x,
1001 const char name[],
1002 const size_t maxNumToPrint)
1003 {
1004 out << name << ": [";
1005
1006 const size_t numEnt(x.size());
1007 if (maxNumToPrint == 0) {
1008 if (numEnt != 0) {
1009 out << "...";
1010 }
1011 }
1012 else {
1013 const size_t numToPrint = numEnt > maxNumToPrint ?
1014 maxNumToPrint : numEnt;
1015 size_t k = 0;
1016 for ( ; k < numToPrint; ++k) {
1017 out << x[k];
1018 if (k + size_t(1) < numToPrint) {
1019 out << ", ";
1020 }
1021 }
1022 if (k < numEnt) {
1023 out << ", ...";
1024 }
1025 }
1026 out << "]";
1027 }
1028
1032 std::unique_ptr<std::string>
1033 createPrefix(const int myRank,
1034 const char prefix[]);
1035
1043 std::unique_ptr<std::string>
1044 createPrefix(const Teuchos::Comm<int>* comm,
1045 const char functionName[]);
1046
1053 std::unique_ptr<std::string>
1054 createPrefix(const Teuchos::Comm<int>*,
1055 const char className[],
1056 const char methodName[]);
1057
1058 } // namespace Details
1059} // namespace Tpetra
1060
1061#endif // TPETRA_UTIL_HPP
void sh_sort3(const IT1 &first1, const IT1 &last1, const IT2 &first2, const IT2 &, const IT3 &first3, const IT3 &)
Sort the first array using shell sort, and apply the resulting permutation to the second and third ar...
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.
IT getPivot(const IT &first, const IT &last)
Determines the pivot point as part of the quicksort routine.
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().
void sh_sort2(const IT1 &first1, const IT1 &last1, const IT2 &first2, const IT2 &)
Sort the first array using shell sort, and apply the resulting permutation to the second array.
bool isAlreadySorted(const IT1 &first, const IT1 &last)
Determines whether or not a random access sequence is already sorted.
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...
Implementation details of Tpetra.
Implementation details of sort routines used by Tpetra.
void verbosePrintArray(std::ostream &out, const ArrayType &x, const char name[], const size_t maxNumToPrint)
Print min(x.size(), maxNumToPrint) entries of x.
Teuchos::ArrayView< typename DualViewType::t_dev::value_type > getArrayViewFromDualView(const DualViewType &x)
Get a Teuchos::ArrayView which views the host Kokkos::View of the input 1-D Kokkos::DualView.
std::unique_ptr< std::string > createPrefix(const int myRank, const char prefix[])
Create string prefix for each line of verbose output.
bool congruent(const Teuchos::Comm< int > &comm1, const Teuchos::Comm< int > &comm2)
Whether the two communicators are congruent.
Definition: Tpetra_Util.cpp:64
Kokkos::DualView< T *, DT > getDualViewCopyFromArrayView(const Teuchos::ArrayView< const T > &x_av, const char label[], const bool leaveOnHost)
Get a 1-D Kokkos::DualView which is a deep copy of the input Teuchos::ArrayView (which views host mem...
std::string dualViewStatusToString(const DualViewType &dv, const char name[])
Return the status of the given Kokkos::DualView, as a human-readable string.
Namespace Tpetra contains the class and methods constituting the Tpetra library.
void sort(View &view, const size_t &size)
Convenience wrapper for std::sort for host-accessible views.
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.
void reverse_sort(View &view, const size_t &size)
Convenience wrapper for a reversed std::sort for host-accessible views.
void sort2(const IT1 &first1, const IT1 &last1, const IT2 &first2)
Sort the first array, and apply the resulting permutation to the second array.
MapType::iterator efficientAddOrUpdate(MapType &m, const KeyArgType &k, const ValueArgType &v)
Efficiently insert or replace an entry in an std::map.
void merge2(IT1 &indResultOut, IT2 &valResultOut, IT1 indBeg, IT1 indEnd, IT2 valBeg, IT2)
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.