Stxxl  1.3.2
pq_mergers.h
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 <[email protected]>
7  * Copyright (C) 2003, 2004, 2007 Roman Dementiev <[email protected]>
8  * Copyright (C) 2007-2009 Johannes Singler <[email protected]>
9  * Copyright (C) 2007, 2008 Andreas Beckmann <[email protected]>
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_PQ_MERGERS_HEADER
17 #define STXXL_PQ_MERGERS_HEADER
18 
19 __STXXL_BEGIN_NAMESPACE
20 
24 
27 namespace priority_queue_local
28 {
30 // auxiliary functions
31 
32 // merge length elements from the two sentinel terminated input
33 // sequences source0 and source1 to target
34 // advance source0 and source1 accordingly
35 // require: at least length nonsentinel elements available in source0, source1
36 // require: target may overwrite one of the sources as long as
37 // *(sourcex + length) is before the end of sourcex
38  template <class InputIterator, class OutputIterator, class Cmp_>
39  void merge_iterator(
40  InputIterator & source0,
41  InputIterator & source1,
42  OutputIterator target,
43  unsigned_type length,
44  Cmp_ cmp)
45  {
46  OutputIterator done = target + length;
47 
48  while (target != done)
49  {
50  if (cmp(*source0, *source1))
51  {
52  *target = *source1;
53  ++source1;
54  }
55  else
56  {
57  *target = *source0;
58  ++source0;
59  }
60  ++target;
61  }
62  }
63 
64 // merge length elements from the three sentinel terminated input
65 // sequences source0, source1 and source2 to target
66 // advance source0, source1 and source2 accordingly
67 // require: at least length nonsentinel elements available in source0, source1 and source2
68 // require: target may overwrite one of the sources as long as
69 // *(sourcex + length) is before the end of sourcex
70  template <class InputIterator, class OutputIterator, class Cmp_>
71  void merge3_iterator(
72  InputIterator & source0,
73  InputIterator & source1,
74  InputIterator & source2,
75  OutputIterator target,
76  unsigned_type length,
77  Cmp_ cmp)
78  {
79  OutputIterator done = target + length;
80 
81  if (cmp(*source1, *source0)) {
82  if (cmp(*source2, *source1)) {
83  goto s012;
84  }
85  else {
86  if (cmp(*source0, *source2)) {
87  goto s201;
88  }
89  else {
90  goto s021;
91  }
92  }
93  } else {
94  if (cmp(*source2, *source1)) {
95  if (cmp(*source2, *source0)) {
96  goto s102;
97  }
98  else {
99  goto s120;
100  }
101  } else {
102  goto s210;
103  }
104  }
105 
106 #define Merge3Case(a, b, c) \
107  s ## a ## b ## c : \
108  if (target == done) \
109  return; \
110  *target = *source ## a; \
111  ++target; \
112  ++source ## a; \
113  if (cmp(*source ## b, *source ## a)) \
114  goto s ## a ## b ## c; \
115  if (cmp(*source ## c, *source ## a)) \
116  goto s ## b ## a ## c; \
117  goto s ## b ## c ## a;
118 
119  // the order is chosen in such a way that
120  // four of the trailing gotos can be eliminated by the optimizer
121  Merge3Case(0, 1, 2);
122  Merge3Case(1, 2, 0);
123  Merge3Case(2, 0, 1);
124  Merge3Case(1, 0, 2);
125  Merge3Case(0, 2, 1);
126  Merge3Case(2, 1, 0);
127 
128 #undef Merge3Case
129  }
130 
131 
132 // merge length elements from the four sentinel terminated input
133 // sequences source0, source1, source2 and source3 to target
134 // advance source0, source1, source2 and source3 accordingly
135 // require: at least length nonsentinel elements available in source0, source1, source2 and source3
136 // require: target may overwrite one of the sources as long as
137 // *(sourcex + length) is before the end of sourcex
138  template <class InputIterator, class OutputIterator, class Cmp_>
139  void merge4_iterator(
140  InputIterator & source0,
141  InputIterator & source1,
142  InputIterator & source2,
143  InputIterator & source3,
144  OutputIterator target, unsigned_type length, Cmp_ cmp)
145  {
146  OutputIterator done = target + length;
147 
148 #define StartMerge4(a, b, c, d) \
149  if ((!cmp(*source ## a, *source ## b)) && (!cmp(*source ## b, *source ## c)) && (!cmp(*source ## c, *source ## d))) \
150  goto s ## a ## b ## c ## d;
151 
152  // b>a c>b d>c
153  // a<b b<c c<d
154  // a<=b b<=c c<=d
155  // !(a>b) !(b>c) !(c>d)
156 
157  StartMerge4(0, 1, 2, 3);
158  StartMerge4(1, 2, 3, 0);
159  StartMerge4(2, 3, 0, 1);
160  StartMerge4(3, 0, 1, 2);
161 
162  StartMerge4(0, 3, 1, 2);
163  StartMerge4(3, 1, 2, 0);
164  StartMerge4(1, 2, 0, 3);
165  StartMerge4(2, 0, 3, 1);
166 
167  StartMerge4(0, 2, 3, 1);
168  StartMerge4(2, 3, 1, 0);
169  StartMerge4(3, 1, 0, 2);
170  StartMerge4(1, 0, 2, 3);
171 
172  StartMerge4(2, 0, 1, 3);
173  StartMerge4(0, 1, 3, 2);
174  StartMerge4(1, 3, 2, 0);
175  StartMerge4(3, 2, 0, 1);
176 
177  StartMerge4(3, 0, 2, 1);
178  StartMerge4(0, 2, 1, 3);
179  StartMerge4(2, 1, 3, 0);
180  StartMerge4(1, 3, 0, 2);
181 
182  StartMerge4(1, 0, 3, 2);
183  StartMerge4(0, 3, 2, 1);
184  StartMerge4(3, 2, 1, 0);
185  StartMerge4(2, 1, 0, 3);
186 
187 #define Merge4Case(a, b, c, d) \
188  s ## a ## b ## c ## d : \
189  if (target == done) \
190  return; \
191  *target = *source ## a; \
192  ++target; \
193  ++source ## a; \
194  if (cmp(*source ## c, *source ## a)) \
195  { \
196  if (cmp(*source ## b, *source ## a)) \
197  goto s ## a ## b ## c ## d; \
198  else \
199  goto s ## b ## a ## c ## d; \
200  } \
201  else \
202  { \
203  if (cmp(*source ## d, *source ## a)) \
204  goto s ## b ## c ## a ## d; \
205  else \
206  goto s ## b ## c ## d ## a; \
207  }
208 
209  Merge4Case(0, 1, 2, 3);
210  Merge4Case(1, 2, 3, 0);
211  Merge4Case(2, 3, 0, 1);
212  Merge4Case(3, 0, 1, 2);
213 
214  Merge4Case(0, 3, 1, 2);
215  Merge4Case(3, 1, 2, 0);
216  Merge4Case(1, 2, 0, 3);
217  Merge4Case(2, 0, 3, 1);
218 
219  Merge4Case(0, 2, 3, 1);
220  Merge4Case(2, 3, 1, 0);
221  Merge4Case(3, 1, 0, 2);
222  Merge4Case(1, 0, 2, 3);
223 
224  Merge4Case(2, 0, 1, 3);
225  Merge4Case(0, 1, 3, 2);
226  Merge4Case(1, 3, 2, 0);
227  Merge4Case(3, 2, 0, 1);
228 
229  Merge4Case(3, 0, 2, 1);
230  Merge4Case(0, 2, 1, 3);
231  Merge4Case(2, 1, 3, 0);
232  Merge4Case(1, 3, 0, 2);
233 
234  Merge4Case(1, 0, 3, 2);
235  Merge4Case(0, 3, 2, 1);
236  Merge4Case(3, 2, 1, 0);
237  Merge4Case(2, 1, 0, 3);
238 
239 #undef StartMerge4
240 #undef Merge4Case
241  }
242 } //priority_queue_local
243 
245 
246 __STXXL_END_NAMESPACE
247 
248 #endif // !STXXL_PQ_MERGERS_HEADER
249 // vim: et:ts=4:sw=4
Generated by   doxygen 1.8.5