import math

import itertools

from abc import abstractmethod

from collections import deque

class ParsingError(Exception):

	pass

class Token:

	is_skippable = False

	@abstractmethod

	def list_first(self):

		pass

	@abstractmethod

	def list_last(self):

		pass

	@abstractmethod

	def list_neighbours(self):

		pass

class Lambda(Token):

	is_skippable = True

	def list_first(self):

		yield from []

	def list_last(self):

		yield from []

	def list_neighbours(self):

		yield from []

class Symbol(Token):

	def __init__(self, position, value):

		self.position = position

		self.value = value

	def list_first(self):

		yield self.position

	def list_last(self):

		yield self.position

		return RegexpDFA(rules, end_states, self.alphabet_index)

	def _find_equivalent_states(self):

		n = len(self.alphabet_index)

		state_list = list(range(len(self.rules) // n))

		equivalents = {(s1, s2) for (i, s1) in enumerate(state_list) for s2 in state_list[i+1:] if (s1 in self.end_states) == (s2 in self.end_states)}

		ctrl = True

		while ctrl:

			ctrl = False

			for (s1, s2) in equivalents.copy():

				for ci in range(n):

					t1 = self.rules[s1*n + ci]

					t2 = self.rules[s2*n + ci]

					key = (min(t1, t2), max(t1, t2))

					if t1 != t2 and key not in equivalents:

						equivalents.remove((s1, s2))

						ctrl = True

						break

		return equivalents

	def _collapse_states(self, equivalents):

		n = len(self.alphabet_index)

		rules = []

		eq_mapping = dict()

		for (s1, s2) in equivalents:

			eq_mapping[s2] = min(s1, eq_mapping.get(s2, math.inf))

		discard_mapping = dict()

		discard_count = 0

		for i in range(0, len(self.rules), n):

			si = i//n

			if si in eq_mapping:

				discard_count += 1

				continue

			discard_mapping[si] = si - discard_count

			rules.extend(map(lambda st: eq_mapping.get(st, st), self.rules[i:i+n]))

		rules = [discard_mapping[st] for st in rules]

		end_states = {discard_mapping[eq_mapping.get(st, st)] for st in self.end_states}

		return (rules, end_states)

	tests = ["", "a", "ab", "aabb", "abab", "abcd", "abcbcdbcd"]

	for pattern in ["a(b|c)", "a*b*", "(ab)*", "a((bc)*d)*", "(a|b)*a(a|b)(a|b)(a|b)", "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz"]:

		print("#", pattern)

		try:

			r = RegexpDFA.create(pattern).reduce().normalize()

		except ParsingError as e:

			print("Failed to parse the regexp:")

			print(e)

			continue

		for t in tests:

			print(t, r.match(t))

		print()

use regexp::Regexp;

	let tests = ["", "a", "ab", "aabb", "abab", "abcd", "abcbcdbcd"];

	for pattern in ["a(b|c)", "a*b*", "(ab)*", "a((bc)*d)*", "(a|b)*a(a|b)(a|b)(a|b)", "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz"] {

		println!("# {pattern}");

		let r = match Regexp::new(&pattern.to_string()) {

			Ok(r1) => r1.determinize().reduce().normalize(),

			Err(e) => {

				println!("{e}");

				continue;

			}

		};

		for &t in tests.iter() {

			println!("{t} {}", r.eval(t.to_string()));

		}

		println!();

	}

}