<commit_before>// Copyright (c) 2011 <NAME> <<EMAIL>>. All Rights Reserved.
// This source code is distributed under MIT License in LICENSE file.

#ifndef SARA_SARA_H_
#define SARA_SARA_H_

// Suffix array construction by induced sorting
// see: "Linear Suffix Array Construction by Almost Pure Induced-Sorting"
//      <NAME>., <NAME>. and <NAME>. Data Compression Conference, 2009.

#include <cstddef>
#include <algorithm>
#include <functional>
#include <iterator>
#include <type_traits>
#include <vector>
#include <boost/range.hpp>
#include <boost/range/irange.hpp>
#include <boost/range/adaptors.hpp>
#include <boost/range/algorithm.hpp>

namespace sara {

// Induced sorting
template <typename String, typename Indexes>
void induce_sa(const String& s,
               const std::vector<bool>& t,
               const std::vector<
                 typename boost::range_difference<String>::type>& buckets,
               Indexes& sa) {
  typedef typename std::make_unsigned<
    typename std::decay<decltype(s[0])>::type>::type ch_type;

  // sort L-type indexes
  std::vector<typename boost::range_difference<String>::type>
      poss(buckets.begin(), buckets.end() - 1);

  auto back_idx = boost::size(s) - 1;
  sa[poss[ch_type(s[back_idx])]++] = back_idx;  // sentinel

  for (auto cur : sa) {
    if (--cur >= 0 && !t[cur]) {
      sa[poss[ch_type(s[cur])]++] = cur;
    }
  }

  // sort S-type indexes
  std::copy(buckets.begin() + 1, buckets.end(), poss.begin());
  for (auto cur : sa | boost::adaptors::reversed) {
    if (--cur >= 0 && t[cur]) {
      sa[--poss[ch_type(s[cur])]] = cur;
    }
  }
}

// Constructs suffix array by induced sorting.
// [s_begin, ..., s_begin + n) must not contain elements greater than |ch_max|.
template <typename CharIter, typename IndexIter>
void make(CharIter s_begin, IndexIter sa_begin, int n, int ch_max) {
  typedef typename std::make_unsigned<
    typename std::iterator_traits<CharIter>::value_type>::type ch_type;
  typedef typename std::iterator_traits<CharIter>::difference_type index_type;

  auto sa = boost::make_iterator_range(sa_begin, sa_begin + n);
  auto s = boost::make_iterator_range(s_begin, s_begin + n);
  boost::fill(sa, -1);

  // Create L/S bit array |t|
  std::vector<bool> t(n);
  for (auto i = n - 1; i > 0; --i) {
    t[i - 1] = s[i - 1] == s[i] ? t[i]
                                : ch_type(s[i - 1]) < ch_type(s[i]);
  }

  auto is_not_lms = [&t](index_type i) {
    return !(i > 0 && t[i] && !t[i - 1]);
  };

  // Create buckets
  std::vector<index_type> buckets(ch_max + 2);
  for (ch_type ch : s) {
    ++buckets[ch + 1];
  }
  std::partial_sum(buckets.begin(), buckets.end(), buckets.begin());

  // Induced sorting of S-substrings
  std::vector<std::size_t> poss(buckets.begin() + 1, buckets.end());
  for (int i = 0; i < n; ++i) {
    if (!is_not_lms(i)) {
      sa[--poss[ch_type(s[i])]] = i;
    }
  }
  induce_sa(s, t, buckets, sa);

  // Remove S-substrings other than LMS-substrings
  auto lms_end = boost::remove_if(sa, is_not_lms);
  auto num_lms = lms_end - sa_begin;
  std::fill(lms_end, sa.end(), -1);

  // Get lexicographical names of all (sorted) LMS-substrings and create S1
  int cur_name = 0;
  for (auto it = sa_begin; it != lms_end; ++it) {
    if (it == sa_begin) {
      lms_end[*it / 2] = cur_name;
      continue;
    }
    auto cur = *it, prev = *(it - 1);
    bool miss = s[cur] != s[prev] || t[cur] != t[prev];
    if (!miss) do {
      ++cur, ++prev;
      miss |= cur == n ||
              prev == n ||
              s[cur] != s[prev] ||
              t[cur] != t[prev];
    } while (!miss && is_not_lms(cur) && is_not_lms(prev));

    if (miss) ++cur_name;
    lms_end[*it / 2] = cur_name;
  }
  const int num_names = cur_name + 1;
  std::remove_if(boost::rbegin(sa), boost::rbegin(sa) + (n - num_lms),
                 [](index_type idx) { return idx < 0; });
  auto s1 = sa | boost::adaptors::sliced(n - num_lms, n);

  // Recurse if LMS-substrings are not unique, otherwise generate SA1 directly
  // from S1
  if (num_names < num_lms) {
    make(s1.begin(), sa_begin, num_lms, num_names);
  } else {
    for (int i = 0; i < num_lms; ++i) {
      sa[s1[i]] = i;
    }
  }

  // Induce SA from SA1
  auto p1 = s1;  // reuse the space for efficiency
  boost::remove_copy_if(boost::irange(1, n), p1.begin(), is_not_lms);
  for (int i = 0; i < num_lms; ++i) {
    sa[i] = p1[sa[i]];
  }
  std::fill(sa.begin() + num_lms, sa.end(), -1);

  std::copy(buckets.begin() + 1, buckets.end(), poss.begin());
  for (auto i = num_lms; i-- > 0; ) {
    auto j = sa[i];
    sa[i] = -1;
    sa[--poss[ch_type(s[j])]] = j;
  }
  induce_sa(s, t, buckets, sa);
}

template <typename String>
std::vector<typename boost::range_difference<String>::type>
make(const String& s, int ch_max) {
  std::vector<typename boost::range_difference<String>::type>
      sa(boost::size(s));
  make(boost::begin(s), sa.begin(), boost::size(s), ch_max);
  return sa;
}
<commit_msg>make return type of make(s, ch_max) templated<commit_after>// Copyright (c) 2011 <NAME> <<EMAIL>>. All Rights Reserved.
// This source code is distributed under MIT License in LICENSE file.

#ifndef SARA_SARA_H_
#define SARA_SARA_H_

// Suffix array construction by induced sorting
// see: "Linear Suffix Array Construction by Almost Pure Induced-Sorting"
//      <NAME>., <NAME>. and <NAME>. Data Compression Conference, 2009.

#include <cstddef>
#include <algorithm>
#include <functional>
#include <iterator>
#include <type_traits>
#include <vector>
#include <boost/range.hpp>
#include <boost/range/irange.hpp>
#include <boost/range/adaptors.hpp>
#include <boost/range/algorithm.hpp>

namespace sara {

// Induced sorting
template <typename String, typename Indexes>
void induce_sa(const String& s,
               const std::vector<bool>& t,
               const std::vector<
                 typename boost::range_difference<String>::type>& buckets,
               Indexes& sa) {
  typedef typename std::make_unsigned<
    typename std::decay<decltype(s[0])>::type>::type ch_type;

  // sort L-type indexes
  std::vector<typename boost::range_difference<String>::type>
      poss(buckets.begin(), buckets.end() - 1);

  auto back_idx = boost::size(s) - 1;
  sa[poss[ch_type(s[back_idx])]++] = back_idx;  // sentinel

  for (auto cur : sa) {
    if (--cur >= 0 && !t[cur]) {
      sa[poss[ch_type(s[cur])]++] = cur;
    }
  }

  // sort S-type indexes
  std::copy(buckets.begin() + 1, buckets.end(), poss.begin());
  for (auto cur : sa | boost::adaptors::reversed) {
    if (--cur >= 0 && t[cur]) {
      sa[--poss[ch_type(s[cur])]] = cur;
    }
  }
}

// Constructs suffix array by induced sorting.
// [s_begin, ..., s_begin + n) must not contain elements greater than |ch_max|.
template <typename CharIter, typename IndexIter>
void make(CharIter s_begin, IndexIter sa_begin, int n, int ch_max) {
  typedef typename std::make_unsigned<
    typename std::iterator_traits<CharIter>::value_type>::type ch_type;
  typedef typename std::iterator_traits<CharIter>::difference_type index_type;

  auto sa = boost::make_iterator_range(sa_begin, sa_begin + n);
  auto s = boost::make_iterator_range(s_begin, s_begin + n);
  boost::fill(sa, -1);

  // Create L/S bit array |t|
  std::vector<bool> t(n);
  for (auto i = n - 1; i > 0; --i) {
    t[i - 1] = s[i - 1] == s[i] ? t[i]
                                : ch_type(s[i - 1]) < ch_type(s[i]);
  }

  auto is_not_lms = [&t](index_type i) {
    return !(i > 0 && t[i] && !t[i - 1]);
  };

  // Create buckets
  std::vector<index_type> buckets(ch_max + 2);
  for (ch_type ch : s) {
    ++buckets[ch + 1];
  }
  std::partial_sum(buckets.begin(), buckets.end(), buckets.begin());

  // Induced sorting of S-substrings
  std::vector<std::size_t> poss(buckets.begin() + 1, buckets.end());
  for (int i = 0; i < n; ++i) {
    if (!is_not_lms(i)) {
      sa[--poss[ch_type(s[i])]] = i;
    }
  }
  induce_sa(s, t, buckets, sa);

  // Remove S-substrings other than LMS-substrings
  auto lms_end = boost::remove_if(sa, is_not_lms);
  auto num_lms = lms_end - sa_begin;
  std::fill(lms_end, sa.end(), -1);

  // Get lexicographical names of all (sorted) LMS-substrings and create S1
  int cur_name = 0;
  for (auto it = sa_begin; it != lms_end; ++it) {
    if (it == sa_begin) {
      lms_end[*it / 2] = cur_name;
      continue;
    }
    auto cur = *it, prev = *(it - 1);
    bool miss = s[cur] != s[prev] || t[cur] != t[prev];
    if (!miss) do {
      ++cur, ++prev;
      miss |= cur == n ||
              prev == n ||
              s[cur] != s[prev] ||
              t[cur] != t[prev];
    } while (!miss && is_not_lms(cur) && is_not_lms(prev));

    if (miss) ++cur_name;
    lms_end[*it / 2] = cur_name;
  }
  const int num_names = cur_name + 1;
  std::remove_if(boost::rbegin(sa), boost::rbegin(sa) + (n - num_lms),
                 [](index_type idx) { return idx < 0; });
  auto s1 = sa | boost::adaptors::sliced(n - num_lms, n);

  // Recurse if LMS-substrings are not unique, otherwise generate SA1 directly
  // from S1
  if (num_names < num_lms) {
    make(s1.begin(), sa_begin, num_lms, num_names);
  } else {
    for (int i = 0; i < num_lms; ++i) {
      sa[s1[i]] = i;
    }
  }

  // Induce SA from SA1
  auto p1 = s1;  // reuse the space for efficiency
  boost::remove_copy_if(boost::irange(1, n), p1.begin(), is_not_lms);
  for (int i = 0; i < num_lms; ++i) {
    sa[i] = p1[sa[i]];
  }
  std::fill(sa.begin() + num_lms, sa.end(), -1);

  std::copy(buckets.begin() + 1, buckets.end(), poss.begin());
  for (auto i = num_lms; i-- > 0; ) {
    auto j = sa[i];
    sa[i] = -1;
    sa[--poss[ch_type(s[j])]] = j;
  }
  induce_sa(s, t, buckets, sa);
}

template <typename String, typename SArray = std::vector<
                             typename boost::range_difference<String>::type>>
SArray make(const String& s, int ch_max) {
  SArray sa(boost::size(s));
  make(boost::begin(s), sa.begin(), boost::size(s), ch_max);
  return sa;
}

{'fraction_non_alphanumeric': 0.17515827555019595, 'fraction_numerical': 0.010250226107928851, 'mean_word_length': 3.0686835650040885, 'pattern_counts': {'":': 0, '<': 85, '<?xml version=': 0, '>': 83, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7405205', 'n_tokens_mistral': 3900, 'n_tokens_neox': 3689, 'n_words': 927}