list-tries 0.3 → 0.4

raw patch · 11 files changed

+155/−39 lines, 11 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• CHANGELOG.txt +20/−0
• Data/ListTrie/Base.hs +9/−4
• Data/ListTrie/Map.hs +22/−5
• Data/ListTrie/Patricia/Base.hs +12/−4
• Data/ListTrie/Patricia/Map.hs +22/−5
• Data/ListTrie/Patricia/Set.hs +26/−7
• Data/ListTrie/Set.hs +26/−7
• headers/exports.h +2/−2
• list-tries.cabal +1/−1
• tests/Tests/Cases.hs +3/−2
• tests/Tests/Properties.hs +12/−2

@@ -1,3 +1,23 @@+2010-09-11, 0.4:+	Fixed documentation of the 'deletePrefix' function: if the given key is not+	a prefix of any key, an empty, not unchanged, map/set is returned. Thanks to+	Brian Bloniarz for the bug report.++	Fixed bug in the Patricia version of 'deletePrefix' causing it to not delete+	anything if the prefix to be deleted was a proper prefix of the common+	prefix.++	Changed 'children' to return the map as-is instead of converting it into a+	list first:++		children :: Trie trie st map k => trie map k a -> CMap trie map k a++	Added the 'children1' function as a single-level equivalent of 'children',+	more directly reflecting the structure of the non-Patricia tries. Requested+	by Brian Bloniarz.++		children1 :: Trie trie st map k => trie map k a -> CMap trie map k a+ 2010-09-09, 0.3:    Fixed strictness of the strict versions of the following non-Patricia    functions: insert, adjust, alter, union, difference, intersection,

@@ -25,7 +25,7 @@    , fromList, fromListWith, fromListWith', fromListWithKey, fromListWithKey'    , findMin, findMax, deleteMin, deleteMax, minView, maxView    , findPredecessor, findSuccessor-   , addPrefix, splitPrefix, deletePrefix, children+   , addPrefix, splitPrefix, deletePrefix, children, children1    , showTrieWith    ) where @@ -826,13 +826,18 @@  -- O(m) children :: (Boolable (st a), Trie trie st map k)-         => trie map k a -> [(k, trie map k a)]+         => trie map k a -> CMap trie map k a children tr = let (v,m) = tParts tr                in if hasValue v-                     then Map.toList m+                     then m                      else case Map.singletonView m of                                Just (_, tr') -> children tr'-                               Nothing       -> Map.toList m+                               Nothing       -> m++-- O(1)+children1 :: (Alt st a, Trie trie st map k)+          => trie map k a -> CMap trie map k a+children1 = tMap  -- * Visualization 

@@ -987,7 +987,7 @@  -- | @O(m)@. 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, the map is returned unchanged. For example:+-- prefix of any key in the map, an empty map is returned. For example: -- -- > deletePrefix "a" (fromList [("a",1),("ab",2),("ac",3)]) -- >    == fromList [("",1),("b",2),("c",3)]@@ -1014,14 +1014,31 @@  -- | @O(m)@. The children of the longest common prefix in the trie as maps, -- associated with their distinguishing key value. If the map contains less--- than two keys, this function will return the empty list. Examples;+-- than two keys, this function will return an empty map. Examples; -- -- > children (fromList [("a",1),("abc",2),("abcd",3)])--- >    == [('b',fromList [("c",2),("cd",3)])]+-- >    == Map.fromList [('b',fromList [("c",2),("cd",3)])] -- > children (fromList [("b",1),("c",2)])--- >    == [('b',fromList [("",1)]),('c',fromList [("",2)])]-children :: Map map k => TrieMap map k a -> [(k, TrieMap map k a)]+-- >    == Map.fromList [('b',fromList [("",1)]),('c',fromList [("",2)])]+children :: Map map k => TrieMap map k a -> map k (TrieMap map k a) children = Base.children++-- | @O(1)@. The children of the first element of the longest common prefix in+-- the trie as maps, associated with their distinguishing key value. If the map+-- contains less than two keys, this function will return an empty map.+--+-- If the longest common prefix of all keys in the trie is the empty list, this+-- function is equivalent to 'children'. Otherwise, the result will always be a+-- single-element map.+--+-- Examples:+--+-- > children1 (fromList [("abc",1),("abcd",2)])+-- >    == Map.fromList [('a',fromList [("bc",1),("bcd",2)])]+-- > children1 (fromList [("b",1),("c",2)])+-- >    == Map.fromList [('b',fromList [("",1)]),('c',fromList [("",2)])]+children1 :: Map map k => TrieMap map k a -> map k (TrieMap map k a)+children1 = Base.children1  -- * Visualization 

@@ -26,7 +26,7 @@    , fromList, fromListWith, fromListWith', fromListWithKey, fromListWithKey'    , findMin, findMax, deleteMin, deleteMax, minView, maxView    , findPredecessor, findSuccessor-   , addPrefix, splitPrefix, deletePrefix, children+   , addPrefix, splitPrefix, deletePrefix, children, children1    , showTrieWith    , eqComparePrefixes, ordComparePrefixes    ) where@@ -1272,7 +1272,7 @@    let (v,pre,m) = tParts tr     in case comparePrefixes (Map.eqCmp m) pre xs of             Same                   -> tryCompress (mkTrie v [] m)-            PostFix (Left _)       -> tr+            PostFix (Left ys)      -> mkTrie v ys m             DifferedAt _ _ _       -> empty             PostFix (Right (y:ys)) ->                case Map.lookup y m of@@ -1291,8 +1291,16 @@     in (pre, v, tryCompress $ mkTrie altEmpty [] m)  -- O(1)-children :: Trie trie st map k => trie map k a -> [(k, trie map k a)]-children = Map.toList . tMap+children :: Trie trie st map k => trie map k a -> CMap trie map k a+children = tMap++-- O(1)+children1 :: Trie trie st map k => trie map k a -> CMap trie map k a+children1 tr =+   let (v,pre,m) = tParts tr+    in case pre of+            []   -> m+            p:ps -> Map.singleton p (mkTrie v ps m)  -- * Visualization 

