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_PARTITION_HPP
00008 #define INSTIGATE_STL_PARTITION_HPP
00009
00059
00060 #include "_basis.hpp"
00061 #include "concept.hpp"
00062 #include "_swap.hpp"
00063 #include "_iter_swap.hpp"
00064
00065
00066
00067
00068
00069
00070 namespace instigate {
00071 namespace stl {
00072 namespace implementation {
00073 template <typename F, typename P>
00074 F partition_aux(F b, F e, P p,
00075 instigate::stl::forward_iterator::tag);
00076 template <typename B, typename P>
00077 B partition_aux(B b, B e, P p,
00078 instigate::stl::bidirectional_iterator::tag);
00079 }
00080 template <typename F, typename P>
00081 F partition(F b, F e, P p);
00082 }
00083 }
00084
00118 template <typename F, typename P>
00119 F instigate::stl::partition(F b, F e, P p)
00120 {
00121 CHECK(instigate::stl::forward_iterator::requirements<F>);
00122 CHECK(instigate::stl::lvalue_iterator::requirements<F>);
00123 CHECK(instigate::stl::unary_predicate::requirements<P>);
00124 typedef typename instigate::stl::forward_iterator::interface<F>::
00125 iterator_category category;
00126 return instigate::stl::implementation::
00127 partition_aux(b, e, p, category());
00128 }
00129
00134 template <typename F, typename P>
00135 F instigate::stl::implementation::partition_aux(F b, F e, P p,
00136 instigate::stl::forward_iterator::tag)
00137 {
00138 if (equal(b, e)) {
00139 return b;
00140 }
00141 while (invoke_predicate(p, dereference(b))) {
00142 increment(b);
00143 if (equal(b, e)) {
00144 return b;
00145 }
00146 }
00147 char k[sizeof(F)];
00148 F* next = 0;
00149 assign(next, copy_constructor(k, b));
00150 assert(0 != next);
00151 increment(*next);
00152 while (!equal(*next, e)) {
00153 if (invoke_predicate(p, dereference(*next))) {
00154 instigate::stl::swap(dereference(b),
00155 dereference(*next));
00156 increment(b);
00157 }
00158 increment(*next);
00159 }
00160 return b;
00161 }
00162
00167 template <typename B, typename P>
00168 B instigate::stl::implementation::partition_aux(B b, B e, P p,
00169 instigate::stl::bidirectional_iterator::tag)
00170 {
00171 while(true) {
00172 while(true) {
00173 if (equal(b, e)) {
00174 return b;
00175 } else if (invoke_predicate(p, dereference(b))) {
00176 increment(b);
00177 } else {
00178 break;
00179 }
00180 }
00181 decrement(e);
00182 while (true) {
00183 if (equal(b, e)) {
00184 return b;
00185 } else if (!invoke_predicate(p, dereference(e))) {
00186 decrement(e);
00187 } else {
00188 break;
00189 }
00190 }
00191 instigate::stl::iter_swap(b, e);
00192 increment(b);
00193 }
00194 }
00195
00196
00197
00198 #endif // INSTIGATE_STL_PARTITION_HPP
00199