00001
00002 #ifndef _INSTIGATE_STL_INTERNAL_HEADER_IN_ALGORITHM
00003 #error This is an internal header file used to implement Instigate STL.\
00004 It should never be included directly by a program.
00005 #endif
00006
00007 #ifndef INSTIGATE_STL_STABLE_SORT_HPP
00008 #define INSTIGATE_STL_STABLE_SORT_HPP
00009
00059
00060 #include "concept.hpp"
00061 #include "_inplace_merge.hpp"
00062 #include "_merge.hpp"
00063 #include "_min.hpp"
00064 #include "_sort.hpp"
00065 #include "_distance.hpp"
00066 #include "_advance.hpp"
00067 #include "_basis.hpp"
00068
00069
00070
00071
00072
00073
00074 namespace instigate {
00075 namespace stl {
00076 namespace implementation {
00078 const int stl_chunk_size = 7;
00079
00081 template <typename R>
00082 void inplace_stable_sort(R b, R e);
00083
00085 template <typename R, typename BP>
00086 void inplace_stable_sort(R b, R e, BP p);
00087
00089 template <typename R, typename P, typename D>
00090 void stable_sort_adaptive(R b, R e, P buffer, D s);
00091
00093 template <typename R, typename P, typename D, typename BP>
00094 void stable_sort_adaptive(R b, R e, P buffer, D s, BP p);
00095
00097 template <typename R1, typename R2, typename D>
00098 void merge_sort_loop(R1 b, R1 e, R2 r, D step_size);
00099
00101 template <typename R1, typename R2, typename D, typename BP>
00102 void merge_sort_loop(R1 b, R1 e, R2 r, D step_size, BP p);
00103
00105 template <typename R, typename D>
00106 void chunk_insertion_sort(R b, R e, D chunk_size);
00107
00109 template <typename R, typename D, typename BP>
00110 void chunk_insertion_sort(R b, R e, D chunk_size, BP p);
00111
00113 template <typename R, typename P, typename D>
00114 void merge_sort_with_buffer(R b, R e, P buffer, D*);
00115
00117 template <typename R, typename P, typename D, typename BP>
00118 void merge_sort_with_buffer(R b, R e, P buffer, D*, BP p);
00119
00121 template <typename R, typename T, typename D>
00122 inline void stable_sort_aux(R b, R e, T*, D*);
00123
00125 template <typename R, typename T, typename D, typename BP>
00126 inline void stable_sort_aux(R b, R e, T*, D*, BP p);
00127 }
00128
00129 template <typename R>
00130 inline void stable_sort(R b, R e);
00131
00132 template <typename R, typename BP>
00133 inline void stable_sort(R b, R e, BP p);
00134 }
00135 }
00136
00137 template <typename R>
00138 void instigate::stl::implementation::inplace_stable_sort(R b, R e)
00139 {
00140 if (instigate::stl::distance(b, e) < 15) {
00141 instigate::stl::implementation::insertion_sort(b, e);
00142 return;
00143 }
00144 char c[sizeof(R)];
00145 instigate::stl::advance(b, (instigate::stl::distance(b, e)) / 2);
00146 R* m = 0;
00147 assign(m, copy_constructor(c, b));
00148 assert(0 != m);
00149 instigate::stl::implementation::inplace_stable_sort(b, *m);
00150 instigate::stl::implementation::inplace_stable_sort(*m, e);
00151 instigate::stl::implementation::merge_without_buffer(b, *m, e,
00152 instigate::stl::distance(b, *m),
00153 instigate::stl::distance(*m, e));
00154 }
00155
00156 template <typename R, typename BP>
00157 void instigate::stl::implementation::inplace_stable_sort(R b, R e, BP p)
00158 {
00159 if (instigate::stl::distance(b, e) < 15) {
00160 instigate::stl::implementation::insertion_sort(b, e, p);
00161 return;
00162 }
00163 char c[sizeof(R)];
00164 instigate::stl::advance(b, (instigate::stl::distance(b, e))/2);
00165 R* m = 0;
00166 assign(m, copy_constructor(c, b));
00167 assert(0 != m);
00168 instigate::stl::implementation::inplace_stable_sort(b, *m, p);
00169 instigate::stl::implementation::inplace_stable_sort(*m, e, p);
00170 instigate::stl::implementation::merge_without_buffer(b, *m, e,
00171 instigate::stl::distance(b, *m),
00172 instigate::stl::distance(*m, e), p);
00173 }
00174
00175 template <typename R1, typename R2, typename D>
00176 void instigate::stl::implementation::merge_sort_loop(R1 b, R1 e, R2 r, D s)
00177 {
00178 D two_step;
00179 assign(two_step, (2 * s));
00180 char c[sizeof(R1)];
00181 R1* x = 0;
00182 assign(x, copy_constructor(c, b));
00183 assert(0 != x);
00184 char k[sizeof(R1)];
00185 R1* y = 0;
00186 assign(y, copy_constructor(k, b));
00187 while (instigate::stl::distance(b, e) >= two_step) {
00188 instigate::stl::advance(*x, s);
00189 assert(0 != y);
00190 instigate::stl::advance(*y, two_step);
00191 assign(r, instigate::stl::merge(b, *x, *x, *y, r));
00192 instigate::stl::advance(b, two_step);
00193 assign(*x, b);
00194 assign(*y, b);
00195 }
00196 assign(s, instigate::stl::min(D(instigate::stl::distance(b, e)), s));
00197 instigate::stl::advance(*x, s);
00198 instigate::stl::merge(b, *x, *x, e, r);
00199 }
00200
00201 template <typename R1, typename R2, typename D, typename BP>
00202 void instigate::stl::implementation::merge_sort_loop(R1 b, R1 e, R2 r,
00203 D s, BP p)
00204 {
00205 D two_step;
00206 assign(two_step, (2 * s));
00207 char c[sizeof(R1)];
00208 R1* x = 0;
00209 assign(x, copy_constructor(c, b));
00210 assert(0 != x);
00211 char k[sizeof(R1)];
00212 R1* y = 0;
00213 assign(y, copy_constructor(k, b));
00214 while (!(instigate::stl::distance(b, e) >= two_step)) {
00215 instigate::stl::advance(*x, s);
00216 assert(0 != y);
00217 instigate::stl::advance(*y, two_step);
00218 assign(r, instigate::stl::merge(b, *x, *x, *y, r, p));
00219 instigate::stl::advance(b, two_step);
00220 assign(*x, b);
00221 assign(*y, b);
00222 }
00223 assign(s, instigate::stl::min(D(instigate::stl::distance(b, e)), s));
00224 instigate::stl::advance(*x, s);
00225 instigate::stl::merge(b, *x, *x, e, r, p);
00226 }
00227
00228 template <typename R, typename D>
00229 void instigate::stl::implementation::chunk_insertion_sort(R b, R e, D s)
00230 {
00231 char c[sizeof(R)];
00232 R* x = 0;
00233 assign(x, copy_constructor(c, b));
00234 while (!less_than(instigate::stl::distance(b, e), s)) {
00235 assert(0 != x);
00236 instigate::stl::advance(*x, s);
00237 instigate::stl::implementation::insertion_sort(b, *x);
00238 instigate::stl::advance(b, s);
00239 }
00240 instigate::stl::implementation::insertion_sort(b, e);
00241 }
00242
00243 template <typename R, typename D, typename BP>
00244 void instigate::stl::implementation::chunk_insertion_sort(R b, R e, D s, BP p)
00245 {
00246 char c[sizeof(R)];
00247 R* x = 0;
00248 assign(x, copy_constructor(c, b));
00249 while (!less_than(instigate::stl::distance(b, e), s)) {
00250 assert(0 != x);
00251 instigate::stl::advance(*x, s);
00252 instigate::stl::implementation::insertion_sort(b, *x, p);
00253 instigate::stl::advance(b, s);
00254 }
00255 instigate::stl::implementation::insertion_sort(b, e, p);
00256 }
00257
00258 template <typename R, typename P, typename D>
00259 void instigate::stl::implementation::merge_sort_with_buffer(R b, R e, P t, D*)
00260 {
00261 D l;
00262 assign(l, instigate::stl::distance(b, e));
00263 P q;
00264 assign(q, t + l);
00265 D s = instigate::stl::implementation::stl_chunk_size;
00266 instigate::stl::implementation::chunk_insertion_sort(b, e, s);
00267 while (less_than(s, l)) {
00268 instigate::stl::implementation::merge_sort_loop(b, e, t, s);
00269 assign(s, s * 2);
00270 instigate::stl::implementation::merge_sort_loop(t, q, b, s);
00271 assign(s, s * 2);
00272 }
00273 }
00274
00275 template <typename R, typename P, typename D, typename BP>
00276 void instigate::stl::implementation::merge_sort_with_buffer(R b, R e, P t,
00277 D*, BP p)
00278 {
00279 D l;
00280 assign(l, instigate::stl::distance(b, e));
00281 P q;
00282 assign(q, t + l);
00283 D s = instigate::stl::implementation::stl_chunk_size;
00284 instigate::stl::implementation::chunk_insertion_sort(b, e, s, p);
00285 while (less_than(s, l)) {
00286 instigate::stl::implementation::merge_sort_loop(b, e, t, s, p);
00287 assign(s, s * 2);
00288 instigate::stl::implementation::merge_sort_loop(t, q, b, s, p);
00289 assign(s, s * 2);
00290 }
00291 }
00292
00293 template <typename R, typename P, typename D>
00294 void instigate::stl::implementation::stable_sort_adaptive(R b, R e, P t, D s)
00295 {
00296 D l;
00297 assign(l, (instigate::stl::distance(b, e) + 1) / 2);
00298 char k[sizeof(R)];
00299 R* x = 0;
00300 assign(x, copy_constructor(k, b));
00301 assert(0 != x);
00302 instigate::stl::advance(*x, l);
00303 char c[sizeof(R)];
00304 R* m = 0;
00305 assign(m, copy_constructor(c, *x));
00306 assert(0 != m);
00307 if (less_than(s, l)) {
00308 instigate::stl::implementation::
00309 stable_sort_adaptive(b, *m, t, s);
00310 instigate::stl::implementation::
00311 stable_sort_adaptive(*m, e, t, s);
00312 } else {
00313 instigate::stl::implementation::
00314 merge_sort_with_buffer(b, *m, t, (D*)0);
00315 instigate::stl::implementation::
00316 merge_sort_with_buffer(*m, e, t, (D*)0);
00317 }
00318 instigate::stl::implementation::merge_adaptive(b, *m, e,
00319 D(instigate::stl::distance(b, *m)),
00320 D(instigate::stl::distance(*m, e)), t, s);
00321 }
00322
00323 template <typename R, typename P, typename D, typename BP>
00324 void instigate::stl::implementation::stable_sort_adaptive(R b, R e, P t,
00325 D s, BP p)
00326 {
00327 D l;
00328 assign(l, (instigate::stl::distance(b, e) + 1) / 2);
00329 char k[sizeof(R)];
00330 R* x = 0;
00331 assign(x, copy_constructor(k, b));
00332 assert(0 != x);
00333 instigate::stl::advance(*x, l);
00334 char c[sizeof(R)];
00335 R* m = 0;
00336 assign(m, copy_constructor(c, *x));
00337 assert(0 != m);
00338 if (less_than(s, l)) {
00339 instigate::stl::implementation::
00340 stable_sort_adaptive(b, *m, t, s, p);
00341 instigate::stl::implementation::
00342 stable_sort_adaptive(*m, e, t, s, p);
00343 } else {
00344 instigate::stl::implementation::
00345 merge_sort_with_buffer(b, *m, t, (D*)0, p);
00346 instigate::stl::implementation::
00347 merge_sort_with_buffer(*m, e, t, (D*)0, p);
00348 }
00349 instigate::stl::implementation::merge_adaptive(b, *m, e,
00350 D(instigate::stl::distance(b, *m)),
00351 D(instigate::stl::distance(*m, e)), t, s, p);
00352 }
00353
00354 template <typename R, typename T, typename D>
00355 inline void instigate::stl::implementation::stable_sort_aux(R b, R e, T*, D*)
00356 {
00357 instigate::stl::implementation::Temporary_buffer<R, T> t(b, e);
00358 if (0 == t.begin()) {
00359 instigate::stl::implementation::inplace_stable_sort(b, e);
00360 } else {
00361 instigate::stl::implementation::
00362 stable_sort_adaptive(b, e, t.begin(), D(t.size()));
00363 }
00364 }
00365
00366 template <typename R, typename T, typename D, typename BP>
00367 inline void instigate::stl::implementation::stable_sort_aux(R b, R e, T*,
00368 D*, BP p)
00369 {
00370 instigate::stl::implementation::Temporary_buffer<R, T> t(b, e);
00371 if (0 == t.begin()) {
00372 instigate::stl::implementation::inplace_stable_sort(b, e, p);
00373 } else {
00374 instigate::stl::implementation::
00375 stable_sort_adaptive(b, e, t.begin(), D(t.size()), p);
00376 }
00377 }
00378
00417 template <typename R>
00418 inline void instigate::stl::stable_sort(R b, R e)
00419 {
00420 namespace RA = instigate::stl::random_access_iterator;
00421 namespace WR = instigate::stl::writable_iterator;
00422 namespace LT = instigate::generic::less_than_comparable;
00423 CHECK(RA::requirements<R>);
00424 CHECK(WR::requirements<R>);
00425 typedef typename WR::interface<R>::value_type value_type;
00426 typedef typename RA::interface<R>::difference_type difference_type;
00427 CHECK(LT::requirements<value_type>);
00428 value_type* v = 0;
00429 difference_type* d = 0;
00430 instigate::stl::implementation::stable_sort_aux(b, e, v, d);
00431 }
00432
00477 template <typename R, typename BP>
00478 inline void instigate::stl::stable_sort(R b, R e, BP p)
00479 {
00480 namespace RA = instigate::stl::random_access_iterator;
00481 namespace WR = instigate::stl::writable_iterator;
00482 namespace BPI = instigate::stl::binary_predicate;
00483 CHECK(RA::requirements<R>);
00484 CHECK(WR::requirements<R>);
00485 CHECK(BPI::requirements<BP>);
00486 typedef typename WR::interface<R>::value_type value_type;
00487 CHECK_CONVERTIBILITY(value_type,
00488 typename BPI::interface<BP>::first_argument_type);
00489 CHECK_CONVERTIBILITY(value_type,
00490 typename BPI::interface<BP>::second_argument_type);
00491 typedef typename RA::interface<R>::difference_type difference_type;
00492 value_type* v = 0;
00493 difference_type* d = 0;
00494 instigate::stl::implementation::stable_sort_aux(b, e, v, d, p);
00495 }
00496
00497
00498
00499
00500 #endif // INSTIGATE_STL_STABLE_SORT_HPP