/* Exact byte-level BPE for the HDC engine — browser-native, no dependencies.
 *
 * Why this file exists: the page used to tokenise by greedy longest match over the decoded
 * vocabulary, which is NOT the model's tokenisation. Its own comment said so ("this is NOT the
 * model's exact BPE merge process"). It does not have to be an approximation: a GPT-2-family GGUF
 * carries the whole merge table in its header — Qwen2.5-0.5B carries all 151,387 merges and all
 * 151,936 tokens, untruncated — and a merge table plus a rank is sufficient to reproduce the exact
 * merge sequence. So this module reproduces it.
 *
 * Algorithm (the same order HF's GPT2Tokenizer and llama.cpp use):
 *   1. bytes of the input text -> the byte-level alphabet (printable bytes map to themselves, the
 *      other 68 map to U+0100 + n, which is GPT-2's bytes_to_unicode table),
 *   2. split with the model's pre-tokeniser regex (`tokenizer.ggml.pre`, "qwen2" here),
 *   3. inside each pre-token, repeatedly merge the adjacent pair with the lowest merge rank until
 *      no merge applies,
 *   4. map each surviving piece back through the alphabet to its surface string, and look it up in
 *      the vocabulary for its id.
 *
 * SURFACE FORMS ARE THE CONTRACT. The page builds its item memory from the decoded surface form of
 * every vocabulary entry, so `tokenize` must return exactly what `decodeToken(token, "gpt2")` in
 * app.js returns — `c >= 256 ? (c - 256) & 0xFF : c & 0xFF` per character, then UTF-8 decode. A
 * different convention here would make every token unmatchable and the output would be noise.
 *
 * FALLBACK, NOT A CRASH. If the model is not byte-level BPE (`tokenizer.ggml.model !== "gpt2"`) or
 * the file carries no merges — true of the llama SentencePiece fixtures stories260K and stories15M,
 * which store 0 merges — then exact merging is impossible and the module falls back to greedy
 * longest match over the decoded tokens, reporting `exact: false` so the caller can say so on the
 * page instead of implying an exactness it does not have.
 */
