util/X86LINUX64/cuda-6.5/include/thrust/system/cpp/detail/dispatch/sort.h

   1 /*
   2  *  Copyright 2008-2013 NVIDIA Corporation
   3  *
   4  *  Licensed under the Apache License, Version 2.0 (the "License");
   5  *  you may not use this file except in compliance with the License.
   6  *  You may obtain a copy of the License at
   7  *
   8  *      http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  *  Unless required by applicable law or agreed to in writing, software
  11  *  distributed under the License is distributed on an "AS IS" BASIS,
  12  *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  *  See the License for the specific language governing permissions and
  14  *  limitations under the License.
  15  */
  16
  17 #pragma once
  18
  19 #include <thrust/reverse.h>
  20
  21 #include <thrust/detail/type_traits.h>
  22 #include <thrust/iterator/iterator_traits.h>
  23
  24 #include <thrust/system/detail/internal/scalar/stable_merge_sort.h>
  25 #include <thrust/system/detail/internal/scalar/stable_radix_sort.h>
  26
  27 namespace thrust
  28 {
  29 namespace system
  30 {
  31 namespace cpp
  32 {
  33 namespace detail
  34 {
  35 namespace dispatch
  36 {
  37
  38 ////////////////
  39 // Radix Sort //
  40 ////////////////
  41
  42 template<typename RandomAccessIterator,
  43          typename StrictWeakOrdering>
  44 void stable_sort(RandomAccessIterator first,
  45                  RandomAccessIterator last,
  46                  StrictWeakOrdering comp,
  47                  thrust::detail::true_type)
  48 {
  49   thrust::system::detail::internal::scalar::stable_radix_sort(first, last);
  50
  51   // if comp is greater<T> then reverse the keys
  52   typedef typename thrust::iterator_traits<RandomAccessIterator>::value_type KeyType;
  53   const static bool reverse = thrust::detail::is_same<StrictWeakOrdering, typename thrust::greater<KeyType> >::value;
  54
  55   if (reverse)
  56     thrust::reverse(first, last);
  57 }
  58
  59 template<typename RandomAccessIterator1,
  60          typename RandomAccessIterator2,
  61          typename StrictWeakOrdering>
  62 void stable_sort_by_key(RandomAccessIterator1 first1,
  63                         RandomAccessIterator1 last1,
  64                         RandomAccessIterator2 first2,
  65                         StrictWeakOrdering comp,
  66                         thrust::detail::true_type)
  67 {
  68   // if comp is greater<T> then reverse the keys and values
  69   typedef typename thrust::iterator_traits<RandomAccessIterator1>::value_type KeyType;
  70   const static bool reverse = thrust::detail::is_same<StrictWeakOrdering, typename thrust::greater<KeyType> >::value;
  71
  72   // note, we also have to reverse the (unordered) input to preserve stability
  73   if (reverse)
  74   {
  75     thrust::reverse(first1,  last1);
  76     thrust::reverse(first2, first2 + (last1 - first1));
  77   }
  78
  79   thrust::system::detail::internal::scalar::stable_radix_sort_by_key(first1, last1, first2);
  80
  81   if (reverse)
  82   {
  83     thrust::reverse(first1,  last1);
  84     thrust::reverse(first2, first2 + (last1 - first1));
  85   }
  86 }
  87
  88 ////////////////
  89 // Merge Sort //
  90 ////////////////
  91
  92 template<typename RandomAccessIterator,
  93          typename StrictWeakOrdering>
  94 void stable_sort(RandomAccessIterator first,
  95                  RandomAccessIterator last,
  96                  StrictWeakOrdering comp,
  97                  thrust::detail::false_type)
  98 {
  99   thrust::system::detail::internal::scalar::stable_merge_sort(first, last, comp);
 100 }
 101
 102 template<typename RandomAccessIterator1,
 103          typename RandomAccessIterator2,
 104          typename StrictWeakOrdering>
 105 void stable_sort_by_key(RandomAccessIterator1 first1,
 106                         RandomAccessIterator1 last1,
 107                         RandomAccessIterator2 first2,
 108                         StrictWeakOrdering comp,
 109                         thrust::detail::false_type)
 110 {
 111   thrust::system::detail::internal::scalar::stable_merge_sort_by_key(first1, last1, first2, comp);
 112 }
 113
 114 } // end namespace dispatch
 115 } // end namespace detail
 116 } // end namespace cpp
 117 } // end namespace system
 118 } // end namespace thrust
 119