util/X86LINUX64/cuda-6.5/include/thrust/detail/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
  18 /*! \file binary_search.inl
  19  *  \brief Inline file for binary_search.h.
  20  */
  21
  22 #include <thrust/detail/config.h>
  23 #include <thrust/binary_search.h>
  24 #include <thrust/iterator/iterator_traits.h>
  25 #include <thrust/system/detail/generic/select_system.h>
  26 #include <thrust/system/detail/generic/binary_search.h>
  27 #include <thrust/system/detail/adl/binary_search.h>
  28
  29 namespace thrust
  30 {
  31
  32
  33 template <typename DerivedPolicy, typename ForwardIterator, typename LessThanComparable>
  34 ForwardIterator lower_bound(const thrust::detail::execution_policy_base<DerivedPolicy> &exec,
  35                             ForwardIterator first,
  36                             ForwardIterator last,
  37                             const LessThanComparable &value)
  38 {
  39     using thrust::system::detail::generic::lower_bound;
  40     return lower_bound(thrust::detail::derived_cast(thrust::detail::strip_const(exec)), first, last, value);
  41 }
  42
  43
  44 template<typename DerivedPolicy, typename ForwardIterator, typename T, typename StrictWeakOrdering>
  45 ForwardIterator lower_bound(const thrust::detail::execution_policy_base<DerivedPolicy> &exec,
  46                             ForwardIterator first,
  47                             ForwardIterator last,
  48                             const T &value,
  49                             StrictWeakOrdering comp)
  50 {
  51     using thrust::system::detail::generic::lower_bound;
  52     return lower_bound(thrust::detail::derived_cast(thrust::detail::strip_const(exec)), first, last, value, comp);
  53 }
  54
  55
  56 template<typename DerivedPolicy, typename ForwardIterator, typename LessThanComparable>
  57 ForwardIterator upper_bound(const thrust::detail::execution_policy_base<DerivedPolicy> &exec,
  58                             ForwardIterator first,
  59                             ForwardIterator last,
  60                             const LessThanComparable &value)
  61 {
  62     using thrust::system::detail::generic::upper_bound;
  63     return upper_bound(thrust::detail::derived_cast(thrust::detail::strip_const(exec)), first, last, value);
  64 }
  65
  66
  67 template<typename DerivedPolicy, typename ForwardIterator, typename T, typename StrictWeakOrdering>
  68 ForwardIterator upper_bound(const thrust::detail::execution_policy_base<DerivedPolicy> &exec,
  69                             ForwardIterator first,
  70                             ForwardIterator last,
  71                             const T &value,
  72                             StrictWeakOrdering comp)
  73 {
  74     using thrust::system::detail::generic::upper_bound;
  75     return upper_bound(thrust::detail::derived_cast(thrust::detail::strip_const(exec)), first, last, value, comp);
  76 }
  77
  78
  79 template <typename DerivedPolicy, typename ForwardIterator, typename LessThanComparable>
  80 bool binary_search(const thrust::detail::execution_policy_base<DerivedPolicy> &exec,
  81                    ForwardIterator first,
  82                    ForwardIterator last,
  83                    const LessThanComparable& value)
  84 {
  85     using thrust::system::detail::generic::binary_search;
  86     return binary_search(thrust::detail::derived_cast(thrust::detail::strip_const(exec)), first, last, value);
  87 }
  88
  89
  90 template <typename DerivedPolicy, typename ForwardIterator, typename T, typename StrictWeakOrdering>
  91 bool binary_search(const thrust::detail::execution_policy_base<DerivedPolicy> &exec,
  92                    ForwardIterator first,
  93                    ForwardIterator last,
  94                    const T& value,
  95                    StrictWeakOrdering comp)
  96 {
  97     using thrust::system::detail::generic::binary_search;
  98     return binary_search(thrust::detail::derived_cast(thrust::detail::strip_const(exec)), first, last, value, comp);
  99 }
 100
 101
 102 template <typename DerivedPolicy, typename ForwardIterator, typename T, typename StrictWeakOrdering>
 103 thrust::pair<ForwardIterator, ForwardIterator>
 104 equal_range(const thrust::detail::execution_policy_base<DerivedPolicy> &exec,
 105             ForwardIterator first,
 106             ForwardIterator last,
 107             const T& value,
 108             StrictWeakOrdering comp)
 109 {
 110     using thrust::system::detail::generic::equal_range;
 111     return equal_range(thrust::detail::derived_cast(thrust::detail::strip_const(exec)), first, last, value, comp);
 112 }
 113
 114
 115 template <typename DerivedPolicy, typename ForwardIterator, typename LessThanComparable>
 116 thrust::pair<ForwardIterator, ForwardIterator>
 117 equal_range(const thrust::detail::execution_policy_base<DerivedPolicy> &exec,
 118             ForwardIterator first,
 119             ForwardIterator last,
 120             const LessThanComparable& value)
 121 {
 122     using thrust::system::detail::generic::equal_range;
 123     return equal_range(thrust::detail::derived_cast(thrust::detail::strip_const(exec)), first, last, value);
 124 }
 125
 126
 127 template <typename DerivedPolicy, typename ForwardIterator, typename InputIterator, typename OutputIterator>
 128 OutputIterator lower_bound(const thrust::detail::execution_policy_base<DerivedPolicy> &exec,
 129                            ForwardIterator first,
 130                            ForwardIterator last,
 131                            InputIterator values_first,
 132                            InputIterator values_last,
 133                            OutputIterator output)
 134 {
 135     using thrust::system::detail::generic::lower_bound;
 136     return lower_bound(thrust::detail::derived_cast(thrust::detail::strip_const(exec)), first, last, values_first, values_last, output);
 137 }
 138
 139
 140 template <typename DerivedPolicy, typename ForwardIterator, typename InputIterator, typename OutputIterator, typename StrictWeakOrdering>
 141 OutputIterator lower_bound(const thrust::detail::execution_policy_base<DerivedPolicy> &exec,
 142                            ForwardIterator first,
 143                            ForwardIterator last,
 144                            InputIterator values_first,
 145                            InputIterator values_last,
 146                            OutputIterator output,
 147                            StrictWeakOrdering comp)
 148 {
 149     using thrust::system::detail::generic::lower_bound;
 150     return lower_bound(thrust::detail::derived_cast(thrust::detail::strip_const(exec)), first, last, values_first, values_last, output, comp);
 151 }
 152
 153
 154 template <typename DerivedPolicy, typename ForwardIterator, typename InputIterator, typename OutputIterator>
 155 OutputIterator upper_bound(const thrust::detail::execution_policy_base<DerivedPolicy> &exec,
 156                            ForwardIterator first,
 157                            ForwardIterator last,
 158                            InputIterator values_first,
 159                            InputIterator values_last,
 160                            OutputIterator output)
 161 {
 162     using thrust::system::detail::generic::upper_bound;
 163     return upper_bound(thrust::detail::derived_cast(thrust::detail::strip_const(exec)), first, last, values_first, values_last, output);
 164 }
 165
 166
 167 template <typename DerivedPolicy, typename ForwardIterator, typename InputIterator, typename OutputIterator, typename StrictWeakOrdering>
 168 OutputIterator upper_bound(const thrust::detail::execution_policy_base<DerivedPolicy> &exec,
 169                            ForwardIterator first,
 170                            ForwardIterator last,
 171                            InputIterator values_first,
 172                            InputIterator values_last,
 173                            OutputIterator output,
 174                            StrictWeakOrdering comp)
 175 {
 176     using thrust::system::detail::generic::upper_bound;
 177     return upper_bound(thrust::detail::derived_cast(thrust::detail::strip_const(exec)), first, last, values_first, values_last, output, comp);
 178 }
 179
 180
 181 template <typename DerivedPolicy, typename ForwardIterator, typename InputIterator, typename OutputIterator>
 182 OutputIterator binary_search(const thrust::detail::execution_policy_base<DerivedPolicy> &exec,
 183                              ForwardIterator first,
 184                              ForwardIterator last,
 185                              InputIterator values_first,
 186                              InputIterator values_last,
 187                              OutputIterator output)
 188 {
 189     using thrust::system::detail::generic::binary_search;
 190     return binary_search(thrust::detail::derived_cast(thrust::detail::strip_const(exec)), first, last, values_first, values_last, output);
 191 }
 192
 193
 194 template <typename DerivedPolicy, typename ForwardIterator, typename InputIterator, typename OutputIterator, typename StrictWeakOrdering>
 195 OutputIterator binary_search(const thrust::detail::execution_policy_base<DerivedPolicy> &exec,
 196                              ForwardIterator first,
 197                              ForwardIterator last,
 198                              InputIterator values_first,
 199                              InputIterator values_last,
 200                              OutputIterator output,
 201                              StrictWeakOrdering comp)
 202 {
 203     using thrust::system::detail::generic::binary_search;
 204     return binary_search(thrust::detail::derived_cast(thrust::detail::strip_const(exec)), first, last, values_first, values_last, output, comp);
 205 }
 206
 207
 208 //////////////////////
 209 // Scalar Functions //
 210 //////////////////////
 211
 212 template <typename ForwardIterator, typename LessThanComparable>
 213 ForwardIterator lower_bound(ForwardIterator first,
 214                             ForwardIterator last,
 215                             const LessThanComparable& value)
 216 {
 217     using thrust::system::detail::generic::select_system;
 218
 219     typedef typename thrust::iterator_system<ForwardIterator>::type System;
 220
 221     System system;
 222
 223     return thrust::lower_bound(select_system(system), first, last, value);
 224 }
 225
 226 template <typename ForwardIterator, typename T, typename StrictWeakOrdering>
 227 ForwardIterator lower_bound(ForwardIterator first,
 228                             ForwardIterator last,
 229                             const T& value,
 230                             StrictWeakOrdering comp)
 231 {
 232     using thrust::system::detail::generic::select_system;
 233
 234     typedef typename thrust::iterator_system<ForwardIterator>::type System;
 235
 236     System system;
 237
 238     return thrust::lower_bound(select_system(system), first, last, value, comp);
 239 }
 240
 241 template <typename ForwardIterator, typename LessThanComparable>
 242 ForwardIterator upper_bound(ForwardIterator first,
 243                             ForwardIterator last,
 244                             const LessThanComparable& value)
 245 {
 246     using thrust::system::detail::generic::select_system;
 247
 248     typedef typename thrust::iterator_system<ForwardIterator>::type System;
 249
 250     System system;
 251
 252     return thrust::upper_bound(select_system(system), first, last, value);
 253 }
 254
 255 template <typename ForwardIterator, typename T, typename StrictWeakOrdering>
 256 ForwardIterator upper_bound(ForwardIterator first,
 257                             ForwardIterator last,
 258                             const T& value,
 259                             StrictWeakOrdering comp)
 260 {
 261     using thrust::system::detail::generic::select_system;
 262
 263     typedef typename thrust::iterator_system<ForwardIterator>::type System;
 264
 265     System system;
 266
 267     return thrust::upper_bound(select_system(system), first, last, value, comp);
 268 }
 269
 270 template <typename ForwardIterator, typename LessThanComparable>
 271 bool binary_search(ForwardIterator first,
 272                    ForwardIterator last,
 273                    const LessThanComparable& value)
 274 {
 275     using thrust::system::detail::generic::select_system;
 276
 277     typedef typename thrust::iterator_system<ForwardIterator>::type System;
 278
 279     System system;
 280
 281     return thrust::binary_search(select_system(system), first, last, value);
 282 }
 283
 284 template <typename ForwardIterator, typename T, typename StrictWeakOrdering>
 285 bool binary_search(ForwardIterator first,
 286                    ForwardIterator last,
 287                    const T& value,
 288                    StrictWeakOrdering comp)
 289 {
 290     using thrust::system::detail::generic::select_system;
 291
 292     typedef typename thrust::iterator_system<ForwardIterator>::type System;
 293
 294     System system;
 295
 296     return thrust::binary_search(select_system(system), first, last, value, comp);
 297 }
 298
 299 template <typename ForwardIterator, typename LessThanComparable>
 300 thrust::pair<ForwardIterator, ForwardIterator>
 301 equal_range(ForwardIterator first,
 302             ForwardIterator last,
 303             const LessThanComparable& value)
 304 {
 305     using thrust::system::detail::generic::select_system;
 306
 307     typedef typename thrust::iterator_system<ForwardIterator>::type System;
 308
 309     System system;
 310
 311     return thrust::equal_range(select_system(system), first, last, value);
 312 }
 313
 314 template <typename ForwardIterator, typename T, typename StrictWeakOrdering>
 315 thrust::pair<ForwardIterator, ForwardIterator>
 316 equal_range(ForwardIterator first,
 317             ForwardIterator last,
 318             const T& value,
 319             StrictWeakOrdering comp)
 320 {
 321     using thrust::system::detail::generic::select_system;
 322
 323     typedef typename thrust::iterator_system<ForwardIterator>::type System;
 324
 325     System system;
 326
 327     return thrust::equal_range(select_system(system), first, last, value, comp);
 328 }
 329
 330 //////////////////////
 331 // Vector Functions //
 332 //////////////////////
 333
 334 template <typename ForwardIterator, typename InputIterator, typename OutputIterator>
 335 OutputIterator lower_bound(ForwardIterator first,
 336                            ForwardIterator last,
 337                            InputIterator values_first,
 338                            InputIterator values_last,
 339                            OutputIterator output)
 340 {
 341     using thrust::system::detail::generic::select_system;
 342
 343     typedef typename thrust::iterator_system<ForwardIterator>::type System1;
 344     typedef typename thrust::iterator_system<InputIterator>::type   System2;
 345     typedef typename thrust::iterator_system<OutputIterator>::type  System3;
 346
 347     System1 system1;
 348     System2 system2;
 349     System3 system3;
 350
 351     return thrust::lower_bound(select_system(system1,system2,system3), first, last, values_first, values_last, output);
 352 }
 353
 354 template <typename ForwardIterator, typename InputIterator, typename OutputIterator, typename StrictWeakOrdering>
 355 OutputIterator lower_bound(ForwardIterator first,
 356                            ForwardIterator last,
 357                            InputIterator values_first,
 358                            InputIterator values_last,
 359                            OutputIterator output,
 360                            StrictWeakOrdering comp)
 361 {
 362     using thrust::system::detail::generic::select_system;
 363
 364     typedef typename thrust::iterator_system<ForwardIterator>::type System1;
 365     typedef typename thrust::iterator_system<InputIterator>::type   System2;
 366     typedef typename thrust::iterator_system<OutputIterator>::type  System3;
 367
 368     System1 system1;
 369     System2 system2;
 370     System3 system3;
 371
 372     return thrust::lower_bound(select_system(system1,system2,system3), first, last, values_first, values_last, output, comp);
 373 }
 374
 375 template <typename ForwardIterator, typename InputIterator, typename OutputIterator>
 376 OutputIterator upper_bound(ForwardIterator first,
 377                            ForwardIterator last,
 378                            InputIterator values_first,
 379                            InputIterator values_last,
 380                            OutputIterator output)
 381 {
 382     using thrust::system::detail::generic::select_system;
 383
 384     typedef typename thrust::iterator_system<ForwardIterator>::type System1;
 385     typedef typename thrust::iterator_system<InputIterator>::type   System2;
 386     typedef typename thrust::iterator_system<OutputIterator>::type  System3;
 387
 388     System1 system1;
 389     System2 system2;
 390     System3 system3;
 391
 392     return thrust::upper_bound(select_system(system1,system2,system3), first, last, values_first, values_last, output);
 393 }
 394
 395 template <typename ForwardIterator, typename InputIterator, typename OutputIterator, typename StrictWeakOrdering>
 396 OutputIterator upper_bound(ForwardIterator first,
 397                            ForwardIterator last,
 398                            InputIterator values_first,
 399                            InputIterator values_last,
 400                            OutputIterator output,
 401                            StrictWeakOrdering comp)
 402 {
 403     using thrust::system::detail::generic::select_system;
 404
 405     typedef typename thrust::iterator_system<ForwardIterator>::type System1;
 406     typedef typename thrust::iterator_system<InputIterator>::type   System2;
 407     typedef typename thrust::iterator_system<OutputIterator>::type  System3;
 408
 409     System1 system1;
 410     System2 system2;
 411     System3 system3;
 412
 413     return thrust::upper_bound(select_system(system1,system2,system3), first, last, values_first, values_last, output, comp);
 414 }
 415
 416 template <typename ForwardIterator, typename InputIterator, typename OutputIterator>
 417 OutputIterator binary_search(ForwardIterator first,
 418                              ForwardIterator last,
 419                              InputIterator values_first,
 420                              InputIterator values_last,
 421                              OutputIterator output)
 422 {
 423     using thrust::system::detail::generic::select_system;
 424
 425     typedef typename thrust::iterator_system<ForwardIterator>::type System1;
 426     typedef typename thrust::iterator_system<InputIterator>::type   System2;
 427     typedef typename thrust::iterator_system<OutputIterator>::type  System3;
 428
 429     System1 system1;
 430     System2 system2;
 431     System3 system3;
 432
 433     return thrust::binary_search(select_system(system1,system2,system3), first, last, values_first, values_last, output);
 434 }
 435
 436 template <typename ForwardIterator, typename InputIterator, typename OutputIterator, typename StrictWeakOrdering>
 437 OutputIterator binary_search(ForwardIterator first,
 438                              ForwardIterator last,
 439                              InputIterator values_first,
 440                              InputIterator values_last,
 441                              OutputIterator output,
 442                              StrictWeakOrdering comp)
 443 {
 444     using thrust::system::detail::generic::select_system;
 445
 446     typedef typename thrust::iterator_system<ForwardIterator>::type System1;
 447     typedef typename thrust::iterator_system<InputIterator>::type   System2;
 448     typedef typename thrust::iterator_system<OutputIterator>::type  System3;
 449
 450     System1 system1;
 451     System2 system2;
 452     System3 system3;
 453
 454     return thrust::binary_search(select_system(system1,system2,system3), first, last, values_first, values_last, output, comp);
 455 }
 456
 457 } // end namespace thrust
 458