for (c, target_set) in new_rules.items():

				target_tup = tuple(sorted(target_set))

				if target_tup not in index:

					new_target = len(index)

					index[target_tup] = new_target

					compact_rules.extend([-1] * n)

					stack.append(target_tup)

				compact_rules[index[multistate]*n + alphabet_index[c]] = index[target_tup]

				if any(st in self.end_states for st in target_set):

					end_states.add(index[target_tup])

		return (compact_rules, end_states, alphabet_index)

class RegexpDFA:

	def __init__(self, rules, end_states, alphabet_index):

		self.rules = rules

		self.end_states = end_states

		self.alphabet_index = alphabet_index

	@classmethod

	def create(cls, pattern):

		r = Regexp(pattern)

		(rules, end_states, alphabet_index) = r.determinize()

		return cls(rules, end_states, alphabet_index)

	def match(self, s):

		st = 0

		n = len(self.alphabet_index)

		for c in s:

				return False

			key = (st*n + self.alphabet_index[c])

			st = self.rules[key]

		return st in self.end_states

	def reduce(self):

		equivalents = self._find_equivalent_states()

		(rules, end_states) = self._collapse_states(equivalents)

		return RegexpDFA(rules, end_states, self.alphabet_index)

	def normalize(self):

		n = len(self.alphabet_index)

		queue = deque([0])

		rules = []

		while queue:

			si = queue.popleft()

			row = self.rules[si*n:(si+1)*n]

			for sj in row:

				if sj not in index:

					queue.append(sj)

			rules.extend(index[sj] for sj in row)

		end_states = {index[si] for si in self.end_states}

		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)}

						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_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}

use std::{collections::{HashMap, HashSet, VecDeque}, iter};

mod token;

pub use token::ParsingError;

use token::parse;

const START_NFA: usize = usize::MAX;

const START_DFA: usize = 0;

fn encode_set(set: &HashSet<usize>) -> String {

	let mut v = Vec::from_iter(set.iter());

	v.sort();

	let res: Vec<String> = v.into_iter().map(|x| x.to_string()).collect();

	return res.join(",");

}

#[derive(Debug)]

pub struct Regexp {

	rules: HashMap<(usize, char), HashSet<usize>>,

	end_states: HashSet<usize>,

					new_multistate = new_multistate.union(&x).map(|&y| y).collect();

				} else if let Some(x) = self.rules.get(&(state, '.')) {

					new_multistate = new_multistate.union(&x).map(|&y| y).collect();

				}

			}

			multistate = new_multistate;

		}

		return multistate.iter().any(|x| self.end_states.contains(x));

	}

	pub fn determinize(&self) -> RegexpDFA {

		let alphabet_index: HashMap<char, usize> = self.alphabet.iter().enumerate().map(|(i, c)| (*c, i)).collect();

		let n = alphabet_index.len();

		let mut compact_rules = vec![FAIL; n];

		let mut end_states: HashSet<usize> = HashSet::new();

		if self.end_states.contains(&START_NFA) {end_states.insert(START_DFA);}

		// string hash -> single int DFA state

		let mut index_new = HashMap::from([(START_NFA.to_string(), START_DFA)]);

		// string hash -> HashSet NFA multistate

		let mut index_multi = HashMap::from([(START_NFA.to_string(), HashSet::from([START_NFA]))]);

		let mut stack = Vec::from([START_NFA.to_string()]);

					index_new.insert(target_hash.clone(), target_new);

					index_multi.insert(target_hash.clone(), target_set);

					compact_rules.extend(iter::repeat(FAIL).take(n));

					stack.push(target_hash.clone());

				}

				compact_rules[index_new[&state_hash]*n + alphabet_index[&c]] = index_new[&target_hash];

				if is_end {

					end_states.insert(index_new[&target_hash]);

				}

			}

		}

		return RegexpDFA{rules: compact_rules, end_states, alphabet_index};

	}

}

pub struct RegexpDFA {

	rules: Vec<usize>,

	end_states: HashSet<usize>,

	alphabet_index: HashMap<char, usize>

}

impl RegexpDFA {

	pub fn eval(&self, s: String) -> bool {

		let n = self.alphabet_index.len();

		let mut state = START_DFA;

		for c in s.chars() {

			if let Some(ci) = self.alphabet_index.get(&c) {

				state = self.rules[state*n + ci];

			} else {

				return false;

			}

				return false;

			}

		}

		return self.end_states.contains(&state);

	}

	pub fn reduce(&self) -> RegexpDFA {

		if self.alphabet_index.len() == 0 {

			return RegexpDFA{rules: self.rules.clone(), end_states: self.end_states.clone(), alphabet_index: self.alphabet_index.clone()};

		}

		let equivalents = self.find_equivalent_states();

		return self.collapse_states(equivalents);

	}

	pub fn normalize(&self) -> RegexpDFA {

		let n = self.alphabet_index.len();

		if n == 0 {

			return RegexpDFA{rules: self.rules.clone(), end_states: self.end_states.clone(), alphabet_index: self.alphabet_index.clone()}; 

		}

		let m = self.rules.len()/n;

		index[0] = 0;

		let mut queue = VecDeque::from([START_DFA]);

		let mut rules = vec![];

		let mut k = 1;

		while !queue.is_empty() {

			let si = queue.pop_front().unwrap();

			let row = &self.rules[si*n..(si+1)*n];

			for &sj in row {

					index[sj] = k;

					k += 1;

					queue.push_back(sj);

				}

			}

		}

		let end_states = self.end_states.iter().map(|st| index[*st]).collect();

		return RegexpDFA{rules, end_states, alphabet_index: self.alphabet_index.clone()};

	}

	fn find_equivalent_states(&self) -> Vec<(usize, usize)> {

		let n = self.alphabet_index.len();

		let state_vec: Vec<usize> = (0..self.rules.len()/n).collect();

		let mut equivalents = HashSet::new();

		state_vec.iter().enumerate().for_each(|(i, s1)| {

			eq_mapping[s2] = eq_mapping[s2].min(s1);

		}

		let mut discard_mapping: Vec<usize> = ((0..m)).collect();

		let mut discard_count = 0;

		for si in 0..m {

			if eq_mapping[si] != si {

				discard_count += 1;

				continue;

			}

			discard_mapping[si] = si-discard_count;

		}

		let end_states = self.end_states.iter().map(|st| discard_mapping[eq_mapping[*st]]).collect();

		return RegexpDFA{rules, end_states, alphabet_index: self.alphabet_index.clone()};

	}

}