Test.lean

import LeanAlgorithms.Trie
import LeanAlgorithms.Queue
import LeanAlgorithms.AhoCorasick
open Std
open LeanAlgorithms
open Trie

def testQueue : IO Unit := do
  IO.println "Testing Queue..."

  let q0 := LeanAlgorithms.Queue.empty
  let q1 := q0.enqueue 1
  let q2 := q1.enqueue 2
  let q3 := q2.enqueue 3

  let (val, q4) := q3.dequeue!
  if val != 1 then throw (IO.userError s!"Expected 1, got {val}")

  let q5 := q4.enqueue 4

  let (v2, q6) := q5.dequeue!
  if v2 != 2 then throw (IO.userError s!"Expected 2, got {v2}")

  let (v3, q7) := q6.dequeue!
  if v3 != 3 then throw (IO.userError s!"Expected 3, got {v3}")

  let (v4, q8) := q7.dequeue!
  if v4 != 4 then throw (IO.userError s!"Expected 4, got {v4}")

  if !q8.isEmpty then
    throw (IO.userError s!"Queue should be empty! State: {repr q8}")
  else
    IO.println "✅ Queue Logic Passed"

def testTrie : IO Unit := do
  IO.println "Testing Trie..."
  let trie : Trie := {}
  let insertWords : TrieM Unit := do
    insert "cat"
    insert "car"
    insert "cart"
    insert "dog"
    insert "doom"

  let (_, finalTrie) := insertWords.run trie

  let check(word: String)(expected: Bool) : IO Unit := do
    let (result, _) := (search word).run finalTrie
    if result == expected then
      IO.println s!"✅ PASS: search \"{word}\" -> {result}"
    else
      IO.println s!"❌ FAIL: search \"{word}\" -> {result} (Expected {expected})"

  check "car" true
  check "cat" true
  check "cart" true
  check "dog" true
  check "doom" true
  check "animal" false
  check "ca" false
  check "can" false

  IO.println (repr finalTrie)
  IO.println "✅ Trie Logic Passed"

def testAhoCorasick (patterns : List String) (text : String) (expected : List (Nat × Nat)): IO Unit := do
  IO.println "Testing Aho-Corasick..."

  let workflow : TrieM (List (Nat × Nat)) := do
    for pattern in patterns do
      insert pattern

    AhoCorasick.buildFailureLinks

    AhoCorasick.findPatterns text

  let emptyTrie : Trie := {}
  let (result, _) := workflow.run emptyTrie

  if result == expected then
    IO.println "✅ Aho-Corasick Logic Passed"
  else
    IO.println s!"❌ FAIL: Text '{text}'"
    IO.println s!"   Expected: {expected}"
    IO.println s!"   Got:      {result}"


def main : IO Unit := do
  testQueue
  testTrie
  testAhoCorasick
    ["he", "she", "hers", "his"]
    "ushers"
    [(3, 3), (3, 2), (5, 4)]

  IO.println "🎉 ALL TESTS PASSED 🎉"