Struct KGST

pub struct KGST<T, U>
where
    T: Display + Debug + Eq + PartialEq + Hash + Clone + PartialOrd,
    U: Display + Debug + Eq + PartialEq + Hash + Clone,
{ /* private fields */ }

A Generalized Truncated Suffix Tree implemented with a variation of Ukkonen’s Algorithm.

Implementations

impl<T, U> KGST<T, U>

where T: Display + Debug + Eq + PartialEq + Hash + Clone + Serialize + PartialOrd, U: Display + Debug + Eq + PartialEq + Hash + Clone + Serialize,

pub fn new(terminal_character: T) -> Self

Creates a new empty K-Truncated Generalized Suffix tree, with a constant end symbol.

Examples

use generalized_suffix_tree::suffix_tree::KGST;
 
let tree: KGST<char, String> = KGST::new('$');

pub fn clear(&mut self)

Empties the tree of all strings and nodes.

pub fn num_nodes(&self) -> usize

pub fn get_strings(&self) -> &HashMap<StringID, (TreeItem<T, U>, usize)>

Returns a Hashmap of all the strings present in the tree along with their respective tree depth.

pub fn get_nodes(&self) -> &HashMap<NodeID, Node<T>>

pub fn get_node(&self, node_id: &NodeID) -> &Node<T>

Retrieves a node from the tree by node id

pub fn get_node_label(&self, node_id: &NodeID) -> &[Character<T>]

Returns the string represented by the incoming edge of the node.

pub fn suffix_match(&self, s: &[T]) -> HashMap<U, HashSet<usize>>

Retrieves all strings that the input slice is a suffix of.

pub fn substring_match(&self, s: &[T]) -> HashMap<U, HashSet<usize>>

Retrieves all strings that contain the input slice as some substring.

pub fn get_node_data( &self, node_id: &NodeID, ) -> &HashMap<StringID, HashSet<usize>>

pub fn insert(&mut self, k: U, v: Vec<T>, max_depth: &usize)

inserts all suffixes of a string into the tree. If max_depth>0, all substrings of length==max_depth are inserted.

pub fn contains(&self, string_id: &U) -> bool

pub fn iter_strings(&self) -> Iter<'_, usize, (TreeItem<T, U>, usize)>

Returns a string iterator of the tree

pub fn print_tree(&self)

Prints tree as a string.

pub fn iter_nodes_pre(&self) -> PreOrdNodes<T>

Returns a preorder node iterator of the tree

pub fn iter_nodes_post(&self) -> PostOrdNodes<T>

Returns a preorder node iterator of the tree

pub fn iter_path_pre(&self, node_id: &NodeID) -> IntoIter<usize>

Returns the nodes in a path in preorder

pub fn iter_path_post(&self, node_id: &NodeID) -> IntoIter<usize>

Returns the nodes in a path in postorder

pub fn iter_edges_post(&self) -> PostOrdEdges<T>

Returns a postorder edge iterator of the tree

Trait Implementations

impl<T, U> Debug for KGST<T, U>

where T: Display + Debug + Eq + PartialEq + Hash + Clone + PartialOrd + Debug, U: Display + Debug + Eq + PartialEq + Hash + Clone + Debug,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T, U> Serialize for KGST<T, U>

where T: Display + Debug + Eq + PartialEq + Hash + Clone + Serialize + PartialOrd, U: Display + Debug + Eq + PartialEq + Hash + Clone + Serialize,

fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>

where S: Serializer,

Serialize this value into the given Serde serializer.

impl<T, U> SuffixTree<T> for KGST<T, U>

where T: Display + Debug + Eq + PartialEq + Hash + Clone + Serialize + PartialOrd, U: Display + Debug + Eq + PartialEq + Hash + Clone + Serialize,

fn root(&self) -> &NodeID

fn is_leaf(&self, node_id: &NodeID) -> bool

fn get_node_child(&self, node_id: &NodeID, edge_label: &T) -> Option<&NodeID>

fn get_node_parent(&self, node_id: &NodeID) -> Option<&NodeID>

fn get_node_depth(&self, node_id: &NodeID) -> usize

fn get_suffix_link(&self, node_id: &NodeID) -> &usize

fn get_node_label(&self, node_id: &NodeID) -> Vec<T>

fn get_node_path_label(&self, _node_id: &NodeID) -> &[T]

fn get_node_path_pre(&self, node_id: &NodeID) -> LinkedList<NodeID>

fn get_node_path_post(&self, node_id: &NodeID) -> LinkedList<NodeID>

fn is_suffix(&self, s: &[T]) -> bool

Checks if the input slice is a suffix of any of the strings present in the tree.