"""Consonant-skeleton index over the lexicon: a storage-free 'romanization memory'.
Both the Devanagari lexicon word and the romanized input are reduced to a coarse consonant-class string
(vowels, y, aspiration, nukta, halant dropped; n/m/anusvara merged; repeats collapsed). The index is built at load time
from lex.bin (no extra bytes shipped). At query time, lexicon words sharing the input's skeleton (top-K by frequency)
become candidates and are scored by the model (teacher-forced). The JS runtime (release/space/js/aksharalp.mjs) mirrors
these tables exactly -- keep them in sync."""
DEV = {}
for chars, c in (("कखक़ख़", "K"), ("गघग़", "G"), ("चछ", "C"), ("जझज़", "J"), ("टठतथ", "T"), ("डढदधड़ढ़", "D"),
                 ("ङञणनऩमंँ", "N"), ("पफफ़", "P"), ("बभ", "B"), ("रऱऋृ", "R"), ("लळ", "L"), ("व", "V"), ("शषस", "S"),
                 ("हः", "H")):
    for ch in chars:
        if ch != "\u093c": DEV[ch] = c
DEV.pop("\u093c", None)   # nukta: dropped (NFC keeps क़ etc. decomposed)
ROM1 = dict(k="K", q="K", g="G", j="J", z="J", t="T", d="D", n="N", m="N", p="P", f="P", b="B", r="R", l="L", v="V", w="V",
            s="S", h="H")
ASP = set("kgcjtdpbsz")   # consonant + h -> same class (h dropped); 'sh' -> S, 'ch' -> C


def dev_skel(w):
    out = []
    for ch in w:
        c = DEV.get(ch)
        if c and (not out or out[-1] != c): out.append(c)
    return "".join(out)


def rom_skels(w, maxk=4):
    """Skeletons of a roman word, ambiguity expanded (c -> K|S, ch -> C|K, tion -> SN|TN), at most maxk."""
    w = w.lower(); outs = [""]; i = 0; n = len(w)
    while i < n:
        ch = w[i]; step = 1
        if ch in "ts" and w.startswith("ion", i + 1):
            opts = ["SN", "TN"] if ch == "t" else ["SN"]; step = 4
        elif ch == "c":
            nx = w[i + 1] if i + 1 < n else ""
            if nx == "h":
                opts = ["C", "K"]; step = 2
                while i + step < n and w[i + step] in "ch": step += 1      # chh, chch
            elif nx in ("e", "i", "y"): opts = ["S", "K"]
            elif nx == "k": opts = ["K"]; step = 2
            else: opts = ["K", "S"]
        elif ch == "x": opts = ["KS"]
        elif ch in ASP and i + 1 < n and w[i + 1] == "h":
            opts = [ROM1.get(ch, "")]; step = 2
            while i + step < n and w[i + step] == "h": step += 1
        else: opts = [ROM1.get(ch, "")]
        new = []
        for o in outs:
            for p in opts:
                s = o
                for c in p:
                    if not s or s[-1] != c: s += c
                new.append(s)
        outs = list(dict.fromkeys(new))[:maxk]; i += step
    return outs


class SkelIndex:
    def __init__(self, words, uni):
        """words: lexicon list; uni(i) -> unigram log-prob. Buckets keep ids sorted by frequency (desc)."""
        b = {}
        for i, w in enumerate(words):
            k = dev_skel(w)
            if k: b.setdefault(k, []).append(i)
        for k, v in b.items(): v.sort(key=lambda i: (-uni(i), i))
        self.b = b

    def lookup(self, roman, topk=24):
        seen = []; S = set()
        for k in rom_skels(roman):
            for i in self.b.get(k, ())[:topk]:
                if i not in S: S.add(i); seen.append(i)
        return seen


# ---- cheap rule romanizer + edit distance prefilter (rank skeleton-bucket words before model scoring)
_C = dict(zip("कखगघङचछजझञटठडढणतथदधनपफबभमयरलवशषसहळ",
              "k kh g gh n ch chh j jh n t th d dh n t th d dh n p ph b bh m y r l v sh sh s h l".split()))
_V = dict(zip("अआइईउऊऋएऐओऔऑ", "a aa i ee u oo ri e ai o au o".split()))
_M = dict(zip("ािीुूृेैोौॉॅ", "a i ee u oo ri e ai o au o e".split()))


def dev_rom(w):
    out = []; L = len(w)
    for j, ch in enumerate(w):
        if ch in _C:
            out.append(_C[ch]); nx = w[j + 1] if j + 1 < L else ""
            if nx == "\u093c": nx = w[j + 2] if j + 2 < L else ""
            if nx and nx not in _M and nx != "\u094d" and j + 1 < L - 1: out.append("a")
        elif ch in _V: out.append(_V[ch])
        elif ch in _M: out.append(_M[ch])
        elif ch in "ंँ": out.append("n")
        elif ch == "ः": out.append("h")
        elif ch == "\u093c" and out:
            out[-1] = {"k": "q", "kh": "kh", "g": "g", "j": "z", "ph": "f", "d": "r", "dh": "rh"}.get(out[-1], out[-1])
    return "".join(out)


def lev(a, b):
    if len(a) < len(b): a, b = b, a
    prev = list(range(len(b) + 1))
    for i, ca in enumerate(a, 1):
        cur = [i]
        for j, cb in enumerate(b, 1):
            cur.append(min(prev[j] + 1, cur[j - 1] + 1, prev[j - 1] + (ca != cb)))
        prev = cur
    return prev[-1]