dawg 0.3.0 → 0.4.0

raw patch · 4 files changed

+87/−93 lines, 4 filesdep −monad-codecPVP ok

version bump matches the API change (PVP)

Dependencies removed: monad-codec

API changes (from Hackage documentation)

Files

• Data/DAWG.hs +62/−14
• Data/DAWG/Graph.hs +23/−9
• Data/DAWG/Wrapper.hs +0/−62
• dawg.cabal +2/−8

@@ -8,9 +8,11 @@ , empty , numStates , insert+, insertWith , delete , lookup , fromList+, fromListWith , fromLang ) where @@ -30,10 +32,10 @@ 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 }+insertLeaf :: Ord a => GraphM a Id +insertLeaf = do+    i <- insertNode (G.Value Nothing)+    insertNode (G.Branch i V.empty)  -- | Return node with the given identifier. nodeBy :: Id -> GraphM a (Node (Maybe a))@@ -47,25 +49,45 @@ deleteNode :: Ord a => Node (Maybe a) -> GraphM a () deleteNode = S.state . mkState . G.delete +-- | Invariant: the identifier points to the 'Branch' node. insertM :: Ord a => String -> a -> Id -> GraphM a Id-insertM [] y i = do-    n <- nodeBy i-    deleteNode n-    insertNode (n { G.value = Just y }) insertM (x:xs) y i = do     n <- nodeBy i     j <- case G.onChar x n of         Just j  -> return j-        Nothing -> insertNode leaf+        Nothing -> insertLeaf     k <- insertM xs y j     deleteNode n     insertNode (G.subst x k n)+insertM [] y i = do+    n <- nodeBy i+    w <- nodeBy (G.eps n)+    deleteNode w+    deleteNode n+    j <- insertNode (G.Value $ Just y)+    insertNode (n { G.eps = j }) -deleteM :: Ord a => String -> Id -> GraphM a Id-deleteM [] i = do+insertWithM :: Ord a => (a -> a -> a) -> String -> a -> Id -> GraphM a Id+insertWithM f (x:xs) y i = do     n <- nodeBy i+    j <- case G.onChar x n of+        Just j  -> return j+        Nothing -> insertLeaf+    k <- insertWithM f xs y j     deleteNode n-    insertNode (n { G.value = Nothing })+    insertNode (G.subst x k n)+insertWithM f [] y i = do+    n <- nodeBy i+    w <- nodeBy (G.eps n)+    deleteNode w+    deleteNode n+    let y'new = case G.unValue w of+            Just y' -> f y y'+            Nothing -> y+    j <- insertNode (G.Value $ Just y'new)+    insertNode (n { G.eps = j })++deleteM :: Ord a => String -> Id -> GraphM a Id deleteM (x:xs) i = do     n <- nodeBy i     case G.onChar x n of@@ -74,9 +96,18 @@             k <- deleteM xs j             deleteNode n             insertNode (G.subst x k n)+deleteM [] i = do+    n <- nodeBy i+    w <- nodeBy (G.eps n)+    deleteNode w+    deleteNode n+    j <- insertLeaf+    insertNode (n { G.eps = j })      lookupM :: String -> Id -> GraphM a (Maybe a)-lookupM [] i = G.value <$> nodeBy i+lookupM [] i = do+    j <- G.eps <$> nodeBy i+    G.unValue <$> nodeBy j lookupM (x:xs) i = do     n <- nodeBy i     case G.onChar x n of@@ -99,7 +130,7 @@ -- | Empty DAWG. empty :: Ord a => DAWG a empty = -    let (i, g) = G.insert leaf G.empty+    let (i, g) = S.runState insertLeaf G.empty     in  DAWG g i  -- | Number of states in the underlying graph.@@ -112,6 +143,15 @@     let (i, g) = S.runState (insertM xs y $ root d) (graph d)     in  DAWG g i +-- | Insert with a function, combining new value and old value.+-- 'insertWith' f key value d will insert the pair (key, value) into d if+-- key does not exist in the DAWG. If the key does exist, the function+-- will insert the pair (key, f new_value old_value).+insertWith :: Ord a => (a -> a -> a) -> String -> a -> DAWG a -> DAWG a+insertWith f xs y d =+    let (i, g) = S.runState (insertWithM f 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 =@@ -126,6 +166,14 @@ fromList :: Ord a => [(String, a)] -> DAWG a fromList xs =     let update t (x, v) = insert x v t+    in  foldl' update empty xs++-- | Construct DAWG from the list of (word, value) pairs+-- with a combining function.  The combining function is+-- applied strictly.+fromListWith :: Ord a => (a -> a -> a) -> [(String, a)] -> DAWG a+fromListWith f xs =+    let update t (x, v) = insertWith f x v t     in  foldl' update empty xs  -- | Make DAWG from the list of words.  Annotate each word with

@@ -23,7 +23,7 @@ ) where  import Control.Applicative ((<$>), (<*>))-import Data.Binary (Binary, put, get)+import Data.Binary (Binary, Get, put, get) import qualified Data.Map as M import qualified Data.IntSet as IS import qualified Data.IntMap as IM@@ -37,26 +37,40 @@ -- consequently, they must be represented as one node in the graph) -- iff they are equal with respect to their values and outgoing -- edges.-data Node a = Node-    { value :: !a-    , edges :: !(V.VMap Id) }+--+-- Invariant: the 'value' identifier always points to the 'Value' node.+-- 'edges', on the other hand, point to 'Branch' nodes.+data Node a+    = Branch+        { eps   :: {-# UNPACK #-} !Id+        , edges :: !(V.VMap Id) }+    | Value+        { unValue :: !a }     deriving (Show, Eq, Ord)  instance Functor Node where-    fmap f n = n { value = f (value n) }+    fmap f (Value x) = Value (f x)+    fmap _ (Branch x y) = Branch x y  instance Binary a => Binary (Node a) where-    put Node{..} = put value >> put edges-    get = Node <$> get <*> get+    put Branch{..} = put (1 :: Int) >> put eps >> put edges+    put Value{..}  = put (2 :: Int) >> put unValue+    get = do+        x <- get :: Get Int+        case x of+            1 -> Branch <$> get <*> get+            _ -> Value <$> get  -- | Identifier of the child determined by the given character. onChar :: Char -> Node a -> Maybe Id-onChar x n = V.lookup x (edges n)+onChar x (Branch _ es)  = V.lookup x es+onChar _ (Value _)      = error "onChar: value node"  -- | Substitue the identifier of the child determined by the given -- character. subst :: Char -> Id -> Node a -> Node a-subst x i n = n { edges = V.insert x i (edges n) }+subst x i (Branch w es) = Branch w (V.insert x i es)+subst _ _ (Value _)     = error "subst: value node"  -- | A set of nodes.  To every node a unique identifier is assigned. -- Invariants: 

@@ -1,62 +0,0 @@--- | The module provides a wrapper over the 'D.DAWG' with separate--- 'C.Codec' for values encoding, which is beneficial when the set--- of possible DAWG values is small but individual values occupy--- a lot of memory.--- NOTE: Useless values are not deleted from the codec when--- deleting the DAWG entry.--module Data.DAWG.Wrapper-( DAWG (..)-, empty-, numStates-, insert-, delete-, lookup-, fromList-, fromLang-) where--import Prelude hiding (lookup)-import Data.List (foldl')-import qualified Control.Monad.Codec as C-import qualified Data.DAWG as D---- | A plain 'D.DAWG' with separate 'C.Codec' for values encoding.-data DAWG a = DAWG-    { dawg  :: !(D.DAWG Int)-    , codec :: !(C.AtomCodec a) }---- | Empty DAWG.-empty :: DAWG a-empty = DAWG D.empty C.empty---- | Number of states in the underlying graph.-numStates :: DAWG a -> Int-numStates = D.numStates . dawg---- | Insert the (key, value) pair into the DAWG.-insert :: Ord a => String -> a -> DAWG a -> DAWG a-insert xs y d =-    let (y', c') = C.runCodec (codec d) (C.encode C.idLens y)-    in  DAWG (D.insert xs y' (dawg d)) c'---- | Delete the key from the DAWG.-delete :: Ord a => String -> DAWG a -> DAWG a-delete xs d = DAWG (D.delete xs (dawg d)) (codec d)---- | Find value associated with the key.-lookup :: Ord a => String -> DAWG a -> Maybe a-lookup xs d =-    D.lookup xs (dawg d) >>=-    C.evalCodec (codec d) . C.maybeDecode C.idLens---- | Construct DAWG from the list of (word, value) pairs.-fromList :: Ord a => [(String, a)] -> DAWG a-fromList xs =-    let update t (x, v) = insert x v t-    in  foldl' update empty xs---- | Make DAWG from the list of words.  Annotate each word with--- the @()@ value.-fromLang :: [String] -> DAWG ()-fromLang xs = fromList [(x, ()) | x <- xs]

@@ -1,13 +1,9 @@ name:               dawg-version:            0.3.0+version:            0.4.0 synopsis:           Directed acyclic word graphs description:     The library implements /directed acyclic word graphs/ (DAWGs), which can-    be also interpreted as /minimal acyclic finite-state automata/. -    .-    In most cases you can use the "Data.DAWG" module which provides the basic-    implementation of DAWGs.  If values have substantial memory footprint-    consider using the "Data.DAWG.Wrapper" module instead.+    be also interpreted as /minimal acyclic finite-state automata/. license:            BSD3 license-file:       LICENSE cabal-version:      >= 1.6@@ -27,11 +23,9 @@       , vector       , vector-binary       , mtl-      , monad-codec >= 0.2 && < 0.3      exposed-modules:         Data.DAWG-      , Data.DAWG.Wrapper       , Data.DAWG.Graph       , Data.DAWG.VMap