general_sam/sam/
state.rs

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

general_sam/sam/
state.rs
