#![warn(missing_docs)]
//! This crate implements non-deterministic finite automata.
//!
//! By default this uses the graph from the crate [`graph`].  To use
//! another external graph, add a module in which the external graph
//! implements the Graph trait from the [`graph`] crate, and then use
//! that external graph type as [`Graph`][graph::Graph] here.

pub mod error;

extern crate graph;

use core::fmt::Display;

use std::ops::{Deref, DerefMut};

use graph::{Graph, GraphLabel, LabelGraph};

use error::Error;

pub use desrec::DesRec;

use default::regex::RegexType;

/// The expected behaviour of a regular language.
///
/// Nondeterministic finite automata are equivalent to regular
/// languages.  Since regular languages are easier to understand for a
/// human being, nondeterministic finite automata include the data for
/// the equivalent regular languages.
pub trait Regex<T: GraphLabel>: Graph + Display + Clone {
    /// Return the label of a vertex, or an error if the node is
    /// invalid.
    fn vertex_label(&self, node_id: usize) -> Result<T, Error>;

    #[inline]
    /// Return the root node of the regular language.
    ///
    /// Implementations can follow different conventions for the root
    /// node, and hence this function.
    ///
    /// If the regular language is empty, the implementation should
    /// return None.
    ///
    /// The default implementation uses the convention that the root
    /// node is always the first node.
    fn root(&self) -> Option<usize> {
        if self.is_empty() {
            None
        } else {
            Some(0)
        }
    }

    // TODO: add functions that determine if certain "positions" in a
    // regular language satisfy some special properties, like at the
    // end of a Kleene star, or at the end of a regular language, et
    // cetera.  These might be needed later.
}

/// Since Option<T> does not inherit the Display from T, we wrap it to
/// provide an automatic implementation of Display.
#[derive(Debug, Clone, Copy, Ord, PartialOrd, Eq, PartialEq, Hash)]
pub struct DOption<T>(Option<T>);

impl<T> Default for DOption<T> {
    fn default() -> Self {
        Self(None)
    }
}

impl<T> Deref for DOption<T> {
    type Target = Option<T>;

    fn deref(&self) -> &Self::Target {
        &self.0
    }
}

impl<T> DerefMut for DOption<T> {
    fn deref_mut(&mut self) -> &mut Self::Target {
        &mut self.0
    }
}

impl<T: Display> Display for DOption<T> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self.deref() {
            Some(value) => Display::fmt(value, f),
            None => write!(f, "ε"),
        }
    }
}

/// Substitute or Carry
///
/// This enumeration indicates whether a label from a regular
/// expression should be substituted by another regular expression, or
/// to be carried around in the resulting nondeterministic finite
/// automaton, in the process of the [`to_nfa`][Nfa::to_nfa] function.
///
/// # Transform labels
///
/// The label that is returned to be carried can be different from the
/// original label, as a way to transform the labels.
///
/// # Remark on the abbreviation
///
/// It happens "by chance" that this abbreviation coincides with the
/// abbreviation of "system on chip".  Since I know nothing about this
/// topic, this is just a meaningless pun.
#[derive(Debug, Copy, Clone)]
pub enum SoC<T> {
    /// To be substituted by another regular expression.
    Sub(usize),
    /// To carry around this label.
    Carry(T),
}

/// The expected behvaiour of a nondeterministic finite automaton.
///
/// Every NFA is a special labelled graph.
pub trait Nfa<T: GraphLabel>: LabelGraph<T> {
    /// Remove all empty transitions from the nondeterministic finite
    /// automaton.
    fn remove_epsilon(&mut self) -> Result<(), Error>;

    /// Return a state-minimal NFA equivalent with the original one.
    ///
    /// This is not required.  It is just to allow me to experiment
    /// with NFA optimization algorithms.
    fn minimize(&self) -> Result<Self, Error> {
        Err(Error::UnsupportedOperation)
    }

    /// When we convert a regular expression to a nondeterministic
    /// finite automaton, the label should be optional, so we use a
    /// different type for the result type.
    type FromRegex<S: GraphLabel + Display + Default>;

    /// Build a nondeterministic finite automaton out of a set of
    /// regular expressions.
    ///
    /// The SUB_PRED is a predicate function that returns an optional
    /// index for a label.  If it returns some index, then this means
    /// we should substitute the index-th regular expression in the
    /// set, whereever that label occurs in the set of regular
    /// expressions.
    fn to_nfa(
        regexps: &[impl Regex<RegexType<T>>],
        sub_pred: impl Fn(T) -> Result<SoC<T>, Error>,
    ) -> Result<Self::FromRegex<DOption<T>>, Error>;

    /// Remove all dead states from the nondeterministic finite
    /// automaton.
    ///
    /// A state is dead if there are no edges going to the state.
    fn remove_dead(&mut self) -> Result<(), Error>;

    /// For each edge from A to B whose edge is considered nullable by
    /// a function `f`, and for every edge from B to C, add an edge
    /// from A to C.
    ///
    /// This is needed specifically by the algorithm to produce a set
    /// of atomic languages that represent "null-closed" derived
    /// languages.
    fn nulling(&mut self, f: impl Fn(T) -> bool) -> Result<(), Error>;
}

pub mod default;
pub mod desrec;

#[cfg(test)]
mod nfa_tests {}