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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

use crate::algorithms::{Queue, QueueType};
use crate::StateId;

/// Trivial queue discipline; one may enqueue at most one state at a time. It
/// can be used for strongly connected components with only one state and no
/// self-loops.
#[derive(Debug, Default, Clone)]
pub struct TrivialQueue {
    state: Option<StateId>,
}

impl Queue for TrivialQueue {
    fn head(&mut self) -> Option<StateId> {
        self.state
    }

    fn enqueue(&mut self, state: StateId) {
        self.state = Some(state);
    }

    fn dequeue(&mut self) {
        self.state = None;
    }

    fn update(&mut self, _state: StateId) {}

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

    fn clear(&mut self) {
        self.state = None;
    }

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

#[cfg(test)]
mod test {
    use super::*;

    use anyhow::Result;

    #[test]
    fn test_trivial_queue() -> Result<()> {
        let mut queue = TrivialQueue::default();

        assert_eq!(queue.head(), None);

        queue.enqueue(2);
        queue.enqueue(3);
        assert_eq!(queue.head(), Some(3));
        queue.dequeue();
        assert_eq!(queue.head(), None);

        queue.enqueue(2);
        queue.enqueue(3);
        assert_eq!(queue.is_empty(), false);
        assert_eq!(queue.head(), Some(3));
        queue.clear();
        assert_eq!(queue.head(), None);
        assert_eq!(queue.is_empty(), true);
        Ok(())
    }
}