dawg 0.2.0 → 0.3.0

raw patch · 4 files changed

+80/−19 lines, 4 filesdep +monad-codecdep ~containersPVP ok

version bump matches the API change (PVP)

Dependencies added: monad-codec

Dependency ranges changed: containers

API changes (from Hackage documentation)

Files

• Data/DAWG.hs +2/−2
• Data/DAWG/Graph.hs +4/−12
• Data/DAWG/Wrapper.hs +62/−0
• dawg.cabal +12/−5

@@ -90,7 +90,7 @@     , root  :: !Id }     deriving (Show, Eq, Ord) -instance (Binary a, Ord a) => Binary (DAWG a) where+instance (Ord a, Binary a) => Binary (DAWG a) where     put d = do         put (graph d)         put (root d)@@ -123,7 +123,7 @@ lookup xs d = S.evalState (lookupM xs $ root d) (graph d)  -- | Construct DAWG from the list of (word, value) pairs.-fromList :: (Ord a) => [(String, a)] -> DAWG a+fromList :: Ord a => [(String, a)] -> DAWG a fromList xs =     let update t (x, v) = insert x v t     in  foldl' update empty xs

@@ -24,9 +24,9 @@  import Control.Applicative ((<$>), (<*>)) import Data.Binary (Binary, put, get)-import qualified Data.Map.Strict as M+import qualified Data.Map as M import qualified Data.IntSet as IS-import qualified Data.IntMap.Strict as IM+import qualified Data.IntMap as IM  import qualified Data.DAWG.VMap as V @@ -84,7 +84,7 @@     , ingoMap   :: !(IM.IntMap Int) }     deriving (Show, Eq, Ord) -instance (Binary a, Ord a) => Binary (Graph a) where+instance (Ord a, Binary a) => Binary (Graph a) where     put Graph{..} = do     	put idMap 	put freeIDs@@ -96,14 +96,6 @@ empty :: Graph a 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@@ -141,7 +133,7 @@  -- | Increment the number of ingoing paths. incIngo :: Id -> Graph a -> Graph a-incIngo i g = g { ingoMap = IM.adjust (+1) i (ingoMap g) }+incIngo i g = g { ingoMap = IM.insertWith' (+) i 1 (ingoMap g) }  -- | Descrement the number of ingoing paths and return -- the resulting number.

@@ -0,0 +1,62 @@+-- | 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,8 +1,13 @@ name:               dawg-version:            0.2.0-synopsis:           DAWG+version:            0.3.0+synopsis:           Directed acyclic word graphs description:-    Directed acyclic word graphs.+    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. license:            BSD3 license-file:       LICENSE cabal-version:      >= 1.6@@ -17,18 +22,20 @@ library     build-depends:         base >= 4 && < 5-      , containers >= 0.5 && < 0.6+      , containers       , binary       , vector       , vector-binary       , mtl+      , monad-codec >= 0.2 && < 0.3      exposed-modules:         Data.DAWG+      , Data.DAWG.Wrapper       , Data.DAWG.Graph       , Data.DAWG.VMap -    ghc-options: -Wall+    ghc-options: -Wall -O2  source-repository head     type: git