<commit_before>// Copyright (c) 2016 <NAME>
//
// Permission is hereby granted, free of charge, to any person obtaining a
// copy of this software and associated documentation files (the "Software"),
// to deal in the Software without restriction, including without limitation
// the rights to use, copy, modify, merge, publish, distribute, sublicense,
// and/or sell copies of the Software, and to permit persons to whom the
// Software is furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included
// in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
// THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
// IN THE SOFTWARE.

// Three Pivot Quicksort
//  a three pivot quicksort implementation switching to three way
//  partitioning if usefull

#ifndef SORT_DETAIL_INPLACE_H
#define SORT_DETAIL_INPLACE_H

#ifdef __INTEL_COMPILER
#pragma warning disable 3373
#endif

#include <array>
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdint>
#include <tuple>
#include <type_traits>

#include "misc.h"

namespace sort {
namespace detail {
namespace inplace {

template <class T, class I, class V>
inline std::pair<T, T> partition(T first, T last, I index, V pa) {
  using W = std::remove_reference_t<decltype(*first)>;
  // Doesn't assume that pa is in [first, last)
  // see "Engineering a Sort Function" - BENTLEY, McILROY

  auto a = first, c = std::prev(last);
  auto b = first, d = last;

  while (true) {
    W bv, cv;
    for (V v; b <= c && (v = index(bv = *b)) <= pa; ++b)
      if (v == pa) *b = *a, *a++ = bv;

    for (V v; b <= c && pa <= (v = index(cv = *c)); --c)
      if (v == pa) *c = *--d, *d = cv;

    if (b > c) break;

    *c-- = bv; *b++ = cv;
  }

  auto s = std::min(first + (b - a), a);
  std::swap_ranges(first, s, b - (s - first));

  auto t = std::min(last + (b - d), d);
  std::swap_ranges(b, t, last - (t - b));

  return std::make_pair(first + (b - a), last + (b - d));
}

template <class T, class I, class V>
inline std::pair<T, T> exchange1(T a, T f, I index, V pa) {
  using W = std::remove_reference_t<decltype(*a)>;
  // Assumes pa to be at least the median of 3 elements in [a, f)
  // see "Engineering a Sort Function" - <NAME>

  auto b = a;
  while (b != f && index(*b) == pa) ++b;
  if (b == f) return std::make_pair(a, f);
  b -= a != b; // we need at least one pivot element in the range

  auto c = b, d = f, e = f;
  while (true) {
    W cv, dv; V v1, v2;
    while ((v1 = index(cv = *c++)) < pa);
    while (pa < (v2 = index(dv = *--d)));

    if (--c >= d) break;

    if (v1 == pa) *d = *--e, *e = cv; else *d = cv;
    if (v2 == pa) *c = *b, *b++ = dv; else *c = dv;
    ++c;
  }
  d = c + (c == d); // c == d means center element is equal to pa, keep it there

  auto s = std::min(a + (c - b), b);
  std::swap_ranges(a, s, c - (s - a));

  auto t = std::min(d + (f - e), e);
  std::swap_ranges(d, t, f - (t - d));

  return std::make_pair(a + (c - b), d + (f - e));
}

template <class T, class I, class V>
inline std::tuple<T, T, T> exchange3(T first, T last, I index, V pa, V pb, V pc) {
  using W = std::remove_reference_t<decltype(*first)>;
  // Assumes pa < pb < pc and all exists within [first, last)
  // see "How Good is Multi-Pivot Quicksort?" - Aumueller, Dietzfelbinger, Klaue

  auto a = first, c = last - 1;
  auto b = first, d = last;

  while (true) {
    W bv, cv; V v1, v2;
    for (; !(pb < (v1 = index(bv = *b))); ++b)
      if (v1 < pa) *b = *a, *a++ = bv;

    for (;  (pb < (v2 = index(cv = *c))); --c)
      if (v2 > pc) *c = *--d, *d = cv;

    if (b > c) break;

    if (v2 < pa) *b = *a, *a++ = cv; else *b = cv;
    if (v1 > pc) *c = *--d, *d = bv; else *c = bv;
    ++b; c--;
  }

  return std::make_tuple(a, b, d);
}

template <class T, class I, class V>
inline T exchange_block(T first, T last, I index, V p) {
  //using W = std::remove_reference_t<decltype(*first)>;
  // Assumes p is at least median of three and exists within [first, last)
  // see "BlockQuicksort: How Branch Mispredictions don't affect Quicksort" - Edelkamp, Weiss

  auto a = first, b = last;

  constexpr const int BLOCK_SIZE = detail::misc::BLOCK_SIZE;
  std::array<uint8_t, BLOCK_SIZE> offsets_a;
  std::array<uint8_t, BLOCK_SIZE> offsets_b;
  int ac = 0, bc = 0; // counts
  int au = 0, bu = 0; // number of used

  while (2 * BLOCK_SIZE <= std::distance(a, b)) {
    if (ac == 0) {
      au = 0;
      for (int i = 0; i < BLOCK_SIZE;) {
        offsets_a[ac] = i; ac += p <= index(a[i]); ++i;
        offsets_a[ac] = i; ac += p <= index(a[i]); ++i;
        offsets_a[ac] = i; ac += p <= index(a[i]); ++i;
        offsets_a[ac] = i; ac += p <= index(a[i]); ++i;
      }
    }
    if (bc == 0) {
      bu = 0;
      for (int i = 0; i < BLOCK_SIZE;) {
        offsets_b[bc] = i; bc += index(b[-i - 1]) < p; ++i;
        offsets_b[bc] = i; bc += index(b[-i - 1]) < p; ++i;
        offsets_b[bc] = i; bc += index(b[-i - 1]) < p; ++i;
        offsets_b[bc] = i; bc += index(b[-i - 1]) < p; ++i;
      }
    }

    int c = std::min(ac, bc);
    for (int i = 0; i < c; ++i)
      std::iter_swap(a + offsets_a[au + i], b - offsets_b[bu + i] - 1);

    ac -= c; bc -= c;
    au += c; bu += c;
    if (ac == 0) a += BLOCK_SIZE;<commit_msg>Optimized the hot path of *::exchange_block()*<commit_after>// Copyright (c) 2016 <NAME>
//
// Permission is hereby granted, free of charge, to any person obtaining a
// copy of this software and associated documentation files (the "Software"),
// to deal in the Software without restriction, including without limitation
// the rights to use, copy, modify, merge, publish, distribute, sublicense,
// and/or sell copies of the Software, and to permit persons to whom the
// Software is furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included
// in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
// THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
// IN THE SOFTWARE.

// Three Pivot Quicksort
//  a three pivot quicksort implementation switching to three way
//  partitioning if usefull

#ifndef SORT_DETAIL_INPLACE_H
#define SORT_DETAIL_INPLACE_H

#ifdef __INTEL_COMPILER
#pragma warning disable 3373
#endif

#include <array>
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdint>
#include <tuple>
#include <type_traits>

#include "misc.h"

namespace sort {
namespace detail {
namespace inplace {

template <class T, class I, class V>
inline std::pair<T, T> partition(T first, T last, I index, V pa) {
  using W = std::remove_reference_t<decltype(*first)>;
  // Doesn't assume that pa is in [first, last)
  // see "Engineering a Sort Function" - <NAME>

  auto a = first, c = std::prev(last);
  auto b = first, d = last;

  while (true) {
    W bv, cv;
    for (V v; b <= c && (v = index(bv = *b)) <= pa; ++b)
      if (v == pa) *b = *a, *a++ = bv;

    for (V v; b <= c && pa <= (v = index(cv = *c)); --c)
      if (v == pa) *c = *--d, *d = cv;

    if (b > c) break;

    *c-- = bv; *b++ = cv;
  }

  auto s = std::min(first + (b - a), a);
  std::swap_ranges(first, s, b - (s - first));

  auto t = std::min(last + (b - d), d);
  std::swap_ranges(b, t, last - (t - b));

  return std::make_pair(first + (b - a), last + (b - d));
}

template <class T, class I, class V>
inline std::pair<T, T> exchange1(T a, T f, I index, V pa) {
  using W = std::remove_reference_t<decltype(*a)>;
  // Assumes pa to be at least the median of 3 elements in [a, f)
  // see "Engineering a Sort Function" - <NAME>

  auto b = a;
  while (b != f && index(*b) == pa) ++b;
  if (b == f) return std::make_pair(a, f);
  b -= a != b; // we need at least one pivot element in the range

  auto c = b, d = f, e = f;
  while (true) {
    W cv, dv; V v1, v2;
    while ((v1 = index(cv = *c++)) < pa);
    while (pa < (v2 = index(dv = *--d)));

    if (--c >= d) break;

    if (v1 == pa) *d = *--e, *e = cv; else *d = cv;
    if (v2 == pa) *c = *b, *b++ = dv; else *c = dv;
    ++c;
  }
  d = c + (c == d); // c == d means center element is equal to pa, keep it there

  auto s = std::min(a + (c - b), b);
  std::swap_ranges(a, s, c - (s - a));

  auto t = std::min(d + (f - e), e);
  std::swap_ranges(d, t, f - (t - d));

  return std::make_pair(a + (c - b), d + (f - e));
}

template <class T, class I, class V>
inline std::tuple<T, T, T> exchange3(T first, T last, I index, V pa, V pb, V pc) {
  using W = std::remove_reference_t<decltype(*first)>;
  // Assumes pa < pb < pc and all exists within [first, last)
  // see "How Good is Multi-Pivot Quicksort?" - Aumueller, <NAME>

  auto a = first, c = last - 1;
  auto b = first, d = last;

  while (true) {
    W bv, cv; V v1, v2;
    for (; !(pb < (v1 = index(bv = *b))); ++b)
      if (v1 < pa) *b = *a, *a++ = bv;

    for (;  (pb < (v2 = index(cv = *c))); --c)
      if (v2 > pc) *c = *--d, *d = cv;

    if (b > c) break;

    if (v2 < pa) *b = *a, *a++ = cv; else *b = cv;
    if (v1 > pc) *c = *--d, *d = bv; else *c = bv;
    ++b; c--;
  }

  return std::make_tuple(a, b, d);
}

template <class T, class I, class V>
inline T exchange_block(T first, T last, I index, V p) {
  //using W = std::remove_reference_t<decltype(*first)>;
  // Assumes p is at least median of three and exists within [first, last)
  // see "BlockQuicksort: How Branch Mispredictions don't affect Quicksort" - <NAME>

  auto a = first, b = last;

  constexpr const int BLOCK_SIZE = detail::misc::BLOCK_SIZE;
  std::array<uint8_t, BLOCK_SIZE> offsets_a;
  std::array<uint8_t, BLOCK_SIZE> offsets_b;
  intptr_t ac = 0, bc = 0; // counts
  intptr_t au = 0, bu = 0; // number of used
  while (2 * BLOCK_SIZE <= std::distance(a, b)) {
    auto t = ac;
    if (ac == 0) {
      au = 0;
      for (int i = 0; i < BLOCK_SIZE;) {
        offsets_a[ac] = i; ac += p <= index(a[i]); ++i;
        offsets_a[ac] = i; ac += p <= index(a[i]); ++i;
        offsets_a[ac] = i; ac += p <= index(a[i]); ++i;
        offsets_a[ac] = i; ac += p <= index(a[i]); ++i;
      }
    }
    if (t != 0 || bc == 0) {
      bu = 0;
      for (int i = BLOCK_SIZE-1; 0 <= i;) {
        offsets_b[bc] = i; bc += index(b[i - BLOCK_SIZE]) < p; --i;
        offsets_b[bc] = i; bc += index(b[i - BLOCK_SIZE]) < p; --i;
        offsets_b[bc] = i; bc += index(b[i - BLOCK_SIZE]) < p; --i;
        offsets_b[bc] = i; bc += index(b[i - BLOCK_SIZE]) < p; --i;
      }
    }

    auto c = std::min(ac, bc);
    for (intptr_t i = 0; i < c; ++i)
      std::iter_swap(a + offsets_a[au + i], b + offsets_b[bu + i] - BLOCK_SIZE);
    ac -= c; bc -= c;
    au += c; bu += c;
    if (ac == 0) a += BLOCK_SIZE;
{'fraction_non_alphanumeric': 0.17305347500435464, 'fraction_numerical': 0.007751262846194043, 'mean_word_length': 2.7053888351080992, 'pattern_counts': {'":': 0, '<': 98, '<?xml version=': 0, '>': 60, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '571763', 'n_tokens_mistral': 4479, 'n_tokens_neox': 4300, 'n_words': 1614}