utiltools/X86MAC64/cuda/include/thrust/system/detail/internal/scalar/stable_merge_sort.inl

   1 /*
   2  *  Copyright 2008-2012 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
  18 #include <thrust/iterator/iterator_traits.h>
  19 #include <thrust/detail/temporary_array.h>
  20 #include <thrust/system/detail/internal/scalar/merge.h>
  21 #include <thrust/system/detail/internal/scalar/insertion_sort.h>
  22
  23 namespace thrust
  24 {
  25 namespace system
  26 {
  27 namespace detail
  28 {
  29 namespace internal
  30 {
  31 namespace scalar
  32 {
  33 namespace detail
  34 {
  35
  36 template <typename RandomAccessIterator,
  37           typename StrictWeakOrdering>
  38 void inplace_merge(RandomAccessIterator first,
  39                    RandomAccessIterator middle,
  40                    RandomAccessIterator last,
  41                    StrictWeakOrdering comp)
  42 {
  43   // XXX the type of exec should be:
  44   //     typedef decltype(select_system(first, middle, last)) DerivedPolicy;
  45   typedef typename thrust::iterator_system<RandomAccessIterator>::type DerivedPolicy;
  46   typedef typename thrust::iterator_value<RandomAccessIterator>::type value_type;
  47
  48   // XXX assumes DerivedPolicy is default constructible
  49   // XXX find a way to get a stateful execution policy into this function
  50   //     or simply pass scratch space
  51   DerivedPolicy exec;
  52   thrust::detail::temporary_array<value_type, DerivedPolicy> a(exec, first, middle);
  53   thrust::detail::temporary_array<value_type, DerivedPolicy> b(exec, middle, last);
  54
  55   thrust::system::detail::internal::scalar::merge(a.begin(), a.end(), b.begin(), b.end(), first, comp);
  56 }
  57
  58 template <typename RandomAccessIterator1,
  59           typename RandomAccessIterator2,
  60           typename StrictWeakOrdering>
  61 void inplace_merge_by_key(RandomAccessIterator1 first1,
  62                           RandomAccessIterator1 middle1,
  63                           RandomAccessIterator1 last1,
  64                           RandomAccessIterator2 first2,
  65                           StrictWeakOrdering comp)
  66 {
  67   // XXX the type of exec should be:
  68   //     typedef decltype(select_system(first1, middle1, last1, first2)) DerivedPolicy;
  69   typedef typename thrust::iterator_system<RandomAccessIterator1>::type DerivedPolicy;
  70   typedef typename thrust::iterator_value<RandomAccessIterator1>::type value_type1;
  71   typedef typename thrust::iterator_value<RandomAccessIterator2>::type value_type2;
  72
  73   RandomAccessIterator2 middle2 = first2 + (middle1 - first1);
  74   RandomAccessIterator2 last2   = first2 + (last1   - first1);
  75
  76   // XXX assumes DerivedPolicy is default constructible
  77   // XXX find a way to get a stateful exec into this function
  78   //     or simply pass scratch space
  79   DerivedPolicy exec;
  80   thrust::detail::temporary_array<value_type1, DerivedPolicy> lhs1(exec, first1, middle1);
  81   thrust::detail::temporary_array<value_type1, DerivedPolicy> rhs1(exec, middle1, last1);
  82   thrust::detail::temporary_array<value_type2, DerivedPolicy> lhs2(exec, first2, middle2);
  83   thrust::detail::temporary_array<value_type2, DerivedPolicy> rhs2(exec, middle2, last2);
  84
  85   thrust::system::detail::internal::scalar::merge_by_key
  86     (lhs1.begin(), lhs1.end(), rhs1.begin(), rhs1.end(),
  87      lhs2.begin(), rhs2.begin(),
  88      first1, first2, comp);
  89 }
  90
  91 } // end namespace detail
  92
  93 //////////////
  94 // Key Sort //
  95 //////////////
  96
  97 template <typename RandomAccessIterator,
  98           typename StrictWeakOrdering>
  99 void stable_merge_sort(RandomAccessIterator first,
 100                        RandomAccessIterator last,
 101                        StrictWeakOrdering comp)
 102 {
 103   if (last - first < 32)
 104   {
 105     thrust::system::detail::internal::scalar::insertion_sort(first, last, comp);
 106   }
 107   else
 108   {
 109     RandomAccessIterator middle = first + (last - first) / 2;
 110
 111     thrust::system::detail::internal::scalar::stable_merge_sort(first, middle, comp);
 112     thrust::system::detail::internal::scalar::stable_merge_sort(middle,  last, comp);
 113     detail::inplace_merge(first, middle, last, comp);
 114   }
 115 }
 116
 117
 118 ////////////////////
 119 // Key-Value Sort //
 120 ////////////////////
 121
 122 template <typename RandomAccessIterator1,
 123           typename RandomAccessIterator2,
 124           typename StrictWeakOrdering>
 125 void stable_merge_sort_by_key(RandomAccessIterator1 first1,
 126                               RandomAccessIterator1 last1,
 127                               RandomAccessIterator2 first2,
 128                               StrictWeakOrdering comp)
 129 {
 130   if (last1 - first1 <= 32)
 131   {
 132     thrust::system::detail::internal::scalar::insertion_sort_by_key(first1, last1, first2, comp);
 133   }
 134   else
 135   {
 136     RandomAccessIterator1 middle1 = first1 + (last1 - first1) / 2;
 137     RandomAccessIterator2 middle2 = first2 + (last1 - first1) / 2;
 138
 139     thrust::system::detail::internal::scalar::stable_merge_sort_by_key(first1, middle1, first2,  comp);
 140     thrust::system::detail::internal::scalar::stable_merge_sort_by_key(middle1,  last1, middle2, comp);
 141     detail::inplace_merge_by_key(first1, middle1, last1, first2, comp);
 142   }
 143 }
 144
 145 } // end namespace scalar
 146 } // end namespace internal
 147 } // end namespace detail
 148 } // end namespace system
 149 } // end namespace thrust
 150