Tpetra parallel linear algebra  Version of the Day
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 // Questions? Contact Michael A. Heroux (maherou@sandia.gov)
38 //
39 // ************************************************************************
40 // @HEADER
41 
42 #ifndef TPETRA_UTIL_HPP
43 #define TPETRA_UTIL_HPP
44 
54 #include "Tpetra_ConfigDefs.hpp" // for map, vector, string, and iostream
55 #include "Kokkos_DualView.hpp"
56 #include "Teuchos_Utils.hpp"
57 #include "Teuchos_Assert.hpp"
58 #include <algorithm>
59 #include <iterator>
60 #include <sstream>
61 
62 #if defined(HAVE_TPETRA_THROW_EFFICIENCY_WARNINGS) || defined(HAVE_TPETRA_PRINT_EFFICIENCY_WARNINGS)
63 #define TPETRA_EFFICIENCY_WARNING(throw_exception_test,Exception,msg) \
97 { \
98  const bool tpetraEfficiencyWarningTest = (throw_exception_test); \
99  if (tpetraEfficiencyWarningTest) { \
100  std::ostringstream errStream; \
101  errStream << Teuchos::typeName(*this) << ":" << std::endl; \
102  errStream << "Efficiency warning: " << #throw_exception_test << std::endl; \
103  errStream << msg; \
104  std::string err = errStream.str(); \
105  if (TPETRA_PRINTS_EFFICIENCY_WARNINGS && tpetraEfficiencyWarningTest) { \
106  std::cerr << err << std::endl; \
107  } \
108  TEUCHOS_TEST_FOR_EXCEPTION(TPETRA_THROWS_EFFICIENCY_WARNINGS && tpetraEfficiencyWarningTest, Exception, err); \
109  } \
110 }
111 #else
112 #define TPETRA_EFFICIENCY_WARNING(throw_exception_test,Exception,msg)
146 #endif
147 
148 // handle an abuse warning, according to HAVE_TPETRA_THROW_ABUSE_WARNINGS and HAVE_TPETRA_PRINT_ABUSE_WARNINGS
149 #if defined(HAVE_TPETRA_THROW_ABUSE_WARNINGS) || defined(HAVE_TPETRA_PRINT_ABUSE_WARNINGS)
150 #define TPETRA_ABUSE_WARNING(throw_exception_test,Exception,msg) \
152 { \
153  std::ostringstream errStream; \
154  errStream << Teuchos::typeName(*this) << msg; \
155  std::string err = errStream.str(); \
156  if (TPETRA_PRINTS_ABUSE_WARNINGS && (throw_exception_test)) { \
157  std::cerr << err << std::endl; \
158  } \
159  TEUCHOS_TEST_FOR_EXCEPTION(TPETRA_THROWS_ABUSE_WARNINGS && (throw_exception_test), Exception, err); \
160 }
161 #else
162 #define TPETRA_ABUSE_WARNING(throw_exception_test,Exception,msg)
164 #endif
165 
195 #define SHARED_TEST_FOR_EXCEPTION(throw_exception_test,Exception,msg,comm) \
196 { \
197  using Teuchos::outArg; \
198  const int lcl_throw_exception = (throw_exception_test) ? Teuchos::rank(comm)+1 : 0; \
199  int gbl_throw; \
200  Teuchos::reduceAll(comm,Teuchos::REDUCE_MAX,lcl_throw_exception,outArg(gbl_throw)); \
201  TEUCHOS_TEST_FOR_EXCEPTION(gbl_throw,Exception, \
202  msg << " Failure on at least one process, including process " << gbl_throw-1 << "." << std::endl); \
203 }
204 
205 #ifdef HAVE_TEUCHOS_DEBUG
206 #define SWITCHED_TEST_FOR_EXCEPTION(throw_exception_test,Exception,msg,comm) \
208 { \
209  SHARED_TEST_FOR_EXCEPTION(throw_exception_test,Exception,msg,comm); \
210 }
211 #else
212 #define SWITCHED_TEST_FOR_EXCEPTION(throw_exception_test,Exception,msg,comm) \
214 { \
215  TEUCHOS_TEST_FOR_EXCEPTION(throw_exception_test,Exception,msg); \
216 }
217 #endif
218 
219 namespace Tpetra {
220 
232  template<typename MapType, typename KeyArgType, typename ValueArgType>
233  typename MapType::iterator efficientAddOrUpdate(MapType& m,
234  const KeyArgType & k,
235  const ValueArgType & v)
236  {
237  typename MapType::iterator lb = m.lower_bound(k);
238  if(lb != m.end() && !(m.key_comp()(k, lb->first))) {
239  lb->second = v;
240  return(lb);
241  }
242  else {
243  typedef typename MapType::value_type MVT;
244  return(m.insert(lb, MVT(k, v)));
245  }
246  }
247 
255  namespace SortDetails {
256 
265  template<class IT1>
266  bool isAlreadySorted(const IT1& first, const IT1& last){
267  typedef typename std::iterator_traits<IT1>::difference_type DT;
268  DT myit = Teuchos::OrdinalTraits<DT>::one();
269  const DT sz = last - first;
270  for(;myit < sz; ++myit){
271  if(first[myit] < first[myit-1]){
272  return false;
273  }
274  }
275  return true;
276  }
277 
287  template<class IT>
288  IT getPivot(const IT& first, const IT& last){
289  IT pivot(first+(last-first)/2);
290  if(*first<=*pivot && *(last-1)<=*first) pivot=first;
291  else if(*(last-1)<=*pivot && *first<= *(last-1)) pivot = last-1;
292  return pivot;
293  }
294 
309  template<class IT1, class IT2>
311  const IT1& first1,
312  const IT1& last1,
313  const IT2& first2,
314  const IT2& last2,
315  const IT1& pivot)
316  {
317  typename std::iterator_traits<IT1>::value_type piv(*pivot);
318  std::swap(*pivot, *(last1-1));
319  std::swap(first2[(pivot-first1)], *(last2-1));
320  IT1 store1=first1;
321  for(IT1 it=first1; it!=last1-1; ++it){
322  if(*it<=piv){
323  std::swap(*store1, *it);
324  std::swap(first2[(store1-first1)], first2[(it-first1)]);
325  ++store1;
326  }
327  }
328  std::swap(*(last1-1), *store1);
329  std::swap(*(last2-1), first2[store1-first1]);
330  return store1;
331  }
332 
349  template<class IT1, class IT2, class IT3>
351  const IT1& first1,
352  const IT1& last1,
353  const IT2& first2,
354  const IT2& last2,
355  const IT3& first3,
356  const IT3& last3,
357  const IT1& pivot)
358  {
359  typename std::iterator_traits<IT1>::value_type piv(*pivot);
360  std::swap(*pivot, *(last1-1));
361  std::swap(first2[(pivot-first1)], *(last2-1));
362  std::swap(first3[(pivot-first1)], *(last3-1));
363  IT1 store1=first1;
364  for(IT1 it=first1; it!=last1-1; ++it){
365  if(*it<=piv){
366  std::swap(*store1, *it);
367  std::swap(first2[(store1-first1)], first2[(it-first1)]);
368  std::swap(first3[(store1-first1)], first3[(it-first1)]);
369  ++store1;
370  }
371  }
372  std::swap(*(last1-1), *store1);
373  std::swap(*(last2-1), first2[store1-first1]);
374  std::swap(*(last3-1), first3[store1-first1]);
375  return store1;
376  }
377 
388  template<class IT1, class IT2>
390  const IT1& first1,
391  const IT1& last1,
392  const IT2& first2,
393  const IT2& last2)
394  {
395  typedef typename std::iterator_traits<IT1>::difference_type DT;
396  DT DT1 = Teuchos::OrdinalTraits<DT>::one();
397  if(last1-first1 > DT1){
398  IT1 pivot = getPivot(first1, last1);
399  pivot = partition2(first1, last1, first2, last2, pivot);
400  quicksort2(first1, pivot, first2, first2+(pivot-first1));
401  quicksort2(pivot+1, last1, first2+(pivot-first1)+1, last2);
402  }
403  }
404 
417  template<class IT1, class IT2, class IT3>
419  const IT1& first1,
420  const IT1& last1,
421  const IT2& first2,
422  const IT2& last2,
423  const IT3& first3,
424  const IT3& last3)
425  {
426  typedef typename std::iterator_traits<IT1>::difference_type DT;
427  DT DT1 = Teuchos::OrdinalTraits<DT>::one();
428  if(last1-first1 > DT1){
429  IT1 pivot = getPivot(first1, last1);
430  pivot = partition3(first1, last1, first2, last2, first3, last3, pivot);
431  quicksort3(first1, pivot, first2, first2+(pivot-first1), first3, first3+(pivot-first1));
432  quicksort3(pivot+1, last1, first2+(pivot-first1)+1, last2, first3+(pivot-first1)+1, last3);
433  }
434  }
435 
442  template<class IT1, class IT2, class IT3>
443  void sh_sort3(
444  const IT1& first1,
445  const IT1& last1,
446  const IT2& first2,
447  const IT2& last2,
448  const IT3& first3,
449  const IT3& last3)
450  {
451  typedef typename std::iterator_traits<IT1>::difference_type DT;
452  DT n = last1 - first1;
453  DT m = n / 2;
454  DT z = Teuchos::OrdinalTraits<DT>::zero();
455  while (m > z)
456  {
457  DT max = n - m;
458  for (DT j = 0; j < max; j++)
459  {
460  for (DT k = j; k >= 0; k-=m)
461  {
462  if (first1[k+m] >= first1[k])
463  break;
464  std::swap(first1[k+m], first1[k]);
465  std::swap(first2[k+m], first2[k]);
466  std::swap(first3[k+m], first3[k]);
467  }
468  }
469  m = m/2;
470  }
471  }
472 
479  template<class IT1, class IT2>
480  void sh_sort2(
481  const IT1& first1,
482  const IT1& last1,
483  const IT2& first2,
484  const IT2& last2)
485  {
486  typedef typename std::iterator_traits<IT1>::difference_type DT;
487  DT n = last1 - first1;
488  DT m = n / 2;
489  DT z = Teuchos::OrdinalTraits<DT>::zero();
490  while (m > z)
491  {
492  DT max = n - m;
493  for (DT j = 0; j < max; j++)
494  {
495  for (DT k = j; k >= 0; k-=m)
496  {
497  if (first1[k+m] >= first1[k])
498  break;
499  std::swap(first1[k+m], first1[k]);
500  std::swap(first2[k+m], first2[k]);
501  }
502  }
503  m = m/2;
504  }
505  }
506 
507  } //end namespace SortDetails
508 
509 
528  template<class IT1, class IT2>
529  void sort2(const IT1 &first1, const IT1 &last1, const IT2 &first2) {
530  // Quicksort uses best-case N log N time whether or not the input
531  // data is sorted. However, the common case in Tpetra is that the
532  // input data are sorted, so we first check whether this is the
533  // case before reverting to Quicksort.
534  if(SortDetails::isAlreadySorted(first1, last1)){
535  return;
536  }
537  SortDetails::sh_sort2(first1, last1, first2, first2+(last1-first1));
538 #ifdef HAVE_TPETRA_DEBUG
539  if(!SortDetails::isAlreadySorted(first1, last1)){
540  std::cout << "Trouble: sort() did not sort !!" << std::endl;
541  return;
542  }
543 #endif
544  }
545 
546 
562  template<class IT1, class IT2, class IT3>
563  void sort3(const IT1 &first1, const IT1 &last1, const IT2 &first2,
564  const IT3 &first3)
565  {
566  // Quicksort uses best-case N log N time whether or not the input
567  // data is sorted. However, the common case in Tpetra is that the
568  // input data are sorted, so we first check whether this is the
569  // case before reverting to Quicksort.
570  if(SortDetails::isAlreadySorted(first1, last1)){
571  return;
572  }
573  SortDetails::sh_sort3(first1, last1, first2, first2+(last1-first1), first3,
574  first3+(last1-first1));
575 
576 #ifdef HAVE_TPETRA_DEBUG
577  if(!SortDetails::isAlreadySorted(first1, last1)){
578  std::cout << " Trouble sort did not actually sort... !!!!!!" <<
579  std::endl;
580  return;
581  }
582 #endif
583  }
584 
628  template<class IT1, class IT2>
629  void
630  merge2 (IT1& indResultOut, IT2& valResultOut,
631  IT1 indBeg, IT1 indEnd,
632  IT2 valBeg, IT2 valEnd)
633  {
634  if (indBeg == indEnd) {
635  indResultOut = indBeg; // It's allowed for indResultOut to alias indEnd
636  valResultOut = valBeg; // It's allowed for valResultOut to alias valEnd
637  }
638  else {
639  IT1 indResult = indBeg;
640  IT2 valResult = valBeg;
641  if (indBeg != indEnd) {
642  ++indBeg;
643  ++valBeg;
644  while (indBeg != indEnd) {
645  if (*indResult == *indBeg) { // adjacent column indices equal
646  *valResult += *valBeg; // merge entries by adding their values together
647  } else { // adjacent column indices not equal
648  *(++indResult) = *indBeg; // shift over the index
649  *(++valResult) = *valBeg; // shift over the value
650  }
651  ++indBeg;
652  ++valBeg;
653  }
654  ++indResult; // exclusive end of merged result
655  ++valResult; // exclusive end of merged result
656 
657  // mfh 24 Feb 2014: Setting these is technically correct, but
658  // since the resulting variables aren't used after this point,
659  // it may result in a build error.
660  //
661  // indEnd = indResult;
662  // valEnd = valResult;
663  }
664  indResultOut = indResult;
665  valResultOut = valResult;
666  }
667  }
668 
717  template<class IT1, class IT2, class BinaryFunction>
718  void
719  merge2 (IT1& indResultOut, IT2& valResultOut,
720  IT1 indBeg, IT1 indEnd,
721  IT2 valBeg, IT2 valEnd,
722  BinaryFunction f)
723  {
724  if (indBeg == indEnd) {
725  indResultOut = indBeg; // It's allowed for indResultOut to alias indEnd
726  valResultOut = valBeg; // It's allowed for valResultOut to alias valEnd
727  }
728  else {
729  IT1 indResult = indBeg;
730  IT2 valResult = valBeg;
731  if (indBeg != indEnd) {
732  ++indBeg;
733  ++valBeg;
734  while (indBeg != indEnd) {
735  if (*indResult == *indBeg) { // adjacent column indices equal
736  *valResult = f (*valResult, *valBeg); // merge entries via values
737  } else { // adjacent column indices not equal
738  *(++indResult) = *indBeg; // shift over the index
739  *(++valResult) = *valBeg; // shift over the value
740  }
741  ++indBeg;
742  ++valBeg;
743  }
744  ++indResult; // exclusive end of merged result
745  ++valResult; // exclusive end of merged result
746  indEnd = indResult;
747  valEnd = valResult;
748  }
749  indResultOut = indResult;
750  valResultOut = valResult;
751  }
752  }
753 
754 
783  template<class KeyInputIterType, class ValueInputIterType,
784  class KeyOutputIterType, class ValueOutputIterType,
785  class BinaryFunction>
786  void
787  keyValueMerge (KeyInputIterType keyBeg1, KeyInputIterType keyEnd1,
788  ValueInputIterType valBeg1, ValueInputIterType valEnd1,
789  KeyInputIterType keyBeg2, KeyInputIterType keyEnd2,
790  ValueInputIterType valBeg2, ValueInputIterType valEnd2,
791  KeyOutputIterType keyOut, ValueOutputIterType valOut,
792  BinaryFunction f)
793  {
794  while (keyBeg1 != keyEnd1 && keyBeg2 != keyEnd2) {
795  if (*keyBeg1 < *keyBeg2) {
796  *keyOut++ = *keyBeg1++;
797  *valOut++ = *valBeg1++;
798  } else if (*keyBeg1 > *keyBeg2) {
799  *keyOut++ = *keyBeg2++;
800  *valOut++ = *valBeg2++;
801  } else { // *keyBeg1 == *keyBeg2
802  *keyOut++ = *keyBeg1;
803  *valOut++ = f (*valBeg1, *valBeg2);
804  ++keyBeg1;
805  ++valBeg1;
806  ++keyBeg2;
807  ++valBeg2;
808  }
809  }
810  // At most one of the two sequences will be nonempty.
811  std::copy (keyBeg1, keyEnd1, keyOut);
812  std::copy (valBeg1, valEnd1, valOut);
813  std::copy (keyBeg2, keyEnd2, keyOut);
814  std::copy (valBeg2, valEnd2, valOut);
815  }
816 
817  template<class KeyInputIterType>
818  size_t
819  keyMergeCount (KeyInputIterType keyBeg1, KeyInputIterType keyEnd1,
820  KeyInputIterType keyBeg2, KeyInputIterType keyEnd2)
821  {
822  size_t count = 0;
823  while (keyBeg1 != keyEnd1 && keyBeg2 != keyEnd2) {
824  if (*keyBeg1 < *keyBeg2) {
825  ++keyBeg1;
826  } else if (*keyBeg1 > *keyBeg2) {
827  ++keyBeg2;
828  } else { // *keyBeg1 == *keyBeg2
829  ++keyBeg1;
830  ++keyBeg2;
831  }
832  ++count;
833  }
834  // At most one of the two sequences will be nonempty.
835  count += static_cast<size_t> (keyEnd1 - keyBeg1) +
836  static_cast<size_t> (keyEnd2 - keyBeg2);
837  return count;
838  }
839 
840  namespace Details {
860  bool
861  congruent (const Teuchos::Comm<int>& comm1,
862  const Teuchos::Comm<int>& comm2);
863 
873  template<class DualViewType>
874  Teuchos::ArrayView<typename DualViewType::t_dev::value_type>
875  getArrayViewFromDualView (const DualViewType& x)
876  {
877  static_assert (static_cast<int> (DualViewType::t_dev::rank) == 1,
878  "The input DualView must have rank 1.");
879  TEUCHOS_TEST_FOR_EXCEPTION
880  (x.template need_sync<Kokkos::HostSpace> (), std::logic_error, "The "
881  "input Kokkos::DualView was most recently modified on device, but this "
882  "function needs the host view of the data to be the most recently "
883  "modified.");
884 
885  auto x_host = x.template view<Kokkos::HostSpace> ();
886  typedef typename DualViewType::t_dev::value_type value_type;
887  return Teuchos::ArrayView<value_type> (x_host.ptr_on_device (),
888  x_host.dimension_0 ());
889  }
890 
907  template<class T, class DT>
908  Kokkos::DualView<T*, DT>
909  getDualViewCopyFromArrayView (const Teuchos::ArrayView<const T>& x_av,
910  const char label[],
911  const bool leaveOnHost)
912  {
913  using Kokkos::MemoryUnmanaged;
914  typedef typename DT::memory_space DMS;
915  typedef Kokkos::HostSpace HMS;
916 
917  const size_t len = static_cast<size_t> (x_av.size ());
918  Kokkos::View<const T*, HMS, MemoryUnmanaged> x_in (x_av.getRawPtr (), len);
919  Kokkos::DualView<T*, DT> x_out (label, len);
920  if (leaveOnHost) {
921  x_out.template modify<HMS> ();
922  Kokkos::deep_copy (x_out.template view<HMS> (), x_in);
923  }
924  else {
925  x_out.template modify<DMS> ();
926  Kokkos::deep_copy (x_out.template view<DMS> (), x_in);
927  }
928  return x_out;
929  }
930 
931  } // namespace Details
932 } // namespace Tpetra
933 
934 #endif // TPETRA_UTIL_HPP
bool congruent(const Teuchos::Comm< int > &comm1, const Teuchos::Comm< int > &comm2)
Whether the two communicators are congruent.
Definition: Tpetra_Util.cpp:65
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 deep_copy(MultiVector< DS, DL, DG, DN, dstClassic > &dst, const MultiVector< SS, SL, SG, SN, srcClassic > &src)
Copy the contents of the MultiVector src into dst.
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.
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...
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.
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.
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...