separating_nodes.rs 996 Bytes
Newer Older
Bharat Garhewal's avatar
Bharat Garhewal committed
1
2
use fnv::FnvHashMap;
use std::{fmt::Debug, hash::Hash};
Bharat Garhewal's avatar
Bharat Garhewal committed
3
4

/// Helper struct to hold all the state pairs.
Bharat Garhewal's avatar
Bharat Garhewal committed
5
/// `K` is the type of the states of the FSM.
Bharat Garhewal's avatar
Bharat Garhewal committed
6
#[derive(Debug, Default, Clone)]
Bharat Garhewal's avatar
Bharat Garhewal committed
7
pub(super) struct SeparatingNodes<K, V> {
Bharat Garhewal's avatar
Bharat Garhewal committed
8
    /// Each pair of states maps to the node index which separates the pair.
Bharat Garhewal's avatar
Bharat Garhewal committed
9
    inner: FnvHashMap<(K, K), V>,
Bharat Garhewal's avatar
Bharat Garhewal committed
10
11
}

Bharat Garhewal's avatar
Bharat Garhewal committed
12
impl<K, V> SeparatingNodes<K, V>
Bharat Garhewal's avatar
Bharat Garhewal committed
13
where
Bharat Garhewal's avatar
Bharat Garhewal committed
14
    K: PartialOrd,
Bharat Garhewal's avatar
Bharat Garhewal committed
15
{
Bharat Garhewal's avatar
Bharat Garhewal committed
16
17
18
19
20
    fn make_key(x: K, y: K) -> (K, K) {
        if x < y {
            (x, y)
        } else {
            (y, x)
Bharat Garhewal's avatar
Bharat Garhewal committed
21
22
23
24
        }
    }
}

Bharat Garhewal's avatar
Bharat Garhewal committed
25
impl<K, V> SeparatingNodes<K, V>
Bharat Garhewal's avatar
Bharat Garhewal committed
26
where
Bharat Garhewal's avatar
Bharat Garhewal committed
27
28
    K: PartialEq + Hash + PartialOrd + Eq,
    V: Copy,
Bharat Garhewal's avatar
Bharat Garhewal committed
29
{
Bharat Garhewal's avatar
Bharat Garhewal committed
30
    pub fn insert_pair(&mut self, s1: K, s2: K, idx: V) {
Bharat Garhewal's avatar
Bharat Garhewal committed
31
        let key = Self::make_key(s1, s2);
Bharat Garhewal's avatar
Bharat Garhewal committed
32
        self.inner.insert(key, idx);
Bharat Garhewal's avatar
Bharat Garhewal committed
33
34
    }

Bharat Garhewal's avatar
Bharat Garhewal committed
35
    /// Returns ``Some(Index)`` of the LCA for a pair of states, if present.
Bharat Garhewal's avatar
Bharat Garhewal committed
36
    pub fn check_pair(&self, s1: K, s2: K) -> Option<V> {
Bharat Garhewal's avatar
Bharat Garhewal committed
37
        let key = Self::make_key(s1, s2);
Bharat Garhewal's avatar
Bharat Garhewal committed
38
        self.inner.get(&key).copied()
Bharat Garhewal's avatar
Bharat Garhewal committed
39
    }
Bharat Garhewal's avatar
Bharat Garhewal committed
40
}