Instigate Open Source Documentation

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_INPLACE_MERGE_HPP
00008 #define INSTIGATE_STL_INPLACE_MERGE_HPP
00009 
00059 // headers from this project
00060 #include "concept.hpp"
00061 #include "temporary_buffer.hpp"
00062 #include "_copy.hpp"
00063 #include "_copy_backward.hpp"
00064 #include "_merge.hpp"
00065 #include "_lower_bound.hpp"
00066 #include "_upper_bound.hpp"
00067 #include "_swap.hpp"
00068 #include "_rotate.hpp"
00069 
00070 // headers from other project
00071 #include <generic/base.hpp>
00072 
00073 // headers from standard library
00074 
00075 // forward declaration
00076 namespace instigate {
00077         namespace stl {
00078                 template <typename B>
00079                 inline void inplace_merge(B b, B m, B e);
00080 
00081                 template <typename B, typename BP>
00082                 inline void inplace_merge(B b, B m, B e, BP p);
00083 
00090                 namespace implementation {
00091                 template <typename B1, typename B2, typename D>
00092                 B1 rotate_adaptive(B1 b, B1 m, B1 e, D len1, D l2, B2 buffer,
00093                                  D buffer_size);
00094 
00095                 template <typename B1, typename B2, typename B3>
00096                 B3 merge_backward(B1 b, B1 e, B2 f, B2 l, B3 r); 
00097 
00098                 template <typename B, typename D, typename Pointer>
00099                 void merge_adaptive(B b, B m, B e, D len1, D l2,
00100                                 Pointer buffer, D buffer_size);
00101 
00102                 template <typename B, typename D>
00103                 void merge_without_buffer(B b, B m, B e, D len1, D l2);
00104 
00105                 template <typename B, typename TP, typename D>
00106                 inline void inplace_merge_aux(B b, B m, B e, TP*, D*);
00107 
00108                 template <typename B1, typename B2, typename B3, typename BP>
00109                 B3 merge_backward(B1 b, B1 e, B2 f, B2 l, B3 r, BP p); 
00110 
00111                 template <typename B, typename D, typename Pointer,
00112                          typename BP>
00113                 void merge_adaptive(B b, B m, B e, D len1, D l2,
00114                                 Pointer buffer, D buffer_size, BP p);
00115 
00116                 template <typename B, typename D, typename BP>
00117                 void merge_without_buffer(B b, B m, B e, D len1, D l2, BP p);
00118 
00119                 template <typename B, typename TP, typename D, typename BP>
00120                 inline void inplace_merge_aux(B b, B m, B e, TP*, D*, BP p);
00121                 } // namespace instigate::stl::implementation
00122         } // instigate::stl
00123 }// instigate
00124 
00171 template <typename B>
00172 inline void instigate::stl::inplace_merge(B b, B m, B e)
00173 {
00174         namespace BI = instigate::stl::bidirectional_iterator;
00175         namespace WR = instigate::stl::writable_iterator;
00176         namespace LT = instigate::generic::less_than_comparable;
00177         namespace SP = instigate::stl::single_pass_iterator;
00178         CHECK(BI::requirements<B>);
00179         CHECK(WR::requirements<B>);
00180         typedef typename WR::interface<B>::value_type value_type;
00181         typedef typename SP::interface<B>::difference_type difference_type;
00182         CHECK(LT::requirements<value_type>);
00183         if (equal(b, m) || equal(m, e)) {
00184                 return;
00185         }
00186         value_type* vt = 0;
00187         difference_type* dt = 0;
00188         implementation::inplace_merge_aux(b, m, e, vt, dt);
00189 }
00190 
00195 template <typename B1, typename B2, typename D>
00196 B1 instigate::stl::implementation::rotate_adaptive(B1 b, B1 m, B1 e, D len1, 
00197                 D l2, B2 buffer, D buffer_size) 
00198 {
00199         char k[sizeof(B2)];
00200         B2* buffer_end = 0;
00201         assign(buffer_end, initialize<B2>(k));
00202         if (equal(l2, len1) && !equal(buffer_size, l2)) {
00203                 assert(0 != buffer_end);
00204                 assign(*buffer_end, instigate::stl::copy(m, e, buffer));
00205                 instigate::stl::copy_backward(b, m, e);
00206                 return instigate::stl::copy(buffer, *buffer_end, b);
00207         } else if (!equal(buffer_size, len1)) {
00208                 assert(0 != buffer_end);
00209                 assign(*buffer_end, instigate::stl::copy(b, m, buffer));
00210                 instigate::stl::copy(m, e, b);
00211                 return instigate::stl::copy_backward(buffer, *buffer_end, e);
00212         } else {
00213                 return instigate::stl::rotate(b, m, e);
00214         }
00215 }
00216 
00221 template <typename B1, typename B2, typename B3>
00222 B3 instigate::stl::implementation::merge_backward(B1 b, B1 e, B2 f, B2 l, B3 r) 
00223 {
00224         namespace RI = instigate::stl::readable_iterator;
00225         typedef typename RI::interface<B2>::value_type value_type;
00226         if (equal(b, e)) {
00227                 return instigate::stl::copy_backward(f, l, r);
00228         }
00229         if (equal(f, l)) {
00230                 return instigate::stl::copy_backward(b, e, r);
00231         }
00232         decrement(e);
00233         decrement(l);
00234         while (true) {
00235                 if (less_than(const_dereference(l), const_dereference(e))) {
00236                         decrement(r);
00237                         dereference_assign(r, const_dereference(e));
00238                         if (equal(b, e)) {
00239                                 increment(l);
00240                                 return instigate::stl::copy_backward(f, l, r);
00241                         }
00242                         decrement(e);
00243                 } else {
00244                         decrement(r);
00245                         dereference_assign(r, const_dereference(l));
00246                         if (equal(f, l)) {
00247                                 increment(e);
00248                                 return instigate::stl::copy_backward(b, e, r);
00249                         }
00250                         decrement(l);
00251                 }
00252         }
00253 }
00254 
00255 
00260 template <typename B, typename D, typename Pointer>
00261 void instigate::stl::implementation::merge_adaptive(B b, B m, B e, D len1, 
00262                 D l2, Pointer buffer, D buffer_size) 
00263 {
00264         if (!less_than(l2, len1) && (!less_than(buffer_size, len1))) {
00265                 Pointer buffer_end;
00266                 assign(buffer_end, instigate::stl::copy(b, m, buffer));
00267                 instigate::stl::merge(buffer, buffer_end, m, e, b);
00268         } else if (!less_than(buffer_size, l2)) {
00269                 Pointer buffer_end;
00270                 assign(buffer_end, instigate::stl::copy(m, e, buffer));
00271                 merge_backward(b, m, buffer, buffer_end, e);
00272         } else {
00273                 char k[sizeof(B)];
00274                 B* first_cut = 0;
00275                 assign(first_cut, copy_constructor(k, b));
00276                 assert(0 != first_cut);
00277                 char p[sizeof(B)];
00278                 B* second_cut = 0;
00279                 assign(second_cut, copy_constructor(p, m));
00280                 assert(0 != second_cut);
00281                 D len11 = 0;
00282                 D l22 = 0;
00283                 if (less_than(l2, len1)) {
00284                         assign(len11, len1/2);
00285                         instigate::stl::advance(*first_cut, len11);
00286                         assign(*second_cut, instigate::stl::lower_bound(m, e, 
00287                                                 const_dereference(*first_cut)));
00288                         assign(l22, instigate::stl::distance(m, *second_cut)); 
00289                 } else {
00290                         assign(l22, l2/2);
00291                         instigate::stl::advance(*second_cut, l22);
00292                         assign(*first_cut,
00293                         instigate::stl::upper_bound(b, m, 
00294                                         const_dereference(*second_cut)));
00295                         assign(len11,
00296                         instigate::stl::distance(b, *first_cut));
00297                 }
00298                 char t[sizeof(B)];
00299                 B* new_middle = 0;
00300                 assign(new_middle, copy_constructor(t, 
00301                                 rotate_adaptive(*first_cut, m, *second_cut, 
00302                                 len1 - len11, l22, buffer, buffer_size)));
00303                 assert(0 != new_middle);
00304                 merge_adaptive(b, *first_cut, *new_middle, len11, l22, 
00305                                 buffer, buffer_size);
00306                 merge_adaptive(*new_middle, *second_cut, e, len1 - len11,
00307                                 l2 - l22, buffer, buffer_size);
00308         }
00309 }
00310 
00311 
00316 template <typename B, typename D>
00317 void instigate::stl::implementation::merge_without_buffer(B b, B m, B e, 
00318                 D len1, D l2) 
00319 {
00320         if (0 == len1 || 0 == l2) {
00321                 return;
00322         }
00323         if (2 == len1 + l2) {
00324                 if (less_than(const_dereference(m), const_dereference(b))) {
00325                         instigate::stl::iter_swap(b, m);
00326                 }
00327                 return;
00328         }
00329         char k[sizeof(B)];
00330         B* first_cut = 0;
00331         assign(first_cut, copy_constructor(k, b));
00332         assert(0 != first_cut);
00333         char p[sizeof(B)];
00334         B* second_cut = 0;
00335         assign(second_cut, copy_constructor(p, m));
00336         assert(0 != second_cut);
00337         D len11 = 0;
00338         len1 = 0;
00339         D l22 = 0;
00340         if (less_than(l2, len1)) {
00341                 assign(len11, len1 / 2);
00342                 instigate::stl::advance(first_cut, len11);
00343                 assign(*second_cut, instigate::stl::lower_bound(m, e, 
00344                                         const_dereference(*first_cut)));
00345                 assign(l22, instigate::stl::distance(m, *second_cut));
00346         }
00347         else {
00348                 assign(l22, l2 / 2);
00349                 instigate::stl::advance(*second_cut, l22);
00350                 assign(*first_cut, instigate::stl::upper_bound(b, m, 
00351                                         const_dereference(*second_cut)));
00352                 assign(len11, instigate::stl::distance(b, *first_cut));
00353         }
00354         char t[sizeof(B)];
00355         B* new_middle = 0;
00356         assign(new_middle, copy_constructor(t,instigate::stl::rotate(
00357                                         *first_cut,m, *second_cut)));
00358         assert(0 != new_middle);
00359         merge_without_buffer(b, *first_cut, *new_middle, len11, l22);
00360         merge_without_buffer(*new_middle, *second_cut, e, len1 - len11,
00361                         l2 - l22);
00362 }
00363 
00364 
00369 template <typename B, typename TP, typename D>
00370 inline void instigate::stl::implementation::inplace_merge_aux(B b, B m, B e, 
00371                                                                         TP*, D*)
00372 {
00373         D len1 = 0;
00374         assign(len1, instigate::stl::distance(b, m));
00375         D l2 = 0;
00376         assign(l2, instigate::stl::distance(m, e));
00377         instigate::stl::implementation::Temporary_buffer<B, TP> buf(b, e);
00378         if (buf.begin() == 0) {
00379                 merge_without_buffer(b, m, e, len1, l2);
00380         } else {
00381                 merge_adaptive(b, m, e, len1, l2, buf.begin(), 
00382                                 D(buf.size()));
00383         }
00384 }
00385 
00424 template <typename B, typename BP>
00425 inline void instigate::stl::inplace_merge(B b, B m, B e, BP p)
00426 {
00427         namespace BI = instigate::stl::bidirectional_iterator;
00428         namespace WR = instigate::stl::writable_iterator;
00429         namespace BPI = instigate::stl::binary_predicate;
00430         namespace SP = instigate::stl::single_pass_iterator;
00431         typedef typename WR::interface<B>::value_type value_type;
00432         typedef typename SP::interface<B>::difference_type difference_type;
00433         typedef typename BPI::interface<BP>::first_argument_type 
00434                 first_argument_type;
00435         typedef typename BPI::interface<BP>::second_argument_type 
00436                 second_argument_type;
00437         CHECK(BI::requirements<B>);
00438         CHECK(BPI::requirements<BP>);
00439         CHECK(WR::requirements<B>);
00440         CHECK_CONVERTIBILITY(value_type, first_argument_type);
00441         CHECK_CONVERTIBILITY(value_type, second_argument_type);
00442         if (equal(b, m) || equal(m, e)) {
00443                 return;
00444         }
00445         value_type* vt = 0;
00446         difference_type* dt = 0;
00447         instigate::stl::implementation::inplace_merge_aux(b, m, e, vt, dt, p);
00448 }
00449 
00454 template <typename B1, typename B2, typename B3, typename BP>
00455 B3 instigate::stl::implementation::merge_backward(B1 b, B1 e, B2 f, B2 l, B3 r,
00456                                                         BP p) 
00457 {
00458         namespace RI = instigate::stl::readable_iterator;
00459         typedef typename RI::interface<B2>::value_type value_type;
00460         if (equal(b, e)) {
00461                 return instigate::stl::copy_backward(f, l, r);
00462         }
00463         if (equal(f, l)) {
00464                 return instigate::stl::copy_backward(b, e, r);
00465         }
00466         decrement(e);
00467         decrement(l);
00468         while (true) {
00469                 if (invoke_predicate(p, const_dereference(l), 
00470                                                         const_dereference(e))) 
00471                 {
00472                         decrement(r);
00473                         dereference_assign(r, const_dereference(e));
00474                         if (equal(b, e)) {
00475                                 increment(l);
00476                                 return instigate::stl::copy_backward(f, l, r);
00477                         }
00478                         decrement(e);
00479                 } else {
00480                         decrement(r);
00481                         dereference_assign(r, const_dereference(l));
00482                         if (equal(f, l)) {
00483                                 increment(e);
00484                                 return instigate::stl::copy_backward(b, e, r);
00485                         }
00486                         decrement(l);
00487                 }
00488         }
00489 }
00490 
00495 template <typename B, typename D, typename Pointer, typename BP>
00496 void instigate::stl::implementation::merge_adaptive(B b, B m, B e, D len1, 
00497                 D l2, Pointer buffer, D buffer_size, BP bp) 
00498 {
00499         if (!less_than(l2, len1) && !less_than(buffer_size, len1)){
00500                 Pointer buffer_end;
00501                 assign(buffer_end, instigate::stl::copy(b, m, buffer));
00502                 instigate::stl::merge(buffer, buffer_end, m, e, b, bp);
00503         } else if (!less_than(buffer_size, l2)) {
00504                 Pointer buffer_end;
00505                 assign(buffer_end, instigate::stl::copy(m, e, buffer));
00506                 merge_backward(b, m, buffer, buffer_end, e, bp);
00507         } else {
00508                 char k[sizeof(B)];
00509                 B* first_cut = 0;
00510                 assign(first_cut, copy_constructor(k, b));
00511                 assert(0 != first_cut);
00512                 char p[sizeof(B)];
00513                 B* second_cut = 0;
00514                 assign(second_cut, copy_constructor(p, m));
00515                 assert(0 != second_cut);
00516                 D len11 = 0;
00517                 D l22 = 0;
00518                 if (less_than(l2, len1)) {
00519                         assign(len11, len1/2);
00520                         instigate::stl::advance(*first_cut, len11);
00521                         assign(*second_cut, instigate::stl::lower_bound(m, e, 
00522                                         const_dereference(*first_cut), bp));
00523                         assign(l22, instigate::stl::distance(m, *second_cut)); 
00524                 } else {
00525                         assign(l22, l2/2);
00526                         instigate::stl::advance(*second_cut, l22);
00527                         assign(*first_cut, instigate::stl::upper_bound(b, m, 
00528                                           const_dereference(*second_cut), bp));
00529                         assign(len11, instigate::stl::distance(b, *first_cut));
00530                 }
00531                 char t[sizeof(B)];
00532                 B* new_middle = 0;
00533                 assign(new_middle, copy_constructor(t, 
00534                                 rotate_adaptive(*first_cut, m, *second_cut, 
00535                                 len1 - len11, l22, buffer, buffer_size)));
00536                 assert(0 != new_middle);
00537                 merge_adaptive(b, *first_cut, *new_middle, len11, l22, 
00538                                 buffer, buffer_size, bp);
00539                 merge_adaptive(*new_middle, *second_cut, e, len1 - len11,
00540                                 l2 - l22, buffer, buffer_size, bp);
00541         }
00542 }
00543 
00548 template <typename B, typename D, typename BP>
00549 void instigate::stl::implementation::merge_without_buffer(B b, B m, B e, 
00550                 D len1, D l2, BP p) 
00551 {
00552         if (0 == len1 ||  0 == l2) {
00553                 return;
00554         }
00555         if (2 == len1 + l2) {
00556                 if (invoke_predicate(p, const_dereference(m), 
00557                                                 const_dereference(b)))
00558                 {
00559                         instigate::stl::iter_swap(b, m);
00560                 }
00561                 return;
00562         }
00563         char k[sizeof(B)];
00564         B* first_cut = 0;
00565         assign(first_cut, copy_constructor(k, b));
00566         assert(0 != first_cut);
00567         char u[sizeof(B)];
00568         B* second_cut = 0;
00569         assign(second_cut, copy_constructor(u, m));
00570         assert(0 != second_cut);
00571         D len11 = 0;
00572         D l22 = 0;
00573         if (less_than(l2, len1)) {
00574                 assign(len11, len1 / 2);
00575                 instigate::stl::advance(first_cut, len11);
00576                 assign(*second_cut, instigate::stl::lower_bound(m, e, 
00577                                             const_dereference(*first_cut), p));
00578                 assign(l22, instigate::stl::distance(m, *second_cut));
00579         } else {
00580                 assign(l22, l2 / 2);
00581                 instigate::stl::advance(*second_cut, l22);
00582                 assign(*first_cut, instigate::stl::upper_bound(b, m, 
00583                         const_dereference(*second_cut), p));
00584                 assign(len11, instigate::stl::distance(b, *first_cut));
00585         }
00586         char t[sizeof(B)];
00587         B* new_middle = 0;
00588         assign( new_middle, copy_constructor(t, 
00589                 instigate::stl::rotate(*first_cut, m, *second_cut)));
00590         assert(0 != new_middle);
00591         merge_without_buffer(b, *first_cut, *new_middle, len11, l22, p);
00592         merge_without_buffer(*new_middle, *second_cut, e, len1 - len11,
00593                         l2 - l22, p);
00594 }
00595 
00600 template <typename B, typename TP, typename D, typename BP>
00601 inline void instigate::stl::implementation::inplace_merge_aux(B b, B m, B e, 
00602                                                                 TP*, D*, BP p)
00603 {
00604         D len1;
00605         assign(len1, instigate::stl::distance(b, m));
00606         D l2 = instigate::stl::distance(m, e);
00607         instigate::stl::implementation::Temporary_buffer<B, TP> buf(b, e);
00608         if (buf.begin() == 0) {
00609                 merge_without_buffer(b, m, e, len1, l2, p);
00610         } else {
00611                 merge_adaptive(b, m, e, len1, l2, buf.begin(), 
00612                                 D(buf.size()), p);
00613         }
00614 }
00615 
00616 // vim:et:tabstop=8:shiftwidth=8:cindent:fo=croq:textwidth=80:
00617 
00618 #endif // INSTIGATE_STL_INPLACE_MERGE_HPP
src/stl/_inplace_merge.hpp
