← Back to branch summary

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

« back to all changes in this revision

Viewing changes to detail/device/generic/unique.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/unique.inl
 
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 unique.inl
 
19
 *  \brief Inline file for unique.h.
 
20
 */
 
21
 
 
22
#pragma once
 
23
 
 
24
#include <thrust/iterator/iterator_traits.h>
 
25
#include <thrust/iterator/zip_iterator.h>
 
26
#include <thrust/transform.h>
 
27
 
 
28
#include <thrust/detail/raw_buffer.h>
 
29
#include <thrust/detail/type_traits.h>
 
30
#include <thrust/detail/internal_functional.h>
 
31
 
 
32
#include <thrust/detail/device/scan.h>
 
33
#include <thrust/detail/device/copy.h>
 
34
 
 
35
namespace thrust
 
36
{
 
37
namespace detail
 
38
{
 
39
namespace device
 
40
{
 
41
namespace generic
 
42
{
 
43
 
 
44
template <typename ForwardIterator,
 
45
          typename BinaryPredicate>
 
46
ForwardIterator unique(ForwardIterator first,
 
47
                       ForwardIterator last,
 
48
                       BinaryPredicate binary_pred)
 
49
{
 
50
    typedef typename thrust::iterator_traits<ForwardIterator>::value_type InputType;
 
51
    typedef typename thrust::iterator_space<ForwardIterator>::type        Space;
 
52
 
 
53
    thrust::detail::raw_buffer<InputType,Space> input(first, last);
 
54
 
 
55
    return thrust::detail::device::generic::unique_copy(input.begin(), input.end(), first, binary_pred);
 
56
}
 
57
 
 
58
template <typename InputIterator,
 
59
          typename OutputIterator,
 
60
          typename BinaryPredicate>
 
61
OutputIterator unique_copy(InputIterator first,
 
62
                           InputIterator last,
 
63
                           OutputIterator output,
 
64
                           BinaryPredicate binary_pred)
 
65
{
 
66
    typedef typename thrust::detail::minimum_space<
 
67
      typename thrust::iterator_space<InputIterator>::type,
 
68
      typename thrust::iterator_space<OutputIterator>::type
 
69
    >::type Space;
 
70
 
 
71
    // empty sequence
 
72
    if(first == last)
 
73
        return output;
 
74
 
 
75
    thrust::detail::raw_buffer<int,Space> stencil(thrust::distance(first, last));
 
76
 
 
77
    // mark first element in each group
 
78
    stencil[0] = 1; 
 
79
    thrust::transform(first, last - 1, first + 1, stencil.begin() + 1, thrust::detail::not2(binary_pred)); 
 
80
 
 
81
    return thrust::detail::device::copy_if(first, last, stencil.begin(), output, thrust::identity<int>());
 
82
}
 
83
 
 
84
template <typename ForwardIterator1,
 
85
          typename ForwardIterator2,
 
86
          typename BinaryPredicate>
 
87
  thrust::pair<ForwardIterator1,ForwardIterator2>
 
88
  unique_by_key(ForwardIterator1 keys_first, 
 
89
                ForwardIterator1 keys_last,
 
90
                ForwardIterator2 values_first,
 
91
                BinaryPredicate binary_pred)
 
92
{
 
93
    typedef typename thrust::iterator_traits<ForwardIterator1>::value_type InputType1;
 
94
    typedef typename thrust::iterator_traits<ForwardIterator2>::value_type InputType2;
 
95
    typedef typename thrust::iterator_space<ForwardIterator1>::type        Space;
 
96
 
 
97
    ForwardIterator2 values_last = values_first + (keys_last - keys_first);
 
98
 
 
99
    thrust::detail::raw_buffer<InputType1,Space> keys(keys_first, keys_last);
 
100
    thrust::detail::raw_buffer<InputType2,Space> vals(values_first, values_last);
 
101
 
 
102
    return thrust::detail::device::generic::unique_by_key_copy
 
103
        (keys.begin(), keys.end(), vals.begin(), keys_first, values_first, binary_pred);
 
104
}
 
105
 
 
106
template <typename InputIterator1,
 
107
          typename InputIterator2,
 
108
          typename OutputIterator1,
 
109
          typename OutputIterator2,
 
110
          typename BinaryPredicate>
 
111
  thrust::pair<OutputIterator1,OutputIterator2>
 
112
  unique_by_key_copy(InputIterator1 keys_first, 
 
113
                     InputIterator1 keys_last,
 
114
                     InputIterator2 values_first,
 
115
                     OutputIterator1 keys_output,
 
116
                     OutputIterator2 values_output,
 
117
                     BinaryPredicate binary_pred)
 
118
{
 
119
    typedef typename thrust::iterator_traits<InputIterator1>::difference_type difference_type;
 
120
    typedef typename thrust::detail::minimum_space<
 
121
      typename thrust::iterator_space<InputIterator1>::type,
 
122
      typename thrust::iterator_space<InputIterator2>::type,
 
123
      typename thrust::iterator_space<OutputIterator1>::type,
 
124
      typename thrust::iterator_space<OutputIterator2>::type
 
125
    >::type Space;
 
126
 
 
127
    // empty sequence
 
128
    if(keys_first == keys_last)
 
129
        return thrust::make_pair(keys_output, values_output);
 
130
 
 
131
    difference_type n = thrust::distance(keys_first, keys_last);
 
132
 
 
133
    thrust::detail::raw_buffer<int,Space> stencil(n);
 
134
 
 
135
    // mark first element in each group
 
136
    stencil[0] = 1; 
 
137
    thrust::transform(keys_first, keys_last - 1, keys_first + 1, stencil.begin() + 1, thrust::detail::not2(binary_pred)); 
 
138
 
 
139
    thrust::zip_iterator< thrust::tuple<OutputIterator1, OutputIterator2> > result =
 
140
        thrust::detail::device::copy_if(thrust::make_zip_iterator(thrust::make_tuple(keys_first, values_first)),
 
141
                                        thrust::make_zip_iterator(thrust::make_tuple(keys_first, values_first)) + n,
 
142
                                        stencil.begin(),
 
143
                                        thrust::make_zip_iterator(thrust::make_tuple(keys_output, values_output)),
 
144
                                        thrust::identity<int>());
 
145
    
 
146
    difference_type output_size = result - thrust::make_zip_iterator(thrust::make_tuple(keys_output, values_output));
 
147
                                    
 
148
    return thrust::make_pair(keys_output + output_size, values_output + output_size);
 
149
}
 
150
 
 
151
} // end namespace generic
 
152
} // end namespace device
 
153
} // end namespace detail
 
154
} // end namespace thrust
 
155