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_SORT_HPP
00008 #define INSTIGATE_STL_SORT_HPP
00009
00058
00059 #include "concept.hpp"
00060 #include "_basis.hpp"
00061 #include "_copy_backward.hpp"
00062 #include "_partial_sort.hpp"
00063 #include "_distance.hpp"
00064 #include "_stable_partition.hpp"
00065
00066
00067 #include <generic/base.hpp>
00068
00069
00070 #include <algorithm>
00071
00072
00073 namespace instigate {
00074 namespace stl {
00075 template <typename R>
00076 void sort(R, R);
00077
00078 template <typename R, typename C>
00079 void sort(R, R, C);
00080
00087 namespace implementation {
00089 const int stl_threshold = 16;
00090
00092 template <typename R, typename T>
00093 void unguarded_linear_insert(R, T);
00094
00096 template <typename R, typename T, typename C>
00097 void unguarded_linear_insert(R, T, C);
00098
00100 template <typename R>
00101 void linear_insert(R, R);
00102
00104 template <typename R, typename C>
00105 void linear_insert(R, R, C);
00106
00108 template <typename R>
00109 void insertion_sort(R, R);
00110
00112 template <typename R, typename C>
00113 void insertion_sort(R, R, C);
00114
00116 template <typename R>
00117 void unguarded_insertion_sort(R, R);
00118
00120 template <typename R, typename C>
00121 void unguarded_insertion_sort(R, R, C);
00122
00124 template <typename R>
00125 void final_insertion_sort(R, R);
00126
00128 template <typename R, typename C>
00129 void final_insertion_sort(R, R, C);
00130
00132 template <typename S>
00133 S lg(S);
00134
00136 template <typename R, typename S>
00137 void introsort_loop(R, R, S);
00138
00140 template <typename R, typename S, typename C>
00141 void introsort_loop(R, R, S, C);
00142
00143 }
00144 }
00145 }
00146
00167 template <typename R>
00168 void instigate::stl::sort(R b, R e)
00169 {
00170 CHECK(stl::random_access_iterator::requirements<R>);
00171 CHECK(stl::writable_iterator::requirements<R>);
00172 CHECK(stl::lvalue_iterator::requirements<R>);
00173 CHECK(instigate::generic::less_than_comparable::requirements<R>);
00174 CHECK(instigate::generic::less_than_comparable::requirements<typename
00175 instigate::stl::writable_iterator::interface<R>::value_type>);
00176 if (!equal(b, e)) {
00177 implementation::introsort_loop(b, e,
00178 implementation::lg(instigate::stl::distance(b, e) * 2));
00179 implementation::final_insertion_sort(b, e);
00180 }
00181 }
00182
00200 template <typename R, typename C>
00201 void instigate::stl::sort(R b, R e, C c)
00202 {
00203 CHECK(stl::random_access_iterator::requirements<R>);
00204 CHECK(stl::writable_iterator::requirements<R>);
00205 CHECK(stl::lvalue_iterator::requirements<R>);
00206 CHECK(instigate::generic::less_than_comparable::requirements<R>);
00207 CHECK(stl::binary_predicate::requirements<C>);
00208 if (!equal(b, e)) {
00209 implementation::introsort_loop(b, e,
00210 implementation::lg(stl::distance(b, e) * 2), c);
00211 implementation::final_insertion_sort(b, e, c);
00212 }
00213 }
00214
00215 template <typename R, typename T>
00216 void instigate::stl::implementation::unguarded_linear_insert(R e, T v)
00217 {
00218 char ptr[sizeof(R)];
00219 R* n = 0;
00220 assign(n, copy_constructor(ptr, e));
00221 assert(0 != n);
00222 decrement(*n);
00223 while (less_than(v, const_dereference(*n))) {
00224 dereference_assign(e, dereference(*n));
00225 assign(e, *n);
00226 decrement(*n);
00227 }
00228 dereference_assign(e, v);
00229 }
00230
00231 template <typename R, typename T, typename C>
00232 void instigate::stl::implementation::unguarded_linear_insert(R e, T v, C c)
00233 {
00234 char ptr[sizeof(R)];
00235 R* n = 0;
00236 assign(n, copy_constructor(ptr, e));
00237 assert(0 != n);
00238 decrement(*n);
00239 while (invoke_predicate(c, v, const_dereference(*n))) {
00240 dereference_assign(e, const_dereference(*n));
00241 assign(e, *n);
00242 decrement(*n);
00243 }
00244 dereference_assign(e, v);
00245 }
00246
00247 template <typename R>
00248 void instigate::stl::implementation::linear_insert(R b, R e)
00249 {
00250 typename stl::lvalue_iterator::interface<R>::value_type v;
00251 assign(v, const_dereference(e));
00252 char buf[sizeof(R)];
00253 R* buf_p = 0;
00254 assign(buf_p, copy_constructor(buf, e));
00255 assert(0 != buf_p);
00256 increment(*buf_p);
00257 if (less_than(v, const_dereference(b))) {
00258 stl::copy_backward(b, e, *buf_p);
00259 dereference_assign(b, v);
00260 } else {
00261 unguarded_linear_insert(e, v);
00262 }
00263 }
00264
00265 template <typename R, typename C>
00266 inline void instigate::stl::implementation::linear_insert(R b, R e, C c)
00267 {
00268 typename instigate::stl::lvalue_iterator::interface<R>::value_type v;
00269 assign(v, dereference(e));
00270 char buf[sizeof(R)];
00271 R* buf_p = 0;
00272 assign(buf_p, copy_constructor(buf, e));
00273 assert(0 != buf_p);
00274 increment(*buf_p);
00275 if (invoke_predicate(c, v, const_dereference(b))) {
00276 stl::copy_backward(b, e, *buf_p);
00277 dereference_assign(b, v);
00278 } else {
00279 unguarded_linear_insert(e, v, c);
00280 }
00281 }
00282
00283 template <typename R>
00284 void instigate::stl::implementation::insertion_sort(R b, R e)
00285 {
00286 if (equal(b, e)) {
00287 return;
00288 }
00289 char ptr[sizeof(R)];
00290 R* i = 0;
00291 assign(i, copy_constructor(ptr, b));
00292 assert(0 != i);
00293 increment(*i);
00294 for ( ; !equal(*i, e); increment(*i)) {
00295 linear_insert(b, *i);
00296 }
00297 }
00298
00299 template <typename R, typename C>
00300 void instigate::stl::implementation::insertion_sort(R b, R e, C c)
00301 {
00302 if (equal(b, e)) {
00303 return;
00304 }
00305 char ptr[sizeof(R)];
00306 R* i = 0;
00307 assign(i, copy_constructor(ptr, b));
00308 assert(0 != i);
00309 increment(*i);
00310 for (; !equal(*i, e); increment(*i)) {
00311 linear_insert(b, *i, c);
00312 }
00313 }
00314
00315 template <typename R>
00316 void instigate::stl::implementation::unguarded_insertion_sort(R b, R e)
00317 {
00318 char ptr[sizeof(R)];
00319 R* i = 0;
00320 assign(i, copy_constructor(ptr, b));
00321 assert(0 != i);
00322 for (; !equal(*i, e); increment(*i)) {
00323 unguarded_linear_insert(*i, dereference(*i));
00324 }
00325 }
00326
00327 template <typename R, typename C>
00328 void instigate::stl::implementation::unguarded_insertion_sort(R b, R e, C c)
00329 {
00330 char ptr[sizeof(R)];
00331 R* i = 0;
00332 assign(i, copy_constructor(ptr, b));
00333 assert(0 != i);
00334 for ( ; !equal(*i, e); increment(*i)) {
00335 unguarded_linear_insert(*i, dereference(*i), c);
00336 }
00337 }
00338
00339 template <typename R>
00340 void instigate::stl::implementation::final_insertion_sort(R b, R e)
00341 {
00342 typename stl::single_pass_iterator::interface<R>::difference_type a;
00343 a = stl_threshold;
00344 char ptr[sizeof(R)];
00345 R* i = 0;
00346 assign(i, copy_constructor(ptr, b));
00347 assert(0 != i);
00348 stl::advance(*i, a);
00349 if (stl::distance(b, e) > a) {
00350 insertion_sort(b, *i);
00351 unguarded_insertion_sort(*i, e);
00352 } else {
00353 insertion_sort(b, e);
00354 }
00355 }
00356
00357 template <typename R, typename C>
00358 void instigate::stl::implementation::final_insertion_sort(R b, R e, C c)
00359 {
00360 typename stl::single_pass_iterator::interface<R>::difference_type a;
00361 a = stl_threshold;
00362 char ptr[sizeof(R)];
00363 R* i = 0;
00364 assign(i, copy_constructor(ptr, b));
00365 assert(0 != i);
00366 std::advance(*i, a);
00367 if (std::distance(b, e) > a) {
00368 insertion_sort(b, *i, c);
00369 unguarded_insertion_sort(*i, e, c);
00370 } else {
00371 insertion_sort(b, e, c);
00372 }
00373 }
00374
00375 template <typename S>
00376 inline S instigate::stl::implementation::lg(S n)
00377 {
00378 S k = 0;
00379 for (; n != 1; n >>= 1) {
00380 ++k;
00381 }
00382 return k;
00383 }
00384
00385 template <typename R, typename S>
00386 void instigate::stl::implementation::introsort_loop(R b, R e, S dl)
00387 {
00388 typedef typename instigate::stl::lvalue_iterator::
00389 interface<R>::value_type value_type;
00390 char ptr[sizeof(R)];
00391 char buf[sizeof(R)];
00392 char buf2[sizeof(R)];
00393 R* buf_p = 0;
00394 R* buf_p2 = 0;
00395 S a = 0;
00396 R* cut = 0;
00397 assign(cut, initialize<R>(ptr));
00398 while (stl::distance(b, e) > stl_threshold) {
00399 if(equal(dl, a)) {
00400 stl::partial_sort(b, e, e);
00401 return;
00402 }
00403 --dl;
00404 assign(buf_p, copy_constructor(buf, e));
00405 assert(0 != buf_p);
00406 decrement(*buf_p);
00407 assign(buf_p2, copy_constructor(buf2, b));
00408 assert(0 != buf_p2);
00409 stl::advance(*buf_p2, stl::distance(b, e) / 2);
00410 assert(0 != cut);
00411 assign(*cut, unguarded_partition(b, e,
00412 value_type(std::__median(dereference(b),
00413 dereference(*buf_p2),
00414 dereference(*buf_p)))));
00415 introsort_loop(*cut, e, dl);
00416 assign(e, *cut);
00417 }
00418 }
00419
00420 template <typename R, typename S, typename C>
00421 void instigate::stl::implementation::introsort_loop(R b, R e, S dl, C c)
00422 {
00423 typedef typename instigate::stl::lvalue_iterator::
00424 interface<R>::value_type value_type;
00425 char ptr[sizeof(R)];
00426 char buf[sizeof(R)];
00427 char buf2[sizeof(R)];
00428 R* buf_p = 0;
00429 R* buf_p2 = 0;
00430 S a = 0;
00431 R* cut = 0;
00432 assign(cut, initialize<R>(ptr));
00433 while (instigate::stl::distance(b, e) > stl_threshold) {
00434 if (equal(dl, a)) {
00435 instigate::stl::partial_sort(b, e, e, c);
00436 return;
00437 }
00438 --dl;
00439 assign(buf_p, copy_constructor(buf, e));
00440 assert(0 != buf_p);
00441 decrement(*buf_p);
00442 assign(buf_p2, copy_constructor(buf2, b));
00443 assert(0 != buf_p2);
00444 stl::advance(*buf_p2, stl::distance(b, e) / 2);
00445 assert(0 != cut);
00446 assign(*cut, unguarded_partition(b, e,
00447 value_type(std::__median(dereference(b),
00448 dereference(*buf_p2),
00449 dereference(*buf_p))), c));
00450
00451 introsort_loop(*cut, e, dl, c);
00452 assign(e, *cut);
00453 }
00454 }
00455
00456
00457
00458 #endif // INSTIGATE_STL_SORT_HPP