44#ifndef TPETRA_DETAILS_SHORTSORT_HPP
45#define TPETRA_DETAILS_SHORTSORT_HPP
55#include "TpetraCore_config.h"
56#include "Kokkos_Macros.hpp"
63#ifdef TPETRA_DETAILS_SWAP_KEYSANDVALUES
64# error "The TPETRA_DETAILS_SWAP_KEYSANDVALUES macro is already defined."
87#define TPETRA_DETAILS_SWAP_KEYSANDVALUES( i, j ) \
88 if (keys[i] > keys[j]) { \
89 const KeyType tmpKey (keys[i]); \
92 const ValueType tmpVal (values[i]); \
93 values[i] = values[j]; \
98#ifdef TPETRA_DETAILS_SWAP_KEYS
99# error "The TPETRA_DETAILS_SWAP_KEYS macro is already defined."
119#define TPETRA_DETAILS_SWAP_KEYS( i, j ) \
120 if (keys[i] > keys[j]) { \
121 const KeyType tmpKey (keys[i]); \
136template<
class KeyType,
class ValueType>
152template<
class KeyType>
172template<
class KeyType,
class ValueType>
194template<
class KeyType>
220template<
class KeyType,
class ValueType>
244template<
class KeyType>
272template<
class KeyType,
class ValueType>
310template<
class KeyType>
347template<
class KeyType,
class ValueType,
class IndexType>
353 static_assert (std::is_integral<IndexType>::value,
354 "IndexType must be a signed integer type.");
355 static_assert (std::is_signed<IndexType>::value,
356 "IndexType must be a signed integer type. "
357 "This implementation does a count-down loop, "
358 "and may thus loop forever "
359 "if one attempts to use it with unsigned IndexType.");
388template<
class KeyType,
class IndexType>
392 static_assert (std::is_integral<IndexType>::value,
393 "IndexType must be a signed integer type.");
394 static_assert (std::is_signed<IndexType>::value,
395 "IndexType must be a signed integer type. "
396 "This implementation does a count-down loop, "
397 "and may thus loop forever "
398 "if one attempts to use it with unsigned IndexType.");
420template<
typename KeyType,
typename ValueType,
typename IndexType>
426 IndexType gaps[] = {3548, 1577, 701, 301, 132, 57, 23, 10, 4, 1};
427 for(IndexType gapIndex = 0; gapIndex < ngaps; gapIndex++)
429 auto gap = gaps[gapIndex];
433 for(IndexType gapOffset = 0; gapOffset < gap; gapOffset++)
435 for(IndexType i = gap + gapOffset; i < n; i += gap)
438 if(keys[i - gap] > keys[i])
440 IndexType finalPos = i - gap;
441 while(finalPos - gap >= 0 && keys[finalPos - gap] > keys[i])
446 auto tempKey = keys[i];
447 auto tempVal = values[i];
448 for(IndexType j = i - gap; j >= finalPos; j -= gap)
450 keys[j + gap] = keys[j];
451 values[j + gap] = values[j];
453 keys[finalPos] = tempKey;
454 values[finalPos] = tempVal;
#define TPETRA_DETAILS_SWAP_KEYS(i, j)
Macro that swaps the i and j entries of keys, if keys[i] > keys[j] (i.e., if keys[i] and keys[j] are ...
#define TPETRA_DETAILS_SWAP_KEYSANDVALUES(i, j)
Macro that swaps the i and j entries of keys and values, if keys[i] > keys[j] (i.e....
Struct that holds views of the contents of a CrsMatrix.
Implementation details of Tpetra.
KOKKOS_FUNCTION void shellSortKeys(KeyType keys[], const IndexType n)
Shellsort (yes, it's one word) the input array keys.
KOKKOS_FUNCTION void shortSortKeysAndValues_3(KeyType keys[3], ValueType values[3])
Sort keys and values jointly, by keys, for arrays of length 3.
KOKKOS_FUNCTION void shortSortKeysAndValues_8(KeyType keys[8], ValueType values[8])
Sort keys and values jointly, by keys, for arrays of length 8.
KOKKOS_FUNCTION void shellSortKeysAndValues(KeyType keys[], ValueType values[], const IndexType n)
Shellsort (yes, it's one word) the input array keys, and apply the resulting permutation to the input...
KOKKOS_FUNCTION void shortSortKeys_3(KeyType keys[3])
Sort length-3 array of keys.
KOKKOS_FUNCTION void shortSortKeysAndValues_2(KeyType keys[2], ValueType values[2])
Sort keys and values jointly, by keys, for arrays of length 2.
KOKKOS_FUNCTION void shortSortKeys_2(KeyType keys[2])
Sort length-2 array of keys.
KOKKOS_FUNCTION void shortSortKeys_8(KeyType keys[8])
Sort length-8 array of keys.
KOKKOS_FUNCTION void shortSortKeysAndValues_4(KeyType keys[4], ValueType values[4])
Sort keys and values jointly, by keys, for arrays of length 4.
KOKKOS_FUNCTION void shortSortKeys_4(KeyType keys[4])
Sort length-4 array of keys.
Namespace Tpetra contains the class and methods constituting the Tpetra library.
@ ZERO
Replace old values with zero.