Safe Haskell  None 

Internal representation of the Data.DAWG automaton. Names in this module correspond to a graphical representation of automaton: nodes refer to states and edges refer to transitions.
 data Node a
 type Id = Int
 edges :: Node a > [(Int, Id)]
 onSym :: Int > Node a > Maybe Id
 subst :: Int > Id > Node a > Node a
 data Graph a = Graph {}
 empty :: Graph a
 size :: Graph a > Int
 nodeBy :: Id > Graph a > Node a
 nodeID :: Ord a => Node a > Graph a > Id
 insert :: Ord a => Node a > Graph a > (Id, Graph a)
 delete :: Ord a => Node a > Graph a > Graph a
Node
Two nodes (states) belong to the same equivalence class (and, consequently, they must be represented as one node in the graph) iff they are equal with respect to their values and outgoing edges.
Since Value
nodes are distinguished from Branch
nodes, two values
equal with respect to ==
function are always kept in one Value
node in the graph. It doesn't change the fact that to all Branch
nodes one value is assigned through the epsilon transition.
Invariant: the value
identifier always points to the Value
node.
Edges in the edgeMap
, on the other hand, point to Branch
nodes.
subst :: Int > Id > Node a > Node aSource
Substitue the identifier of the child determined by the given symbol.
Graph
A set of nodes. To every node a unique identifier is assigned. Invariants:
 freeIDs \intersection occupiedIDs = \emptySet,
 freeIDs \sum occupiedIDs = {0, 1, ..., freeIDs \sum occupiedIDs  1},
where occupiedIDs = elemSet idMap.
TODO: Is it possible to merge freeIDs
with ingoMap
to reduce
the memory footprint?
Graph  

insert :: Ord a => Node a > Graph a > (Id, Graph a)Source
Insert node into the graph. If the node was already a member of the graph, just increase the number of ingoing paths. NOTE: Number of ingoing paths will not be changed for any descendants of the node, so the operation alone will not ensure that properties of the graph are preserved.
delete :: Ord a => Node a > Graph a > Graph aSource
Delete node from the graph. If the node was present in the graph at multiple positions, just decrease the number of ingoing paths. NOTE: The function does not delete descendant nodes which may become inaccesible nor does it change the number of ingoing paths for any descendant of the node.