@@ -1005,7 +1005,7 @@  -- | @O(m)@. 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, the map is returned unchanged. For example:+-- prefix of any key in the map, an empty map is returned. For example: -- -- > deletePrefix "a" (fromList [("a",1),("ab",2),("ac",3)]) -- >    == fromList [("",1),("b",2),("c",3)]@@ -1032,14 +1032,31 @@  -- | @O(1)@. The children of the longest common prefix in the trie as maps, -- associated with their distinguishing key value. If the map contains less--- than two keys, this function will return the empty list. Examples;+-- than two keys, this function will return an empty map. Examples; -- -- > children (fromList [("a",1),("abc",2),("abcd",3)])--- >    == [('b',fromList [("c",2),("cd",3)])]+-- >    == Map.fromList [('b',fromList [("c",2),("cd",3)])] -- > children (fromList [("b",1),("c",2)])--- >    == [('b',fromList [("",1)]),('c',fromList [("",2)])]-children :: Map map k => TrieMap map k a -> [(k, TrieMap map k a)]+-- >    == Map.fromList [('b',fromList [("",1)]),('c',fromList [("",2)])]+children :: Map map k => TrieMap map k a -> map k (TrieMap map k a) children = Base.children++-- | @O(1)@. The children of the first element of the longest common prefix in+-- the trie as maps, associated with their distinguishing key value. If the map+-- contains less than two keys, this function will return an empty map.+--+-- If the longest common prefix of all keys in the trie is the empty list, this+-- function is equivalent to 'children'. Otherwise, the result will always be a+-- single-element map.+--+-- Examples:+--+-- > children1 (fromList [("abc",1),("abcd",2)])+-- >    == Map.fromList [('a',fromList [("bc",1),("bcd",2)])]+-- > children1 (fromList [("b",1),("c",2)])+-- >    == Map.fromList [('b',fromList [("",1)]),('c',fromList [("",2)])]+children1 :: Map map k => TrieMap map k a -> map k (TrieMap map k a)+children1 = Base.children1  -- * Visualization 

