| 4922 | |
| 4923 | // std variant for elements with == |
| 4924 | template <typename I, typename Pred> void partition(I begin, I middle, I end, const Pred& pred, I* out_eqbeg, I* out_eqend) |
| 4925 | { |
| 4926 | I eqbeg = middle, eqend = middle + 1; |
| 4927 | |
| 4928 | // expand equal range |
| 4929 | while (eqbeg != begin && *(eqbeg - 1) == *eqbeg) --eqbeg; |
| 4930 | while (eqend != end && *eqend == *eqbeg) ++eqend; |
| 4931 | |
| 4932 | // process outer elements |
| 4933 | I ltend = eqbeg, gtbeg = eqend; |
| 4934 | |
| 4935 | for (;;) |
| 4936 | { |
| 4937 | // find the element from the right side that belongs to the left one |
| 4938 | for (; gtbeg != end; ++gtbeg) |
| 4939 | if (!pred(*eqbeg, *gtbeg)) |
| 4940 | { |
| 4941 | if (*gtbeg == *eqbeg) swap(*gtbeg, *eqend++); |
| 4942 | else break; |
| 4943 | } |
| 4944 | |
| 4945 | // find the element from the left side that belongs to the right one |
| 4946 | for (; ltend != begin; --ltend) |
| 4947 | if (!pred(*(ltend - 1), *eqbeg)) |
| 4948 | { |
| 4949 | if (*eqbeg == *(ltend - 1)) swap(*(ltend - 1), *--eqbeg); |
| 4950 | else break; |
| 4951 | } |
| 4952 | |
| 4953 | // scanned all elements |
| 4954 | if (gtbeg == end && ltend == begin) |
| 4955 | { |
| 4956 | *out_eqbeg = eqbeg; |
| 4957 | *out_eqend = eqend; |
| 4958 | return; |
| 4959 | } |
| 4960 | |
| 4961 | // make room for elements by moving equal area |
| 4962 | if (gtbeg == end) |
| 4963 | { |
| 4964 | if (--ltend != --eqbeg) swap(*ltend, *eqbeg); |
| 4965 | swap(*eqbeg, *--eqend); |
| 4966 | } |
| 4967 | else if (ltend == begin) |
| 4968 | { |
| 4969 | if (eqend != gtbeg) swap(*eqbeg, *eqend); |
| 4970 | ++eqend; |
| 4971 | swap(*gtbeg++, *eqbeg++); |
| 4972 | } |
| 4973 | else swap(*gtbeg++, *--ltend); |
| 4974 | } |
| 4975 | } |
| 4976 | |
| 4977 | template <typename I, typename Pred> void median3(I first, I middle, I last, const Pred& pred) |
| 4978 | { |