packages feed

list-tries 0.4.3 → 0.5

raw patch · 12 files changed

+197/−30 lines, 12 filesdep ~test-frameworkdep ~test-framework-hunitdep ~test-framework-quickcheck2

Dependency ranges changed: test-framework, test-framework-hunit, test-framework-quickcheck2

Files

CHANGELOG.txt view
@@ -1,3 +1,17 @@+2013-05-09, 0.5:+	Added the 'lookupPrefix' and 'deleteSuffixes' functions, of which especially+	the former was an embarrassing omission:++		lookupPrefix   :: [k] -> trie map k a -> trie map k a+		deleteSuffixes :: [k] -> trie map k a -> trie map k a++	Fixed the documentation headers to refer to 's' instead of 'k' as what we+	use for the length of the given key.++	Fixed documentation of 'deletePrefix': its complexity is O(s), not O(m).++	Some dependency updates.+ 2012-10-18, 0.4.3: 	Dependency updates for GHC 7.6 and otherwise.
Data/ListTrie/Base.hs view
@@ -25,7 +25,8 @@    , fromList, fromListWith, fromListWith', fromListWithKey, fromListWithKey'    , findMin, findMax, deleteMin, deleteMax, minView, maxView    , findPredecessor, findSuccessor-   , addPrefix, splitPrefix, deletePrefix, children, children1+   , lookupPrefix, addPrefix, deletePrefix, deleteSuffixes+   , splitPrefix, children, children1    , showTrieWith    ) where @@ -799,12 +800,24 @@ -- * Trie-only operations  -- O(s)+lookupPrefix :: (Alt st a, Boolable (st a), Trie trie st map k)+             => [k] -> trie map k a -> trie map k a+lookupPrefix []     tr = tr+lookupPrefix (x:xs) tr =+   case Map.lookup x (tMap tr) of+        Nothing  -> empty+        Just tr' -> let tr'' = lookupPrefix xs tr'+                     in if null tr''+                           then tr''+                           else mkTrie altEmpty (Map.singleton x tr'')++-- O(s) addPrefix :: (Alt st a, Trie trie st map k)           => [k] -> trie map k a -> trie map k a addPrefix []     = id addPrefix (x:xs) = mkTrie altEmpty . Map.singleton x . addPrefix xs --- O(m)+-- O(s) deletePrefix :: (Alt st a, Trie trie st map k)              => [k] -> trie map k a -> trie map k a deletePrefix []     tr = tr@@ -812,6 +825,19 @@    case Map.lookup x (tMap tr) of         Nothing  -> empty         Just tr' -> deletePrefix xs tr'++-- O(s)+deleteSuffixes :: (Alt st a, Boolable (st a), Trie trie st map k)+               => [k] -> trie map k a -> trie map k a+deleteSuffixes []     _  = empty+deleteSuffixes (x:xs) tr =+   let (v,m) = tParts tr+    in case Map.lookup x m of+            Nothing  -> tr+            Just tr' -> let tr'' = deleteSuffixes xs tr'+                         in if null tr''+                               then mkTrie v (Map.delete x      m)+                               else mkTrie v (Map.insert x tr'' m)  -- O(m) splitPrefix :: (Alt st a, Trie trie st map k)
Data/ListTrie/Map.hs view
@@ -8,8 +8,8 @@ -- | The base implementation of a trie representing a map with list keys, -- generalized over any type of map from element values to tries. ----- Worst-case complexities are given in terms of @n@, @m@, and @k@. @n@ refers--- to the number of keys in the map and @m@ to their maximum length. @k@ refers+-- Worst-case complexities are given in terms of @n@, @m@, and @s@. @n@ refers+-- to the number of keys in the map and @m@ to their maximum length. @s@ refers -- to the length of a key given to the function, not any property of the map. -- -- In addition, the trie's branching factor plays a part in almost every@@ -978,6 +978,14 @@  -- * Trie-only operations +-- | @O(s)@. The map which contains all keys of which the given key is a+-- prefix. For example:+--+-- > lookupPrefix "ab" (fromList [("a",1),("ab",2),("ac",3),("abc",4)])+-- >    == fromList [("ab",2),("abc",4)]+lookupPrefix :: Map map k => [k] -> TrieMap map k a -> TrieMap map k a+lookupPrefix = Base.lookupPrefix+ -- | @O(s)@. Prepends the given key to all the keys of the map. For example: -- -- > addPrefix "xa" (fromList [("a",1),("b",2)])@@ -985,7 +993,7 @@ addPrefix :: Map map k => [k] -> TrieMap map k a -> TrieMap map k a addPrefix = Base.addPrefix --- | @O(m)@. The map which contains all keys of which the given key is a+-- | @O(s)@. The map which contains all keys of which the given key is a -- prefix, with the prefix removed from each key. If the given key is not a -- prefix of any key in the map, an empty map is returned. For example: --@@ -1000,6 +1008,13 @@ -- be a member of the map. deletePrefix :: Map map k => [k] -> TrieMap map k a -> TrieMap map k a deletePrefix = Base.deletePrefix++-- | @O(s)@. Deletes all keys which are suffixes of the given key. For example:+--+-- > deleteSuffixes "ab" (fromList $ zip ["a","ab","ac","b","abc"] [1..])+-- >    == fromList [("a",1),("ac",3),("b",4)]+deleteSuffixes :: Map map k => [k] -> TrieMap map k a -> TrieMap map k a+deleteSuffixes = Base.deleteSuffixes  -- | @O(m)@. A triple containing the longest common prefix of all keys in the -- map, the value associated with that prefix, if any, and the map with that
Data/ListTrie/Patricia/Base.hs view
@@ -26,7 +26,8 @@    , fromList, fromListWith, fromListWith', fromListWithKey, fromListWithKey'    , findMin, findMax, deleteMin, deleteMax, minView, maxView    , findPredecessor, findSuccessor-   , addPrefix, splitPrefix, deletePrefix, children, children1+   , lookupPrefix, addPrefix, deletePrefix, deleteSuffixes+   , splitPrefix, children, children1    , showTrieWith    , eqComparePrefixes, ordComparePrefixes    ) where@@ -1259,13 +1260,34 @@ -- * Trie-only operations  -- O(s)+lookupPrefix :: (Alt st a, Boolable (st a), Trie trie st map k)+             => [k] -> trie map k a -> trie map k a+lookupPrefix xs tr =+   let (_,pre,m) = tParts tr+    in case comparePrefixes (Map.eqCmp m) pre xs of+            DifferedAt _ _ _       -> empty+            Same                   -> tr+            PostFix (Left _)       -> tr+            PostFix (Right (y:ys)) ->+               case Map.lookup y m of+                    Nothing  -> empty+                    Just tr' -> let tr''         = lookupPrefix ys tr'+                                    (v',pre',m') = tParts tr''+                                 in if null tr''+                                       then tr''+                                       else mkTrie v' (pre ++ y : pre') m'+            _ ->+               error+                  "Data.ListTrie.Patricia.Base.lookupPrefix :: internal error"++-- O(s) addPrefix :: (Alt st a, Trie trie st map k)           => [k] -> trie map k a -> trie map k a addPrefix xs tr =    let (v,pre,m) = tParts tr     in mkTrie v (xs ++ pre) m --- O(m)+-- O(s) deletePrefix :: (Alt st a, Boolable (st a), Trie trie st map k)              => [k] -> trie map k a -> trie map k a deletePrefix xs tr =@@ -1282,6 +1304,27 @@             _ ->                error                   "Data.ListTrie.Patricia.Base.deletePrefix :: internal error"++-- O(s)+deleteSuffixes :: (Alt st a, Boolable (st a), Trie trie st map k)+               => [k] -> trie map k a -> trie map k a+deleteSuffixes xs tr =+   let (v,pre,m) = tParts tr+    in case comparePrefixes (Map.eqCmp m) pre xs of+            DifferedAt _ _ _       -> tr+            Same                   -> empty+            PostFix (Left _)       -> empty+            PostFix (Right (y:ys)) ->+               case Map.lookup y m of+                    Nothing  -> tr+                    Just tr' ->+                       let tr'' = deleteSuffixes ys tr'+                        in if null tr''+                              then tryCompress$ mkTrie v pre (Map.delete y m)+                              else mkTrie v pre (Map.insert y tr'' m)++            _ -> error "Data.ListTrie.Patricia.Base.deleteSuffixes \+                       \:: internal error"  -- O(1) splitPrefix :: (Alt st a, Boolable (st a), Trie trie st map k)
Data/ListTrie/Patricia/Map.hs view
@@ -8,8 +8,8 @@ -- | The base implementation of a Patricia trie representing a map with list -- keys, generalized over any type of map from element values to tries. ----- Worst-case complexities are given in terms of @n@, @m@, and @k@. @n@ refers--- to the number of keys in the map and @m@ to their maximum length. @k@ refers+-- Worst-case complexities are given in terms of @n@, @m@, and @s@. @n@ refers+-- to the number of keys in the map and @m@ to their maximum length. @s@ refers -- to the length of a key given to the function, not any property of the map. -- -- In addition, the trie's branching factor plays a part in almost every@@ -996,6 +996,14 @@  -- * Trie-only operations +-- | @O(s)@. The map which contains all keys of which the given key is a+-- prefix. For example:+--+-- > lookupPrefix "ab" (fromList [("a",1),("ab",2),("ac",3),("abc",4)])+-- >    == fromList [("ab",2),("abc",4)]+lookupPrefix :: Map map k => [k] -> TrieMap map k a -> TrieMap map k a+lookupPrefix = Base.lookupPrefix+ -- | @O(s)@. Prepends the given key to all the keys of the map. For example: -- -- > addPrefix "xa" (fromList [("a",1),("b",2)])@@ -1003,7 +1011,7 @@ addPrefix :: Map map k => [k] -> TrieMap map k a -> TrieMap map k a addPrefix = Base.addPrefix --- | @O(m)@. The map which contains all keys of which the given key is a+-- | @O(s)@. The map which contains all keys of which the given key is a -- prefix, with the prefix removed from each key. If the given key is not a -- prefix of any key in the map, an empty map is returned. For example: --@@ -1018,6 +1026,13 @@ -- be a member of the map. deletePrefix :: Map map k => [k] -> TrieMap map k a -> TrieMap map k a deletePrefix = Base.deletePrefix++-- | @O(s)@. Deletes all keys which are suffixes of the given key. For example:+--+-- > deleteSuffixes "ab" (fromList $ zip ["a","ab","ac","b","abc"] [1..])+-- >    == fromList [("a",1),("ac",3),("b",4)]+deleteSuffixes :: Map map k => [k] -> TrieMap map k a -> TrieMap map k a+deleteSuffixes = Base.deleteSuffixes  -- | @O(1)@. A triple containing the longest common prefix of all keys in the -- map, the value associated with that prefix, if any, and the map with that
Data/ListTrie/Patricia/Set.hs view
@@ -8,8 +8,8 @@ -- | The base implementation of a Patricia trie representing a set of lists, -- generalized over any type of map from element values to tries. ----- Worst-case complexities are given in terms of @n@, @m@, and @k@. @n@ refers--- to the number of keys in the set and @m@ to their maximum length. @k@ refers+-- Worst-case complexities are given in terms of @n@, @m@, and @s@. @n@ refers+-- to the number of keys in the set and @m@ to their maximum length. @s@ refers -- to the length of a key given to the function, not any property of the set. -- -- In addition, the trie's branching factor plays a part in almost every@@ -367,13 +367,21 @@  -- * Trie-only operations +-- | @O(s)@. The set which contains all keys of which the given key is a+-- prefix. For example:+--+-- > lookupPrefix "ab" (fromList ["a","ab","ac","abc"])+-- >    == fromList ["ab","abc"]+lookupPrefix :: Map map a => [a] -> TrieSet map a -> TrieSet map a+lookupPrefix = TS .: Base.lookupPrefix .:. unTS+ -- | @O(s)@. Prepends the given key to all the keys of the set. For example: -- -- > addPrefix "pre" (fromList ["a","b"]) == fromList ["prea","preb"] addPrefix :: Map map a => [a] -> TrieSet map a -> TrieSet map a addPrefix = TS .: Base.addPrefix .:. unTS --- | @O(m)@. The set which contains all keys of which the given key is a+-- | @O(s)@. The set which contains all keys of which the given key is a -- prefix, with the prefix removed from each key. If the given key is not a -- prefix of any key in the set, an empty set is returned. For example: --@@ -387,6 +395,13 @@ -- be a member of the set. deletePrefix :: Map map a => [a] -> TrieSet map a -> TrieSet map a deletePrefix = TS .: Base.deletePrefix .:. unTS++-- | @O(s)@. Deletes all keys which are suffixes of the given key. For example:+--+-- > deleteSuffixes "ab" (fromList $ zip ["a","ab","ac","b","abc"] [1..])+-- >    == fromList [("a",1),("ac",3),("b",4)]+deleteSuffixes :: Map map a => [a] -> TrieSet map a -> TrieSet map a+deleteSuffixes = TS .: Base.deleteSuffixes .:. unTS  -- | @O(1)@. A triple containing the longest common prefix of all keys in the -- set, whether that prefix was a member of the set, and the set with that
Data/ListTrie/Set.hs view
@@ -8,8 +8,8 @@ -- | The base implementation of a trie representing a set of lists, generalized -- over any type of map from key values to tries. ----- Worst-case complexities are given in terms of @n@, @m@, and @k@. @n@ refers--- to the number of keys in the set and @m@ to their maximum length. @k@ refers+-- Worst-case complexities are given in terms of @n@, @m@, and @s@. @n@ refers+-- to the number of keys in the set and @m@ to their maximum length. @s@ refers -- to the length of a key given to the function, not any property of the set. -- -- In addition, the trie's branching factor plays a part in almost every@@ -362,13 +362,21 @@  -- * Trie-only operations +-- | @O(s)@. The set which contains all keys of which the given key is a+-- prefix. For example:+--+-- > lookupPrefix "ab" (fromList ["a","ab","ac","abc"])+-- >    == fromList ["ab","abc"]+lookupPrefix :: Map map a => [a] -> TrieSet map a -> TrieSet map a+lookupPrefix = TS .: Base.lookupPrefix .:. unTS+ -- | @O(s)@. Prepends the given key to all the keys of the set. For example: -- -- > addPrefix "pre" (fromList ["a","b"]) == fromList ["prea","preb"] addPrefix :: Map map a => [a] -> TrieSet map a -> TrieSet map a addPrefix = TS .: Base.addPrefix .:. unTS --- | @O(m)@. The set which contains all keys of which the given key is a+-- | @O(s)@. The set which contains all keys of which the given key is a -- prefix, with the prefix removed from each key. If the given key is not a -- prefix of any key in the set, an empty set is returned. For example: --@@ -382,6 +390,13 @@ -- be a member of the set. deletePrefix :: Map map a => [a] -> TrieSet map a -> TrieSet map a deletePrefix = TS .: Base.deletePrefix .:. unTS++-- | @O(s)@. Deletes all keys which are suffixes of the given key. For example:+--+-- > deleteSuffixes "ab" (fromList $ zip ["a","ab","ac","b","abc"] [1..])+-- >    == fromList [("a",1),("ac",3),("b",4)]+deleteSuffixes :: Map map a => [a] -> TrieSet map a -> TrieSet map a+deleteSuffixes = TS .: Base.deleteSuffixes .:. unTS  -- | @O(m)@. A triple containing the longest common prefix of all keys in the -- set, whether that prefix was a member of the set, and the set with that
LICENSE.txt view
@@ -2,7 +2,7 @@ are held by whoever wrote the code in question: see CREDITS.txt for a list of authors. -Copyright (c) 2008-2010 <authors>+Copyright (c) 2008-2013 <authors> All rights reserved.  Redistribution and use in source and binary forms, with or without
headers/exports.h view
@@ -42,7 +42,8 @@ 	\ 	{- * Trie-specific operations -} \ 	{- $trie-only-ops -} \-	addPrefix, deletePrefix, splitPrefix, children, children1, \+	lookupPrefix, addPrefix, deletePrefix, deleteSuffixes, \+	splitPrefix, children, children1, \ 	\ 	{- * Visualization -} \ 	showTrie@@ -128,7 +129,8 @@ 	\ 	{- * Trie-specific operations -} \ 	{- $trie-only-ops -} \-	addPrefix, deletePrefix, splitPrefix, children, children1, \+	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.4.3+Version:     0.5 Homepage:    http://iki.fi/matti.niemenmaa/list-tries/ Synopsis:    Tries and Patricia tries: finite sets and maps for list keys Category:    Data, Data Structures@@ -90,9 +90,9 @@      Build-Depends: template-haskell           >= 2.3 && < 2.9                   , HUnit                      >= 1.2 && < 1.3                   , QuickCheck                 >= 2.1 && < 2.6-                  , test-framework             >= 0.2 && < 0.7-                  , test-framework-hunit       >= 0.2 && < 0.3-                  , test-framework-quickcheck2 >= 0.2 && < 0.3+                  , test-framework             >= 0.2 && < 0.9+                  , test-framework-hunit       >= 0.2 && < 0.4+                  , test-framework-quickcheck2 >= 0.2 && < 0.4                   , ChasingBottoms             >= 1.2 && < 1.4     Other-Modules: Data.ListTrie.Base.Map
tests/Tests/Properties.hs view
@@ -433,7 +433,32 @@        in deletePrefix k (addPrefix k t) == (t :: TrieType)  |]) +-- lookupPrefix k == addPrefix k . deletePrefix k if the result is nonempty+$(makeFunc allTries ["lookupPrefix","addPrefix","deletePrefix","null"] [d|+   prop_prefixOps6 lookupPrefix addPrefix deletePrefix null t k_ =+      let k = unArb k_+          t' = lookupPrefix k (t :: TrieType)+       in null t' || t' == addPrefix k (deletePrefix k t)+ |]) +-- The result of lookupPrefix should always be a subset of the original.+$(makeFunc setsOnly ["lookupPrefix","isSubsetOf"] [d|+   prop_prefixOps7_s lookupPrefix isSubsetOf t k =+      lookupPrefix (unArb k) (t :: TrieType) `isSubsetOf` t+ |])+$(makeFunc mapsOnly ["lookupPrefix","isSubmapOf"] [d|+   prop_prefixOps7_m lookupPrefix isSubmapOf t k =+      lookupPrefix (unArb k) (t :: TrieType) `isSubmapOf` t+ |])++-- deleteSuffixes k t == difference t (lookupPrefix k t)+$(makeFunc allTries ["deleteSuffixes","difference","lookupPrefix"] [d|+   prop_prefixOps8 deleteSuffixes lookupPrefix difference t k_ =+      let k = unArb k_+       in deleteSuffixes k (t :: TrieType) == difference t (lookupPrefix k t)+ |])++ -- The monoid laws: associativity, left identity, right identity $(makeFunc allTries [] [d|    prop_monoidLaw1 x y z =@@ -540,6 +565,10 @@    , $(makeProps setsOnly "prop_prefixOps4_s")    , $(makeProps mapsOnly "prop_prefixOps4_m")    , $(makeProps allTries "prop_prefixOps5")+   , $(makeProps allTries "prop_prefixOps6")+   , $(makeProps setsOnly "prop_prefixOps7_s")+   , $(makeProps mapsOnly "prop_prefixOps7_m")+   , $(makeProps allTries "prop_prefixOps8")    , $(makeProps allTries "prop_monoidLaw1")    , $(makeProps allTries "prop_monoidLaw2")    , $(makeProps allTries "prop_monoidLaw3")
tests/Tests/Strictness.hs view
@@ -9,20 +9,13 @@ import Test.Framework.Providers.HUnit (testCase) import Test.HUnit                     (assert) -import qualified Data.ListTrie.Set.Eq-import qualified Data.ListTrie.Set.Ord-import qualified Data.ListTrie.Set.Enum import qualified Data.ListTrie.Map.Eq import qualified Data.ListTrie.Map.Ord import qualified Data.ListTrie.Map.Enum-import qualified Data.ListTrie.Patricia.Set.Eq-import qualified Data.ListTrie.Patricia.Set.Ord-import qualified Data.ListTrie.Patricia.Set.Enum import qualified Data.ListTrie.Patricia.Map.Eq import qualified Data.ListTrie.Patricia.Map.Ord import qualified Data.ListTrie.Patricia.Map.Enum -import Tests.Base import Tests.TH  -- size doesn't evaluate the values but it does traverse the whole trie