(function (root) {
  "use strict";

  /* ---------------------------------------------------------------- byte-level alphabet */

  // GPT-2 bytes_to_unicode: 33..126, 161..172, 174..255 map to themselves; the remaining 68 bytes
  // (0..32, 127..160, 173) are pushed to U+0100+n, which is what keeps every byte printable and
  // space-free inside a token string.
  var BYTE_TO_CHAR = (function () {
    var table = new Array(256), extra = 0, b;
    function printable(x) {
      return (x >= 0x21 && x <= 0x7e) || (x >= 0xa1 && x <= 0xac) || (x >= 0xae && x <= 0xff);
    }
    for (b = 0; b < 256; b++) if (printable(b)) table[b] = String.fromCharCode(b);
    for (b = 0; b < 256; b++) if (!printable(b)) table[b] = String.fromCharCode(256 + extra++);
    return table;
  })();

  // The inverse, matching app.js's decodeToken(token, "gpt2") character-for-character.
  function charToByte(c) { return c >= 256 ? (c - 256) & 0xFF : c & 0xFF; }

  var textEncoder = typeof TextEncoder !== "undefined" ? new TextEncoder() : null;
  var textDecoder = typeof TextDecoder !== "undefined" ? new TextDecoder("utf-8") : null;

  function utf8Bytes(str) {
    if (textEncoder) return textEncoder.encode(str);
    var out = [], i, c, cp;                     // minimal UTF-8 encoder for environments without it
    for (i = 0; i < str.length; i++) {
      c = str.charCodeAt(i);
      if (c >= 0xd800 && c <= 0xdbff && i + 1 < str.length) {
        cp = (c - 0xd800) * 0x400 + (str.charCodeAt(i + 1) - 0xdc00) + 0x10000;
        i++;
      } else cp = c;
      if (cp < 0x80) out.push(cp);
      else if (cp < 0x800) out.push(0xc0 | (cp >> 6), 0x80 | (cp & 0x3f));
      else if (cp < 0x10000) out.push(0xe0 | (cp >> 12), 0x80 | ((cp >> 6) & 0x3f), 0x80 | (cp & 0x3f));
      else out.push(0xf0 | (cp >> 18), 0x80 | ((cp >> 12) & 0x3f), 0x80 | ((cp >> 6) & 0x3f), 0x80 | (cp & 0x3f));
    }
    return new Uint8Array(out);
  }

  function bytesToString(bytes) {
    if (textDecoder) {
      try { return textDecoder.decode(bytes instanceof Uint8Array ? bytes : new Uint8Array(bytes)); }
      catch (e) { /* fall through */ }
    }
    var s = "", i;
    for (i = 0; i < bytes.length; i++) s += String.fromCharCode(bytes[i]);
    return s;
  }

  // text -> the tokeniser's alphabet. Every character of the result represents exactly one byte.
  function encodeText(text) {
    var bytes = utf8Bytes(text), out = "", i;
    for (i = 0; i < bytes.length; i++) out += BYTE_TO_CHAR[bytes[i]];
    return out;
  }

  // one vocabulary piece (already in the alphabet) -> the text it represents
  function decodePiece(piece) {
    var bytes = new Uint8Array(piece.length), n = 0, i;
    for (i = 0; i < piece.length; i++) bytes[n++] = charToByte(piece.charCodeAt(i));
    return bytesToString(bytes.subarray(0, n));
  }

  /* ---------------------------------------------------------------- pre-tokeniser */

  var CONTRACTIONS = ["s", "t", "re", "ve", "m", "ll", "d"];

  // Both spellings of each contraction, so the pattern works without an inline case-insensitive
  // group: `(?i:...)` only compiles on engines that support RegExp modifier groups.
  function contractionAlternation() {
    var parts = [], i, w, a, b;
    for (i = 0; i < CONTRACTIONS.length; i++) {
      w = CONTRACTIONS[i];
      parts.push("'" + w);
      for (a = 0; a < w.length; a++) {
        var mixed = "";
        for (b = 0; b < w.length; b++) mixed += (b === a) ? w.charAt(b).toUpperCase() : w.charAt(b);
        parts.push("'" + mixed);
      }
    }
    return parts.join("|");
  }

  // llama.cpp's qwen2 pre-tokeniser, and GPT-2's own pattern for other byte-level models.
  var PATTERNS = {
    qwen2: "|" + "[^\\r\\n\\p{L}\\p{N}]?\\p{L}+" + "|\\p{N}" +
           "| ?[^\\s\\p{L}\\p{N}]+[\\r\\n]*" + "|\\s*[\\r\\n]+" + "|\\s+(?!\\S)" + "|\\s+",
    gpt2: "|" + " ?\\p{L}+" + "| ?\\p{N}+" +
          "| ?[^\\s\\p{L}\\p{N}]+" + "|\\s+(?!\\S)" + "|\\s+"
  };

  function compilePretokenizer(pre) {
    var name = PATTERNS[pre] ? pre : "gpt2";
    var body = "(" + contractionAlternation() + ")" + PATTERNS[name];
    var re = null, used = null, uFlag = false;
    try { re = new RegExp(body, "gu"); used = name; uFlag = true; }
    catch (e) {
      try { re = new RegExp(body, "g"); used = name; }
      catch (e2) { re = null; used = null; }
    }
    return { re: re, name: used, unicode: uFlag };
  }

  function pretokenize(re, text) {
    if (!re) return [text];
    if (!re.global) return [text];
    re.lastIndex = 0;
    var out = [], m;
    while ((m = re.exec(text)) !== null) {
      if (m[0].length) out.push(m[0]);
      if (m.index === re.lastIndex) re.lastIndex++;   // never spin on a zero-length match
    }
    return out.length ? out : [text];
  }

  /* ---------------------------------------------------------------- merges */

  // "A B" -> rank, keyed on A + SEP + B. SEP is a character that cannot occur in the alphabet
  // (which is entirely printable and space-free), so keys cannot collide.
  var SEP = "\u0000";

  function buildMerges(list) {
    var rank = new Map(), i, s, at;
    for (i = 0; i < list.length; i++) {
      s = list[i];
      if (typeof s !== "string") continue;
      at = s.indexOf(" ");
      if (at < 1 || at === s.length - 1) continue;
      rank.set(s.slice(0, at) + SEP + s.slice(at + 1), i);
    }
    return rank;
  }

  // The standard BPE reduction: merge the lowest-ranked adjacent pair, ties going to the leftmost,
  // until no recorded merge applies.
  function bpeReduce(piece, rank) {
    var parts = [], i;
    for (i = 0; i < piece.length; i++) parts.push(piece.charAt(i));
    if (parts.length < 2) return parts;
    while (true) {
      var bestRank = Infinity, bestAt = -1, r;
      for (i = 0; i + 1 < parts.length; i++) {
        r = rank.get(parts[i] + SEP + parts[i + 1]);
        if (r !== undefined && r < bestRank) { bestRank = r; bestAt = i; }
      }
      if (bestAt < 0) break;
      parts.splice(bestAt, 2, parts[bestAt] + parts[bestAt + 1]);
    }
    return parts;
  }

  /* ---------------------------------------------------------------- greedy fallback */

  // Mirrors app.js's tokenize(): longest match first, whitespace skipped only when no symbol
  // matches at that position, unknown non-space characters kept as their own symbol.
  function makeGreedy(surfacesByPiece, maxLen) {
    var set = new Set(), i;
    surfacesByPiece.forEach(function (surface) { set.add(surface); });
    return function (text) {
      var toks = [], i = 0, n = text.length, best, limit, L, sub, c;
      while (i < n) {
        best = null;
        limit = Math.min(maxLen, n - i);
        for (L = limit; L >= 1; L--) {
          sub = text.substr(i, L);
          if (set.has(sub)) { best = sub; break; }
        }
        if (best) { toks.push(best); i += best.length; continue; }
        c = text.charAt(i);
        if (c === " " || c === "\n" || c === "\t" || c === "\r") { i += 1; continue; }
        toks.push(c);
        i += 1;
      }
      return toks;
    };
  }

  /* ---------------------------------------------------------------- the entry point */

  function fromVocab(vocab) {
    vocab = vocab || {};
    var model = vocab.model || "";
    var tokens = vocab.tokens || [];
    var merges = vocab.merges || [];
    var pre = vocab.pre || "";

    var idOf = new Map(), surfaceOfPiece = new Map(), i, t, surf;
    for (i = 0; i < tokens.length; i++) {
      t = tokens[i];
      if (typeof t !== "string") continue;
      if (!idOf.has(t)) idOf.set(t, i);
      if (model === "gpt2") surfaceOfPiece.set(t, decodePiece(t));
    }

    var rank = buildMerges(merges);
    var exact = model === "gpt2" && rank.size > 0;
    var pt = exact ? compilePretokenizer(pre) : { re: null, name: null, unicode: false };

    var surfaces = [];
    if (!exact) {
      var seen = new Set();
      for (i = 0; i < tokens.length; i++) {
        t = tokens[i];
        if (typeof t !== "string") continue;
        surf = decodeSurface(t, model);
        if (!surf || seen.has(surf)) continue;
        seen.add(surf);
        surfaces.push([t, surf]);
      }
    }
    var maxLen = 1;
    for (i = 0; i < surfaces.length; i++) if (surfaces[i][1].length > maxLen) maxLen = surfaces[i][1].length;
    var greedy = makeGreedy(new Map(surfaces), Math.min(maxLen, 24));

    function decodeSurface(piece, m) {
      if (m === "gpt2") return decodePiece(piece);
      var mm = /^<0x([0-9A-Fa-f]{2})>$/.exec(piece);
      if (mm) return bytesToString([parseInt(mm[1], 16)]);
      return piece.replace(/\u2581/g, " ");
    }

    // Exact path: pre-tokenise -> merge -> surface. Returns both surfaces and pieces, because the
    // id lookup needs the encoded piece while the page needs the decoded surface.
    function piecesFor(text) {
      if (!exact) return null;
      var words = pretokenize(pt.re, encodeText(text));
      var out = [], w, j, merged;
      for (w = 0; w < words.length; w++) {
        merged = bpeReduce(words[w], rank);
        for (j = 0; j < merged.length; j++) out.push(merged[j]);
      }
      return out;
    }

    function tokenize(text) {
      if (typeof text !== "string" || !text.length) return [];
      if (!exact) return greedy(text);
      var pieces = piecesFor(text), out = [], i2;
      for (i2 = 0; i2 < pieces.length; i2++) out.push(surfaceOfPiece.get(pieces[i2]) || decodePiece(pieces[i2]));
      return out;
    }

    function ids(text) {
      if (typeof text !== "string" || !text.length) return [];
      if (!exact) {
        var gs = greedy(text), out = [], i3, id;
        for (i3 = 0; i3 < gs.length; i3++) {
          id = idForSurface(gs[i3]);
          out.push(id);
        }
        return out;
      }
      var pieces = piecesFor(text), res = [], j, id2;
      for (j = 0; j < pieces.length; j++) {
        id2 = idOf.has(pieces[j]) ? idOf.get(pieces[j]) : byteFallbackId(pieces[j]);
        res.push(id2);
      }
      return res;
    }

    // reverse lookup for the fallback path, built lazily
    var surfaceIndexOf = null;
    function idForSurface(s) {
      if (!surfaceIndexOf) {
        surfaceIndexOf = new Map();
        for (var k = 0; k < surfaces.length; k++) if (!surfaceIndexOf.has(surfaces[k][1])) surfaceIndexOf.set(surfaces[k][1], surfaces[k][0]);
      }
      var piece = surfaceIndexOf.get(s);
      return piece !== undefined && idOf.has(piece) ? idOf.get(piece) : -1;
    }

    // A piece with no vocabulary entry is a byte sequence the vocabulary cannot represent; the
    // byte tokens <0xNN> on a SentencePiece vocabulary are the usual backstop. -1 means "no id".
    function byteFallbackId(piece) {
      if (piece.length !== 1) return -1;
      var hex = charToByte(piece.charCodeAt(0)).toString(16).toUpperCase();
      if (hex.length < 2) hex = "0" + hex;
      var key = "<0x" + hex + ">";
      return idOf.has(key) ? idOf.get(key) : -1;
    }

    return {
      model: model,
      pre: pre,
      exact: exact,
      pretokenizer: pt.name,
      unicodeRegex: pt.unicode,
      mergeCount: rank.size,
      vocabSize: tokens.length,
      tokenize: tokenize,
      ids: ids,
      encodeText: encodeText,
      decodePiece: decodePiece,
      pieces: piecesFor
    };
  }

  var api = { fromVocab: fromVocab, encodeText: encodeText, decodePiece: decodePiece,
              bytesToString: bytesToString, BYTE_TO_CHAR: BYTE_TO_CHAR, charToByte: charToByte,
              buildMerges: buildMerges, bpeReduce: bpeReduce };

  if (typeof module !== "undefined" && module.exports) module.exports = api;
  root.HDCBPE = api;
})(typeof globalThis !== "undefined" ? globalThis : this);