1 /***************************************************************************
2 * include/stxxl/bits/containers/pq_mergers.h
3 *
4 * Part of the STXXL. See http://stxxl.sourceforge.net
5 *
6 * Copyright (C) 1999 Peter Sanders <sanders@mpi-sb.mpg.de>
7 * Copyright (C) 2003, 2004, 2007 Roman Dementiev <dementiev@mpi-sb.mpg.de>
8 * Copyright (C) 2007-2009 Johannes Singler <singler@ira.uka.de>
9 * Copyright (C) 2007, 2008 Andreas Beckmann <beckmann@cs.uni-frankfurt.de>
10 *
11 * Distributed under the Boost Software License, Version 1.0.
12 * (See accompanying file LICENSE_1_0.txt or copy at
13 * http://www.boost.org/LICENSE_1_0.txt)
14 **************************************************************************/
15
16 #ifndef STXXL_CONTAINERS_PQ_MERGERS_HEADER
17 #define STXXL_CONTAINERS_PQ_MERGERS_HEADER
18
19 #include <stxxl/bits/containers/pq_helpers.h>
20
21 STXXL_BEGIN_NAMESPACE
22
23 //! \addtogroup stlcontinternals
24 //!
25 //! \{
26
27 /*! \internal
28 */
29 namespace priority_queue_local {
30
31 /////////////////////////////////////////////////////////////////////
32 // auxiliary functions
33
34 // merge length elements from the two sentinel terminated input
35 // sequences source0 and source1 to target
36 // advance source0 and source1 accordingly
37 // require: at least length nonsentinel elements available in source0, source1
38 // require: target may overwrite one of the sources as long as
39 // *(sourcex + length) is before the end of sourcex
40 template <class InputIterator, class OutputIterator,
41 class CompareType, typename SizeType>
merge_iterator(InputIterator & source0,InputIterator & source1,OutputIterator target,SizeType length,CompareType & cmp)42 void merge_iterator(
43 InputIterator& source0,
44 InputIterator& source1,
45 OutputIterator target,
46 SizeType length,
47 CompareType& cmp)
48 {
49 OutputIterator done = target + length;
50
51 while (target != done)
52 {
53 if (cmp(*source0, *source1))
54 {
55 *target = *source1;
56 ++source1;
57 }
58 else
59 {
60 *target = *source0;
61 ++source0;
62 }
63 ++target;
64 }
65 }
66
67 // merge length elements from the three sentinel terminated input
68 // sequences source0, source1 and source2 to target
69 // advance source0, source1 and source2 accordingly
70 // require: at least length nonsentinel elements available in source0, source1 and source2
71 // require: target may overwrite one of the sources as long as
72 // *(sourcex + length) is before the end of sourcex
73 template <class InputIterator, class OutputIterator,
74 class CompareType, typename SizeType>
merge3_iterator(InputIterator & source0,InputIterator & source1,InputIterator & source2,OutputIterator target,SizeType length,CompareType & cmp)75 void merge3_iterator(
76 InputIterator& source0,
77 InputIterator& source1,
78 InputIterator& source2,
79 OutputIterator target,
80 SizeType length,
81 CompareType& cmp)
82 {
83 OutputIterator done = target + length;
84
85 if (cmp(*source1, *source0)) {
86 if (cmp(*source2, *source1)) {
87 goto s012;
88 }
89 else {
90 if (cmp(*source0, *source2)) {
91 goto s201;
92 }
93 else {
94 goto s021;
95 }
96 }
97 } else {
98 if (cmp(*source2, *source1)) {
99 if (cmp(*source2, *source0)) {
100 goto s102;
101 }
102 else {
103 goto s120;
104 }
105 } else {
106 goto s210;
107 }
108 }
109
110 #define Merge3Case(a, b, c) \
111 s ## a ## b ## c : \
112 if (target == done) \
113 return; \
114 *target = *source ## a; \
115 ++target; \
116 ++source ## a; \
117 if (cmp(*source ## b, *source ## a)) \
118 goto s ## a ## b ## c; \
119 if (cmp(*source ## c, *source ## a)) \
120 goto s ## b ## a ## c; \
121 goto s ## b ## c ## a;
122
123 // the order is chosen in such a way that
124 // four of the trailing gotos can be eliminated by the optimizer
125 Merge3Case(0, 1, 2);
126 Merge3Case(1, 2, 0);
127 Merge3Case(2, 0, 1);
128 Merge3Case(1, 0, 2);
129 Merge3Case(0, 2, 1);
130 Merge3Case(2, 1, 0);
131
132 #undef Merge3Case
133 }
134
135 // merge length elements from the four sentinel terminated input
136 // sequences source0, source1, source2 and source3 to target
137 // advance source0, source1, source2 and source3 accordingly
138 // require: at least length nonsentinel elements available in source0, source1, source2 and source3
139 // require: target may overwrite one of the sources as long as
140 // *(sourcex + length) is before the end of sourcex
141 template <class InputIterator, class OutputIterator,
142 class CompareType, typename SizeType>
merge4_iterator(InputIterator & source0,InputIterator & source1,InputIterator & source2,InputIterator & source3,OutputIterator target,SizeType length,CompareType & cmp)143 void merge4_iterator(
144 InputIterator& source0,
145 InputIterator& source1,
146 InputIterator& source2,
147 InputIterator& source3,
148 OutputIterator target, SizeType length, CompareType& cmp)
149 {
150 OutputIterator done = target + length;
151
152 #define StartMerge4(a, b, c, d) \
153 if ((!cmp(*source ## a, *source ## b)) && \
154 (!cmp(*source ## b, *source ## c)) && \
155 (!cmp(*source ## c, *source ## d))) \
156 goto s ## a ## b ## c ## d;
157
158 // b>a c>b d>c
159 // a<b b<c c<d
160 // a<=b b<=c c<=d
161 // !(a>b) !(b>c) !(c>d)
162
163 StartMerge4(0, 1, 2, 3);
164 StartMerge4(1, 2, 3, 0);
165 StartMerge4(2, 3, 0, 1);
166 StartMerge4(3, 0, 1, 2);
167
168 StartMerge4(0, 3, 1, 2);
169 StartMerge4(3, 1, 2, 0);
170 StartMerge4(1, 2, 0, 3);
171 StartMerge4(2, 0, 3, 1);
172
173 StartMerge4(0, 2, 3, 1);
174 StartMerge4(2, 3, 1, 0);
175 StartMerge4(3, 1, 0, 2);
176 StartMerge4(1, 0, 2, 3);
177
178 StartMerge4(2, 0, 1, 3);
179 StartMerge4(0, 1, 3, 2);
180 StartMerge4(1, 3, 2, 0);
181 StartMerge4(3, 2, 0, 1);
182
183 StartMerge4(3, 0, 2, 1);
184 StartMerge4(0, 2, 1, 3);
185 StartMerge4(2, 1, 3, 0);
186 StartMerge4(1, 3, 0, 2);
187
188 StartMerge4(1, 0, 3, 2);
189 StartMerge4(0, 3, 2, 1);
190 StartMerge4(3, 2, 1, 0);
191 StartMerge4(2, 1, 0, 3);
192
193 #define Merge4Case(a, b, c, d) \
194 s ## a ## b ## c ## d : \
195 if (target == done) \
196 return; \
197 *target = *source ## a; \
198 ++target; \
199 ++source ## a; \
200 if (cmp(*source ## c, *source ## a)) \
201 { \
202 if (cmp(*source ## b, *source ## a)) \
203 goto s ## a ## b ## c ## d; \
204 else \
205 goto s ## b ## a ## c ## d; \
206 } \
207 else \
208 { \
209 if (cmp(*source ## d, *source ## a)) \
210 goto s ## b ## c ## a ## d; \
211 else \
212 goto s ## b ## c ## d ## a; \
213 }
214
215 Merge4Case(0, 1, 2, 3);
216 Merge4Case(1, 2, 3, 0);
217 Merge4Case(2, 3, 0, 1);
218 Merge4Case(3, 0, 1, 2);
219
220 Merge4Case(0, 3, 1, 2);
221 Merge4Case(3, 1, 2, 0);
222 Merge4Case(1, 2, 0, 3);
223 Merge4Case(2, 0, 3, 1);
224
225 Merge4Case(0, 2, 3, 1);
226 Merge4Case(2, 3, 1, 0);
227 Merge4Case(3, 1, 0, 2);
228 Merge4Case(1, 0, 2, 3);
229
230 Merge4Case(2, 0, 1, 3);
231 Merge4Case(0, 1, 3, 2);
232 Merge4Case(1, 3, 2, 0);
233 Merge4Case(3, 2, 0, 1);
234
235 Merge4Case(3, 0, 2, 1);
236 Merge4Case(0, 2, 1, 3);
237 Merge4Case(2, 1, 3, 0);
238 Merge4Case(1, 3, 0, 2);
239
240 Merge4Case(1, 0, 3, 2);
241 Merge4Case(0, 3, 2, 1);
242 Merge4Case(3, 2, 1, 0);
243 Merge4Case(2, 1, 0, 3);
244
245 #undef StartMerge4
246 #undef Merge4Case
247 }
248
249 } // namespace priority_queue_local
250
251 //! \}
252
253 STXXL_END_NAMESPACE
254
255 #endif // !STXXL_CONTAINERS_PQ_MERGERS_HEADER
256 // vim: et:ts=4:sw=4
257