import tkinter as tk
from collections import namedtuple

Snapshot = namedtuple("Snapshot", "text label")
default_snapshot = Snapshot("...\n...", 'Press the "Search!" button.')
snapshots = [default_snapshot]
snapshot_index = 0

DEFAULT_HAYSTACK = "Better than the bitter butter made her latter bitter batter better."
DEFAULT_NEEDLE = "batter"

BGCOLOR = "#333333"
BGCOLOR2 = "black"
FONTCOLOR = "#ffffff"
FONT = "Consolas"


def preprocess(needle):
    def lex_search(needle, invert_alphabet):
        max_suffix = 0
        candidate = 1
        k = 0
        period = 1

        while candidate + k < len(needle):
            text = '\n'.join(["Needle:    " + needle,
                              "candidate: " + " " * candidate + "^" * (k + 1),
                              "best:      " + " " * max_suffix + "^" * (k + 1),
                              ])
            label = (f"Potential period: {period}   "
                     f"invert: {invert_alphabet}")

            a = needle[candidate + k]
            b = needle[max_suffix + k]
            condition = (a < b) if invert_alphabet else (b < a)
            if condition:
                msg = "Candidate is worse."
                candidate += k + 1
                k = 0
                period = candidate - max_suffix
            elif a == b:
                if k + 1 != period:
                    msg = "Keep scanning."
                    k += 1
                else:
                    msg = "Matched a whole period."
                    candidate += period
                    k = 0
            else:
                msg = "Candidate is better."
                max_suffix = candidate
                candidate += 1
                k = 0
                period = 1

            yield Snapshot(text=text,
                           label=label + "\n" + msg)

        return max_suffix, period

    cut1, period1 = yield from lex_search(needle, False)
    cut2, period2 = yield from lex_search(needle, True)

    cut, period = max([(cut1, period1),
                       (cut2, period2)])

    left, right = needle[:cut], needle[cut:]
    periodic = (needle[:cut] == needle[period:period + cut])
    pstr = "(periodic)" if periodic else "(not periodic)"

    yield Snapshot(
        text=f'''Split: "{left}" + "{right}"''',
        label=f'''period: {period} {pstr}'''
    )

    return cut, period, periodic


def walkthrough(needle, haystack):
    cut, period, periodic = yield from preprocess(needle)

    j = 0
    if periodic:
        pass
    else:
        period = max(cut, len(needle) - cut) + 1

    memory = 0
    while j <= len(haystack) - len(needle):
        i = cut
        if periodic and memory > cut:
            i = memory

        while i < len(needle) and needle[i] == haystack[j + i]:
            yield Snapshot(
                haystack + '\n'
                + ' ' * j + needle + '\n'
                + ' ' * (j + cut) + "^" * (i - cut + 1),
                ""
            )
            i += 1
        if i >= len(needle):
            i = cut - 1
            while i >= 0 and needle[i] == haystack[j + i]:
                yield Snapshot(
                    haystack + '\n'
                    + ' ' * j + needle + '\n'
                    + ' ' * (j + i) + "^" * (len(needle) - i),
                    ""
                )
                i -= 1
            if i < 0:
                return j
            yield Snapshot(
                haystack + '\n'
                + ' ' * j + needle + '\n'
                + ' ' * (j + i) + "X" + "^" * (len(needle) - i - 1),
                f"Right half matched, so jump by {period}"
                + ("\nRemember the right half's progress!" if periodic else "")
            )
            memory = len(needle) - period
            j += period
        else:
            yield Snapshot(
                haystack + '\n'
                + ' ' * j + needle + '\n'
                + ' ' * (j + cut) + "^" * (i - cut) + "X",
                f"Matched {i - cut}, so jump ahead by {i - cut + 1}."
            )
            j += i - cut + 1
            memory = 0
    return -1


######################################################


window = tk.Tk()
window.title("Crochemore & Perrin's Two-Way Algorithm")
window.configure(background=BGCOLOR)

haystack_box = tk.Entry(
    width=80,
    font=FONT,
    bg=BGCOLOR2,
    fg=FONTCOLOR,
    insertbackground="#7777ff",
)
haystack_box.insert(0, DEFAULT_HAYSTACK)
haystack_box.pack()

needle_box = tk.Entry(
    width=80,
    font=FONT,
    bg=BGCOLOR2,
    fg=FONTCOLOR,
    insertbackground="#7777ff"
)
needle_box.insert(0, DEFAULT_NEEDLE)
needle_box.pack()

start_button = tk.Button(
    width=20,
    height=3,
    text="Search!",
    font=FONT,
    bg="#000077",
    fg=FONTCOLOR,
)
start_button.pack()


def start_search(event):
    haystack = haystack_box.get()
    needle = needle_box.get()

    global snapshots, snapshot_index
    snapshots = list(walkthrough(needle, haystack))
    snapshot_index = 0
    display_snapshot(snapshots[0])


start_button.bind("<Button-1>", start_search)

output_label_var = tk.StringVar()

output_text = tk.Text(
    width=80,
    height=3,
    font=FONT,
    bg=BGCOLOR2,
    fg=FONTCOLOR,
)
output_text.pack()

output_label = tk.Label(
    width=80,
    textvariable=output_label_var,
    font=FONT,
    bg=BGCOLOR,
    fg=FONTCOLOR,
)
output_label.pack()


def display_snapshot(s: Snapshot):
    output_text.delete("1.0", tk.END)
    output_text.insert("1.0", s.text)
    output_label_var.set(s.label)


display_snapshot(default_snapshot)

bottom_buttons = tk.Frame()
bottom_buttons.pack()

prev_button = tk.Button(
    width=20, height=3,
    master=bottom_buttons,
    text="<--\n(or arrow key)",
    bg="#770000",
    font=FONT,
    fg=FONTCOLOR,
)
prev_button.grid(row=0, column=0)

next_button = tk.Button(
    width=20,
    height=3,
    master=bottom_buttons,
    text="-->\n(or arrow key)",
    bg="#007700",
    font=FONT,
    fg=FONTCOLOR,
)
next_button.grid(row=0, column=1)


def step_forward(event):
    global snapshot_index
    if snapshot_index < len(snapshots) - 1:
        snapshot_index += 1
        display_snapshot(snapshots[snapshot_index])


next_button.bind("<Button-1>", step_forward)


def step_back(event):
    global snapshot_index
    if snapshot_index > 0:
        snapshot_index -= 1
        display_snapshot(snapshots[snapshot_index])


prev_button.bind("<Button-1>", step_back)

keymap = {
    "Right": step_forward,
    "Left": step_back,
    "Enter": start_search,
}

def key_pressed(event):
    f = keymap.get(event.keysym)
    if f is not None:
        f(event)

window.bind("<Key>", key_pressed)


def test():
    def run_walkthrough(needle, haystack):
        try:
            gen = walkthrough(needle, haystack)
            while True:
                next(gen)
        except StopIteration as e:
            return e.value

    import random
    rr = random.randrange
    for i in range(100):
        haystack = "".join(random.choices("abc", k=rr(20)))
        rand_string = "".join(random.choices("abc", k=rr(5)))
        rand_sub = haystack[rr(21):rr(21)]

        for p in rand_string, rand_sub:
            expected = haystack.find(p)
            actual = run_walkthrough(p, haystack)
            assert actual == expected, (p, haystack)

    print(f"{i + 1} tests ok.")


if __name__ == '__main__':
    test()
    window.mainloop()