list-tries 0.0 → 0.1

raw patch · 10 files changed

+102/−27 lines, 10 filesdep +binaryPVP ok

version bump matches the API change (PVP)

Dependencies added: binary

API changes (from Hackage documentation)

Files

• CHANGELOG.txt +10/−0
• CREDITS.txt +4/−0
• Data/ListTrie/Base/Map.hs +15/−1
• Data/ListTrie/Map.hs +6/−0
• Data/ListTrie/Patricia/Map.hs +6/−0
• Data/ListTrie/Patricia/Set.hs +10/−0
• Data/ListTrie/Set.hs +10/−0
• LICENSE.txt +28/−24
• list-tries.cabal +6/−2
• tests/Tests/Properties.hs +7/−0

@@ -0,0 +1,10 @@+2009-07-05, 0.1:+	All tries are now instances of Binary, thanks to Gregory Crosswhite. Adds a+	dependency on the 'binary' library as well as the following two methods to+	the Map class in Base.Map:++		serializeToList     :: m k a -> [(k,a)]+		deserializeFromList :: [(k,a)] -> m k a++2009-04-21, 0.0:+	Initial release.

@@ -0,0 +1,4 @@+In alphabetical order by surname:++Gregory Crosswhite+Matti   Niemenmaa

@@ -29,7 +29,8 @@  import Data.ListTrie.Util (both, (.:)) -#ifdef MIN_VERSION_containers -- from Cabal+-- MIN_VERSION_containers is defined by Cabal+#ifdef MIN_VERSION_containers # if !(MIN_VERSION_containers(0,3,0)) # define TOO_OLD_CONTAINERS # endif@@ -99,6 +100,9 @@    fromList     ::                  [(k,a)] -> m k a    fromListWith :: (a -> a -> a) -> [(k,a)] -> m k a +   serializeToList     :: m k a -> [(k,a)]+   deserializeFromList :: [(k,a)] -> m k a+    isSubmapOfBy :: (a -> b -> Bool) -> m k a -> m k b -> Bool     singletonView :: m k a -> Maybe (k,a)@@ -135,6 +139,9 @@    fromList       = fromListWith const    fromListWith f = foldr (uncurry $ insertWith f) empty +   serializeToList     = toList+   deserializeFromList = fromList+    singletonView m =       case toList m of            [x] -> Just x@@ -375,6 +382,9 @@    fromList     = M.fromList    fromListWith = M.fromListWith +   serializeToList     = M.toAscList+   deserializeFromList = M.fromDistinctAscList+    isSubmapOfBy = M.isSubmapOfBy     singletonView m =@@ -479,6 +489,10 @@    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)++   serializeToList (IMap x) = Prelude.map (first toEnum) . IM.toAscList $ x+   deserializeFromList      =+      IMap . IM.fromDistinctAscList . Prelude.map (first fromEnum)     isSubmapOfBy f (IMap x) (IMap y) = IM.isSubmapOfBy f x y 

@@ -38,6 +38,8 @@  import Control.Applicative ((<*>),(<$>)) import Control.Arrow       ((***), second)+import Control.Monad       (liftM2)+import Data.Binary         (Binary,get,put) import qualified Data.DList as DL import Data.Either         (partitionEithers) import Data.Function       (on)@@ -124,6 +126,10 @@       (xs, rest) <- readsPrec (p+1) list       [(fromList xs, rest)] #endif++instance (Map map k, Binary k, Binary a) => Binary (TrieMap map k a) where+   put (Tr v m) = put v >> (put . Map.serializeToList $ m)+   get = liftM2 Tr get (get >>= return . Map.deserializeFromList)  -- * Construction 

@@ -38,6 +38,8 @@  import Control.Applicative ((<*>),(<$>)) import Control.Arrow       ((***), second)+import Control.Monad       (liftM3)+import Data.Binary         (Binary,get,put) import qualified Data.DList as DL import Data.Either         (partitionEithers) import Data.Function       (on)@@ -136,6 +138,10 @@       (xs, rest) <- readsPrec (p+1) list       [(fromList xs, rest)] #endif++instance (Map map k, Binary k, Binary a) => Binary (TrieMap map k a) where+   put (Tr v k m) = put v >> put k >> (put . Map.serializeToList $ m)+   get = liftM3 Tr get get (get >>= return . Map.deserializeFromList)  -- * Construction 

@@ -24,6 +24,8 @@ module Data.ListTrie.Patricia.Set (SET_EXPORTS) where  import Control.Arrow  ((***), second)+import Control.Monad  (liftM3)+import Data.Binary    (Binary,get,put) import Data.Function  (on) import Data.Monoid    (Monoid(..)) import Prelude hiding (filter, foldl, foldr, map, null)@@ -119,6 +121,14 @@       (xs, rest) <- readsPrec (p+1) list       [(fromList xs, rest)] #endif++instance (Map map k, Binary k, Binary a) => Binary (TrieSetBase map k a) where+   put (Tr v k m) = put v >> put k >> (put . Map.serializeToList $ m)+   get = liftM3 Tr get get (get >>= return . Map.deserializeFromList)++instance (Map map a, Binary a) => Binary (TrieSet map a) where+   put = put . unTS+   get = get >>= return . TS  -- * Construction 

