packages feed

dawg-ord 0.4.0.2 → 0.5.0.0

raw patch · 8 files changed

+100/−90 lines, 8 filesdep +HUnitdep +dawg-orddep +smallcheck

Dependencies added: HUnit, dawg-ord, smallcheck, tasty, tasty-hunit, tasty-quickcheck, tasty-smallcheck

Files

dawg-ord.cabal view
@@ -1,20 +1,20 @@ name:               dawg-ord-version:            0.4.0.2+version:            0.5.0.0 synopsis:           Directed acyclic word graphs description:     The library implements /directed acyclic word graphs/ (DAWGs) internally     represented as /minimal acyclic deterministic finite-state automata/.-    The implemented version of DAWG is, semantically, a map from+    The implemented version of DAWG can be seen as a map from     sequences of alphabet symbols (keys) to values.     .     The library allows to build DAWGs over any symbols and values     provided that they both have `Ord` instances (see the-    `Data.DAWG.Ord` module).+    "Data.DAWG.Ord" module).     It also provides a fast insert operation which can be used to     construct DAWGs on-the-fly. license:            BSD3 license-file:       LICENSE-cabal-version:      >= 1.6+cabal-version:      >= 1.10 copyright:          Copyright (c) 2015 Jakub Waszczuk author:             Jakub Waszczuk maintainer:         waszczuk.kuba@gmail.com@@ -24,10 +24,12 @@ build-type:         Simple  library+    default-language:+        Haskell2010     hs-source-dirs: src     build-depends:         base            >= 4        && < 5-      , containers      >= 0.4.1    && < 0.6+      , containers      >= 0.5      && < 0.6       , vector          >= 0.10     && < 0.12       , mtl             >= 2.1      && < 2.3       , transformers    >= 0.3      && < 0.5@@ -51,6 +53,29 @@       , Data.DAWG.Gen.Util      ghc-options: -Wall+++test-suite test+    default-language:+        Haskell2010+    type:+        exitcode-stdio-1.0+    hs-source-dirs:+        tests+    main-is:+        test.hs+    build-depends:+        dawg-ord+      , base                    >= 4        && < 5+      , containers              >= 0.5      && < 0.6+      , mtl                     >= 2.1      && < 2.3+      , tasty                   >= 0.10+      , smallcheck              >= 1.1+      , tasty-smallcheck        >= 0.8+      , tasty-quickcheck        >= 0.8+      , tasty-hunit             >= 0.9+      , HUnit                   >= 1.2+  source-repository head     type: git
src/Data/DAWG/Gen/Types.hs view
@@ -6,11 +6,11 @@ , Val ) where --- | Node identifier.+-- | Identifier of a DAWG node (automaton state). type ID = Int --- | Internal representation of an alphabet element.+-- | A transition symbol. type Sym = Int --- | Internal representation of an automaton value.+-- | A type of DAWG values, stored in accept states. type Val = Int
src/Data/DAWG/Int.hs view
@@ -1,10 +1,11 @@ -- | The module implements /directed acyclic word graphs/ (DAWGs) internaly -- represented as /minimal acyclic deterministic finite-state automata/.--- The implementation provides a fast insert operation which can be--- used to build the DAWG structure incrementaly.+-- The implementation provides fast insert and delete operations+-- which can be used to build the DAWG structure incrementaly. ----- Keys and values must provide an 'Enum' instance; see the--- 'Data.DAWG.Ord' module if you look for a more generic solution.+-- See the "Data.DAWG.Ord" module if you look for a more generic+-- solution (which, for the moment, lacks some of the functionality provided+-- here, e.g. the `delete` function).   module Data.DAWG.Int@@ -12,6 +13,7 @@ -- * DAWG type   DAWG , ID+, Sym , Val , root
src/Data/DAWG/Int/Dynamic.hs view
@@ -176,27 +176,26 @@   -- | Empty DAWG.-empty :: DAWG a+empty :: DAWG empty =     let (i, g) = S.runState insertLeaf G.empty     in  DAWG g i   -- | Number of states in the automaton.-numStates :: DAWG a -> Int+numStates :: DAWG -> Int numStates = G.size . graph  --- | Number of edges in the automaton.-numEdges :: DAWG a -> Int+-- | Number of transitions in the automaton.+numEdges :: DAWG -> Int numEdges = sum . map (length . N.edges) . G.nodes . graph   -- | Insert the (key, value) pair into the DAWG.-insert :: Enum a => [a] -> Val -> DAWG a -> DAWG a-insert xs' y d =-    let xs = map fromEnum xs'-        (i, g) = S.runState (insertM xs y $ root d) (graph d)+insert :: [Sym] -> Val -> DAWG -> DAWG+insert xs y d =+    let (i, g) = S.runState (insertM xs y $ root d) (graph d)     in  DAWG g i {-# INLINE insert #-} @@ -206,32 +205,23 @@ -- 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-    :: Enum a => (Val -> Val -> Val)-    -> [a] -> Val -> DAWG a -> DAWG a-insertWith f xs' y d =-    let xs = map fromEnum xs'-        (i, g) = S.runState (insertWithM f xs y $ root d) (graph d)+    :: (Val -> Val -> Val)+    -> [Sym] -> Val -> DAWG -> DAWG+insertWith f xs y d =+    let (i, g) = S.runState (insertWithM f xs y $ root d) (graph d)     in  DAWG g i-{-# SPECIALIZE insertWith-        :: (Val -> Val -> Val) -> String -> Val-        -> DAWG Char -> DAWG Char #-}   -- | Delete the key from the DAWG.-delete :: Enum a => [a] -> DAWG a -> DAWG a-delete xs' d =-    let xs = map fromEnum xs'-        (i, g) = S.runState (deleteM xs $ root d) (graph d)+delete :: [Sym] -> DAWG -> DAWG+delete xs d =+    let (i, g) = S.runState (deleteM xs $ root d) (graph d)     in  DAWG g i-{-# SPECIALIZE delete :: String -> DAWG Char -> DAWG Char #-}   -- | Find value associated with the key.-lookup :: Enum a => [a] -> DAWG a -> Maybe Val-lookup xs' d =-    let xs = map fromEnum xs'-    in  S.evalState (lookupM xs $ root d) (graph d)-{-# SPECIALIZE lookup :: String -> DAWG Char -> Maybe Val #-}+lookup :: [Sym] -> DAWG -> Maybe Val+lookup xs d = S.evalState (lookupM xs $ root d) (graph d)   -- -- | Find all (key, value) pairs such that key is prefixed@@ -248,51 +238,40 @@   -- | Return all key/value pairs in the DAWG in ascending key order.-assocs :: Enum a => DAWG a -> [([a], Val)]-assocs-    = map (first (map toEnum))-    . (subPairs <$> graph <*> root)-{-# SPECIALIZE assocs :: DAWG Char -> [(String, Val)] #-}+assocs :: DAWG -> [([Sym], Val)]+assocs = subPairs <$> graph <*> root   -- | Return all keys of the DAWG in ascending order.-keys :: Enum a => DAWG a -> [[a]]+keys :: DAWG -> [[Sym]] keys = map fst . assocs-{-# SPECIALIZE keys :: DAWG Char -> [String] #-}   -- | Return all elements of the DAWG in the ascending order of their keys.-elems :: DAWG a -> [Val]+elems :: DAWG -> [Val] elems = map snd . (subPairs <$> graph <*> root)  --- | Construct DAWG from the list of (word, value) pairs.-fromList :: Enum a => [([a], Val)] -> DAWG a+-- | Construct DAWG from the list of (key, value) pairs.+fromList :: [([Sym], Val)] -> DAWG fromList xs =     let update t (x, v) = insert x v t     in  foldl' update empty xs-{-# INLINE fromList #-}  --- | Construct DAWG from the list of (word, value) pairs+-- | Construct DAWG from the list of (key, value) pairs -- with a combining function.  The combining function is -- applied strictly.-fromListWith-    :: Enum a => (Val -> Val -> Val)-    -> [([a], Val)] -> DAWG a+fromListWith :: (Val -> Val -> Val) -> [([Sym], Val)] -> DAWG fromListWith f xs =     let update t (x, v) = insertWith f x v t     in  foldl' update empty xs-{-# SPECIALIZE fromListWith-        :: (Val -> Val -> Val)-        -> [(String, Val)] -> DAWG Char #-}  --- | Make DAWG from the list of words.  Annotate each word with--- the @()@ value.-fromLang :: Enum a => [[a]] -> DAWG a+-- | Make DAWG from the list of words (by annotating each word with+-- a dummy value).+fromLang :: [[Sym]] -> DAWG fromLang xs = fromList [(x, 0) | x <- xs]-{-# SPECIALIZE fromLang :: [String] -> DAWG Char #-}   ------------------------------------------------------------@@ -301,24 +280,22 @@   -- | A list of outgoing edges (automaton transitions).-edges :: Enum a => ID -> DAWG a -> [(a, ID)]+edges :: ID -> DAWG -> [(Sym, ID)] edges i     = map (first toEnum)     . N.edges . G.nodeBy i     . graph-{-# SPECIALIZE edges :: ID -> DAWG Char -> [(Char, ID)] #-}-{-# SPECIALIZE edges :: ID -> DAWG Int  -> [(Int, ID)]  #-}   -- | Value stored in the given automaton state.-value :: ID -> DAWG a -> Maybe Val+value :: ID -> DAWG -> Maybe Val value i = N.value . G.nodeBy i . graph   -- | Follow a transition with the given symbol from the given state.-follow :: Enum a => ID -> a -> DAWG a -> Maybe ID+follow :: ID -> Sym -> DAWG -> Maybe ID follow i x DAWG{..} = flip S.evalState graph $ runMaybeT $-    followPath [fromEnum x] i+    followPath [x] i   ------------------------------------------------------------
src/Data/DAWG/Int/Dynamic/Internal.hs view
@@ -16,16 +16,12 @@ import qualified Data.DAWG.Int.Dynamic.Node as N  --- | A directed acyclic word graph with phantom type @a@--- representing the type of alphabet symbols (type @a@ must provide--- an 'Enum' instance).------ A DAWG is, semantically, a map from keys (sequences of @a@'s) to--- integral values.--- See 'Data.DAWG.Ord' for a more generic version of DAWGs.-data DAWG a = DAWG+-- | A directed acyclic word graph (DAWG), which can be seen as a map+-- from keys (sequences of 'Sym`'s) to values 'Val'.+-- See "Data.DAWG.Ord" for a more generic version of DAWGs.+data DAWG = DAWG     { graph :: !(Graph N.Node)-    -- | Root of the DAWG.+    -- | The root (start state) of the DAWG.     , root  :: !ID }     deriving (Show, Eq, Ord)
src/Data/DAWG/Ord.hs view
@@ -1,4 +1,4 @@--- | A version of 'Data.DAWG.Int' adapted to keys and values with+-- | A version of "Data.DAWG.Int" adapted to keys and values with -- 'Ord' instances.
src/Data/DAWG/Ord/Dynamic.hs view
@@ -1,7 +1,7 @@ {-# LANGUAGE RecordWildCards #-}  --- | A version of 'Data.DAWG.Int.Dynamic' adapted to+-- | A version of "Data.DAWG.Int.Dynamic" adapted to -- keys and values with 'Ord' instances.  @@ -56,10 +56,10 @@ -- the type of alphabet symbols (over which keys are constructed) -- and type @b@ -- the type of values. ----- A DAWG is, semantically, a map from keys (sequences of @a@'s) to+-- A DAWG can be seen as a map from keys (sequences of @a@'s) to -- values @b@. data DAWG a b = DAWG-    { intDAWG   :: D.DAWG Sym+    { intDAWG   :: D.DAWG     , symMap    :: M.Map a Int     , symMapR   :: M.Map Int a     , valMap    :: M.Map b Int@@ -67,7 +67,7 @@     } deriving (Show, Eq, Ord)  --- | Root of the DAWG.+-- | The root (start state) of the DAWG. root :: DAWG a b -> ID root = D.root . intDAWG @@ -103,9 +103,10 @@ -- TODO: We could optimize it. addVal :: Ord b => b -> DM a b Int addVal x = S.state $ \dawg@DAWG{..} ->-    let y = case M.lookup x valMap of-            Nothing -> M.size valMap-            Just k  -> k+    let y = fromMaybe (M.size valMap) (M.lookup x valMap)+--     let y = case M.lookup x valMap of+--             Nothing -> M.size valMap+--             Just k  -> k     in  (y, dawg             { valMap  = M.insert x y valMap             , valMapR = M.insert y x valMapR })@@ -125,12 +126,12 @@ empty = DAWG D.empty M.empty M.empty M.empty M.empty  --- | Number of states in the automaton.+-- | Number of states in the underlying automaton. numStates :: DAWG a b -> Int numStates = D.numStates . intDAWG  --- | Number of edges in the automaton.+-- | Number of transitions in the underlying automaton. numEdges :: DAWG a b -> Int numEdges = D.numEdges . intDAWG @@ -168,14 +169,14 @@ -- | Find value associated with the key. lookup :: (Ord a, Ord b) => [a] -> DAWG a b -> Maybe b lookup xs0 DAWG{..} = do-    xs <- mapM (flip M.lookup symMap) xs0+    xs <- mapM (`M.lookup` symMap) xs0     y  <- D.lookup xs intDAWG     M.lookup y valMapR   -- | Return all key/value pairs in the DAWG in ascending key order. assocs :: DAWG a b -> [([a], b)]-assocs DAWG{..} = +assocs DAWG{..} =     [ (decodeKey xs, decodeVal y)     | (xs, y) <- D.assocs intDAWG ]   where@@ -194,15 +195,15 @@ elems = map snd . assocs  --- | Construct DAWG from the list of (word, value) pairs.+-- | Construct DAWG from the list of (key, value) pairs. fromList :: (Ord a, Ord b) => [([a], b)] -> DAWG a b 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.+-- | Make DAWG from the list of words (annotate each word with+-- the @()@ value). fromLang :: Ord a => [[a]] -> DAWG a () fromLang xs = fromList [(x, ()) | x <- xs]
+ tests/test.hs view
@@ -0,0 +1,9 @@+import           Test.Tasty (defaultMain, testGroup)++import qualified Ord+++main :: IO ()+main = defaultMain $ testGroup "Tests"+    [ Ord.tests+    ]