util/X86LINUX64/cuda-6.5/include/thrust/system/detail/generic/scalar/binary_search.inl

   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/detail/config.h>
  20 #include <thrust/pair.h>
  21 #include <thrust/detail/function.h>
  22 #include <thrust/iterator/iterator_traits.h>
  23
  24 namespace thrust
  25 {
  26
  27 namespace system
  28 {
  29
  30 namespace detail
  31 {
  32
  33 namespace generic
  34 {
  35
  36 namespace scalar
  37 {
  38
  39 template<typename RandomAccessIterator, typename Size, typename T, typename BinaryPredicate>
  40 __host__ __device__
  41 RandomAccessIterator lower_bound_n(RandomAccessIterator first,
  42                                    Size n,
  43                                    const T &val,
  44                                    BinaryPredicate comp)
  45 {
  46   // wrap comp
  47   thrust::detail::host_device_function<
  48     BinaryPredicate,
  49     bool
  50   > wrapped_comp(comp);
  51
  52   Size start = 0, i;
  53   while(start < n)
  54   {
  55     i = (start + n) / 2;
  56     if(wrapped_comp(first[i], val))
  57     {
  58       start = i + 1;
  59     }
  60     else
  61     {
  62       n = i;
  63     }
  64   } // end while
  65
  66   return first + start;
  67 }
  68
  69 // XXX generalize these upon implementation of scalar::distance & scalar::advance
  70
  71 template<typename RandomAccessIterator, typename T, typename BinaryPredicate>
  72 __host__ __device__
  73 RandomAccessIterator lower_bound(RandomAccessIterator first, RandomAccessIterator last,
  74                                  const T &val,
  75                                  BinaryPredicate comp)
  76 {
  77   typename thrust::iterator_difference<RandomAccessIterator>::type n = last - first;
  78   return lower_bound_n(first, n, val, comp);
  79 }
  80
  81 template<typename RandomAccessIterator, typename Size, typename T, typename BinaryPredicate>
  82 __host__ __device__
  83 RandomAccessIterator upper_bound_n(RandomAccessIterator first,
  84                                    Size n,
  85                                    const T &val,
  86                                    BinaryPredicate comp)
  87 {
  88   // wrap comp
  89   thrust::detail::host_device_function<
  90     BinaryPredicate,
  91     bool
  92   > wrapped_comp(comp);
  93
  94   Size start = 0, i;
  95   while(start < n)
  96   {
  97     i = (start + n) / 2;
  98     if(wrapped_comp(val, first[i]))
  99     {
 100       n = i;
 101     }
 102     else
 103     {
 104       start = i + 1;
 105     }
 106   } // end while
 107
 108   return first + start;
 109 }
 110
 111 template<typename RandomAccessIterator, typename T, typename BinaryPredicate>
 112 __host__ __device__
 113 RandomAccessIterator upper_bound(RandomAccessIterator first, RandomAccessIterator last,
 114                                  const T &val,
 115                                  BinaryPredicate comp)
 116 {
 117   typename thrust::iterator_difference<RandomAccessIterator>::type n = last - first;
 118   return upper_bound_n(first, n, val, comp);
 119 }
 120
 121 template<typename RandomAccessIterator, typename T, typename BinaryPredicate>
 122 __host__ __device__
 123   pair<RandomAccessIterator,RandomAccessIterator>
 124     equal_range(RandomAccessIterator first, RandomAccessIterator last,
 125                 const T &val,
 126                 BinaryPredicate comp)
 127 {
 128   RandomAccessIterator lb = thrust::system::detail::generic::scalar::lower_bound(first, last, val, comp);
 129   return thrust::make_pair(lb, thrust::system::detail::generic::scalar::upper_bound(lb, last, val, comp));
 130 }
 131
 132
 133 template<typename RandomAccessIterator, typename T, typename Compare>
 134 __host__ __device__
 135 bool binary_search(RandomAccessIterator first, RandomAccessIterator last, const T &value, Compare comp)
 136 {
 137   RandomAccessIterator iter = thrust::system::detail::generic::scalar::lower_bound(first, last, value, comp);
 138
 139   // wrap comp
 140   thrust::detail::host_device_function<
 141     Compare,
 142     bool
 143   > wrapped_comp(comp);
 144
 145   return iter != last && !wrapped_comp(value,*iter);
 146 }
 147
 148 } // end scalar
 149
 150 } // end generic
 151
 152 } // end detail
 153
 154 } // end system
 155
 156 } // end thrust
 157
 158 #include <thrust/system/detail/generic/scalar/binary_search.inl>
 159