@@ -23,7 +23,7 @@ -- Disclaimer: the complexities have not been proven. module Data.ListTrie.Patricia.Set (SET_EXPORTS) where -import Control.Arrow  ((***), second)+import Control.Arrow  ((***)) import Control.Monad  (liftM3) import Data.Binary    (Binary,get,put) import Data.Function  (on)@@ -375,7 +375,7 @@  -- | @O(m)@. 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, the set is returned unchanged. For example:+-- prefix of any key in the set, an empty set is returned. For example: -- -- > deletePrefix "a" (fromList ["a","ab","ac"]) == fromList ["","b","c"] --@@ -399,12 +399,31 @@  -- | @O(1)@. The children of the longest common prefix in the trie as sets, -- associated with their distinguishing key value. If the set contains less--- than two keys, this function will return the empty list. Examples;+-- than two keys, this function will return an empty map. Examples; ----- > children (fromList ["a","abc","abcd"]) == [('b',fromList ["c","cd"])]--- > children (fromList ["b","c"]) == [('b',fromList [""]),('c',fromList [""])]-children :: Map map a => TrieSet map a -> [(a, TrieSet map a)]-children = Prelude.map (second TS) . Base.children . unTS+-- > children (fromList ["a","abc","abcd"])+-- >    == Map.fromList [('b',fromList ["c","cd"])]+-- > children (fromList ["b","c"])+-- >    == Map.fromList [('b',fromList [""]),('c',fromList [""])]+children :: Map map a => TrieSet map a -> map a (TrieSet map a)+children = Map.map TS . Base.children . unTS++-- | @O(1)@. The children of the first element of the longest common prefix in+-- the trie as sets, associated with their distinguishing key value. If the set+-- contains less than two keys, this function will return an empty map.+--+-- If the longest common prefix of all keys in the trie is the empty list, this+-- function is equivalent to 'children'. Otherwise, the result will always be a+-- single-element map.+--+-- Examples:+--+-- > children1 (fromList ["abc","abcd"])+-- >    == Map.fromList [('a',fromList ["bc","bcd"])]+-- > children1 (fromList ["b","c"])+-- >    == Map.fromList [('b',fromList [""]),('c',fromList [""])]+children1 :: Map map a => TrieSet map a -> map a (TrieSet map a)+children1 = Map.map TS . Base.children1 . unTS  -- * Visualization 

@@ -23,7 +23,7 @@ -- Disclaimer: the complexities have not been proven. module Data.ListTrie.Set (SET_EXPORTS) where -import Control.Arrow  ((***), second)+import Control.Arrow  ((***)) import Control.Monad  (liftM2) import Data.Binary    (Binary,get,put) import Data.Function  (on)@@ -370,7 +370,7 @@  -- | @O(m)@. 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, the set is returned unchanged. For example:+-- prefix of any key in the set, an empty set is returned. For example: -- -- > deletePrefix "a" (fromList ["a","ab","ac"]) == fromList ["","b","c"] --@@ -394,12 +394,31 @@  -- | @O(m)@. The children of the longest common prefix in the trie as sets, -- associated with their distinguishing key value. If the set contains less--- than two keys, this function will return the empty list. Examples;+-- than two keys, this function will return an empty map. Examples; ----- > children (fromList ["a","abc","abcd"]) == [('b',fromList ["c","cd"])]--- > children (fromList ["b","c"]) == [('b',fromList [""]),('c',fromList [""])]-children :: Map map a => TrieSet map a -> [(a, TrieSet map a)]-children = Prelude.map (second TS) . Base.children . unTS+-- > children (fromList ["a","abc","abcd"])+-- >    == Map.fromList [('b',fromList ["c","cd"])]+-- > children (fromList ["b","c"])+-- >    == Map.fromList [('b',fromList [""]),('c',fromList [""])]+children :: Map map a => TrieSet map a -> map a (TrieSet map a)+children = Map.map TS . Base.children . unTS++-- | @O(1)@. The children of the first element of the longest common prefix in+-- the trie as sets, associated with their distinguishing key value. If the set+-- contains less than two keys, this function will return an empty map.+--+-- If the longest common prefix of all keys in the trie is the empty list, this+-- function is equivalent to 'children'. Otherwise, the result will always be a+-- single-element map.+--+-- Examples:+--+-- > children1 (fromList ["abc","abcd"])+-- >    == Map.fromList [('a',fromList ["bc","bcd"])]+-- > children1 (fromList ["b","c"])+-- >    == Map.fromList [('b',fromList [""]),('c',fromList [""])]+children1 :: Map map a => TrieSet map a -> map a (TrieSet map a)+children1 = Map.map TS . Base.children1 . unTS  -- * Visualization 