@@ -24,6 +24,8 @@ module Data.ListTrie.Set (SET_EXPORTS) where  import Control.Arrow  ((***), second)+import Control.Monad  (liftM2)+import Data.Binary    (Binary,get,put) import Data.Function  (on) import Data.Monoid    (Monoid(..)) import Prelude hiding (filter, foldl, foldr, map, null)@@ -114,6 +116,14 @@       (xs, rest) <- readsPrec (p+1) list       [(fromList xs, rest)] #endif++instance (Map map k, Binary k, Binary a) => Binary (TrieSetBase map k a) where+   put (Tr v m) = put v >> (put . Map.serializeToList $ m)+   get = liftM2 Tr get (get >>= return . Map.deserializeFromList)++instance (Map map a, Binary a) => Binary (TrieSet map a) where+   put = put . unTS+   get = get >>= return . TS  -- * Construction 

@@ -1,24 +1,28 @@-Copyright (c) 2009 Matti Niemenmaa
-All rights reserved.
-
-Redistribution and use in source and binary forms, with or without
-modification, are permitted provided that the following conditions are met:
-    * Redistributions of source code must retain the above copyright
-      notice, this list of conditions and the following disclaimer.
-    * Redistributions in binary form must reproduce the above copyright
-      notice, this list of conditions and the following disclaimer in the
-      documentation and/or other materials provided with the distribution.
-    * Neither the name of the project nor the names of its contributors may be
-      used to endorse or promote products derived from this software without
-      specific prior written permission.
-
-THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS OR IMPLIED
-WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
-MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
-EVENT SHALL THE AUTHORS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
-INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
-LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
-PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
-LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
-OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
-ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+The code is released under the license below. Copyrights to parts of the code+are held by whoever wrote the code in question: see CREDITS.txt for a list of+authors.++Copyright (c) 2008-2009 <authors>+All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met:+    * Redistributions of source code must retain the above copyright+      notice, this list of conditions and the following disclaimer.+    * Redistributions in binary form must reproduce the above copyright+      notice, this list of conditions and the following disclaimer in the+      documentation and/or other materials provided with the distribution.+    * Neither the name of the project nor the names of its contributors may be+      used to endorse or promote products derived from this software without+      specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS OR IMPLIED+WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF+MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO+EVENT SHALL THE AUTHORS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,+INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR+PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF+LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE+OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF+ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

@@ -1,7 +1,7 @@ Cabal-Version: >= 1.6  Name:        list-tries-Version:     0.0+Version:     0.1 Homepage:    http://iki.fi/matti.niemenmaa/list-tries/ Synopsis:    Tries and Patricia tries: finite sets and maps for list keys Category:    Data, Data Structures@@ -29,7 +29,9 @@  Build-Type: Simple -Extra-Source-Files: headers/*.h+Extra-Source-Files: CHANGELOG.txt+                    CREDITS.txt+                    headers/*.h                     tests/README.txt                     tests/*.hs                     tests/Tests/*.hs@@ -48,10 +50,12 @@       Build-Depends: base       >= 3 && < 4.1                    , containers >= 0.3 && < 0.4                    , dlist      == 0.4.*+                   , binary     >= 0.5 && < 0.6    else       Build-Depends: base       >= 3 && < 4.1                    , containers >= 0.2 && < 0.3                    , dlist      == 0.4.*+                   , binary     >= 0.5 && < 0.6     Exposed-Modules: Data.ListTrie.Base.Map                     Data.ListTrie.Map

@@ -5,6 +5,7 @@ module Tests.Properties (tests) where  import Control.Arrow    ((&&&), first)+import Data.Binary      (encode,decode) import Data.Foldable    (foldMap) import Data.Function    (on) import Data.List        (nubBy)@@ -468,6 +469,11 @@       compare x (y :: TrieType) == compare (toAscList x) (toAscList y)  |]) +-- serialization followed by deserialization should not alter the trie+$(makeFunc allTries [] [d|+   prop_serializeDeserialize x = (decode.encode) (x :: TrieType) == x+ |])+ tests = testGroup "QuickCheck properties"    [ $(makeProps allTries "prop_size1")    , $(makeProps allTries "prop_size2")@@ -533,4 +539,5 @@    , $(makeProps mapsOnly "prop_traversableLaw2")    , $(makeProps allTries "prop_showRead1")    , $(makeProps allTries "prop_ord1")+   , $(makeProps allTries "prop_serializeDeserialize")    ]