Regex Pattern Matcher

defmodule RegexMatcher do
  @moduledoc """
  A simple regex pattern matcher supporting basic operations:
  - Literal characters
  - . (any character)
  - * (zero or more of preceding character)
  - + (one or more of preceding character)
  - ? (zero or one of preceding character)
  - ^ (start of string)
  - $ (end of string)
  """

  def match(pattern, text) do
    match_here(pattern, text, 0, 0)
  end

  defp match_here(pattern, text, p_idx, t_idx) do
    cond do
      p_idx >= String.length(pattern) ->
        true

      p_idx + 1 < String.length(pattern) and String.at(pattern, p_idx + 1) == "*" ->
        match_star(String.at(pattern, p_idx), pattern, text, p_idx + 2, t_idx)

      p_idx + 1 < String.length(pattern) and String.at(pattern, p_idx + 1) == "+" ->
        match_plus(String.at(pattern, p_idx), pattern, text, p_idx + 2, t_idx)

      p_idx + 1 < String.length(pattern) and String.at(pattern, p_idx + 1) == "?" ->
        match_question(String.at(pattern, p_idx), pattern, text, p_idx + 2, t_idx)

      String.at(pattern, p_idx) == "$" and p_idx == String.length(pattern) - 1 ->
        t_idx == String.length(text)

      t_idx >= String.length(text) ->
        false

      match_char(String.at(pattern, p_idx), String.at(text, t_idx)) ->
        match_here(pattern, text, p_idx + 1, t_idx + 1)

      true ->
        false
    end
  end

  defp match_star(char, pattern, text, p_idx, t_idx) do
    # Try matching zero occurrences first
    if match_here(pattern, text, p_idx, t_idx) do
      true
    else
      # Try matching one or more occurrences
      match_star_helper(char, pattern, text, p_idx, t_idx)
    end
  end

  defp match_star_helper(char, pattern, text, p_idx, t_idx) do
    cond do
      t_idx >= String.length(text) ->
        false

      not match_char(char, String.at(text, t_idx)) ->
        false

      match_here(pattern, text, p_idx, t_idx + 1) ->
        true

      true ->
        match_star_helper(char, pattern, text, p_idx, t_idx + 1)
    end
  end

  defp match_plus(char, pattern, text, p_idx, t_idx) do
    cond do
      t_idx >= String.length(text) ->
        false

      not match_char(char, String.at(text, t_idx)) ->
        false

      true ->
        match_star(char, pattern, text, p_idx, t_idx + 1)
    end
  end

  defp match_question(char, pattern, text, p_idx, t_idx) do
    # Try matching zero occurrences
    if match_here(pattern, text, p_idx, t_idx) do
      true
    else
      # Try matching one occurrence
      if t_idx < String.length(text) and match_char(char, String.at(text, t_idx)) do
        match_here(pattern, text, p_idx, t_idx + 1)
      else
        false
      end
    end
  end

  defp match_char(".", _), do: true
  defp match_char(pattern_char, text_char), do: pattern_char == text_char

  def find_all_matches(pattern, text) do
    find_matches(pattern, text, 0, [])
  end

  defp find_matches(pattern, text, start_idx, matches) do
    cond do
      start_idx >= String.length(text) ->
        Enum.reverse(matches)

      String.at(pattern, 0) == "^" ->
        if match_here(String.slice(pattern, 1..-1), text, 0, start_idx) do
          [start_idx | matches]
        else
          matches
        end |> Enum.reverse()

      match_here(pattern, String.slice(text, start_idx..-1), 0, 0) ->
        find_matches(pattern, text, start_idx + 1, [start_idx | matches])

      true ->
        find_matches(pattern, text, start_idx + 1, matches)
    end
  end
end

# Example usage and tests
defmodule RegexMatcherTest do
  def run_tests do
    IO.puts("Running Regex Matcher Tests")
    IO.puts("===========================")

    test_cases = [
      {"hello", "hello world", true},
      {"h.llo", "hello world", true},
      {"wo.*d", "hello world", true},
      {"a*", "aaab", true},
      {"a+", "aaab", true},
      {"a+", "bbbb", false},
      {"colou?r", "color", true},
      {"colou?r", "colour", true},
      {"^hello", "hello world", true},
      {"^world", "hello world", false},
      {"world$", "hello world", true},
      {"hello$", "hello world", false},
      {"a.*b", "acccb", true},
      {"x+y*z", "xxxyyyzzz", true}
    ]

    Enum.each(test_cases, fn {pattern, text, expected} ->
      result = RegexMatcher.match(pattern, text)
      status = if result == expected, do: "✓", else: "✗"
      IO.puts("#{status} Pattern: '#{pattern}' Text: '#{text}' Expected: #{expected} Got: #{result}")
    end)

    IO.puts("\nFinding all matches:")
    text = "The cat in the hat sat"
    pattern = ".at"
    matches = RegexMatcher.find_all_matches(pattern, text)
    IO.puts("Pattern '#{pattern}' in '#{text}' found at positions: #{inspect(matches)}")
  end
end

RegexMatcherTest.run_tests()