rustfst 0.5.0

use failure::Fallible;

use crate::algorithms::dfs_visit::dfs_visit;
use crate::algorithms::visitors::SccVisitor;
use crate::algorithms::{Queue, QueueType};
use crate::fst_properties::FstProperties;
use crate::fst_traits::{ExpandedFst, MutableFst};
use crate::semirings::{Semiring, SemiringProperties};

use super::{
    natural_less, FifoQueue, LifoQueue, NaturalShortestFirstQueue, SccQueue, StateOrderQueue,
    TopOrderQueue, TrivialQueue,
};
use crate::algorithms::arc_filters::ArcFilter;

#[derive(Debug)]
pub struct AutoQueue {
    queue: Box<dyn Queue>,
}

impl AutoQueue {
    pub fn new<F: MutableFst + ExpandedFst, A: ArcFilter<F::W>>(
        fst: &F,
        distance: Option<&Vec<F::W>>,
        arc_filter: &A,
    ) -> Fallible<Self>
    where
        F::W: 'static,
    {
        let props = fst.properties()?;

        let queue: Box<dyn Queue>;

        if props.contains(FstProperties::TOP_SORTED) || fst.start().is_none() {
            queue = Box::new(StateOrderQueue::default());
        } else if props.contains(FstProperties::ACYCLIC) {
            queue = Box::new(TopOrderQueue::new(fst, arc_filter));
        } else if props.contains(FstProperties::UNWEIGHTED)
            && F::W::properties().contains(SemiringProperties::IDEMPOTENT)
        {
            queue = Box::new(LifoQueue::default());
        } else {
            let mut scc_visitor = SccVisitor::new(fst, true, false);
            dfs_visit(fst, &mut scc_visitor, arc_filter, false);
            let sccs: Vec<_> = scc_visitor
                .scc
                .unwrap()
                .into_iter()
                .map(|v| v as usize)
                .collect();
            let n_sccs = scc_visitor.nscc as usize;

            let mut queue_types = vec![QueueType::TrivialQueue; n_sccs];
            let less = if distance.is_some()
                && !distance.unwrap().is_empty()
                && F::W::properties().contains(SemiringProperties::PATH)
            {
                Some(natural_less)
            } else {
                None
            };

            // Finds the queue type to use per SCC.
            let mut unweighted = false;
            let mut all_trivial = false;
            Self::scc_queue_type(
                fst,
                &sccs,
                less,
                &mut queue_types,
                &mut all_trivial,
                &mut unweighted,
                arc_filter,
            )?;

            if unweighted {
                // If unweighted and semiring is idempotent, uses LIFO queue.
                queue = Box::new(LifoQueue::default());
            } else if all_trivial {
                // If all the SCC are trivial, the FST is acyclic and the scc number gives
                // the topological order.
                queue = Box::new(TopOrderQueue::from_precomputed_order(sccs));
            } else {
                // AutoQueue: using SCC meta-discipline
                let mut queues: Vec<Box<dyn Queue>> = Vec::with_capacity(n_sccs);
                for queue_type in queue_types.iter().take(n_sccs) {
                    match queue_type {
                        QueueType::TrivialQueue => queues.push(Box::new(TrivialQueue::default())),
                        QueueType::ShortestFirstQueue => queues.push(Box::new(
                            NaturalShortestFirstQueue::new(distance.unwrap().clone()),
                        )),
                        QueueType::LifoQueue => queues.push(Box::new(LifoQueue::default())),
                        _ => queues.push(Box::new(FifoQueue::default())),
                    }
                }
                queue = Box::new(SccQueue::new(queues, sccs));
            }
        }

        Ok(Self { queue })
    }

    pub fn scc_queue_type<
        F: MutableFst + ExpandedFst,
        C: Fn(&F::W, &F::W) -> Fallible<bool>,
        A: ArcFilter<F::W>,
    >(
        fst: &F,
        sccs: &[usize],
        compare: Option<C>,
        queue_types: &mut Vec<QueueType>,
        all_trivial: &mut bool,
        unweighted: &mut bool,
        arc_filter: &A,
    ) -> Fallible<()> {
        *all_trivial = true;
        *unweighted = true;

        queue_types
            .iter_mut()
            .for_each(|v| *v = QueueType::TrivialQueue);

        for state in 0..fst.num_states() {
            for arc in unsafe { fst.arcs_iter_unchecked(state) } {
                if !arc_filter.keep(arc) {
                    continue;
                }
                if sccs[state] == sccs[arc.nextstate] {
                    let queue_type = unsafe { queue_types.get_unchecked_mut(sccs[state]) };
                    if compare.is_none() || compare.as_ref().unwrap()(&arc.weight, &F::W::one())? {
                        *queue_type = QueueType::FifoQueue;
                    } else if *queue_type == QueueType::TrivialQueue
                        || *queue_type == QueueType::LifoQueue
                    {
                        if !F::W::properties().contains(SemiringProperties::IDEMPOTENT)
                            || (!arc.weight.is_zero() && !arc.weight.is_one())
                        {
                            *queue_type = QueueType::ShortestFirstQueue;
                        } else {
                            *queue_type = QueueType::LifoQueue;
                        }
                    }

                    if *queue_type != QueueType::TrivialQueue {
                        *all_trivial = false;
                    }
                }

                if !F::W::properties().contains(SemiringProperties::IDEMPOTENT)
                    || (!arc.weight.is_zero() && !arc.weight.is_one())
                {
                    *unweighted = false;
                }
            }
        }
        Ok(())
    }
}

impl Queue for AutoQueue {
    fn head(&mut self) -> Option<usize> {
        self.queue.head()
    }

    fn enqueue(&mut self, state: usize) {
        self.queue.enqueue(state)
    }

    fn dequeue(&mut self) {
        self.queue.dequeue()
    }

    fn update(&mut self, state: usize) {
        self.queue.update(state)
    }

    fn is_empty(&self) -> bool {
        self.queue.is_empty()
    }

    fn clear(&mut self) {
        self.queue.clear()
    }

    fn queue_type(&self) -> QueueType {
        QueueType::AutoQueue
    }
}