← Back to branch summary

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

« back to all changes in this revision

Viewing changes to detail/backend/cpp/scan.h

  • Committer: Package Import Robot
  • Author(s): Andreas Beckmann
  • Date: 2011-12-02 01:48:24 UTC
  • mfrom: (1.1.1)
  • Revision ID: package-import@ubuntu.com-20111202014824-bpfczhbx39usefge
Tags: 1.5.0-1
* New upstream release.
* debian/copyright:
  - Update to dep5.mdwn?revision=202.
  - Update copyright entries for added/moved files.

Show diffs side-by-side

added added

removed removed

Lines of Context:
detail/backend/cpp/scan.h
 
1
/*
 
2
 *  Copyright 2008-2011 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 scan.h
 
19
 *  \brief C++ implementations of scan functions.
 
20
 */
 
21
 
 
22
#pragma once
 
23
 
 
24
#include <thrust/iterator/iterator_traits.h>
 
25
 
 
26
#include <thrust/detail/type_traits.h>
 
27
#include <thrust/detail/type_traits/function_traits.h>
 
28
#include <thrust/detail/type_traits/iterator/is_output_iterator.h>
 
29
 
 
30
#include <thrust/detail/backend/dereference.h>
 
31
 
 
32
namespace thrust
 
33
{
 
34
namespace detail
 
35
{
 
36
namespace backend
 
37
{
 
38
namespace cpp
 
39
{
 
40
 
 
41
template<typename InputIterator,
 
42
         typename OutputIterator,
 
43
         typename BinaryFunction>
 
44
  OutputIterator inclusive_scan(InputIterator first,
 
45
                                InputIterator last,
 
46
                                OutputIterator result,
 
47
                                BinaryFunction binary_op)
 
48
{
 
49
  // the pseudocode for deducing the type of the temporary used below:
 
50
  // 
 
51
  // if BinaryFunction is AdaptableBinaryFunction
 
52
  //   TemporaryType = AdaptableBinaryFunction::result_type
 
53
  // else if OutputIterator is a "pure" output iterator
 
54
  //   TemporaryType = InputIterator::value_type
 
55
  // else
 
56
  //   TemporaryType = OutputIterator::value_type
 
57
  //
 
58
  // XXX upon c++0x, TemporaryType needs to be:
 
59
  // result_of<BinaryFunction>::type
 
60
 
 
61
  typedef typename eval_if<
 
62
    has_result_type<BinaryFunction>::value,
 
63
    result_type<BinaryFunction>,
 
64
    eval_if<
 
65
      is_output_iterator<OutputIterator>::value,
 
66
      thrust::iterator_value<InputIterator>,
 
67
      thrust::iterator_value<OutputIterator>
 
68
    >
 
69
  >::type ValueType;
 
70
 
 
71
  if(first != last)
 
72
  {
 
73
    ValueType sum = dereference(first);
 
74
 
 
75
    dereference(result) = sum;
 
76
 
 
77
    for(++first, ++result; first != last; ++first, ++result)
 
78
      dereference(result) = sum = binary_op(sum, dereference(first));
 
79
  }
 
80
 
 
81
  return result;
 
82
}
 
83
 
 
84
 
 
85
template<typename InputIterator,
 
86
         typename OutputIterator,
 
87
         typename T,
 
88
         typename BinaryFunction>
 
89
  OutputIterator exclusive_scan(InputIterator first,
 
90
                                InputIterator last,
 
91
                                OutputIterator result,
 
92
                                T init,
 
93
                                BinaryFunction binary_op)
 
94
{
 
95
  // the pseudocode for deducing the type of the temporary used below:
 
96
  // 
 
97
  // if BinaryFunction is AdaptableBinaryFunction
 
98
  //   TemporaryType = AdaptableBinaryFunction::result_type
 
99
  // else if OutputIterator is a "pure" output iterator
 
100
  //   TemporaryType = InputIterator::value_type
 
101
  // else
 
102
  //   TemporaryType = OutputIterator::value_type
 
103
  //
 
104
  // XXX upon c++0x, TemporaryType needs to be:
 
105
  // result_of<BinaryFunction>::type
 
106
 
 
107
  typedef typename eval_if<
 
108
    has_result_type<BinaryFunction>::value,
 
109
    result_type<BinaryFunction>,
 
110
    eval_if<
 
111
      is_output_iterator<OutputIterator>::value,
 
112
      thrust::iterator_value<InputIterator>,
 
113
      thrust::iterator_value<OutputIterator>
 
114
    >
 
115
  >::type ValueType;
 
116
 
 
117
  if(first != last)
 
118
  {
 
119
    ValueType tmp = dereference(first);  // temporary value allows in-situ scan
 
120
    ValueType sum = init;
 
121
 
 
122
    *result = sum;
 
123
    sum = binary_op(sum, tmp);
 
124
 
 
125
    for(++first, ++result; first != last; ++first, ++result)
 
126
    {
 
127
      tmp = dereference(first);
 
128
      dereference(result) = sum;
 
129
      sum = binary_op(sum, tmp);
 
130
    }
 
131
  }
 
132
 
 
133
  return result;
 
134
} 
 
135
 
 
136
 
 
137
template<typename InputIterator1,
 
138
         typename InputIterator2,
 
139
         typename OutputIterator,
 
140
         typename BinaryPredicate,
 
141
         typename BinaryFunction>
 
142
  OutputIterator inclusive_scan_by_key(InputIterator1 first1,
 
143
                                       InputIterator1 last1,
 
144
                                       InputIterator2 first2,
 
145
                                       OutputIterator result,
 
146
                                       BinaryPredicate binary_pred,
 
147
                                       BinaryFunction binary_op)
 
148
{
 
149
    typedef typename thrust::iterator_traits<InputIterator1>::value_type KeyType;
 
150
    typedef typename thrust::iterator_traits<OutputIterator>::value_type ValueType;
 
151
 
 
152
    if(first1 != last1)
 
153
    {
 
154
        KeyType   prev_key   = dereference(first1);
 
155
        ValueType prev_value = dereference(first2);
 
156
 
 
157
        dereference(result) = prev_value;
 
158
 
 
159
        for(++first1, ++first2, ++result;
 
160
                first1 != last1;
 
161
                ++first1, ++first2, ++result)
 
162
        {
 
163
            KeyType key = dereference(first1);
 
164
 
 
165
            if (binary_pred(prev_key, key))
 
166
                dereference(result) = prev_value = binary_op(prev_value, dereference(first2));
 
167
            else
 
168
                dereference(result) = prev_value = dereference(first2);
 
169
 
 
170
            prev_key = key;
 
171
        }
 
172
    }
 
173
 
 
174
    return result;
 
175
}
 
176
 
 
177
 
 
178
template<typename InputIterator1,
 
179
         typename InputIterator2,
 
180
         typename OutputIterator,
 
181
         typename T,
 
182
         typename BinaryPredicate,
 
183
         typename BinaryFunction>
 
184
  OutputIterator exclusive_scan_by_key(InputIterator1 first1,
 
185
                                       InputIterator1 last1,
 
186
                                       InputIterator2 first2,
 
187
                                       OutputIterator result,
 
188
                                       T init,
 
189
                                       BinaryPredicate binary_pred,
 
190
                                       BinaryFunction binary_op)
 
191
{
 
192
    typedef typename thrust::iterator_traits<InputIterator1>::value_type KeyType;
 
193
    typedef typename thrust::iterator_traits<OutputIterator>::value_type ValueType;
 
194
 
 
195
    if(first1 != last1)
 
196
    {
 
197
        KeyType   temp_key   = dereference(first1);
 
198
        ValueType temp_value = dereference(first2);
 
199
        
 
200
        ValueType next = init;
 
201
 
 
202
        // first one is init
 
203
        dereference(result) = next;
 
204
 
 
205
        next = binary_op(next, temp_value);
 
206
 
 
207
        for(++first1, ++first2, ++result;
 
208
                first1 != last1;
 
209
                ++first1, ++first2, ++result)
 
210
        {
 
211
            KeyType key = dereference(first1);
 
212
 
 
213
            // use temp to permit in-place scans
 
214
            temp_value = dereference(first2);
 
215
 
 
216
            if (!binary_pred(temp_key, key))
 
217
                next = init;  // reset sum
 
218
                
 
219
            dereference(result) = next;  
 
220
            next = binary_op(next, temp_value);
 
221
 
 
222
            temp_key = key;
 
223
        }
 
224
    }
 
225
 
 
226
    return result;
 
227
}
 
228
 
 
229
} // end namespace cpp
 
230
} // end namespace backend
 
231
} // end namespace detail
 
232
} // end namespace thrust
 
233