1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

use std::fmt::Debug;

use crate::StateId;

/// Defines the different types of Queues usable.
#[derive(PartialOrd, PartialEq, Clone)]
pub enum QueueType {
    /// Single state queue.
    TrivialQueue,
    /// First-in, first-out queue.
    FifoQueue,
    /// Last-in, first-out queue.
    LifoQueue,
    /// Shortest-first queue.
    ShortestFirstQueue,
    /// Topologically-ordered queue.
    TopOrderQueue,
    /// State ID-ordered queue.
    StateOrderQueue,
    /// Component graph top-ordered meta-queue.
    SccQueue,
    /// Auto-selected queue.
    AutoQueue,
    OtherQueue,
}

// TODO: Test the queues with openfst
/// Unified interface to use different implementation of Queues.
pub trait Queue: Debug {
    fn head(&mut self) -> Option<StateId>;
    fn enqueue(&mut self, state: StateId);
    fn dequeue(&mut self);
    fn update(&mut self, state: StateId);
    fn is_empty(&self) -> bool;
    fn clear(&mut self);
    fn queue_type(&self) -> QueueType;
}