-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Subword graph implementation
--   
--   An implementation of a classic Subword Graph (aka DAWG) data structure
--   for solving string related problems on a single word.
@package subwordgraph
@version 1.0.2


-- | An implementation of a classic Subword Graph (also known as Directed
--   Acyclic Word Graph). A data structure for solving string related
--   problems on a single word. The implementation is based on a lecture in
--   Polish (with pseudocode): <a>http://smurf.mimuw.edu.pl/node/581</a>
module Data.SubwordGraph

-- | Indicates unique id of a node.
type Vertex = Int

-- | Destination node, edge type.
type Edge = (Vertex, EdgeType)

-- | Edge with its label.
type LabeledEdge a = (a, Edge)

-- | Edge with its startpoint.
type RootedEdge a = (Vertex, a, Edge)
data EdgeType
Solid :: EdgeType
Soft :: EdgeType

-- | Node structure contains the node's id, suf binding (Nothing iff root)
--   and the map of all outgoing edges.
data Node a

-- | Graph structure contains ids of its root and sink as well as the map
--   of all nodes.
data SGraph a

-- | Constructs a subword graph for a given word. The performance of this
--   function is linear in the length of a word.
construct :: Ord a => [a] -> SGraph a

-- | Constructs a subword graph for a reversed word. The performance of
--   this function is linear in the length of a word.
constructReversed :: Ord a => [a] -> SGraph a

-- | Indicates whether the subword graph contains the given word.
--   Performance is linear in the length of the word.
elem :: Ord a => [a] -> SGraph a -> Bool

-- | Returns the list of all subwords present in a given subword graph.
subwords :: SGraph a -> [[a]]

-- | Returns the number of all subwords present in the given subword graph.
--   Performance is linear in the size of the graph.
subwordsNum :: SGraph a -> Int

-- | Finds the given word in the subword graph. On failure, returns
--   Nothing. On success, returns the node in the subword graph at which
--   the word ends. Performance is linear in the length of the word.
findNode :: Ord a => [a] -> SGraph a -> Maybe (Node a)

-- | Returns a word corresponding the given subword graph. Performance is
--   linear in the length of the word.
toWord :: Ord a => SGraph a -> [a]

-- | Folds the edges in a graph, using topological order traversal.
--   Transformer function takes current node's state, current state along
--   the edge, an edge and it produces a new state along the edge. Init
--   state at node is equal to the accumulator.
foldl :: (b -> b -> RootedEdge a -> b) -> b -> SGraph a -> b

-- | Folds the edges in a graph up to a given node. Returns computed value,
--   as well as a mapping: vertex -&gt; computed value.
foldlToNode :: (b -> b -> RootedEdge a -> b) -> b -> SGraph a -> Node a -> (b, IntMap b)

-- | Folds the edges in a graph, using post-order traversal. Transformer
--   function takes an edge, current node's state and state along the edge.
--   Init state at node is equal to the accumulator.
foldr :: (LabeledEdge a -> b -> b -> b) -> b -> SGraph a -> b

-- | Folds the edges in a graph starting at a given node. Returns computed
--   value, as well as a mapping: vertex -&gt; computed value.
foldrFromNode :: (LabeledEdge a -> b -> b -> b) -> b -> SGraph a -> Node a -> (b, IntMap b)

-- | For a given graph returns the list of nodes in a topological order.
--   Performance is linear in the size of the graph.
topsort :: SGraph a -> [Node a]

-- | Adds an element to a given graph creating a new graph for a word with
--   this element appended.
insert :: Ord a => a -> SGraph a -> SGraph a

-- | Returns id of the root.
rootId :: SGraph a -> Vertex

-- | Returns id of the sink.
sinkId :: SGraph a -> Vertex

-- | Returns id of the node.
nodeId :: Node a -> Vertex

-- | Returns node's suf binding.
sufId :: Node a -> Maybe Vertex

-- | Returns node's outgoing edges.
edges :: Node a -> Map a Edge

-- | Returns number of nodes for a given graph.
nodesNum :: SGraph a -> Int

-- | Returns number of edges for a given graph.
edgesNum :: SGraph a -> Int

-- | Returns node with a given index. Nothing iff such does not exist.
lookupNode :: Int -> SGraph a -> Maybe (Node a)

-- | Looks up an edge from a given node with a given label.
findEdge :: Ord a => Node a -> a -> Maybe Edge

-- | For a given graph returns its root node.
getRootNode :: SGraph a -> Node a

-- | For a given node in a given graph returns its suf link node.
getSufNode :: Node a -> SGraph a -> Maybe (Node a)

-- | For a given graph returns its sink node.
getSinkNode :: SGraph a -> Node a
instance GHC.Show.Show a => GHC.Show.Show (Data.SubwordGraph.SGraph a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.SubwordGraph.SGraph a)
instance GHC.Show.Show a => GHC.Show.Show (Data.SubwordGraph.Node a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.SubwordGraph.Node a)
instance GHC.Show.Show Data.SubwordGraph.EdgeType
instance GHC.Classes.Eq Data.SubwordGraph.EdgeType