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_PARTITION_HPP
00008 #define INSTIGATE_STL_STABLE_PARTITION_HPP
00009
00059
00060 #include "concept.hpp"
00061 #include "_basis.hpp"
00062 #include "_advance.hpp"
00063 #include "_rotate.hpp"
00064 #include "_copy.hpp"
00065 #include "_iter_swap.hpp"
00066
00067
00068
00069
00070
00071
00072 namespace instigate {
00073 namespace stl {
00074 namespace implementation {
00075 template <typename F, typename P, typename Dist>
00076 F inplace_stable_partition(F b, F e, P p, Dist l);
00077 template <typename F, typename Ptr, typename P, typename Dist>
00078 F stable_partition_adaptive(F b, F e, P p, Dist l,
00079 Ptr buff, Dist buff_size );
00080 template <typename F, typename P, typename T, typename Dist>
00081 inline F stable_partition_aux(F b, F e, P p, T*, Dist* );
00082 template <typename R, typename T>
00083 R unguarded_partition(R b, R e, T p);
00084 template <typename R, typename T, typename C>
00085 R unguarded_partition(R b, R e, T p, C c);
00086 }
00087 template <typename F, typename P>
00088 inline F stable_partition(F b, F e, P p);
00089 }
00090 }
00091
00133 template <typename F, typename P>
00134 inline F instigate::stl::stable_partition(F b, F e, P p)
00135 {
00136 namespace FI = instigate::stl::forward_iterator;
00137 typedef typename instigate::stl::lvalue_iterator::interface<F>::
00138 value_type value_type;
00139 typedef typename FI::interface<F>::difference_type difference_type;
00140 CHECK(FI::requirements<F>);
00141 CHECK(instigate::stl::lvalue_iterator::requirements<F>);
00142 CHECK(instigate::stl::unary_predicate::requirements<P>);
00143 value_type* v = 0;
00144 difference_type* d = 0;
00145 if (equal(b, e)) {
00146 return b;
00147 } else {
00148 return instigate::stl::implementation::
00149 stable_partition_aux(b, e, p, v, d);
00150 }
00151
00152 }
00153
00158 template <typename F, typename P, typename Dist>
00159 F instigate::stl::implementation::
00160 inplace_stable_partition(F b, F e, P p, Dist l)
00161 {
00162 if (1 == l) {
00163 return invoke_predicate(p, dereference(b)) ? e : b;
00164 }
00165 char k[sizeof(F)];
00166 F* middle = 0;
00167 assign(middle, copy_constructor(k, b));
00168 typedef typename stl::single_pass_iterator::interface<F*>::
00169 difference_type DT;
00170 instigate::stl::advance(middle, (DT)l/2);
00171 assert(0 != middle);
00172 return instigate::stl::rotate(
00173 inplace_stable_partition(b, *middle, p, l/2), *middle,
00174 inplace_stable_partition(*middle, e, p, l - l/2));
00175 }
00176
00181 template <typename F, typename Ptr, typename P, typename Dist>
00182 F instigate::stl::implementation::stable_partition_adaptive(F b, F e, P p,
00183 Dist l, Ptr buff, Dist buff_size )
00184 {
00185 if (!less_than(buff_size, l)) {
00186 char k[sizeof(F)];
00187 F* result1 = 0;
00188 assign(result1, copy_constructor(k, b));
00189 assert(0 != result1);
00190 Ptr result2 = buff;
00191 for (; !equal(b, e); increment(b)) {
00192 if (invoke_predicate(p, dereference(b))) {
00193 assign(dereference(*result1), dereference(b));
00194 increment(*result1);
00195 } else {
00196 assign(*result2, dereference(b));
00197 increment(result2);
00198 }
00199 }
00200 instigate::stl::copy(buff, result2, *result1);
00201 return *result1;
00202 } else {
00203 char k[sizeof(F)];
00204 F* middle = 0;
00205 assign(middle, copy_constructor(k, b));
00206 assert(0 != middle);
00207 typedef typename stl::single_pass_iterator::interface<F>::
00208 difference_type DT;
00209 instigate::stl::advance(*middle, (DT)l/2);
00210 return instigate::stl::rotate(stable_partition_adaptive(b,
00211 *middle, p, l/2, buff, buff_size), *middle,
00212 stable_partition_adaptive(*middle, e,
00213 p, l - l/2, buff, buff_size ));
00214 }
00215 }
00216
00220 template <typename F, typename P, typename T, typename Dist>
00221 inline F instigate::stl::implementation::
00222 stable_partition_aux(F b, F e, P p, T*, Dist* )
00223 {
00224 instigate::stl::implementation::Temporary_buffer<F, T> buf(b, e);
00225 if (0 < buf.size()) {
00226 return instigate::stl::implementation::
00227 stable_partition_adaptive(b, e, p,
00228 buf.requested_size(),
00229 buf.begin(), buf.size());
00230 } else {
00231 return instigate::stl::implementation::
00232 inplace_stable_partition(b, e, p,
00233 Dist(buf.requested_size()));
00234 }
00235 }
00236
00262 template <typename R, typename T>
00263 R instigate::stl::implementation::unguarded_partition(R b, R e, T p)
00264 {
00265 namespace RA = instigate::stl::random_access_iterator;
00266 typedef typename instigate::stl::lvalue_iterator::interface<R>::
00267 value_type value_type;
00268 CHECK(RA::requirements<R>);
00269 while (true) {
00270 while (less_than(dereference(b), p)) {
00271 increment(b);
00272 }
00273 decrement(e);
00274 while (less_than(p, dereference(e))) {
00275 decrement(e);
00276 }
00277 if (!less_than(b, e)) {
00278 return b;
00279 }
00280 instigate::stl::iter_swap(b, e);
00281 increment(b);
00282 }
00283 }
00284
00317 template <typename R, typename T, typename C>
00318 R instigate::stl::implementation::unguarded_partition(R b, R e, T p, C c)
00319 {
00320 namespace RA = instigate::stl::random_access_iterator;
00321 typedef typename instigate::stl::lvalue_iterator::interface<R>::
00322 value_type value_type;
00323 CHECK(RA::requirements<R>);
00324 while (true) {
00325 while (invoke_predicate(c, dereference(b), p)) {
00326 increment(b);
00327 }
00328 decrement(e);
00329 while (invoke_predicate(c, p, dereference(e))) {
00330 decrement(e);
00331 }
00332 if (!less_than(b, e)) {
00333 return b;
00334 }
00335 instigate::stl::iter_swap(b, e);
00336 increment(b);
00337 }
00338 }
00339
00340
00341
00342 #endif // INSTIGATE_STL_STABLE_PARTITION_HPP