Data.DAWG.Internal

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.

Node

data Node a

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.

Constructors

Branch

Fields

eps :: !Id

Epsilon transition.

edgeMap :: !VMap

Map from alphabet symbols to Branch node identifiers.

Value

Fields

unValue :: !a

Instances

Functor Node

Eq a => Eq (Node a)

(Eq (Node a), Ord a) => Ord (Node a)

Show a => Show (Node a)

Binary a => Binary (Node a)

type Id = Int

Node identifier.

edges :: Node a -> [(Int, Id)]

List of non-epsilon edges outgoing from the Branch node.

onSym :: Int -> Node a -> Maybe Id

Identifier of the child determined by the given symbol.

subst :: Int -> Id -> Node a -> Node a

Substitue the identifier of the child determined by the given symbol.

Graph

data Graph a

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?

Constructors

Graph

Fields

idMap :: !(Map (Node a) Id)

Map from nodes to IDs.

freeIDs :: !IntSet

Set of free IDs.

nodeMap :: !(IntMap (Node a))

Map from IDs to nodes.

ingoMap :: !(IntMap Int)

Number of ingoing paths (different paths from the root to the given node) for each node ID in the graph. The number of ingoing paths can be also interpreted as a number of occurences of the node in a tree representation of the graph.

Instances

Eq a => Eq (Graph a)

(Eq (Graph a), Ord a) => Ord (Graph a)

Show a => Show (Graph a)

(Ord a, Binary a) => Binary (Graph a)

empty :: Graph a

Empty graph.

size :: Graph a -> Int

Size of the graph (number of nodes).

nodeBy :: Id -> Graph a -> Node a

Node with the given identifier.

nodeID :: Ord a => Node a -> Graph a -> Id

Retrieve the node identifier.

insert :: Ord a => Node a -> Graph a -> (Id, Graph a)

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 a

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.