← Back to branch summary

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

« back to all changes in this revision

Viewing changes to detail/host/detail/merge.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/host/detail/merge.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
#include <thrust/iterator/iterator_traits.h>
 
19
 
 
20
#include <thrust/host_vector.h>
 
21
 
 
22
namespace thrust
 
23
{
 
24
namespace detail
 
25
{
 
26
namespace host
 
27
{
 
28
namespace detail
 
29
{
 
30
 
 
31
template <typename InputIterator1,
 
32
          typename InputIterator2,
 
33
          typename OutputIterator,
 
34
          typename StrictWeakOrdering>
 
35
OutputIterator merge(InputIterator1 first1,
 
36
                     InputIterator1 last1,
 
37
                     InputIterator2 first2,
 
38
                     InputIterator2 last2,
 
39
                     OutputIterator output,
 
40
                     StrictWeakOrdering comp)
 
41
{
 
42
    while(first1 != last1 && first2 != last2)
 
43
    {
 
44
        if(!comp(*first2, *first1))
 
45
        {
 
46
            // *first1 <= *first2
 
47
            *output = *first1;
 
48
            ++first1;
 
49
        }
 
50
        else
 
51
        {
 
52
            // *first1 > first2
 
53
            *output = *first2;
 
54
            ++first2;
 
55
        }
 
56
 
 
57
        ++output;
 
58
    }
 
59
    
 
60
    while(first1 != last1)
 
61
    {
 
62
        *output = *first1;
 
63
        ++first1;
 
64
        ++output;
 
65
    }
 
66
    
 
67
    while(first2 != last2)
 
68
    {
 
69
        *output = *first2;
 
70
        ++first2;
 
71
        ++output;
 
72
    }
 
73
 
 
74
    return output;
 
75
}
 
76
 
 
77
 
 
78
template <typename RandomAccessIterator,
 
79
          typename StrictWeakOrdering>
 
80
void inplace_merge(RandomAccessIterator first,
 
81
                   RandomAccessIterator middle,
 
82
                   RandomAccessIterator last,
 
83
                   StrictWeakOrdering comp)
 
84
{
 
85
    typedef typename thrust::iterator_value<RandomAccessIterator>::type value_type;
 
86
 
 
87
    thrust::host_vector<value_type> a( first, middle);
 
88
    thrust::host_vector<value_type> b(middle,   last);
 
89
 
 
90
    thrust::detail::host::detail::merge(a.begin(), a.end(), b.begin(), b.end(), first, comp);
 
91
}
 
92
 
 
93
 
 
94
template <typename InputIterator1,
 
95
          typename InputIterator2,
 
96
          typename InputIterator3,
 
97
          typename InputIterator4,
 
98
          typename OutputIterator1,
 
99
          typename OutputIterator2,
 
100
          typename StrictWeakOrdering>
 
101
thrust::pair<OutputIterator1,OutputIterator2>
 
102
    merge_by_key(InputIterator1 first1,
 
103
                 InputIterator1 last1,
 
104
                 InputIterator2 first2,
 
105
                 InputIterator2 last2,
 
106
                 InputIterator3 first3,
 
107
                 InputIterator4 first4,
 
108
                 OutputIterator1 output1,
 
109
                 OutputIterator2 output2,
 
110
                 StrictWeakOrdering comp)
 
111
{
 
112
    while(first1 != last1 && first2 != last2)
 
113
    {
 
114
        if(!comp(*first2, *first1))
 
115
        {
 
116
            // *first1 <= *first2
 
117
            *output1 = *first1;
 
118
            *output2 = *first3;
 
119
            ++first1;
 
120
            ++first3;
 
121
        }
 
122
        else
 
123
        {
 
124
            // *first1 > first2
 
125
            *output1 = *first2;
 
126
            *output2 = *first4;
 
127
            ++first2;
 
128
            ++first4;
 
129
        }
 
130
 
 
131
        ++output1;
 
132
        ++output2;
 
133
    }
 
134
    
 
135
    while(first1 != last1)
 
136
    {
 
137
        *output1 = *first1;
 
138
        *output2 = *first3;
 
139
        ++first1;
 
140
        ++first3;
 
141
        ++output1;
 
142
        ++output2;
 
143
    }
 
144
    
 
145
    while(first2 != last2)
 
146
    {
 
147
        *output1 = *first2;
 
148
        *output2 = *first4;
 
149
        ++first2;
 
150
        ++first4;
 
151
        ++output1;
 
152
        ++output2;
 
153
    }
 
154
 
 
155
    return thrust::make_pair(output1, output2);
 
156
}
 
157
 
 
158
 
 
159
template <typename RandomAccessIterator1,
 
160
          typename RandomAccessIterator2,
 
161
          typename StrictWeakOrdering>
 
162
void inplace_merge_by_key(RandomAccessIterator1 first1,
 
163
                          RandomAccessIterator1 middle1,
 
164
                          RandomAccessIterator1 last1,
 
165
                          RandomAccessIterator2 first2,
 
166
                          StrictWeakOrdering comp)
 
167
{
 
168
    typedef typename thrust::iterator_value<RandomAccessIterator1>::type value_type1;
 
169
    typedef typename thrust::iterator_value<RandomAccessIterator2>::type value_type2;
 
170
 
 
171
    RandomAccessIterator2 middle2 = first2 + (middle1 - first1);
 
172
    RandomAccessIterator2 last2   = first2 + (last1   - first1);
 
173
 
 
174
    thrust::host_vector<value_type1> lhs1( first1, middle1);
 
175
    thrust::host_vector<value_type1> rhs1(middle1,   last1);
 
176
    thrust::host_vector<value_type2> lhs2( first2, middle2);
 
177
    thrust::host_vector<value_type2> rhs2(middle2,   last2);
 
178
 
 
179
    thrust::detail::host::detail::merge_by_key
 
180
        (lhs1.begin(), lhs1.end(), rhs1.begin(), rhs1.end(),
 
181
         lhs2.begin(), rhs2.begin(),
 
182
         first1, first2, comp);
 
183
}
 
184
 
 
185
} // end namespace detail
 
186
} // end namespace host
 
187
} // end namespace detail
 
188
} // end namespace thrust
 
189