dawg-ord 0.2 → 0.3

raw patch · 10 files changed

+125/−67 lines, 10 filesdep −binarydep ~mtldep ~transformersdep ~vectorPVP ok

version bump matches the API change (PVP)

Dependencies removed: binary

Dependency ranges changed: mtl, transformers, vector

API changes (from Hackage documentation)

Files

• dawg-ord.cabal +11/−13
• src/Data/DAWG/Gen/Graph.hs +23/−23
• src/Data/DAWG/Gen/HashMap.hs +12/−12
• src/Data/DAWG/Gen/Trans/Hashed.hs +10/−10
• src/Data/DAWG/Gen/Trans/Map.hs +2/−2
• src/Data/DAWG/Gen/Types.hs +0/−4
• src/Data/DAWG/Int.hs +30/−0
• src/Data/DAWG/Int/Dynamic.hs +1/−1
• src/Data/DAWG/Ord.hs +34/−0
• src/Data/DAWG/Ord/Dynamic.hs +2/−2

@@ -1,5 +1,5 @@ name:               dawg-ord-version:            0.2+version:            0.3 synopsis:           Directed acyclic word graphs description:     The library implements /directed acyclic word graphs/ (DAWGs)@@ -24,24 +24,22 @@ library     hs-source-dirs: src     build-depends:-        base            >= 4 && < 5-      , containers      >= 0.4.1 && < 0.6-      , binary-      , vector-      -- , vector-binary-      , mtl-      , transformers+        base            >= 4        && < 5+      , containers      >= 0.4.1    && < 0.6+      , vector          >= 0.10     && < 0.12+      , mtl             >= 2.1      && < 2.3+      , transformers    >= 0.3      && < 0.5      exposed-modules:+        Data.DAWG.Ord+      , Data.DAWG.Int++    other-modules:         Data.DAWG.Gen.Types       , Data.DAWG.Int.Dynamic       , Data.DAWG.Ord.Dynamic---       , Data.DAWG.Ord.Static--    other-modules:-        Data.DAWG.Int.Dynamic.Internal+      , Data.DAWG.Int.Dynamic.Internal       , Data.DAWG.Int.Dynamic.Node-      -- , Data.DAWG.Int.Static.Node       , Data.DAWG.Gen.Graph       , Data.DAWG.Gen.Trans       , Data.DAWG.Gen.Trans.Vector

@@ -19,7 +19,7 @@   -- import Control.Applicative ((<$>), (<*>))-import Data.Binary (Binary, put, get)+-- import Data.Binary (Binary, put, get) import qualified Data.IntSet as S import qualified Data.IntMap as M @@ -29,7 +29,7 @@   -- | A set of nodes.  To every node a unique identifier is assigned.--- Invariants: +-- Invariants: -- --   * freeIDs \\intersection occupiedIDs = \\emptySet, --@@ -46,7 +46,7 @@       idMap     :: !(H.HashMap n ID)     -- | Set of free IDs.     , freeIDs   :: !S.IntSet-    -- | Map from IDs to nodes. +    -- | Map from IDs to nodes.     , nodeMap   :: !(M.IntMap n)     -- | Number of ingoing paths (different paths from the root     -- to the given node) for each node ID in the graph.@@ -56,13 +56,13 @@     , ingoMap   :: !(M.IntMap Int) }     deriving (Show, Eq, Ord) -instance (Ord n, Binary n) => Binary (Graph n) where-    put Graph{..} = do-        put idMap-        put freeIDs-        put nodeMap-        put ingoMap-    get = Graph <$> get <*> get <*> get <*> get+-- instance (Ord n, Binary n) => Binary (Graph n) where+--     put Graph{..} = do+--         put idMap+--         put freeIDs+--         put nodeMap+--         put ingoMap+--     get = Graph <$> get <*> get <*> get <*> get  -- | Empty graph. empty :: Graph n@@ -134,7 +134,7 @@  -- | Delete node from the graph.  If the node was present in the graph -- at multiple positions, just decrease the number of ingoing paths.--- Function crashes if the node is not a member of the graph. +-- Function crashes if the node is not a member of the graph. -- 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.@@ -164,45 +164,45 @@ --             ingo = m IM.! i --         in  foldl' (push ingo) m (edges n) --     push x m j = IM.adjust (+x) j m--- +-- -- postorder :: T.Tree a -> [a] -> [a] -- postorder (T.Node a ts) = postorderF ts . (a :)--- +-- -- postorderF :: T.Forest a -> [a] -> [a] -- postorderF ts = foldr (.) id $ map postorder ts--- +-- -- postOrd :: Graph a -> ID -> [ID] -- postOrd g i = postorder (dfs g i) []--- +-- -- -- | Topological sort given a root ID. -- topSort :: Graph a -> ID -> [ID] -- topSort g = reverse . postOrd g--- +-- -- -- | Depth first search starting with given ID. -- dfs :: Graph a -> ID -> T.Tree ID -- dfs g = prune . generate g--- +-- -- generate :: Graph a -> ID -> T.Tree ID -- generate g i = T.Node i --     ( T.Node (eps n) [] --     : map (generate g) (edges n) ) --   where --     n = nodeBy i g--- +-- -- type SetM a = S.State IS.IntSet a--- +-- -- run :: SetM a -> a -- run act = S.evalState act IS.empty--- +-- -- contains :: ID -> SetM Bool -- contains i = IS.member i <$> S.get--- +-- -- include :: ID -> SetM () -- include i = S.modify (IS.insert i)--- +-- -- prune :: T.Tree ID -> T.Tree ID -- prune t = head $ run (chop [t])--- +-- -- chop :: T.Forest ID -> SetM (T.Forest ID) -- chop [] = return [] -- chop (T.Node v ts : us) = do

