list-tries 0.5.2 → 0.6.0
raw patch · 8 files changed
+192/−179 lines, 8 filesdep ~basedep ~template-haskell
Dependency ranges changed: base, template-haskell
Files
- CHANGELOG.txt +11/−0
- CREDITS.txt +2/−3
- Data/ListTrie/Base.hs +3/−3
- Data/ListTrie/Base/Map.hs +30/−30
- Data/ListTrie/Patricia/Base.hs +4/−5
- headers/exports.h +131/−131
- list-tries.cabal +9/−5
- tests/Tests/Properties.hs +2/−2
CHANGELOG.txt view
@@ -1,3 +1,14 @@+2015-03-28, 0.6.0:+ Updated dependencies for GHC 7.10.++ Fixed library vs. test executable dlist dependency mismatch.++ Renamed Map.toList to toListKV to avoid conflicts with the new Foldable+ class. Also renamed Map.fromList and Map.fromListWith to fromListKV and+ fromListKVWith to match. Thanks to davean for the patch.++ Added Cabal source-repository metadata, pointing to GitHub.+ 2014-03-20, 0.5.2: Updated dependencies, for GHC 7.8 and other new packages.
CREDITS.txt view
@@ -1,4 +1,3 @@-In alphabetical order by surname:-+davean Gregory Crosswhite-Matti Niemenmaa+Matti Niemenmaa
Data/ListTrie/Base.hs view
@@ -560,7 +560,7 @@ genericMapInKeysWith ($$) unionW j f = go where go tr = mapMap ($$) tr $- Map.fromListWith (unionW j) . map (f *** go) . Map.toList+ Map.fromListKVWith (unionW j) . map (f *** go) . Map.toListKV -- * Folding @@ -613,7 +613,7 @@ -- O(n m) toList :: (Boolable (st a), Trie trie st map k) => trie map k a -> [([k],a)]-toList = genericToList Map.toList DL.cons+toList = genericToList Map.toListKV DL.cons -- O(n m) toAscList :: (Boolable (st a), Trie trie st map k, OrdMap map k)@@ -888,4 +888,4 @@ . showString "-> " . sk . showChar ' ' . go (i + lk + 4) f t)- (Map.toList m))+ (Map.toListKV m))
Data/ListTrie/Base/Map.hs view
@@ -21,9 +21,9 @@ import qualified Data.IntMap as IM import qualified Data.Map as M -import Prelude hiding ( foldl,foldl1,foldr,foldr1- , mapM,sequence+import Prelude hiding ( mapM,sequence , null,lookup,filter -- for Haddock+ , toList ) import qualified Prelude @@ -41,7 +41,7 @@ -- -- * 'unionWithKey', 'differenceWithKey', 'intersectionWithKey' ----- * 'toList'+-- * 'toListKV' -- -- * 'empty' or 'fromList' or 'fromListWith' --@@ -87,9 +87,9 @@ filter :: (a -> Bool) -> m k a -> m k a - toList :: m k a -> [(k,a)]- fromList :: [(k,a)] -> m k a- fromListWith :: (a -> a -> a) -> [(k,a)] -> m k a+ toListKV :: m k a -> [(k,a)]+ fromListKV :: [(k,a)] -> m k a+ fromListKVWith :: (a -> a -> a) -> [(k,a)] -> m k a serializeToList :: m k a -> [(k,a)] deserializeFromList :: [(k,a)] -> m k a@@ -98,7 +98,7 @@ singletonView :: m k a -> Maybe (k,a) - empty = fromList []+ empty = fromListKV [] singleton k v = insert k v empty doubleton k v = insert k v .: singleton @@ -120,21 +120,21 @@ mapWithKey f = snd . mapAccumWithKey (\_ k v -> ((), f k v)) () mapAccum f = mapAccumWithKey (const . f) mapAccumWithKey f z =- second fromList .+ second fromListKV . mapAccumL (\a (k,v) -> fmap ((,) k) (f a k v)) z .- toList+ toListKV - filter p = fromList . Prelude.filter (p . snd) . toList+ filter p = fromListKV . Prelude.filter (p . snd) . toListKV -- | Should be strict in the keys- fromList = fromListWith const- fromListWith f = foldr (uncurry $ insertWith f) empty+ fromListKV = fromListKVWith const+ fromListKVWith f = foldr (uncurry $ insertWith f) empty - serializeToList = toList- deserializeFromList = fromList+ serializeToList = toListKV+ deserializeFromList = fromListKV singletonView m =- case toList m of+ case toListKV m of [x] -> Just x _ -> Nothing @@ -182,12 +182,12 @@ minViewWithKey m = case toAscList m of [] -> (Nothing, m)- (x:xs) -> (Just x, fromList xs)+ (x:xs) -> (Just x, fromListKV xs) maxViewWithKey m = case toDescList m of [] -> (Nothing, m)- (x:xs) -> (Just x, fromList xs)+ (x:xs) -> (Just x, fromListKV xs) findPredecessor m = fst . maxViewWithKey . fst . split m findSuccessor m = fst . minViewWithKey . snd . split m@@ -195,11 +195,11 @@ mapAccumAsc f = mapAccumAscWithKey (const . f) mapAccumDesc f = mapAccumDescWithKey (const . f) mapAccumAscWithKey f z =- second fromList .+ second fromListKV . mapAccumL (\a (k,v) -> fmap ((,) k) (f a k v)) z . toAscList mapAccumDescWithKey f z =- second fromList .+ second fromListKV . mapAccumL (\a (k,v) -> fmap ((,) k) (f a k v)) z . toDescList @@ -276,9 +276,9 @@ in (a', (k, v'))) z xs - toList (AL xs) = xs- fromList = AL . nubBy ((==) `on` fst)- fromListWith = AL .: go+ toListKV (AL xs) = xs+ fromListKV = AL . nubBy ((==) `on` fst)+ fromListKVWith = AL .: go where go _ [] = [] go f (x:xs) =@@ -301,8 +301,8 @@ instance Ord k => OrdMap AList k where ordCmp = const compare - toAscList = sortBy ( comparing fst) . toList- toDescList = sortBy (flip $ comparing fst) . toList+ toAscList = sortBy ( comparing fst) . toListKV+ toDescList = sortBy (flip $ comparing fst) . toListKV splitLookup k (AL xs) = let (ls,gs) = partition ((< k).fst) xs@@ -369,9 +369,9 @@ filter = M.filter - toList = M.toList- fromList = M.fromList- fromListWith = M.fromListWith+ toListKV = M.toList+ fromListKV = M.fromList+ fromListKVWith = M.fromListWith serializeToList = M.toAscList deserializeFromList = M.fromDistinctAscList@@ -452,9 +452,9 @@ filter p (IMap x) = IMap $ IM.filter p x - toList (IMap m) = Prelude.map (first toEnum) . IM.toList $ m- fromList = IMap . IM.fromList . Prelude.map (first fromEnum)- fromListWith f = IMap . IM.fromListWith f . Prelude.map (first fromEnum)+ toListKV (IMap m) = Prelude.map (first toEnum) . IM.toList $ m+ fromListKV = IMap . IM.fromList . Prelude.map (first fromEnum)+ fromListKVWith f = IMap . IM.fromListWith f . Prelude.map (first fromEnum) serializeToList (IMap x) = Prelude.map (first toEnum) . IM.toAscList $ x deserializeFromList =
Data/ListTrie/Patricia/Base.hs view
@@ -1,8 +1,7 @@ -- File created: 2008-12-28 17:20:14 {-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies- , FlexibleContexts, ScopedTypeVariables, Rank2Types- , NoMonomorphismRestriction #-}+ , FlexibleContexts, ScopedTypeVariables, Rank2Types #-} module Data.ListTrie.Patricia.Base ( Trie(..)@@ -975,7 +974,7 @@ p' = map f p in listSeq p' `seeq` (mkTrie v p' $- Map.fromListWith (unionW j) . map (f *** go) . Map.toList $ m)+ Map.fromListKVWith (unionW j) . map (f *** go) . Map.toListKV $ m) -- * Folding @@ -1028,7 +1027,7 @@ -- O(n m) toList :: (Boolable (st a), Trie trie st map k) => trie map k a -> [([k],a)]-toList = genericToList Map.toList DL.cons+toList = genericToList Map.toListKV DL.cons -- O(n m) toAscList :: (Boolable (st a), Trie trie st map k, OrdMap map k)@@ -1371,7 +1370,7 @@ . showString "-> " . sk . showChar ' ' . go (i + lk + 4) f t)- (Map.toList m))+ (Map.toListKV m)) -- helpers
headers/exports.h view
@@ -1,136 +1,136 @@ -- File created: 2008-12-30 18:33:18 #define SET_EXPORTS \- {- * Set type -} \- TrieSet, \- {- * Construction -} \- empty, singleton, \- \- {- * Modification -} \- insert, delete, \- \- {- * Querying -} \- null, size, size', member, notMember, \- \- {- ** Subsets -} \- isSubsetOf, isProperSubsetOf, \- \- {- * Combination -} \- union, unions, difference, intersection, \- \- {- * Filtering -} \- filter, partition, \- \- {- * Mapping -} \- map, mapIn, \- \- {- * Folding -} \- foldr, foldrAsc, foldrDesc, \- foldl, foldlAsc, foldlDesc, \- foldl', foldlAsc', foldlDesc', \- \- {- * Conversion to and from lists -} \- toList, toAscList, toDescList, fromList, \- \- {- * Ordering-sensitive operations -} \- {- ** Minimum and maximum -} \- minView, maxView, findMin, findMax, deleteMin, deleteMax, \- \- {- ** Predecessor and successor -} \- split, splitMember, \- findPredecessor, findSuccessor, \- \- {- * Trie-specific operations -} \- {- $trie-only-ops -} \- lookupPrefix, addPrefix, deletePrefix, deleteSuffixes, \- splitPrefix, children, children1, \- \- {- * Visualization -} \- showTrie+ {- * Set type -} \+ TrieSet, \+ {- * Construction -} \+ empty, singleton, \+ \+ {- * Modification -} \+ insert, delete, \+ \+ {- * Querying -} \+ null, size, size', member, notMember, \+ \+ {- ** Subsets -} \+ isSubsetOf, isProperSubsetOf, \+ \+ {- * Combination -} \+ union, unions, difference, intersection, \+ \+ {- * Filtering -} \+ filter, partition, \+ \+ {- * Mapping -} \+ map, mapIn, \+ \+ {- * Folding -} \+ foldr, foldrAsc, foldrDesc, \+ foldl, foldlAsc, foldlDesc, \+ foldl', foldlAsc', foldlDesc', \+ \+ {- * Conversion to and from lists -} \+ toList, toAscList, toDescList, fromList, \+ \+ {- * Ordering-sensitive operations -} \+ {- ** Minimum and maximum -} \+ minView, maxView, findMin, findMax, deleteMin, deleteMax, \+ \+ {- ** Predecessor and successor -} \+ split, splitMember, \+ findPredecessor, findSuccessor, \+ \+ {- * Trie-specific operations -} \+ {- $trie-only-ops -} \+ lookupPrefix, addPrefix, deletePrefix, deleteSuffixes, \+ splitPrefix, children, children1, \+ \+ {- * Visualization -} \+ showTrie #define MAP_EXPORTS \- {- * Map type -} \- TrieMap, \- \- {- * Construction -} \- empty, singleton, \- \- {- * Modification -} \- insert, insert', insertWith, insertWith', \- delete, \- update, updateLookup, \- adjust, adjust', alter, alter', \- \- {- * Querying -} \- null, size, size', member, notMember, \- lookup, lookupWithDefault, \- \- {- ** Submaps -} \- isSubmapOf, isSubmapOfBy, \- isProperSubmapOf, isProperSubmapOfBy, \- \- {- * Combination -} \- {- ** Union -} \- union, union', unions, unions', \- unionWith, unionWithKey, unionsWith, unionsWithKey, \- unionWith', unionWithKey', unionsWith', unionsWithKey', \- \- {- ** Difference -} \- difference, differenceWith, differenceWithKey, \- \- {- ** Intersection -} \- intersection, intersection', \- intersectionWith, intersectionWithKey, \- intersectionWith', intersectionWithKey', \- \- {- * Filtering -} \- filter, filterWithKey, partition, partitionWithKey, \- mapMaybe, mapMaybeWithKey, mapEither, mapEitherWithKey, \- \- {- * Mapping -} \- {- ** Values -} \- map, map', mapWithKey, mapWithKey', \- \- {- ** Keys -} \- mapKeys, mapKeysWith, \- mapInKeys, mapInKeys', mapInKeysWith, mapInKeysWith', \- \- {- ** With accumulation -} \- mapAccum, mapAccumWithKey, \- mapAccum', mapAccumWithKey', \- mapAccumAsc, mapAccumAscWithKey, \- mapAccumAsc', mapAccumAscWithKey', \- mapAccumDesc, mapAccumDescWithKey, \- mapAccumDesc', mapAccumDescWithKey', \- \- {- * Folding -} \- foldr, foldrWithKey, \- foldrAsc, foldrAscWithKey, \- foldrDesc, foldrDescWithKey, \- foldl, foldlWithKey, \- foldlAsc, foldlAscWithKey, \- foldlDesc, foldlDescWithKey, \- foldl', foldlWithKey', \- foldlAsc', foldlAscWithKey', \- foldlDesc', foldlDescWithKey', \- \- {- * Conversion to and from lists -} \- toList, toAscList, toDescList, fromList, \- fromListWith, fromListWithKey, \- fromListWith', fromListWithKey', \- \- {- * Ordering-sensitive operations -} \- {- ** Minimum and maximum -} \- minView, maxView, findMin, findMax, deleteMin, deleteMax, \- \- {- ** Predecessor and successor -} \- split, splitLookup, \- findPredecessor, findSuccessor, \- \- {- * Trie-specific operations -} \- {- $trie-only-ops -} \- lookupPrefix, addPrefix, deletePrefix, deleteSuffixes, \- splitPrefix, children, children1, \- \- {- * Visualization -} \- showTrie, showTrieWith+ {- * Map type -} \+ TrieMap, \+ \+ {- * Construction -} \+ empty, singleton, \+ \+ {- * Modification -} \+ insert, insert', insertWith, insertWith', \+ delete, \+ update, updateLookup, \+ adjust, adjust', alter, alter', \+ \+ {- * Querying -} \+ null, size, size', member, notMember, \+ lookup, lookupWithDefault, \+ \+ {- ** Submaps -} \+ isSubmapOf, isSubmapOfBy, \+ isProperSubmapOf, isProperSubmapOfBy, \+ \+ {- * Combination -} \+ {- ** Union -} \+ union, union', unions, unions', \+ unionWith, unionWithKey, unionsWith, unionsWithKey, \+ unionWith', unionWithKey', unionsWith', unionsWithKey', \+ \+ {- ** Difference -} \+ difference, differenceWith, differenceWithKey, \+ \+ {- ** Intersection -} \+ intersection, intersection', \+ intersectionWith, intersectionWithKey, \+ intersectionWith', intersectionWithKey', \+ \+ {- * Filtering -} \+ filter, filterWithKey, partition, partitionWithKey, \+ mapMaybe, mapMaybeWithKey, mapEither, mapEitherWithKey, \+ \+ {- * Mapping -} \+ {- ** Values -} \+ map, map', mapWithKey, mapWithKey', \+ \+ {- ** Keys -} \+ mapKeys, mapKeysWith, \+ mapInKeys, mapInKeys', mapInKeysWith, mapInKeysWith', \+ \+ {- ** With accumulation -} \+ mapAccum, mapAccumWithKey, \+ mapAccum', mapAccumWithKey', \+ mapAccumAsc, mapAccumAscWithKey, \+ mapAccumAsc', mapAccumAscWithKey', \+ mapAccumDesc, mapAccumDescWithKey, \+ mapAccumDesc', mapAccumDescWithKey', \+ \+ {- * Folding -} \+ foldr, foldrWithKey, \+ foldrAsc, foldrAscWithKey, \+ foldrDesc, foldrDescWithKey, \+ foldl, foldlWithKey, \+ foldlAsc, foldlAscWithKey, \+ foldlDesc, foldlDescWithKey, \+ foldl', foldlWithKey', \+ foldlAsc', foldlAscWithKey', \+ foldlDesc', foldlDescWithKey', \+ \+ {- * Conversion to and from lists -} \+ toList, toAscList, toDescList, fromList, \+ fromListWith, fromListWithKey, \+ fromListWith', fromListWithKey', \+ \+ {- * Ordering-sensitive operations -} \+ {- ** Minimum and maximum -} \+ minView, maxView, findMin, findMax, deleteMin, deleteMax, \+ \+ {- ** Predecessor and successor -} \+ split, splitLookup, \+ findPredecessor, findSuccessor, \+ \+ {- * Trie-specific operations -} \+ {- $trie-only-ops -} \+ lookupPrefix, addPrefix, deletePrefix, deleteSuffixes, \+ splitPrefix, children, children1, \+ \+ {- * Visualization -} \+ showTrie, showTrieWith
list-tries.cabal view
@@ -1,7 +1,7 @@ Cabal-Version: >= 1.6 Name: list-tries-Version: 0.5.2+Version: 0.6.0 Homepage: http://iki.fi/matti.niemenmaa/list-tries/ Synopsis: Tries and Patricia tries: finite sets and maps for list keys Category: Data, Data Structures@@ -36,12 +36,16 @@ tests/*.hs tests/Tests/*.hs +source-repository head+ type: git+ location: https://github.com/Deewiant/list-tries+ flag testing description: Enable building a test executable default: False Library- Build-Depends: base >= 3 && < 4.8+ Build-Depends: base >= 3 && < 4.9 , containers >= 0.3 && < 0.6 , dlist >= 0.4 && < 0.8 , binary >= 0.5 && < 0.8@@ -78,13 +82,13 @@ main-is: Main.hs hs-source-dirs: ., tests - Build-Depends: base >= 3 && < 4.8+ Build-Depends: base >= 3 && < 4.9 , containers >= 0.3 && < 0.6- , dlist >= 0.4 && < 0.7+ , dlist >= 0.4 && < 0.8 , binary >= 0.5 && < 0.8 if flag(testing)- Build-Depends: template-haskell >= 2.3 && < 2.10+ Build-Depends: template-haskell >= 2.3 && < 2.11 , HUnit >= 1.2 && < 1.3 , QuickCheck >= 2.1 && < 2.8 , test-framework >= 0.2 && < 0.9
tests/Tests/Properties.hs view
@@ -415,7 +415,7 @@ let (k,b,_) = splitPrefix (t :: TrieType) in t == ((if b then insert k else id) . addPrefix k . unions $ map (uncurry $ addPrefix . return)- (Map.toList $ children t))+ (Map.toListKV $ children t)) |]) $(makeFunc mapsOnly ["addPrefix","splitPrefix","children","unions","insert"] [d|@@ -423,7 +423,7 @@ let (k,mv,_) = splitPrefix (t :: TrieType) in t == ((case mv of Just v -> insert k v; _ -> id) . addPrefix k . unions $ map (uncurry $ addPrefix . return)- (Map.toList $ children t))+ (Map.toListKV $ children t)) |]) -- Deleting an added prefix should change nothing