dawg 0.4.0 → 0.5.0

raw patch · 4 files changed

+63/−17 lines, 4 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• Data/DAWG.hs +38/−4
• Data/DAWG/Graph.hs +10/−4
• Data/DAWG/VMap.hs +14/−8
• dawg.cabal +1/−1

@@ -4,13 +4,23 @@ -- which can be used to build the DAWG structure incrementaly.  module Data.DAWG-( DAWG (..)-, empty+(+-- * DAWG type+  DAWG (..)+-- * Query , numStates+, lookup+-- * Construction+, empty+-- ** Insertion , insert , insertWith+-- ** Deletion , delete-, lookup+-- * Conversion+, elems+, keys+, assocs , fromList , fromListWith , fromLang@@ -18,6 +28,7 @@  import Prelude hiding (lookup) import Control.Applicative ((<$>), (<*>))+import Control.Arrow (first) import Data.List (foldl') import Data.Binary (Binary, put, get) import qualified Control.Monad.State.Strict as S@@ -26,7 +37,7 @@ import qualified Data.DAWG.Graph as G import qualified Data.DAWG.VMap as V -type GraphM a b = S.State (Graph (Maybe 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)@@ -114,6 +125,17 @@         Just j  -> lookupM xs j         Nothing -> return Nothing +assocsAcc :: Graph (Maybe a) -> Id -> [(String, a)]+assocsAcc g i =+    here w ++ concatMap there (G.edges n)+  where+    n = G.nodeBy i g+    w = G.nodeBy (G.eps n) g+    here v = case G.unValue v of+        Just x  -> [("", x)]+        Nothing -> []+    there (char, j) = map (first (char:)) (assocsAcc g j)+ -- | A 'G.Graph' with one root from which all other graph nodes should -- be accesible. data DAWG a = DAWG@@ -161,6 +183,18 @@ -- | Find value associated with the key. lookup :: String -> DAWG a -> Maybe a lookup xs d = S.evalState (lookupM xs $ root d) (graph d)++-- | Return all keys of the DAWG in ascending order.+keys :: DAWG a -> [String]+keys = map fst . assocs++-- | Return all elements of the DAWG in the ascending order of their keys.+elems :: DAWG a -> [a]+elems = map snd . assocs++-- | Return all key/value pairs in the DAWG in ascending key order.+assocs :: DAWG a -> [(String, a)]+assocs d = assocsAcc (graph d) (root d)  -- | Construct DAWG from the list of (word, value) pairs. fromList :: Ord a => [(String, a)] -> DAWG a

@@ -10,6 +10,7 @@ -- * Node   Node (..) , Id+, edges , onChar , subst -- * Graph@@ -39,11 +40,11 @@ -- edges. -- -- Invariant: the 'value' identifier always points to the 'Value' node.--- 'edges', on the other hand, point to 'Branch' nodes.+-- Edges in the 'edgeMap', on the other hand, point to 'Branch' nodes. data Node a     = Branch-        { eps   :: {-# UNPACK #-} !Id-        , edges :: !(V.VMap Id) }+        { eps       :: {-# UNPACK #-} !Id+        , edgeMap   :: !(V.VMap Id) }     | Value         { unValue :: !a }     deriving (Show, Eq, Ord)@@ -53,13 +54,18 @@     fmap _ (Branch x y) = Branch x y  instance Binary a => Binary (Node a) where-    put Branch{..} = put (1 :: Int) >> put eps >> put edges+    put Branch{..} = put (1 :: Int) >> put eps >> put edgeMap     put Value{..}  = put (2 :: Int) >> put unValue     get = do         x <- get :: Get Int         case x of             1 -> Branch <$> get <*> get             _ -> Value <$> get++-- | List of non-epsilon edges outgoing from the 'Branch' node.+edges :: Node a -> [(Char, Id)]+edges (Branch _ es)     = V.toList es+edges (Value _)         = error "edges: value node"  -- | Identifier of the child determined by the given character. onChar :: Char -> Node a -> Maybe Id

@@ -2,10 +2,11 @@  module Data.DAWG.VMap ( VMap (unVMap)-, mkVMap , empty , lookup , insert+, fromList+, toList ) where  import Prelude hiding (lookup)@@ -24,12 +25,6 @@     put v = put (unVMap v)     get = VMap <$> get --- | Smart VMap constructor which ensures that the underlying vector is--- strictly ascending with respect to 'fst' values.-mkVMap :: U.Unbox a => [(Char, a)] -> VMap a-mkVMap = VMap . U.fromList . M.toAscList  . M.fromList -{-# INLINE mkVMap #-}- -- | Empty map. empty :: U.Unbox a => VMap a empty = VMap U.empty@@ -40,7 +35,7 @@ lookup x = fmap snd . U.find ((==x) . fst) . unVMap {-# INLINE lookup #-} --- | Insert the (character, value) pair into the map.+-- | Insert the character/value pair into the map. -- TODO: Optimize!  Use the invariant, that VMap is -- kept in an ascending vector. insert :: U.Unbox a => Char -> a -> VMap a -> VMap a@@ -49,3 +44,14 @@     . M.insert x y     . M.fromList . U.toList . unVMap {-# INLINE insert #-}++-- | Smart 'VMap' constructor which ensures that the underlying vector is+-- strictly ascending with respect to 'fst' values.+fromList :: U.Unbox a => [(Char, a)] -> VMap a+fromList = VMap . U.fromList . M.toAscList  . M.fromList +{-# INLINE fromList #-}++-- | Convert the 'VMap' to a list of ascending character/value pairs.+toList :: U.Unbox a => VMap a -> [(Char, a)]+toList = U.toList . unVMap+{-# INLINE toList #-}

@@ -1,5 +1,5 @@ name:               dawg-version:            0.4.0+version:            0.5.0 synopsis:           Directed acyclic word graphs description:     The library implements /directed acyclic word graphs/ (DAWGs), which can