@@ -17,7 +17,7 @@  import Prelude hiding (lookup) -- import Control.Applicative ((<$>), (<*>))-import Data.Binary (Binary, Get, put, get)+-- import Data.Binary (Binary, Get, put, get) import qualified Data.Map as M import qualified Data.IntMap as I @@ -59,14 +59,14 @@   -- | Value Binary instance.-instance (Ord a, Binary a, Binary b) => Binary (Value a b) where-    put (Single x y)    = put (1 :: Int) >> put x >> put y-    put (Multi m)       = put (2 :: Int) >> put m-    get = do-        x <- get :: Get Int-        case x of-            1   -> Single <$> get <*> get-            _   -> Multi <$> get+-- instance (Ord a, Binary a, Binary b) => Binary (Value a b) where+--     put (Single x y)    = put (1 :: Int) >> put x >> put y+--     put (Multi m)       = put (2 :: Int) >> put m+--     get = do+--         x <- get :: Get Int+--         case x of+--             1   -> Single <$> get <*> get+--             _   -> Multi <$> get   -- | Find element associated to a value key.@@ -119,9 +119,9 @@     , hashMap   :: !(I.IntMap (Value a b)) }     deriving (Show, Eq, Ord) -instance (Ord a, Binary a, Binary b) => Binary (HashMap a b) where-    put HashMap{..} = put size >> put hashMap-    get = HashMap <$> get <*> get+-- instance (Ord a, Binary a, Binary b) => Binary (HashMap a b) where+--     put HashMap{..} = put size >> put hashMap+--     get = HashMap <$> get <*> get   -- | Empty map.

@@ -12,9 +12,9 @@   import           Prelude hiding (lookup)-import           Control.Applicative ((<$>), (<*>))+-- import           Control.Applicative ((<$>), (<*>)) import           Data.DAWG.Gen.Util (combine)-import           Data.Binary (Binary, put, get)+-- import           Data.Binary (Binary, put, get) import           Data.DAWG.Gen.Trans import qualified Data.DAWG.Gen.Trans.Map as M import qualified Data.DAWG.Gen.Trans.Vector as V@@ -27,23 +27,23 @@     , trans :: !t }     deriving (Show) -instance Binary t => Binary (Hashed t) where-    put Hashed{..} = put hash >> put trans-    get = Hashed <$> get <*> get+-- instance Binary t => Binary (Hashed t) where+--     put Hashed{..} = put hash >> put trans+--     get = Hashed <$> get <*> get   instance Trans t => Trans (Hashed t) where     empty       = Hashed 0 empty-    {-# INLINE empty #-} +    {-# INLINE empty #-}      lookup x    = lookup x . trans-    {-# INLINE lookup #-} +    {-# INLINE lookup #-}      index x     = index x . trans-    {-# INLINE index #-} +    {-# INLINE index #-}      byIndex i   = byIndex i . trans-    {-# INLINE byIndex #-} +    {-# INLINE byIndex #-}      insert x y (Hashed h t) = Hashed         (h - h' + combine x y)@@ -54,7 +54,7 @@             Nothing -> 0     {-# INLINE insert #-} -    fromList xs = Hashed +    fromList xs = Hashed         (sum $ map (uncurry combine) xs)         (fromList xs)     {-# INLINE fromList #-}

@@ -10,7 +10,7 @@   import Prelude hiding (lookup)-import Data.Binary (Binary)+-- import Data.Binary (Binary) import qualified Data.Map as M  import Data.DAWG.Gen.Types@@ -20,7 +20,7 @@ -- | A vector of distinct key/value pairs strictly ascending with respect -- to key values. newtype Trans = Trans { unTrans :: M.Map Sym ID }-    deriving (Show, Eq, Ord, Binary)+    deriving (Show, Eq, Ord) -- , Binary)   instance C.Trans Trans where

@@ -3,7 +3,6 @@ module Data.DAWG.Gen.Types ( ID , Sym-, Val ) where  -- | Node identifier.@@ -11,6 +10,3 @@  -- | Internal representation of an alphabet element. type Sym = Int---- | Internal representation of an automaton value.-type Val = Int

@@ -0,0 +1,30 @@+module Data.DAWG.Int+(+-- * DAWG type+  DAWG+, ID+, root++-- * Query+, member+, numStates+, numEdges++-- * Traversal+, accept+, edges+, follow++-- * Construction+, empty+, fromList+-- ** Insertion+, insert++-- * Conversion+, keys+) where+++import           Data.DAWG.Gen.Types+import           Data.DAWG.Int.Dynamic

@@ -35,7 +35,7 @@ ) where  -import Control.Applicative ((<$>), (<*>))+-- import Control.Applicative ((<$>), (<*>)) import Control.Arrow (first) import Data.List (foldl') import qualified Control.Monad.State.Strict as S

@@ -0,0 +1,34 @@+-- | A version of `Data.DAWG.Int` adapted to words with `Ord`+-- instances.+++module Data.DAWG.Ord+(+-- * DAWG type+  DAWG+, ID+, root++-- * Query+, member+, numStates+, numEdges++-- * Traversal+, accept+, edges+, follow++-- * Construction+, empty+, fromList+-- ** Insertion+, insert++-- * Conversion+, keys+) where+++import           Data.DAWG.Gen.Types+import           Data.DAWG.Ord.Dynamic

@@ -1,8 +1,8 @@ {-# LANGUAGE RecordWildCards #-}  --- | The simplified version of `Data.DAWG.Ord.Dynamic` adapted to--- keys and values with `Ord` instances.+-- | A version of `Data.DAWG.Int.Dynamic` adapted to words with `Ord`+-- instances.   module Data.DAWG.Ord.Dynamic