| 6182 | // std variant for elements with == |
| 6183 | template<typename I, typename Pred> |
| 6184 | void partition(I begin, I middle, I end, const Pred& pred, I* out_eqbeg, I* out_eqend) |
| 6185 | { |
| 6186 | I eqbeg = middle, eqend = middle + 1; |
| 6187 | |
| 6188 | // expand equal range |
| 6189 | while (eqbeg != begin && *(eqbeg - 1) == *eqbeg) |
| 6190 | --eqbeg; |
| 6191 | while (eqend != end && *eqend == *eqbeg) |
| 6192 | ++eqend; |
| 6193 | |
| 6194 | // process outer elements |
| 6195 | I ltend = eqbeg, gtbeg = eqend; |
| 6196 | |
| 6197 | for (;;) |
| 6198 | { |
| 6199 | // find the element from the right side that belongs to the left one |
| 6200 | for (; gtbeg != end; ++gtbeg) |
| 6201 | if (!pred(*eqbeg, *gtbeg)) |
| 6202 | { |
| 6203 | if (*gtbeg == *eqbeg) |
| 6204 | swap(*gtbeg, *eqend++); |
| 6205 | else |
| 6206 | break; |
| 6207 | } |
| 6208 | |
| 6209 | // find the element from the left side that belongs to the right one |
| 6210 | for (; ltend != begin; --ltend) |
| 6211 | if (!pred(*(ltend - 1), *eqbeg)) |
| 6212 | { |
| 6213 | if (*eqbeg == *(ltend - 1)) |
| 6214 | swap(*(ltend - 1), *--eqbeg); |
| 6215 | else |
| 6216 | break; |
| 6217 | } |
| 6218 | |
| 6219 | // scanned all elements |
| 6220 | if (gtbeg == end && ltend == begin) |
| 6221 | { |
| 6222 | *out_eqbeg = eqbeg; |
| 6223 | *out_eqend = eqend; |
| 6224 | return; |
| 6225 | } |
| 6226 | |
| 6227 | // make room for elements by moving equal area |
| 6228 | if (gtbeg == end) |
| 6229 | { |
| 6230 | if (--ltend != --eqbeg) |
| 6231 | swap(*ltend, *eqbeg); |
| 6232 | swap(*eqbeg, *--eqend); |
| 6233 | } |
| 6234 | else if (ltend == begin) |
| 6235 | { |
| 6236 | if (eqend != gtbeg) |
| 6237 | swap(*eqbeg, *eqend); |
| 6238 | ++eqend; |
| 6239 | swap(*gtbeg++, *eqbeg++); |
| 6240 | } |
| 6241 | else |