bytestring-trie 0.2.5.1 → 0.2.5.2
raw patch · 8 files changed
+49/−41 lines, 8 filesdep ~binarydep ~bytestringPVP ok
version bump matches the API change (PVP)
Dependency ranges changed: binary, bytestring
API changes (from Hackage documentation)
Files
- CHANGELOG +3/−1
- README.md +2/−3
- bytestring-trie.cabal +11/−12
- src/Data/Trie.hs +7/−7
- src/Data/Trie/BitTwiddle.hs +10/−10
- src/Data/Trie/ByteStringInternal.hs +1/−1
- src/Data/Trie/Convenience.hs +6/−6
- src/Data/Trie/Internal.hs +9/−1
CHANGELOG view
@@ -1,5 +1,7 @@+0.2.5.2 (2021.10.16):+ - Increasing upper bounds to Hackage latest, instead of just GHC 9.0.1 0.2.5.1 (2021.10.16):- - Fixing things to compile under GHC 9.0+ - Fixing things to compile under GHC 9.0.1 0.2.5.0 (2019.02.25): - Fixing things to compile under GHC 8.4 and 8.6. - Adds Semigroup (Trie a) instance
README.md view
@@ -1,9 +1,8 @@ bytestring-trie =============== [](https://hackage.haskell.org/package/bytestring-trie) -[](http://packdeps.haskellers.com/specific?package=bytestring-trie)-[](https://travis-ci.org/wrengr/bytestring-trie) -[](https://circleci.com/gh/wrengr/bytestring-trie)+[](https://github.com/wrengr/bytestring-trie/actions?query=workflow%3Aci)+[](http://packdeps.haskellers.com/specific?package=bytestring-trie) The bytestring-trie package provides an efficient implementation of tries mapping `ByteString` to values. The implementation is
bytestring-trie.cabal view
@@ -7,7 +7,7 @@ Build-Type: Simple Name: bytestring-trie-Version: 0.2.5.1+Version: 0.2.5.2 Stability: provisional Homepage: http://wrengr.org Author: wren gayle romano@@ -43,16 +43,15 @@ Extra-source-files: AUTHORS, CHANGELOG, README.md --- Cf., <https://travis-ci.org/wrengr/bytestring-lexing>+-- This should work as far back as GHC 7.4.1, but we don't verify that by CI.+-- TODO: add the github-actions link. Tested-With:- GHC ==7.4.1, GHC ==7.4.2,- GHC ==7.6.1, GHC ==7.6.2, GHC ==7.6.3,- GHC ==7.8.1, GHC ==7.8.2, GHC ==7.8.3, GHC ==7.8.4,- GHC ==7.10.1, GHC ==7.10.2, GHC ==7.10.3,- GHC ==8.0.1, GHC ==8.0.2,- GHC ==8.2.1, GHC ==8.2.2,- GHC ==8.4.1, GHC ==8.4.2, GHC ==8.4.3,- GHC ==8.6.1, GHC ==8.6.2,+ GHC ==8.0.2,+ GHC ==8.2.2,+ GHC ==8.4.4,+ GHC ==8.6.5,+ GHC ==8.8.4,+ GHC ==8.10.3, GHC ==9.0.1 Source-Repository head@@ -73,8 +72,8 @@ -- But then, we don't maintain any CI tests for older -- versions, so these are the lowest bounds we've verified. Build-Depends: base >= 4.5 && < 4.16- , bytestring >= 0.9.2 && < 0.11- , binary >= 0.5.1 && < 0.8.9+ , bytestring >= 0.9.2 && < 0.12+ , binary >= 0.5.1 && < 0.11 ------------------------------------------------------------ ------------------------------------------------------- fin.
src/Data/Trie.hs view
@@ -37,22 +37,22 @@ ( -- * Data type Trie()- + -- * Basic functions , empty, null, singleton, size- + -- * Conversion functions , fromList, toListBy, toList, keys, elems- + -- * Query functions , lookupBy, lookup, member, submap, match, matches- + -- * Single-value modification , alterBy, insert, adjust, delete- + -- * Combining tries , mergeBy, unionL, unionR- + -- * Mapping functions , mapBy, filterMap ) where@@ -71,7 +71,7 @@ {------------------------------------------------------------------ Conversion functions +-- Conversion functions ---------------------------------------------------------------} -- | Convert association list into a trie. On key conflict, values
src/Data/Trie/BitTwiddle.hs view
@@ -16,8 +16,8 @@ -- Functions to treat 'Word' as a bit-vector for big-endian patricia -- trees. This code is duplicated from "Data.IntMap". The only -- differences are that some of the conversion functions are--- specialized to 'Word8' for bytestrings, instead of being specialized--- to 'Int'.+-- specialized to 'Data.Word.Word8' for bytestrings, instead of+-- being specialized to 'Int'. ---------------------------------------------------------------- module Data.Trie.BitTwiddle@@ -41,9 +41,9 @@ ---------------------------------------------------------------- -type KeyElem = ByteStringElem -type Prefix = KeyElem -type Mask = KeyElem +type KeyElem = ByteStringElem+type Prefix = KeyElem+type Mask = KeyElem elemToNat :: KeyElem -> Word {-# INLINE elemToNat #-}@@ -159,11 +159,11 @@ highestBitMask :: Word -> Word {-# INLINE highestBitMask #-} highestBitMask x- = case (x .|. shiftRL x 1) of - x -> case (x .|. shiftRL x 2) of - x -> case (x .|. shiftRL x 4) of - x -> case (x .|. shiftRL x 8) of - x -> case (x .|. shiftRL x 16) of + = case (x .|. shiftRL x 1) of+ x -> case (x .|. shiftRL x 2) of+ x -> case (x .|. shiftRL x 4) of+ x -> case (x .|. shiftRL x 8) of+ x -> case (x .|. shiftRL x 16) of x -> case (x .|. shiftRL x 32) of -- for 64 bit platforms x -> (x `xor` shiftRL x 1)
src/Data/Trie/ByteStringInternal.hs view
@@ -62,7 +62,7 @@ return $! (,,) !$ pre !$ s1' !$ s2' -- | Get the 'sizeOf' the type, without requiring @-XScopedTypeVariables@--- nor making a spurious call to 'unsafePerformIO' or similar.+-- nor making a spurious call to 'System.IO.Unsafe.unsafePerformIO' or similar. sizeOfPtr :: Storable a => Ptr a -> Int sizeOfPtr = sizeOf . (undefined :: Ptr a -> a) {-# INLINE sizeOfPtr #-}
src/Data/Trie/Convenience.hs view
@@ -24,19 +24,19 @@ fromListL, fromListR, fromListS , fromListWith, fromListWith' , fromListWithL, fromListWithL'- + -- * Query functions ('lookupBy' variants) , lookupWithDefault- + -- * Inserting values ('alterBy' variants) , insertIfAbsent , insertWith, insertWith' , insertWithKey, insertWithKey'- + -- * Updating and adjusting values ('alterBy' and 'adjustBy' variants) , adjustWithKey , update, updateWithKey- + -- * Combining tries ('mergeBy' variants) , disunion , unionWith, unionWith'@@ -92,7 +92,7 @@ -- | A variant of 'fromListR' that takes a function for combining -- values on conflict. The first argument to the combining function--- is the ``new'' value from the initial portion of the list; the+-- is the \"new\" value from the initial portion of the list; the -- second argument is the value that has been accumulated into the -- trie from the tail of the list (just like the first argument to -- 'foldr'). Thus, @fromList = fromListWith const@.@@ -120,7 +120,7 @@ -- | A left-fold variant of 'fromListWith'. Note that the arguments -- to the combining function are swapped: the first is the value -- in the trie which has been accumulated from the initial part of--- the list; the second argument is the ``new'' value from the+-- the list; the second argument is the \"new\" value from the -- remaining tail of the list (just like the first argument to -- 'foldl'). Thus, @fromListL = fromListWithL const@. fromListWithL :: (a -> a -> a) -> [(ByteString,a)] -> Trie a
src/Data/Trie/Internal.hs view
@@ -66,7 +66,7 @@ import Data.Trie.ByteStringInternal import Data.Trie.BitTwiddle -import Data.Binary+import Data.Binary (Binary(..), Get, Word8) #if MIN_VERSION_base(4,9,0) import Data.Semigroup (Semigroup(..)) #endif@@ -993,6 +993,9 @@ -- Priority-queue functions -----------------------------------------------------------} +-- | Return the lexicographically smallest 'ByteString' and the+-- value it's mapped to; or 'Nothing' for the empty trie. When one+-- entry is a prefix of another, the prefix will be returned. minAssoc :: Trie a -> Maybe (ByteString, a) minAssoc = go S.empty where@@ -1002,6 +1005,9 @@ go q (Branch _ _ l _) = go q l +-- | Return the lexicographically largest 'ByteString' and the+-- value it's mapped to; or 'Nothing' for the empty trie. When one+-- entry is a prefix of another, the longer one will be returned. maxAssoc :: Trie a -> Maybe (ByteString, a) maxAssoc = go S.empty where@@ -1017,6 +1023,7 @@ mapView f (Just (k,v,t)) = Just (k,v, f t) +-- | Update the 'minAssoc' and return the old 'minAssoc'. updateMinViewBy :: (ByteString -> a -> Maybe a) -> Trie a -> Maybe (ByteString, a, Trie a) updateMinViewBy f = go S.empty@@ -1028,6 +1035,7 @@ go q (Branch p m l r) = mapView (\l' -> branch p m l' r) (go q l) +-- | Update the 'maxAssoc' and return the old 'maxAssoc'. updateMaxViewBy :: (ByteString -> a -> Maybe a) -> Trie a -> Maybe (ByteString, a, Trie a) updateMaxViewBy f = go S.empty