summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/pugixml.cpp100
1 files changed, 28 insertions, 72 deletions
diff --git a/src/pugixml.cpp b/src/pugixml.cpp
index 90b24aa..1a69ac6 100644
--- a/src/pugixml.cpp
+++ b/src/pugixml.cpp
@@ -7238,98 +7238,54 @@ PUGI__NS_BEGIN
}
}
- // std variant for elements with ==
- template <typename I, typename Pred> void partition(I begin, I middle, I end, const Pred& pred, I* out_eqbeg, I* out_eqend)
+ template <typename I, typename Pred> I median3(I first, I middle, I last, const Pred& pred)
{
- I eqbeg = middle, eqend = middle + 1;
+ if (pred(*middle, *first)) swap(middle, first);
+ if (pred(*last, *middle)) swap(last, middle);
+ if (pred(*middle, *first)) swap(middle, first);
- // expand equal range
- while (eqbeg != begin && *(eqbeg - 1) == *eqbeg) --eqbeg;
- while (eqend != end && *eqend == *eqbeg) ++eqend;
-
- // process outer elements
- I ltend = eqbeg, gtbeg = eqend;
-
- for (;;)
- {
- // find the element from the right side that belongs to the left one
- for (; gtbeg != end; ++gtbeg)
- if (!pred(*eqbeg, *gtbeg))
- {
- if (*gtbeg == *eqbeg) swap(*gtbeg, *eqend++);
- else break;
- }
-
- // find the element from the left side that belongs to the right one
- for (; ltend != begin; --ltend)
- if (!pred(*(ltend - 1), *eqbeg))
- {
- if (*eqbeg == *(ltend - 1)) swap(*(ltend - 1), *--eqbeg);
- else break;
- }
-
- // scanned all elements
- if (gtbeg == end && ltend == begin)
- {
- *out_eqbeg = eqbeg;
- *out_eqend = eqend;
- return;
- }
-
- // make room for elements by moving equal area
- if (gtbeg == end)
- {
- if (--ltend != --eqbeg) swap(*ltend, *eqbeg);
- swap(*eqbeg, *--eqend);
- }
- else if (ltend == begin)
- {
- if (eqend != gtbeg) swap(*eqbeg, *eqend);
- ++eqend;
- swap(*gtbeg++, *eqbeg++);
- }
- else swap(*gtbeg++, *--ltend);
- }
+ return middle;
}
- template <typename I, typename Pred> void median3(I first, I middle, I last, const Pred& pred)
+ template <typename T, typename Pred> void partition(T* begin, T* end, T pivot, const Pred& pred, T** out_eqbeg, T** out_eqend)
{
- if (pred(*middle, *first)) swap(*middle, *first);
- if (pred(*last, *middle)) swap(*last, *middle);
- if (pred(*middle, *first)) swap(*middle, *first);
- }
+ // invariant: array is split into 4 groups: = < ? > (each variable denotes the boundary between the groups)
+ T* eq = begin;
+ T* lt = begin;
+ T* gt = end;
- template <typename I, typename Pred> void median(I first, I middle, I last, const Pred& pred)
- {
- if (last - first <= 40)
+ while (lt < gt)
{
- // median of three for small chunks
- median3(first, middle, last, pred);
+ if (pred(*lt, pivot))
+ lt++;
+ else if (*lt == pivot)
+ swap(*eq++, *lt++);
+ else
+ swap(*lt, *--gt);
}
- else
- {
- // median of nine
- size_t step = (last - first + 1) / 8;
- median3(first, first + step, first + 2 * step, pred);
- median3(middle - step, middle, middle + step, pred);
- median3(last - 2 * step, last - step, last, pred);
- median3(first + step, middle, last - step, pred);
- }
+ // we now have just 4 groups: = < >; move equal elements to the middle
+ T* eqbeg = gt;
+
+ for (T* it = begin; it != eq; ++it)
+ swap(*it, *--eqbeg);
+
+ *out_eqbeg = eqbeg;
+ *out_eqend = gt;
}
template <typename I, typename Pred> void sort(I begin, I end, const Pred& pred)
{
// sort large chunks
- while (end - begin > 32)
+ while (end - begin > 16)
{
// find median element
I middle = begin + (end - begin) / 2;
- median(begin, middle, end - 1, pred);
+ I median = median3(begin, middle, end - 1, pred);
// partition in three chunks (< = >)
I eqbeg, eqend;
- partition(begin, middle, end, pred, &eqbeg, &eqend);
+ partition(begin, end, *median, pred, &eqbeg, &eqend);
// loop on larger half
if (eqbeg - begin > end - eqend)