@@ -42,7 +42,7 @@ 	\ 	{- * Trie-specific operations -} \ 	{- $trie-only-ops -} \-	addPrefix, deletePrefix, splitPrefix, children, \+	addPrefix, deletePrefix, splitPrefix, children, children1, \ 	\ 	{- * Visualization -} \ 	showTrie@@ -128,7 +128,7 @@ 	\ 	{- * Trie-specific operations -} \ 	{- $trie-only-ops -} \-	addPrefix, deletePrefix, splitPrefix, children, \+	addPrefix, deletePrefix, splitPrefix, children, children1, \ 	\ 	{- * Visualization -} \ 	showTrie, showTrieWith

@@ -1,7 +1,7 @@ Cabal-Version: >= 1.6  Name:        list-tries-Version:     0.3+Version:     0.4 Homepage:    http://iki.fi/matti.niemenmaa/list-tries/ Synopsis:    Tries and Patricia tries: finite sets and maps for list keys Category:    Data, Data Structures

@@ -9,6 +9,7 @@ import Test.Framework.Providers.HUnit (testCase) import Test.HUnit                     (assert) +import qualified Data.ListTrie.Base.Map as Map import qualified Data.ListTrie.Set.Eq import qualified Data.ListTrie.Set.Ord import qualified Data.ListTrie.Set.Enum@@ -159,12 +160,12 @@ $(makeFunc setsOnly ["fromList","children"] [d|    children1_s fromList children =       children (fromList ["foo","foobar"] :: TrieType) ==-         [('b',fromList ["ar"])]+         Map.singleton 'b' (fromList ["ar"])  |]) $(makeFunc mapsOnly ["fromList","children"] [d|    children1_m fromList children =       children (fromList [("foo",1),("foobar",2)] :: TrieType) ==-         [('b',fromList [("ar",2)])]+         Map.singleton 'b' (fromList [("ar",2)])  |])  tests = testGroup "Individual cases"

@@ -17,6 +17,7 @@ import Test.Framework.Providers.QuickCheck2 (testProperty) import Test.QuickCheck                      ((==>)) +import qualified Data.ListTrie.Base.Map as Map import qualified Data.ListTrie.Set.Eq import qualified Data.ListTrie.Set.Ord import qualified Data.ListTrie.Set.Enum@@ -414,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)-                                (children t))+                                (Map.toList $ children t))  |]) $(makeFunc mapsOnly ["addPrefix","splitPrefix","children","unions","insert"]  [d|@@ -422,9 +423,17 @@       let (k,mv,_) = splitPrefix (t :: TrieType)        in t == ((case mv of Just v -> insert k v; _ -> id) . addPrefix k .                    unions $ map (uncurry $ addPrefix . return)-                                (children t))+                                (Map.toList $ children t))  |]) +-- Deleting an added prefix should change nothing+$(makeFunc allTries ["addPrefix","deletePrefix"] [d|+   prop_prefixOps5 addPrefix deletePrefix t k_ =+      let k = unArb k_+       in deletePrefix k (addPrefix k t) == (t :: TrieType)+ |])++ -- The monoid laws: associativity, left identity, right identity $(makeFunc allTries [] [d|    prop_monoidLaw1 x y z =@@ -530,6 +539,7 @@    , $(makeProps allTries "prop_prefixOps3")    , $(makeProps setsOnly "prop_prefixOps4_s")    , $(makeProps mapsOnly "prop_prefixOps4_m")+   , $(makeProps allTries "prop_prefixOps5")    , $(makeProps allTries "prop_monoidLaw1")    , $(makeProps allTries "prop_monoidLaw2")    , $(makeProps allTries "prop_monoidLaw3")