# -*- coding: utf-8 -*-

"""
ตัดคำภาษาไทย 
โดยใช้หลักการ maximal matching และ Thai Character Cluster (TCC)
พัฒนาโดยคุณ Korakot Chaovavanich
Notebooks:
https://colab.research.google.com/notebook#fileId=1V1Z657_5eSWPo8rLfVRwA0A5E4vkg7SI
https://colab.research.google.com/drive/14Ibg-ngZXj15RKwjNwoZlOT32fQBOrBx#scrollTo=MYZ7NzAR7Dmw
"""
import re
from collections import defaultdict
from heapq import heappop, heappush  # for priority queue
from typing import List

from pythainlp.tokenize import DEFAULT_DICT_TRIE

from marisa_trie import Trie

from .tcc import tcc_pos

# ช่วยตัดพวกภาษาอังกฤษ เป็นต้น
_PAT_ENG = re.compile(
    r"""(?x)
[-a-zA-Z]+|   # english
\d[\d,\.]*|   # number
[ \t]+|       # space
\r?\n         # newline
"""
)

_PAT_TWOCHARS = re.compile("[ก-ฮ]{,2}$")


def _bfs_paths_graph(graph, start, goal):
    queue = [(start, [start])]
    while queue:
        (vertex, path) = queue.pop(0)
        for next in graph[vertex]:
            if next == goal:
                yield path + [next]
            else:
                queue.append((next, path + [next]))


def _onecut(text: str, custom_dict: Trie):
    graph = defaultdict(list)  # main data structure
    allow_pos = tcc_pos(text)  # separating position should aligned with TCC

    q = [0]  # min-heap queue
    last_p = 0  # last position for yield
    while q[0] < len(text):
        p = heappop(q)

        for w in custom_dict.prefixes(text[p:]):
            p_ = p + len(w)
            if p_ in allow_pos:  # เลือกที่สอดคล้อง tcc
                graph[p].append(p_)
                if p_ not in q:
                    heappush(q, p_)

        # กรณี length 1 คือ ไม่กำกวมแล้ว ส่งผลลัพธ์ก่อนนี้คืนได้
        if len(q) == 1:
            pp = next(_bfs_paths_graph(graph, last_p, q[0]))
            # เริ่มต้น last_p = pp[0] เอง
            for p in pp[1:]:
                yield text[last_p:p]
                last_p = p
            # สุดท้าย last_p == q[0] เอง

        # กรณี length 0 คือ ไม่มีใน dict
        if len(q) == 0:
            m = _PAT_ENG.match(text[p:])
            if m:  # อังกฤษ, เลข, ว่าง
                i = p + m.end()
            else:  # skip น้อยที่สุด ที่เป็นไปได้
                for i in range(p + 1, len(text)):
                    if i in allow_pos:  # ใช้ tcc ด้วย
                        ww = [
                            w
                            for w in custom_dict.prefixes(text[i:])
                            if (i + len(w) in allow_pos)
                        ]
                        ww = [w for w in ww if not _PAT_TWOCHARS.match(w)]
                        m = _PAT_ENG.match(text[i:])
                        if ww or m:
                            break
                else:
                    i = len(text)
            w = text[p:i]
            graph[p].append(i)
            yield w
            last_p = i
            heappush(q, i)


def segment(text: str, custom_dict: Trie = None) -> List[str]:
    """
    Dictionary-based word segmentation, using maximal matching algorithm and Thai Character Cluster
    :param str text: text to be tokenized to words
    :return: list of words, tokenized from the text    
    """
    if not text or not isinstance(text, str):
        return []

    if not custom_dict:
        custom_dict = DEFAULT_DICT_TRIE

    return list(_onecut(text, custom_dict))

@@ -21,40 +21,57 @@
 -*-%0A
-%0A
 %22%22%22%0A
-%E0%B8%95%E0%B8%B1%E0%B8%94%E0%B8%84%E0%B8%B3%E0%B8%A0%E0%B8%B2%E0%B8%A9%E0%B8%B2%E0%B9%84%E0%B8%97%E0%B8%A2 %0A%E0%B9%82%E0%B8%94%E0%B8%A2%E0%B9%83%E0%B8%8A%E0%B9%89%E0%B8%AB%E0%B8%A5%E0%B8%B1%E0%B8%81%E0%B8%81%E0%B8%B2%E0%B8%A3
+Dictionary-based Thai Word Segmentation%0Ausing
  max
@@ -88,11 +88,21 @@
 ing 
-%E0%B9%81%E0%B8%A5%E0%B8%B0
+algorithm and
  Tha
@@ -131,19 +131,35 @@
 CC)%0A
-%E0%B8%9E%E0%B8%B1%E0%B8%92%E0%B8%99%E0%B8%B2%E0%B9%82%E0%B8%94%E0%B8%A2%E0%B8%84%E0%B8%B8%E0%B8%93
+Based on these notebooks by
  Kor
@@ -179,18 +179,8 @@
 nich
-%0ANotebooks
 :%0Aht
@@ -490,16 +490,45 @@
 t List%0A%0A
+from marisa_trie import Trie%0A
 from pyt
@@ -573,38 +573,8 @@
 IE%0A%0A
-from marisa_trie import Trie%0A%0A
 from
@@ -3168,20 +3168,16 @@
 the text
-    
 %0A    %22%22%22

Update docstring