bytestring-trie 0.2.3 → 0.2.4

raw patch · 10 files changed

+221/−20 lines, 10 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• AUTHORS +16/−0
• LICENSE +1/−1
• VERSION +17/−0
• bytestring-trie.cabal +16/−8
• src/Data/Trie.hs +29/−4
• src/Data/Trie/ByteStringInternal.hs +1/−1
• src/Data/Trie/ByteStringInternal/indexOfDifference.c +1/−1
• src/Data/Trie/Convenience.hs +1/−1
• src/Data/Trie/Errors.hs +1/−1
• src/Data/Trie/Internal.hs +138/−3

@@ -0,0 +1,16 @@+=== Haskell bytestring-trie package AUTHORS/THANKS file ===++The bytestring-trie package was written by wren gayle romano and is+released under the terms in the LICENSE file. I would also like to+give thanks to the following contributers:++Maxime Henrion --- for the Binary (Trie a) instance and extensive+    debugging work including almost all of the QuickCheck properties.++Don Stewart --- for fostering the idea and offering feedback on+    when the unsafe is safe in the internals of ByteStrings.++Mark Wotton --- for benchmarking work comparing Trie to Map ByteString,+    and for debugging.++Gregory Crosswhite --- finding the critical bug in mergeBy

@@ -1,4 +1,4 @@-Copyright (c) 2008, 2009, 2010, 2011 wren ng thornton.+Copyright (c) 2008--2013, wren gayle romano. ALL RIGHTS RESERVED.  Redistribution and use in source and binary forms, with or without

@@ -0,0 +1,17 @@+0.2.4 (2014.10.09):+    - added Data.Trie.Internal.{match_,matches_}, Data.Trie.Base.{match,matches}+0.2.3 (2010.02.12):+    - added Data.Trie.Internal.alterBy_+    - added Data.Trie.Internal.{contextualMap, contextualMap', contextualFilterMap, contextualMapBy}+    - added Data.Trie.Convenience.{fromListWith', fromListWithL, fromListWithL'} as suggested by Ian Taylor+    - added Data.Trie.Convenience{insertWith', insertWithKey', unionWith'}+    - converted fmap, foldMap, traverse, and filterMap to worker/wrapper+0.2.2 (2010.06.10):+    - Corrected a major bug in mergeBy, reported by Gregory Crosswhite+0.2.1.1 (2009.12.20):+    - Added a VERSION file+0.2.1 (2009.02.13):+    - Most recent release before adding a VERSION file++0.1.4 (2009.01.11):+	- The only previous tag

@@ -1,19 +1,22 @@ ------------------------------------------------------------------- wren ng thornton <wren@community.haskell.org>    ~ 2010.11.12+-- wren gayle romano <wren@community.haskell.org>   ~ 2014.10.09 ---------------------------------------------------------------- -Name:           bytestring-trie-Version:        0.2.3--- Source-Repository requires version 1.6+-- By and large Cabal >=1.2 is fine; but >= 1.6 gives tested-with:+-- and source-repository:. Cabal-Version:  >= 1.6 Build-Type:     Simple++Name:           bytestring-trie+Version:        0.2.4 Stability:      provisional-Copyright:      Copyright (c) 2008--2011 wren ng thornton+Homepage:       http://code.haskell.org/~wren/+Author:         wren gayle romano+Maintainer:     wren@community.haskell.org+Copyright:      Copyright (c) 2008--2014 wren gayle romano License:        BSD3 License-File:   LICENSE-Author:         wren ng thornton-Maintainer:     wren@community.haskell.org-Homepage:       http://code.haskell.org/~wren/+ Category:       Data, Data Structures Synopsis:       An efficient finite map from (byte)strings to values. Description:    An efficient finite map from (byte)strings to values.@@ -37,6 +40,11 @@                 contextual mapping, extracting the minimum and                 maximum keys, etc.) ++Tested-With:+    GHC == 6.12.1, GHC == 7.6.1+Extra-source-files:+    AUTHORS, VERSION Source-Repository head     Type:     darcs     Location: http://community.haskell.org/~wren/bytestring-trie

