//! A builder implementation that produces regular expressions in approximately-similar canonical form.

use std::cmp::Ordering;
use std::marker::PhantomData;

use crate::Builder;
use crate::Regex;

#[derive(Clone, Debug, Hash, PartialEq, Eq)]
pub struct ApproximatelySimilarCanonical<S> {
    _phantom: PhantomData<S>,
}

impl<S: Ord> Builder for ApproximatelySimilarCanonical<S> {
    type Symbol = S;

    #[inline]
    fn empty_set() -> Regex<Self> {
        Regex::EmptySet
    }

    #[inline]
    fn empty_string() -> Regex<Self> {
        Regex::EmptyString
    }

    #[inline]
    fn symbol(value: Self::Symbol) -> Regex<Self> {
        Regex::Symbol(value)
    }

    fn closure(inner: Regex<Self>) -> Regex<Self> {
        match inner {
            // ()* --> e
            Regex::EmptySet => Self::empty_string(),
            // e* --> e
            Regex::EmptyString => Self::empty_string(),
            // e** --> e*
            Regex::Closure(inner) => Regex::Closure(inner),
            // (build)
            inner => Regex::Closure(inner.into()),
        }
    }

    fn concat(left: Regex<Self>, right: Regex<Self>) -> Regex<Self> {
        match (left, right) {
            // (R S) T) --> R (S T)
            (Regex::Concat(left_left, left_right), right) => {
                Self::concat(*left_left, Self::concat(*left_right, right))
            }
            // 0 R --> 0
            (left @ Regex::EmptySet, _) => left,
            (_, right @ Regex::EmptySet) => right,
            // e R --> R
            (Regex::EmptyString, right) => right,
            (left, Regex::EmptyString) => left,
            // (build)
            (left, right) => Regex::Concat(left.into(), right.into()),
        }
    }

    fn or(left: Regex<Self>, right: Regex<Self>) -> Regex<Self> {
        match (left, right) {
            // R | R --> R
            (left, right) if left == right => left,
            // (R | S) | T --> R | (S | T)
            (Regex::Or(left_left, left_right), right) => {
                Self::or(*left_left, Self::or(*left_right, right))
            }
            // 0 | R --> R
            (Regex::EmptySet, right) => right,
            (left, Regex::EmptySet) => left,
            // !0 | R --> !0
            (left, _) if left.is_empty_set_complement() => left,
            (_, right) if right.is_empty_set_complement() => right,
            // R | S --> ... with R != _|_
            (left, mut right) => {
                let mut items = Vec::new();
                items.push(left);
                while let Regex::Or(right_left, right_right) = right {
                    items.push(*right_left);
                    right = *right_right;
                }
                items.push(right);
                items.sort_by(cmp);
                items
                    .into_iter()
                    .rev()
                    .reduce(|r, l| Regex::Or(l.into(), r.into()))
                    .expect("at least two items")
            }
        }
    }

    fn and(left: Regex<Self>, right: Regex<Self>) -> Regex<Self> {
        match (left, right) {
            // R & R --> R
            (left, right) if left == right => left,
            // (R & S) & T --> R & (S & T)
            (Regex::And(left_left, left_right), right) => {
                Self::and(*left_left, Self::and(*left_right, right))
            }
            // 0 & R --> 0
            (left @ Regex::EmptySet, _) => left,
            (_, right @ Regex::EmptySet) => right,
            // !0 & R --> R
            (left, right) if left.is_empty_set_complement() => right,
            (left, right) if right.is_empty_set_complement() => left,
            // R & S --> ... with R != _&_
            (left, mut right) => {
                let mut items = Vec::new();
                items.push(left);
                while let Regex::And(right_left, right_right) = right {
                    items.push(*right_left);
                    right = *right_right;
                }
                items.push(right);
                items.sort_by(cmp);
                items
                    .into_iter()
                    .rev()
                    .reduce(|r, l| Regex::And(l.into(), r.into()))
                    .expect("at least two items")
            }
        }
    }

    fn complement(inner: Regex<Self>) -> Regex<Self> {
        match inner {
            // !!R --> R
            Regex::Complement(inner) => *inner,
            // (build)
            inner => Regex::Complement(inner.into()),
        }
    }
}

fn cmp<B: Builder>(left: &Regex<B>, right: &Regex<B>) -> Ordering
where
    B::Symbol: Ord,
{
    match (left, right) {
        (Regex::Symbol(left_value), Regex::Symbol(right_value)) => left_value.cmp(right_value),
        (Regex::Concat(left_left, left_right), Regex::Concat(right_left, right_right)) => {
            cmp(left_left, right_left).then(cmp(left_right, right_right))
        }
        (Regex::Closure(left_inner), Regex::Closure(right_inner)) => cmp(&left_inner, &right_inner),
        (Regex::Or(left_left, left_right), Regex::Or(right_left, right_right)) => {
            cmp(left_left, right_left).then(cmp(left_right, right_right))
        }
        (Regex::And(left_left, left_right), Regex::And(right_left, right_right)) => {
            cmp(left_left, right_left).then(cmp(left_right, right_right))
        }
        (Regex::Complement(left_inner), Regex::Complement(right_inner)) => {
            cmp(&left_inner, &right_inner)
        }
        (left, right) => rank(left).cmp(&rank(right)),
    }
}

fn rank<B: Builder>(re: &Regex<B>) -> usize {
    match re {
        Regex::EmptySet => 1,
        Regex::EmptyString => 2,
        Regex::Symbol(_) => 3,
        Regex::Concat(_, _) => 4,
        Regex::Closure(_) => 5,
        Regex::Or(_, _) => 6,
        Regex::And(_, _) => 7,
        Regex::Complement(_) => 8,
    }
}

#[cfg(test)]
mod tests {
    use crate::ops::*;
    use crate::Pure;

    use super::*;

    #[test]
    fn test_canonical_forms() {
        let tests: Vec<(
            Regex<ApproximatelySimilarCanonical<usize>>,
            Regex<Pure<usize>>,
        )> = vec![
            (().r(), ().r()),
            (().r().c(), [].r()),
            ([].r().c(), [].r()),
            (11.s() & [42.s(), ().r()].r(), ().r()),
            (42.s() & 11.s() & 17.s(), 11.s() & (17.s() & 42.s())),
            (42.s() & !11.s() & 17.s(), 17.s() & (42.s() & !11.s())),
            (42.s() | 11.s() | 17.s(), 11.s() | (17.s() | 42.s())),
            (42.s() | !11.s() | 17.s(), 17.s() | (42.s() | !11.s())),
            (!42.s() & !11.s(), !11.s() & !42.s()),
        ];
        for test in tests {
            assert_eq!(test.1, test.0.rebuild());
        }
    }

    #[test]
    fn test_equivalent_forms() {
        let tests: Vec<(
            Regex<ApproximatelySimilarCanonical<usize>>,
            Regex<ApproximatelySimilarCanonical<usize>>,
        )> = vec![
            (11.s() & 42.s() & 7.s(), 7.s() & 42.s() & 11.s()),
            (11.s() & 7.s() & 42.s(), 42.s() & 7.s() & 11.s()),
            (11.s() | 42.s() | 7.s(), 7.s() | 42.s() | 11.s()),
            (11.s() | 7.s() | 42.s(), 42.s() | 7.s() | 11.s()),
            (42.s().c().c(), 42.s().c()),
        ];
        for test in tests {
            assert_eq!(test.1, test.0.rebuild());
        }
    }
}