dawg 0.1.0 → 0.2.0

raw patch · 3 files changed

+79/−42 lines, 3 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• Data/DAWG.hs +43/−13
• Data/DAWG/Graph.hs +35/−28
• dawg.cabal +1/−1

@@ -1,13 +1,14 @@ -- | The module provides implementation of /directed acyclic word graphs/ -- (DAWGs) also known as /minimal acyclic finite-state automata/.--- The implementation provides fast insert and (TODO:)delete operations+-- The implementation provides fast insert and delete operations -- which can be used to build the DAWG structure incrementaly.  module Data.DAWG ( DAWG (..) , empty-, size+, numStates , insert+, delete , lookup , fromList , fromLang@@ -21,22 +22,29 @@  import Data.DAWG.Graph (Id, Node, Graph) import qualified Data.DAWG.Graph as G+import qualified Data.DAWG.VMap as V -type GraphM a b = S.State (Graph a) b+type GraphM a b = S.State (Graph (Maybe a)) b  mkState :: (Graph a -> Graph a) -> Graph a -> ((), Graph a) mkState f g = ((), f g) +-- | Leaf node with no children and 'Nothing' value.+leaf :: Node (Maybe a)+leaf = G.Node+    { G.value = Nothing+    , G.edges = V.empty }+ -- | Return node with the given identifier.-nodeBy :: Id -> GraphM a (Node a)+nodeBy :: Id -> GraphM a (Node (Maybe a)) nodeBy i = G.nodeBy i <$> S.get  -- Evaluate the 'G.insert' function within the monad.-insertNode :: Ord a => Node a -> GraphM a Id+insertNode :: Ord a => Node (Maybe a) -> GraphM a Id insertNode = S.state . G.insert  -- Evaluate the 'G.delete' function within the monad.-deleteNode :: Ord a => Node a -> GraphM a ()+deleteNode :: Ord a => Node (Maybe a) -> GraphM a () deleteNode = S.state . mkState . G.delete  insertM :: Ord a => String -> a -> Id -> GraphM a Id@@ -48,10 +56,24 @@     n <- nodeBy i     j <- case G.onChar x n of         Just j  -> return j-        Nothing -> insertNode G.leaf+        Nothing -> insertNode leaf     k <- insertM xs y j     deleteNode n     insertNode (G.subst x k n)++deleteM :: Ord a => String -> Id -> GraphM a Id+deleteM [] i = do+    n <- nodeBy i+    deleteNode n+    insertNode (n { G.value = Nothing })+deleteM (x:xs) i = do+    n <- nodeBy i+    case G.onChar x n of+        Nothing -> return i+        Just j  -> do+            k <- deleteM xs j+            deleteNode n+            insertNode (G.subst x k n)      lookupM :: String -> Id -> GraphM a (Maybe a) lookupM [] i = G.value <$> nodeBy i@@ -64,7 +86,7 @@ -- | A 'G.Graph' with one root from which all other graph nodes should -- be accesible. data DAWG a = DAWG-    { graph :: !(Graph a)+    { graph :: !(Graph (Maybe a))     , root  :: !Id }     deriving (Show, Eq, Ord) @@ -75,17 +97,25 @@     get = DAWG <$> get <*> get  -- | Empty DAWG.-empty :: DAWG a-empty = DAWG G.empty 0+empty :: Ord a => DAWG a+empty = +    let (i, g) = G.insert leaf G.empty+    in  DAWG g i --- | DAWG size (number of nodes).-size :: DAWG a -> Int-size = G.size . graph+-- | Number of states in the underlying graph.+numStates :: DAWG a -> Int+numStates = G.size . graph  -- | Insert the (key, value) pair into the DAWG. insert :: Ord a => String -> a -> DAWG a -> DAWG a insert xs y d =     let (i, g) = S.runState (insertM xs y $ root d) (graph d)+    in  DAWG g i++-- | Delete the key from the DAWG.+delete :: Ord a => String -> DAWG a -> DAWG a+delete xs d =+    let (i, g) = S.runState (deleteM xs $ root d) (graph d)     in  DAWG g i  -- | Find value associated with the key.

@@ -1,17 +1,15 @@ {-# LANGUAGE RecordWildCards #-} --- | The module provides a /directed acyclic graph/ (DAG) implementation--- where all equivalent nodes (i.e. roots of DAGs equal with respect to--- the '==' function) are compressed to one node with unique identifier.--- It can be alternatively thought of as a--- /minimal acyclic finite-state automata/.+-- | The module provides a representation of a tree where all equivalent nodes+-- (i.e. trees equal with respect to the '==' function) are compressed to one+-- /directed acyclic graph/ (DAG) node with unique identifier.  Alternatively,+-- it can be thought of as a /minimal acyclic finite-state automata/.  module Data.DAWG.Graph (  -- * Node   Node (..) , Id-, leaf , onChar , subst -- * Graph@@ -40,21 +38,18 @@ -- iff they are equal with respect to their values and outgoing -- edges. data Node a = Node-    { value :: Maybe a-    , edges :: V.VMap Id }+    { value :: !a+    , edges :: !(V.VMap Id) }     deriving (Show, Eq, Ord) +instance Functor Node where+    fmap f n = n { value = f (value n) }+ instance Binary a => Binary (Node a) where     put Node{..} = put value >> put edges     get = Node <$> get <*> get --- | Leaf node with no children and 'Nothing' value.-leaf :: Node a-leaf = Node-    { value = Nothing-    , edges = V.empty }---- | Child identifier found by following the given character.+-- | Identifier of the child determined by the given character. onChar :: Char -> Node a -> Maybe Id onChar x n = V.lookup x (edges n) @@ -79,9 +74,13 @@       idMap     :: !(M.Map (Node a) Id)     -- | Set of free IDs.     , freeIDs   :: !IS.IntSet-    -- | Equivalence class represented by given ID and size of the class. +    -- | Map from IDs to nodes.      , nodeMap   :: !(IM.IntMap (Node a))-    -- | Number of ingoing edges.+    -- | 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.     , ingoMap   :: !(IM.IntMap Int) }     deriving (Show, Eq, Ord) @@ -95,12 +94,16 @@  -- | Empty graph. empty :: Graph a-empty = Graph-    (M.singleton leaf 0)-    IS.empty-    (IM.singleton 0 leaf)-    (IM.singleton 0 1)+empty = Graph M.empty IS.empty IM.empty IM.empty +-- -- | Empty graph.+-- empty :: Graph a+-- empty = Graph+--     (M.singleton leaf 0)+--     IS.empty+--     (IM.singleton 0 leaf)+--     (IM.singleton 0 1)+ -- | Size of the graph (number of nodes). size :: Graph a -> Int size = M.size . idMap@@ -109,7 +112,7 @@ nodeBy :: Id -> Graph a -> Node a nodeBy i g = nodeMap g IM.! i --- | Retrive the node identifier.+-- | Retrieve the node identifier. nodeID :: Ord a => Node a -> Graph a -> Id nodeID n g = idMap g M.! n @@ -136,11 +139,11 @@     freeIDs'    = IS.insert i freeIDs     n           = nodeMap IM.! i --- | Increment the number of ingoing edges.+-- | Increment the number of ingoing paths. incIngo :: Id -> Graph a -> Graph a incIngo i g = g { ingoMap = IM.adjust (+1) i (ingoMap g) } --- | Descrement the number of ingoing edges and return+-- | Descrement the number of ingoing paths and return -- the resulting number. decIngo :: Id -> Graph a -> (Int, Graph a) decIngo i g =@@ -148,16 +151,20 @@     in  (k, g { ingoMap = IM.insert i k (ingoMap g) })  -- | Insert node into the graph.  If the node was already a member--- of the graph, just increase the number of ingoing edges.+-- of the graph, just increase the number of ingoing paths.+-- NOTE: Number of ingoing paths will not be changed for any+-- ancestors of the node, so the operation alone will not ensure+-- that properties of the graph are preserved. insert :: Ord a => Node a -> Graph a -> (Id, Graph a) insert n g = case M.lookup n (idMap g) of     Just i  -> (i, incIngo i g)     Nothing -> newNode n g  -- | Delete node from the graph.  If the node was present in the graph--- at multiple positions, just decrease the number of ingoing edges.+-- at multiple positions, just decrease the number of ingoing paths. -- NOTE: The function does not delete descendant nodes which may become--- inaccesible.+-- inaccesible nor does it change the number of ingoing paths for any+-- ancestor of the node. delete :: Ord a => Node a -> Graph a -> Graph a delete n g = if num == 0     then remNode i g'

@@ -1,5 +1,5 @@ name:               dawg-version:            0.1.0+version:            0.2.0 synopsis:           DAWG description:     Directed acyclic word graphs.