← Back to branch summary

~ubuntu-branches/ubuntu/trusty/libthrust/trusty

« back to all changes in this revision

Viewing changes to detail/device/generic/scalar/binary_search.inl

  • Committer: Bazaar Package Importer
  • Author(s): Andreas Beckmann
  • Date: 2011-05-28 09:32:48 UTC
  • Revision ID: james.westby@ubuntu.com-20110528093248-np3euv5sj7fw3nyv
Tags: upstream-1.4.0
Import upstream version 1.4.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
detail/device/generic/scalar/binary_search.inl
 
1
/*
 
2
 *  Copyright 2008-2009 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/device/dereference.h>
 
22
#include <thrust/iterator/iterator_traits.h>
 
23
 
 
24
namespace thrust
 
25
{
 
26
 
 
27
namespace detail
 
28
{
 
29
 
 
30
namespace device
 
31
{
 
32
 
 
33
namespace generic
 
34
{
 
35
 
 
36
namespace scalar
 
37
{
 
38
 
 
39
// XXX generalize these upon implementation of scalar::distance & scalar::advance
 
40
 
 
41
template<typename RandomAccessIterator, typename T, typename BinaryPredicate>
 
42
__host__ __device__
 
43
RandomAccessIterator lower_bound(RandomAccessIterator first, RandomAccessIterator last,
 
44
                                 const T &val,
 
45
                                 BinaryPredicate comp)
 
46
{
 
47
  typedef typename thrust::iterator_difference<RandomAccessIterator>::type difference_type;
 
48
 
 
49
  // XXX should read len = distance(first,last)
 
50
  difference_type len = last - first;
 
51
 
 
52
  while(len > 0)
 
53
  {
 
54
    difference_type half = len >> 1;
 
55
    RandomAccessIterator middle = first;
 
56
 
 
57
    // XXX should read advance(middle,half)
 
58
    middle += half;
 
59
 
 
60
    if(comp(dereference(middle), val))
 
61
    {
 
62
      first = middle;
 
63
      ++first;
 
64
      len = len - half - 1;
 
65
    }
 
66
    else
 
67
    {
 
68
      len = half;
 
69
    }
 
70
  }
 
71
 
 
72
  return first;
 
73
}
 
74
 
 
75
template<typename RandomAccessIterator, typename T, typename BinaryPredicate>
 
76
__host__ __device__
 
77
RandomAccessIterator upper_bound(RandomAccessIterator first, RandomAccessIterator last,
 
78
                                 const T &val,
 
79
                                 BinaryPredicate comp)
 
80
{
 
81
  typedef typename thrust::iterator_difference<RandomAccessIterator>::type difference_type;
 
82
 
 
83
  // XXX should read len = distance(first,last)
 
84
  difference_type len = last - first;
 
85
 
 
86
  while(len > 0)
 
87
  {
 
88
    difference_type half = len >> 1;
 
89
    RandomAccessIterator middle = first;
 
90
 
 
91
    // XXX should read advance(middle,half)
 
92
    middle += half;
 
93
 
 
94
    if(comp(val, dereference(middle)))
 
95
    {
 
96
      len = half;
 
97
    }
 
98
    else
 
99
    {
 
100
      first = middle;
 
101
      ++first;
 
102
      len = len - half - 1;
 
103
    }
 
104
  }
 
105
 
 
106
  return first;
 
107
}
 
108
 
 
109
template<typename RandomAccessIterator, typename T, typename BinaryPredicate>
 
110
__host__ __device__
 
111
  pair<RandomAccessIterator,RandomAccessIterator>
 
112
    equal_range(RandomAccessIterator first, RandomAccessIterator last,
 
113
                const T &val,
 
114
                BinaryPredicate comp)
 
115
{
 
116
  RandomAccessIterator lb = thrust::detail::device::generic::scalar::lower_bound(first, last, val, comp);
 
117
  return thrust::make_pair(lb, thrust::detail::device::generic::scalar::upper_bound(lb, last, val, comp));
 
118
}
 
119
 
 
120
 
 
121
template<typename RandomAccessIterator, typename T, typename Compare>
 
122
__host__ __device__
 
123
bool binary_search(RandomAccessIterator first, RandomAccessIterator last, const T &value, Compare comp)
 
124
{
 
125
  RandomAccessIterator iter = thrust::detail::device::generic::scalar::lower_bound(first,last,value,comp);
 
126
  return iter != last && !comp(value, *iter);
 
127
}
 
128
 
 
129
} // end scalar
 
130
 
 
131
} // end generic
 
132
 
 
133
} // end device
 
134
 
 
135
} // end detail
 
136
 
 
137
} // end thrust
 
138
 
 
139
#include <thrust/detail/device/generic/scalar/binary_search.inl>
 
140