@@ -2,10 +2,10 @@ {-# OPTIONS_GHC -Wall -fwarn-tabs -fno-warn-unused-imports #-} {-# LANGUAGE NoImplicitPrelude #-} -------------------------------------------------------------------                                                  ~ 2011.02.12+--                                                  ~ 2014.10.09 -- | -- Module      :  Data.Trie--- Copyright   :  Copyright (c) 2008--2011 wren ng thornton+-- Copyright   :  Copyright (c) 2008--2014 wren gayle romano -- License     :  BSD3 -- Maintainer  :  wren@community.haskell.org -- Stability   :  experimental@@ -45,7 +45,7 @@     , fromList, toListBy, toList, keys, elems          -- * Query functions-    , lookupBy, lookup, member, submap+    , lookupBy, lookup, member, submap, match, matches          -- * Single-value modification     , alterBy, insert, adjust, delete@@ -63,6 +63,7 @@ import Data.Trie.Internal import Data.Trie.Errors   (impossible) import Data.ByteString    (ByteString)+import qualified Data.ByteString as S import Data.Maybe         (isJust) import Control.Monad      (liftM) ----------------------------------------------------------------@@ -112,11 +113,35 @@ {-# INLINE lookup #-} lookup = lookupBy_ const Nothing (const Nothing) --- TODO? move to "Data.Trie.Conventience"?+-- TODO? move to "Data.Trie.Convenience"? -- | Does a string have a value in the trie? member :: ByteString -> Trie a -> Bool {-# INLINE member #-} member q = isJust . lookup q+++-- | Given a query, find the longest prefix with an associated value+-- in the trie, returning that prefix, it's value, and the remaining+-- string.+match :: Trie a -> ByteString -> Maybe (ByteString, a, ByteString)+match t q =+    case match_ t q of+    Nothing    -> Nothing+    Just (n,x) ->+        case S.splitAt n q of+        (p,q') -> Just (p, x, q')+++-- | Given a query, find all prefixes with associated values in the+-- trie, returning the prefixes, their values, and their remaining+-- strings. This function is a good producer for list fusion.+matches :: Trie a -> ByteString -> [(ByteString, a, ByteString)]+{-# INLINE matches #-}+matches t q = map f (matches_ t q)+    where+    f (n,x) =+        case S.splitAt n q of+        (p,q') -> (p, x, q')   {---------------------------------------------------------------

@@ -15,7 +15,7 @@ --                                                  ~ 2009.02.06 -- | -- Module      :  Data.Trie.ByteStringInternal--- Copyright   :  Copyright (c) 2008--2011 wren ng thornton+-- Copyright   :  Copyright (c) 2008--2011 wren gayle romano -- License     :  BSD3 -- Maintainer  :  wren@community.haskell.org -- Stability   :  experimental

@@ -2,7 +2,7 @@ --                                                  ~ 2009.01.07 -- | -- Module      :  Data.Trie.ByteStringInternal.indexOfDifference--- Copyright   :  Copyright (c) 2008--2011 wren ng thornton+-- Copyright   :  Copyright (c) 2008--2011 wren gayle romano -- License     :  BSD3 -- Maintainer  :  wren@community.haskell.org -- Stability   :  beta

@@ -4,7 +4,7 @@ --                                                  ~ 2011.02.12 -- | -- Module      :  Data.Trie.Convenience--- Copyright   :  Copyright (c) 2008--2011 wren ng thornton+-- Copyright   :  Copyright (c) 2008--2011 wren gayle romano -- License     :  BSD3 -- Maintainer  :  wren@community.haskell.org -- Stability   :  experimental

@@ -4,7 +4,7 @@ --                                                  ~ 2011.02.12 -- | -- Module      :  Data.Trie.Errors--- Copyright   :  Copyright (c) 2008--2011 wren ng thornton+-- Copyright   :  Copyright (c) 2008--2011 wren gayle romano -- License     :  BSD3 -- Maintainer  :  wren@community.haskell.org -- Stability   :  experimental

@@ -6,10 +6,10 @@ {-# LANGUAGE CPP #-}  -------------------------------------------------------------------                                                  ~ 2010.08.15+--                                                  ~ 2014.10.09 -- | -- Module      :  Data.Trie.Internal--- Copyright   :  Copyright (c) 2008--2011 wren ng thornton+-- Copyright   :  Copyright (c) 2008--2014 wren gayle romano -- License     :  BSD3 -- Maintainer  :  wren@community.haskell.org -- Stability   :  provisional@@ -38,6 +38,7 @@          -- * Query functions     , lookupBy_, submap+    , match_, matches_          -- * Single-value modification     , alterBy, alterBy_, adjustBy@@ -291,7 +292,7 @@ --  2. m >>= return    == m --  3. (m >>= f) >>= g == m >>= (\x -> f x >>= g) instance Monad Trie where-    return x = singleton S.empty x+    return = singleton S.empty          (>>=) Empty              _ = empty     (>>=) (Branch p m l r)   f = branch p m (l >>= f) (r >>= f)@@ -644,6 +645,140 @@ {-# NOINLINE errorEmptyAfterNothing #-} errorEmptyAfterNothing s = errorInvariantBroken s "Empty after Nothing" -- -}++++-- TODO: would it be worth it to have a variant like 'lookupBy_' which takes the three continuations?++-- | Given a query, find the longest prefix with an associated value+-- in the trie, returning the length of that prefix and the associated+-- value.+--+-- This function may not have the most useful return type. For a+-- version that returns the prefix itself as well as the remaining+-- string, see @match@ in "Data.Trie".+match_ :: Trie a -> ByteString -> Maybe (Int, a)+match_ = flip start+    where+    -- | Deal with epsilon query (when there is no epsilon value)+    start q (Branch _ _ _ _) | S.null q = Nothing+    start q t                           = goNothing 0 q t+    +    -- | The initial recursion+    goNothing _ _    Empty       = Nothing+    +    goNothing n q   (Arc k mv t) =+        let (p,k',q') = breakMaximalPrefix k q+            n'        = n + S.length p+        in n' `seq`+            if S.null k'+            then+                if S.null q'+                then (,) n' <$> mv+                else+                    case mv of+                    Nothing -> goNothing   n' q' t+                    Just v  -> goJust n' v n' q' t+            else Nothing+        +    goNothing n q t_@(Branch _ _ _ _) = findArc t_+        where+        qh = errorLogHead "match_" q+        +        -- | /O(min(m,W))/, where /m/ is number of @Arc@s in this+        -- branching, and /W/ is the word size of the Prefix,Mask type.+        findArc (Branch p m l r)+            | nomatch qh p m  = Nothing+            | zero qh m       = findArc l+            | otherwise       = findArc r+        findArc t@(Arc _ _ _) = goNothing n q t+        findArc Empty         = Nothing+        +    -- | The main recursion+    goJust n0 v0 _ _    Empty       = Just (n0,v0)+    +    goJust n0 v0 n q   (Arc k mv t) =+        let (p,k',q') = breakMaximalPrefix k q+            n'        = n + S.length p+        in n' `seq`+            if S.null k'+            then+                if S.null q'+                then+                    case mv of+                    Nothing -> Just (n0,v0)+                    Just v  -> Just (n',v)+                else+                    case mv of+                    Nothing -> goJust n0 v0 n' q' t+                    Just v  -> goJust n' v  n' q' t+            else Just (n0,v0)+        +    goJust n0 v0 n q t_@(Branch _ _ _ _) = findArc t_+        where+        qh = errorLogHead "match_" q+        +        -- | /O(min(m,W))/, where /m/ is number of @Arc@s in this+        -- branching, and /W/ is the word size of the Prefix,Mask type.+        findArc (Branch p m l r)+            | nomatch qh p m  = Just (n0,v0)+            | zero qh m       = findArc l+            | otherwise       = findArc r+        findArc t@(Arc _ _ _) = goJust n0 v0 n q t+        findArc Empty         = Just (n0,v0)+++-- | Given a query, find all prefixes with associated values in the+-- trie, returning their lengths and values. This function is a+-- good producer for list fusion.+--+-- This function may not have the most useful return type. For a+-- version that returns the prefix itself as well as the remaining+-- string, see @matches@ in "Data.Trie".+matches_ :: Trie a -> ByteString -> [(Int,a)]+matches_ t q =+#if !defined(__GLASGOW_HASKELL__)+    matchFB_ t q (((:) .) . (,)) []+#else+    build (\cons nil -> matchFB_ t q ((cons .) . (,)) nil)+{-# INLINE matches_ #-}+#endif++matchFB_ :: Trie a -> ByteString -> (Int -> a -> r -> r) -> r -> r+matchFB_ = \t q cons nil -> matchFB_' cons q t nil+    where+    matchFB_' cons = start+        where+        -- | Deal with epsilon query (when there is no epsilon value)+        start q (Branch _ _ _ _) | S.null q = id+        start q t                           = go 0 q t+    +        -- | The main recursion+        go _ _    Empty       = id+        +        go n q   (Arc k mv t) =+            let (p,k',q') = breakMaximalPrefix k q+                n'        = n + S.length p+            in n' `seq`+                if S.null k'+                then+                    case mv of { Nothing -> id; Just v  -> cons n' v}+                    .+                    if S.null q' then id else go n' q' t+                else id+            +        go n q t_@(Branch _ _ _ _) = findArc t_+            where+            qh = errorLogHead "matches_" q+            +            -- | /O(min(m,W))/, where /m/ is number of @Arc@s in this+            -- branching, and /W/ is the word size of the Prefix,Mask type.+            findArc (Branch p m l r)+                | nomatch qh p m  = id+                | zero qh m       = findArc l+                | otherwise       = findArc r+            findArc t@(Arc _ _ _) = go n q t+            findArc Empty         = id   {---------------------------------------------------------------