#include "LibraryText.h"

#include <Utf8.h>

#include <algorithm>

namespace library {

std::string joinLibraryPath(const std::string_view folder, const std::string_view name) {
  std::string path;
  path.reserve(folder.size() + name.size() + 1);
  if (folder.empty()) {
    path.push_back('/');
  } else {
    path.append(folder);
    if (folder.back() != '/') path.push_back('/');
  }
  path.append(name);
  return path;
}

namespace {

// Letters with no canonical decomposition, plus the punctuation that would
// otherwise become a space and break word shapes. Everything here is a distinct
// letter in Unicode, so no amount of NFD gets us the ASCII form.
struct CharMap {
  uint32_t cp;
  const char* replacement;
};
constexpr CharMap EXPLICIT_MAP[] = {
    {0x00D8, "o"},   // Ø
    {0x00F8, "o"},   // ø  — "Søren" folds to "soren", not "nesb"
    {0x00C6, "ae"},  // Æ
    {0x00E6, "ae"},  // æ
    {0x0152, "oe"},  // Œ
    {0x0153, "oe"},  // œ
    {0x00DF, "ss"},  // ß
    {0x0141, "l"},   // Ł
    {0x0142, "l"},   // ł
    {0x00D0, "d"},   // Ð
    {0x00F0, "d"},   // ð
    {0x0110, "d"},   // Đ
    {0x0111, "d"},   // đ
    {0x00DE, "th"},  // Þ
    {0x00FE, "th"},  // þ
    {0x0131, "i"},   // ı
    {0x0027, "'"},   // ' — kept, not turned into a space, so "O'Brien" stays one word
    {0x2019, "'"},   // ’ — and so the curly form folds to the same thing
    {0x2018, "'"},   // ‘
};

const char* explicitMapping(const uint32_t cp) {
  for (const auto& e : EXPLICIT_MAP) {
    if (e.cp == cp) return e.replacement;
  }
  return nullptr;
}

// Reverse lookup in the NFC table: given a precomposed codepoint, return the
// base letter it was composed from, or 0.
//
// The table is sorted by (base, mark) so this is a linear scan rather than a
// binary search. It runs once per non-ASCII character at index-build time and
// over a short query per keystroke, never over the whole index, so the scan is
// not on any hot path. Reusing the generated table costs no extra flash — it is
// already linked for utf8ComposeNfc().
// Fully decompose: é -> e, and the rare doubly-accented forms (ế -> ê -> e).
uint32_t stripDiacritics(uint32_t cp) {
  for (int guard = 0; guard < 4; guard++) {
    const uint32_t base = utf8DecomposedBase(cp);
    if (base == 0) break;
    cp = base;
  }
  return cp;
}

bool isAsciiAlnum(const uint32_t cp) {
  return (cp >= '0' && cp <= '9') || (cp >= 'a' && cp <= 'z') || (cp >= 'A' && cp <= 'Z');
}

void appendLowerAscii(const uint32_t cp, std::string& out) {
  out.push_back(static_cast<char>(cp >= 'A' && cp <= 'Z' ? cp - 'A' + 'a' : cp));
}

struct CodepointRange {
  uint32_t first;
  uint32_t last;
};

constexpr bool inRanges(const uint32_t cp, const CodepointRange* ranges, const size_t count) {
  for (size_t i = 0; i < count; i++) {
    if (cp >= ranges[i].first && cp <= ranges[i].last) return true;
  }
  return false;
}

// Script coverage follows the SD-font catalog. Keeping the ranges here costs a
// few hundred flash bytes; linking libunibreak solely for its general-category
// table would add roughly 75 KiB of tables plus the classifier code.
constexpr CodepointRange LETTER_RANGES[] = {
    {0x0041, 0x005A},   {0x0061, 0x007A},   {0x00C0, 0x02AF},  // Latin and IPA
    {0x0370, 0x03FF},   {0x1F00, 0x1FFF},                      // Greek
    {0x0400, 0x0481},   {0x048A, 0x052F},                      // Cyrillic
    {0x0531, 0x0556},   {0x0560, 0x0588},                      // Armenian
    {0x05D0, 0x05EA},   {0x05EF, 0x05F2},   {0xFB1D, 0xFB4F},  // Hebrew
    {0x0620, 0x064A},   {0x066E, 0x066F},   {0x0671, 0x06D3},   {0x06D5, 0x06D5},
    {0x06E5, 0x06E6},   {0x06EE, 0x06EF},   {0x06FA, 0x06FC},   {0x06FF, 0x06FF},
    {0x0750, 0x077F},   {0x08A0, 0x08C9},   {0xFB50, 0xFDF9},   {0xFE70, 0xFEFC},  // Arabic
    {0x10A0, 0x10C5},   {0x10D0, 0x10FF},   {0x1C90, 0x1CBF},   {0x2D00, 0x2D25},  // Georgian
    {0x1200, 0x135A},   {0x1380, 0x138F},   {0x2D80, 0x2DDE},                      // Ethiopic
    {0x13A0, 0x13F5},   {0x13F8, 0x13FD},   {0xAB70, 0xABBF},                      // Cherokee
    {0x2D30, 0x2D67},                                                              // Tifinagh
    {0x3041, 0x3096},   {0x30A1, 0x30FA},   {0x3105, 0x312F},   {0x31A0, 0x31BF},  // Kana/Bopomofo
    {0x3400, 0x4DBF},   {0x4E00, 0x9FFF},   {0xF900, 0xFAFF},                      // Han
    {0x1100, 0x11FF},   {0x3131, 0x318E},   {0xA960, 0xA97F},   {0xAC00, 0xD7FF},  // Hangul
    {0x20000, 0x2EBEF}, {0x2F800, 0x2FA1F}, {0x30000, 0x323AF},                    // Han extensions
};

constexpr CodepointRange NUMBER_RANGES[] = {
    {0x0030, 0x0039}, {0x0660, 0x0669}, {0x06F0, 0x06F9}, {0x0966, 0x096F}, {0xFF10, 0xFF19},
};

constexpr CodepointRange MARK_RANGES[] = {
    {0x0483, 0x0489}, {0x0591, 0x05BD}, {0x05BF, 0x05BF}, {0x05C1, 0x05C2}, {0x05C4, 0x05C5},
    {0x05C7, 0x05C7}, {0x0610, 0x061A}, {0x064B, 0x065F}, {0x0670, 0x0670}, {0x06D6, 0x06DC},
    {0x06DF, 0x06E4}, {0x06E7, 0x06E8}, {0x06EA, 0x06ED}, {0x08D3, 0x08FF}, {0xFB1E, 0xFB1E},
};

bool isUnicodeNumber(const uint32_t cp) {
  return inRanges(cp, NUMBER_RANGES, sizeof(NUMBER_RANGES) / sizeof(NUMBER_RANGES[0]));
}

bool isUnicodeMark(const uint32_t cp) {
  return utf8IsCombiningMark(cp) || inRanges(cp, MARK_RANGES, sizeof(MARK_RANGES) / sizeof(MARK_RANGES[0]));
}

bool isUnicodeLetter(const uint32_t cp) {
  if (isUnicodeMark(cp) || isUnicodeNumber(cp) || cp == 0x00D7 || cp == 0x00F7 || cp == 0x0374 || cp == 0x0375 ||
      cp == 0x037E || cp == 0x0387 || cp == 0x03F6)
    return false;
  return inRanges(cp, LETTER_RANGES, sizeof(LETTER_RANGES) / sizeof(LETTER_RANGES[0]));
}

// Views into `folded`, not copies: the caller keeps that string alive for as
// long as the tokens, and a std::string per token costs an allocation each plus
// 24 bytes of stack apiece -- 288 B for the twelve, over the 256 B this repo
// asks callers to justify.
void splitTokens(std::string_view folded, std::string_view* out, size_t maxTokens, size_t& count) {
  count = 0;
  size_t i = 0;
  while (i < folded.size() && count < maxTokens) {
    while (i < folded.size() && folded[i] == ' ') i++;
    const size_t start = i;
    while (i < folded.size() && folded[i] != ' ') i++;
    if (i > start) out[count++] = folded.substr(start, i - start);
  }
}

bool isSingleCodepoint(const std::string_view text) {
  if (text.empty()) return false;
  const auto* cursor = reinterpret_cast<const unsigned char*>(text.data());
  utf8NextCodepoint(&cursor);
  return cursor == reinterpret_cast<const unsigned char*>(text.data() + text.size());
}

}  // namespace

std::string fold(const std::string_view text) {
  std::string out;
  out.reserve(text.size());

  const auto* cursor = reinterpret_cast<const unsigned char*>(text.data());
  const auto* end = cursor + text.size();
  bool pendingSpace = false;

  while (cursor < end) {
    // The shared decoder stops on NUL and every std::string source is
    // NUL-terminated, but fold's contract is string_view — and a view may end
    // mid-sequence. Refuse to decode a lead byte whose continuation bytes lie
    // past the end rather than trusting whatever sits there.
    const unsigned char lead = *cursor;
    const ptrdiff_t promised = lead < 0x80           ? 1
                               : (lead >> 5) == 0x06 ? 2
                               : (lead >> 4) == 0x0E ? 3
                               : (lead >> 3) == 0x1E ? 4
                                                     : 1;
    if (promised > end - cursor) break;
    const uint32_t cp = utf8NextCodepoint(&cursor);
    if (cp == 0) break;

    if (isUnicodeMark(cp)) continue;

    const char* mapped = explicitMapping(cp);
    if (mapped != nullptr) {
      if (pendingSpace && !out.empty()) out.push_back(' ');
      pendingSpace = false;
      out.append(mapped);
      continue;
    }

    const uint32_t base = stripDiacritics(cp);
    if (isAsciiAlnum(base)) {
      if (pendingSpace && !out.empty()) out.push_back(' ');
      pendingSpace = false;
      appendLowerAscii(base, out);
      continue;
    }

    if (base >= 0x80 && (isUnicodeLetter(base) || isUnicodeNumber(base))) {
      if (pendingSpace && !out.empty()) out.push_back(' ');
      pendingSpace = false;
      utf8AppendCodepoint(base, out);
      continue;
    }

    // Everything else — punctuation, symbols, unmapped scripts — separates
    // words. Deferring the space keeps runs collapsed and drops trailing ones.
    if (!out.empty()) pendingSpace = true;
  }

  return out;
}

uint32_t foldedGroupInitial(const std::string_view folded) {
  if (folded.empty()) return 0;
  const auto* cursor = reinterpret_cast<const unsigned char*>(folded.data());
  const uint32_t cp = utf8NextCodepoint(&cursor);
  return isUnicodeLetter(cp) ? cp : 0;
}

std::string cleanPersonName(const std::string_view author) {
  std::string out;
  out.reserve(author.size());
  int depth = 0;
  for (size_t i = 0; i < author.size(); i++) {
    const char c = author[i];
    if (c == '[' || c == '(') {
      depth++;
      continue;
    }
    if (c == ']' || c == ')') {
      if (depth > 0) depth--;
      continue;
    }
    if (c == ';') break;  // secondary authors
    if (depth > 0) continue;
    if (c == '_') {
      // "Herbert G_ Wells" — the underscore stands in for a full stop the
      // filesystem would not take. Between letters it is an abbreviation dot;
      // at the end of a word it is just noise.
      const bool betweenLetters = i > 0 && i + 1 < author.size() &&
                                  isalpha(static_cast<unsigned char>(author[i - 1])) &&
                                  isalpha(static_cast<unsigned char>(author[i + 1]));
      out.push_back(betweenLetters ? '.' : ' ');
      continue;
    }
    out.push_back(c);
  }

  while (!out.empty() &&
         (out.back() == ' ' || out.back() == ',' || out.back() == '-' || out.back() == '.' || out.back() == '_')) {
    out.pop_back();
  }
  size_t start = 0;
  while (start < out.size() && out[start] == ' ') start++;
  out.erase(0, start);

  // Collapse the space runs left behind by the removals.
  std::string collapsed;
  collapsed.reserve(out.size());
  bool space = false;
  for (const char c : out) {
    if (c == ' ') {
      space = true;
      continue;
    }
    if (space && !collapsed.empty()) collapsed.push_back(' ');
    space = false;
    collapsed.push_back(c);
  }

  // "Austen, Jane" is the same person as "Jane Austen", and publishers use both.
  // The spelling vote cannot settle it — with one book per author there is no
  // majority — so the inverted form is turned round here instead. Only a single
  // comma qualifies: "Smith, John, Jr." and lists of several authors are left
  // exactly as they are rather than being scrambled.
  const size_t comma = collapsed.find(',');
  if (comma != std::string::npos && collapsed.find(',', comma + 1) == std::string::npos) {
    std::string_view last(collapsed.data(), comma);
    std::string_view first(collapsed.data() + comma + 1, collapsed.size() - comma - 1);
    while (!first.empty() && first.front() == ' ') first.remove_prefix(1);
    while (!last.empty() && last.back() == ' ') last.remove_suffix(1);
    if (!first.empty() && !last.empty()) {
      std::string swapped;
      swapped.reserve(collapsed.size());
      swapped.append(first);
      swapped.push_back(' ');
      swapped.append(last);
      return swapped;
    }
  }
  return collapsed;
}

std::string authorKey(const std::string_view author) {
  // The same cleanup the display name gets: bracketed spans dropped
  // ("George Sand [Sand, George]") and everything after a multi-author
  // separator cut. cleanPersonName also turns "Austen, Jane" round, which makes
  // no difference here — the tokens are sorted below, so word order is already
  // irrelevant to the key.
  const std::string folded = fold(cleanPersonName(author));

  constexpr size_t MAX_TOKENS = 12;
  std::string_view tokens[MAX_TOKENS];
  size_t count = 0;
  splitTokens(folded, tokens, MAX_TOKENS, count);

  // Initials carry no identity and appear inconsistently ("Herbert G Wells" vs
  // "Herbert Wells"), so they must not change the key.
  size_t kept = 0;
  for (size_t i = 0; i < count; i++) {
    if (!isSingleCodepoint(tokens[i])) tokens[kept++] = tokens[i];
  }
  std::sort(tokens, tokens + kept);

  std::string key;
  for (size_t i = 0; i < kept; i++) {
    if (!key.empty()) key.push_back(' ');
    key.append(tokens[i]);
  }
  // Truncate on bytes, not on a token boundary. Sorting puts a short forename
  // first, so a whole-token cut would reduce "Wollstonecraft, Mary" to the key
  // "alex" and merge every Alex in the library; the byte cut keeps
  // "mary wollsto", which stays a prefix of the full key and discriminates.
  if (key.size() > AUTHOR_KEY_MAX_BYTES) {
    key.resize(static_cast<size_t>(utf8SafeTruncateBuffer(key.data(), AUTHOR_KEY_MAX_BYTES)));
  }
  while (!key.empty() && key.back() == ' ') key.pop_back();
  return key;
}

// fold() keeps the apostrophe, which is right for sorting — "L'Eneide" belongs
// under L. For searching it is wrong: in French the word worth typing is the one
// AFTER the apostrophe, so "eneide" must reach "L'Eneide" and "cote" must
// reach "d'a cote". Treating it as a word boundary here leaves the sort untouched.
bool isWordBreak(const char c) { return c == ' ' || c == '\''; }

bool matchesQuery(const std::string_view haystack, const std::string_view needle) {
  if (needle.empty()) return true;

  // Walk the query one word at a time, and for each one scan the book's words for
  // a prefix hit. Both strings are at most a couple of hundred bytes and this
  // runs once per book per keypress, so a plain scan is cheaper than anything
  // that would need building first.
  size_t qs = 0;
  while (qs < needle.size()) {
    while (qs < needle.size() && isWordBreak(needle[qs])) qs++;
    if (qs >= needle.size()) break;
    size_t qe = qs;
    while (qe < needle.size() && !isWordBreak(needle[qe])) qe++;
    const std::string_view word = needle.substr(qs, qe - qs);

    bool found = false;
    size_t hs = 0;
    while (hs < haystack.size() && !found) {
      while (hs < haystack.size() && isWordBreak(haystack[hs])) hs++;
      if (hs >= haystack.size()) break;
      if (haystack.compare(hs, word.size(), word) == 0) {
        found = true;
        break;
      }
      while (hs < haystack.size() && !isWordBreak(haystack[hs])) hs++;
    }
    if (!found) return false;
    qs = qe;
  }
  return true;
}

std::string surnameKey(const std::string_view displayAuthor) {
  const std::string folded = fold(displayAuthor);
  if (folded.empty()) return {};

  // fold() defers its spaces, so the result has no leading, trailing or repeated
  // space. The last one is therefore the separator before the surname, and a name
  // with no space at all is its own key.
  const size_t sep = folded.rfind(' ');
  if (sep == std::string::npos) return folded;

  std::string key;
  key.reserve(folded.size());
  key.append(folded.substr(sep + 1));
  // The given names follow, so two people sharing a surname stay in a stable,
  // readable order rather than whichever the disk walk happened to produce.
  key.push_back(' ');
  key.append(folded.substr(0, sep));
  return key;
}

}  // namespace library