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

mod token;
pub use token::ParsingError;
use token::{Token, parse};

const START: usize = usize::MAX;

fn encode_set(set: &HashSet<usize>) -> u64 {
	let mut res = 0;
	for x in set.iter() {
		res ^= 1<<x;
	}
	return res;
}

fn decode_set(x: u64) ->HashSet<usize> {
	if x == START as u64 {return HashSet::from([START]);}

	let mut x = x;
	let mut res: HashSet<usize> = HashSet::new();
	
	while x > 0 {
		let y = x.trailing_zeros();
		res.insert(y as usize);
		x ^= 1 << y;
	}

	return res;
}

#[derive(Debug)]
pub struct Regexp {
	rules: HashMap<(usize, char), HashSet<usize>>,
	end_states: HashSet<usize>
}

impl Regexp {
	pub fn new(pattern: &String) -> Result<Regexp, ParsingError> {
		let r = parse(pattern, 0)?;
		let pattern_chars = Vec::from_iter(pattern.chars());
		let mut rules: HashMap<(usize, char), HashSet<usize>> = HashMap::new();
		
		for i in r.list_first() {
			let c = pattern_chars[i];
			let key = (START, c);
			match rules.get_mut(&key) {
				Some(set) => {set.insert(i);},
				None => {rules.insert(key, HashSet::from([i]));}
			};
		}

		for (i, j) in r.list_neighbours() {
			let c = pattern_chars[j];
			let key = (i, c);
			match rules.get_mut(&key) {
				Some(set) => {set.insert(j);},
				None => {rules.insert(key, HashSet::from([j]));}
			};
		}

		let mut end_states = HashSet::from_iter(r.list_last().into_iter());
		if r.is_skippable() {
			end_states.insert(START);
		}

		return Ok(Regexp{rules, end_states});
	}

	pub fn eval(&self, s: String) -> bool {
		let mut multistate = HashSet::from([START]);

		for c in s.chars() {
			let mut new_multistate = HashSet::new();

			for state in multistate {
				if let Some(x) = self.rules.get(&(state, c)) {
					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 mut rules: HashMap<(u64, char), u64> = HashMap::new();
		let mut end_states: HashSet<u64> = HashSet::new();
		if self.end_states.contains(&START) {end_states.insert(START as u64);}

		let mut stack = Vec::from([START as u64]);
		let mut processed_states = HashSet::new();
		while !stack.is_empty() {
			let state = stack.pop().unwrap();
			let multistate = decode_set(state);
			let mut new_rules: HashMap<char, HashSet<usize>> = HashMap::new();

			for key in self.rules.keys().filter(|key| multistate.contains(&key.0)) {
				let (_st, c) = key;
				if !new_rules.contains_key(c) {
					new_rules.insert(*c, HashSet::new());
				}
				for target in &self.rules[key] {
					new_rules.get_mut(c).unwrap().insert(*target);
				}
			}

			for (c, target_set) in new_rules.into_iter() {
				let encoded_target = encode_set(&target_set);
				rules.insert((state, c), encoded_target);
				if target_set.iter().any(|st| self.end_states.contains(st)) {
					end_states.insert(encoded_target);
				}
				if !processed_states.contains(&encoded_target) {
					stack.push(encoded_target);
					processed_states.insert(encoded_target);
				}
			}
		}

		return RegexpDFA{rules, end_states};
	}
}

pub struct RegexpDFA {
	rules: HashMap<(u64, char), u64>,
	end_states: HashSet<u64>
}

impl RegexpDFA {
	pub fn eval(&self, s: String) -> bool {
		let mut state = START as u64;

		for c in s.chars() {
			if let Some(x) = self.rules.get(&(state, c)) {
				state = *x;
			} else {
				return false;
			}
		}

		return self.end_states.contains(&state);
	}
}