general_sam/sam/
state.rs

1//! States of a general suffix automaton.
2
3use std::borrow::Borrow;
4use std::marker::PhantomData;
5
6use crate::{TravelEvent, TrieNodeAlike};
7
8use super::{GeneralSam, GeneralSamNode, SAM_NIL_NODE_ID, SAM_ROOT_NODE_ID, TransitionTable};
9
10#[derive(Debug)]
11pub struct GeneralSamState<TransTable: TransitionTable, SamRef: Borrow<GeneralSam<TransTable>>> {
12    pub sam: SamRef,
13    pub node_id: usize,
14    phantom: PhantomData<TransTable>,
15}
16
17impl<TransTable: TransitionTable, SamRef: Borrow<GeneralSam<TransTable>> + Clone> Clone
18    for GeneralSamState<TransTable, SamRef>
19{
20    fn clone(&self) -> Self {
21        Self {
22            sam: self.sam.clone(),
23            node_id: self.node_id,
24            phantom: PhantomData,
25        }
26    }
27}
28
29impl<TransTable: TransitionTable<KeyType = u8>, SamRef: Borrow<GeneralSam<TransTable>>>
30    GeneralSamState<TransTable, SamRef>
31{
32    pub fn feed_bytes<S: AsRef<[u8]>>(&mut self, seq: S) -> &mut Self {
33        self.feed_ref(seq.as_ref())
34    }
35}
36
37impl<TransTable: TransitionTable<KeyType = char>, SamRef: Borrow<GeneralSam<TransTable>>>
38    GeneralSamState<TransTable, SamRef>
39{
40    pub fn feed_chars<S: AsRef<str>>(&mut self, seq: S) -> &mut Self {
41        self.feed(seq.as_ref().chars())
42    }
43}
44
45impl<TransTable: TransitionTable, SamRef: Borrow<GeneralSam<TransTable>>>
46    GeneralSamState<TransTable, SamRef>
47{
48    pub fn new(sam: SamRef, node_id: usize) -> Self {
49        Self {
50            sam,
51            node_id,
52            phantom: PhantomData,
53        }
54    }
55
56    pub fn inner_as_ref(&self) -> GeneralSamState<TransTable, &GeneralSam<TransTable>> {
57        GeneralSamState {
58            sam: self.sam.borrow(),
59            node_id: self.node_id,
60            phantom: PhantomData,
61        }
62    }
63
64    pub fn is_nil(&self) -> bool {
65        self.node_id == SAM_NIL_NODE_ID
66    }
67
68    pub fn is_root(&self) -> bool {
69        self.node_id == SAM_ROOT_NODE_ID
70    }
71
72    pub fn is_accepting(&self) -> bool {
73        self.get_node()
74            .map(|node| node.is_accepting())
75            .unwrap_or(false)
76    }
77
78    pub fn get_sam_ref(&self) -> &GeneralSam<TransTable> {
79        self.sam.borrow()
80    }
81
82    pub fn get_node(&self) -> Option<&GeneralSamNode<TransTable>> {
83        self.sam.borrow().get_node(self.node_id)
84    }
85
86    pub fn goto_suffix_parent(&mut self) -> &mut Self {
87        if let Some(node) = self.get_node() {
88            self.node_id = node.link;
89        } else {
90            self.node_id = SAM_NIL_NODE_ID;
91        }
92        self
93    }
94
95    pub fn goto<K: Borrow<TransTable::KeyType>>(&mut self, t: &K) -> &mut Self {
96        self.node_id = if let Some(next_node_id) =
97            self.get_node().and_then(|node| node.trans.get(t.borrow()))
98        {
99            *next_node_id
100        } else {
101            SAM_NIL_NODE_ID
102        };
103        self
104    }
105
106    pub fn feed<Seq: IntoIterator<Item = TransTable::KeyType>>(&mut self, seq: Seq) -> &mut Self {
107        for t in seq {
108            if self.is_nil() {
109                break;
110            }
111            self.goto(&t);
112        }
113        self
114    }
115
116    pub fn feed_ref<'s, Seq: IntoIterator<Item = &'s TransTable::KeyType>>(
117        &mut self,
118        seq: Seq,
119    ) -> &mut Self
120    where
121        <TransTable as TransitionTable>::KeyType: 's,
122    {
123        for t in seq {
124            if self.is_nil() {
125                break;
126            }
127            self.goto(t);
128        }
129        self
130    }
131}
132
133impl<TransTable: TransitionTable, SamRef: Borrow<GeneralSam<TransTable>> + Clone>
134    GeneralSamState<TransTable, SamRef>
135{
136    pub fn get_non_nil_trans(&self, key: &TransTable::KeyType) -> Option<Self> {
137        self.get_node()
138            .and_then(|node| node.trans.get(key))
139            .map(|x| Self {
140                sam: self.sam.clone(),
141                node_id: *x,
142                phantom: PhantomData,
143            })
144    }
145
146    #[allow(clippy::type_complexity)]
147    fn wrap_travel_along_callback<
148        's,
149        TN: TrieNodeAlike<InnerType = TransTable::KeyType>,
150        ExtraType,
151        ErrorType,
152        F: 's
153            + FnMut(
154                TravelEvent<(&Self, &TN), ExtraType, TN::InnerType>,
155            ) -> Result<ExtraType, ErrorType>,
156    >(
157        &'s self,
158        mut callback: F,
159    ) -> impl FnMut(
160        TravelEvent<&TN, (Self, ExtraType), TN::InnerType>,
161    ) -> Result<(Self, ExtraType), ErrorType>
162    + 's {
163        move |event| match event {
164            TravelEvent::PushRoot(trie_root) => {
165                let res = callback(TravelEvent::PushRoot((self, trie_root)))?;
166                Ok((self.clone(), res))
167            }
168            TravelEvent::Push(cur_tn, (cur_state, cur_extra), key) => {
169                let mut next_state = cur_state.clone();
170                next_state.goto(&key);
171                let next_extra =
172                    callback(TravelEvent::Push((&next_state, cur_tn), cur_extra, key))?;
173                Ok((next_state, next_extra))
174            }
175            TravelEvent::Pop(cur_tn, (cur_state, extra)) => {
176                let res = callback(TravelEvent::Pop((&cur_state, cur_tn), extra))?;
177                Ok((cur_state, res))
178            }
179        }
180    }
181
182    pub fn dfs_along<
183        TN: TrieNodeAlike<InnerType = TransTable::KeyType> + Clone,
184        ExtraType,
185        ErrorType,
186        F: FnMut(TravelEvent<(&Self, &TN), ErrorType, TN::InnerType>) -> Result<ErrorType, ExtraType>,
187    >(
188        &self,
189        trie_node: TN,
190        callback: F,
191    ) -> Result<(), ExtraType> {
192        trie_node.dfs_travel(self.wrap_travel_along_callback(callback))
193    }
194
195    pub fn bfs_along<
196        TN: TrieNodeAlike<InnerType = TransTable::KeyType>,
197        ExtraType,
198        ErrorType,
199        F: FnMut(TravelEvent<(&Self, &TN), ErrorType, TN::InnerType>) -> Result<ErrorType, ExtraType>,
200    >(
201        &self,
202        trie_node: TN,
203        callback: F,
204    ) -> Result<(), ExtraType> {
205        trie_node.bfs_travel(self.wrap_travel_along_callback(callback))
206    }
207}
general_sam/sam/state.rs

general_sam/sam/
state.rs
