TernaryTrees 0.0.2.1 → 0.0.2.2

raw patch · 4 files changed

+34/−26 lines, 4 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• Data/Map/TernaryMap.hs +11/−8
• Data/Set/TernarySet.hs +4/−2
• Main.hs +6/−1
• TernaryTrees.cabal +13/−15

@@ -5,11 +5,13 @@  -- | Elem2 a b is used to hold elements of a list after insertion, and -- indicate that we've reached the end of the list.-data Elem2 a b = C !a | Val b+data Elem2 a b = C !a+               | Val b              deriving (Show) -- | TernaryMap a b is ternary tree. It is commonly used for storing word lists -- like dictionaries.-data TernaryMap a b = TNode !(Elem2 a b) !(TernaryMap a b) !(TernaryMap a b) !(TernaryMap a b) | TEnd+data TernaryMap a b = TNode !(Elem2 a b) !(TernaryMap a b) !(TernaryMap a b) !(TernaryMap a b)+                    | TEnd                deriving (Show, Eq)  @@ -36,7 +38,8 @@ insert' (x:xs) b = TNode (C x) TEnd (insert' xs b) TEnd insert' []     b = TNode (Val b) TEnd TEnd TEnd --- | Inserts an entries into a tree.+-- | Inserts an entries into a tree. Values with the same key will be replaced+-- with the newer version. insert :: Ord a => [a] -> b -> TernaryMap a b -> TernaryMap a b -- General case insert xss@(x:xs) b (TNode ele l e h) =@@ -47,17 +50,17 @@ -- Insert new elements quickly insert xss@(x:xs) b TEnd =     insert' xss b--- TEnd of word in non empty tree+-- end of word in non empty tree insert [] b (TNode ele l e h) =      case compare (Val b) ele of         EQ -> TNode (Val b) l e h         LT  -> TNode ele (insert [] b l) e h--- TEnd of word in empty tree+-- end of word in empty tree insert [] b TEnd =     TNode (Val b) TEnd TEnd TEnd  --- | Returns true if the `[a]` is in the TernaryMap+-- | Returns true if the `[a]` is a key in the TernaryMap. isKey :: Ord a => [a] -> TernaryMap a b -> Bool isKey          _ TEnd              = False isKey         [] (TNode ele l e h) = isVal ele || isKey [] l@@ -95,8 +98,8 @@ -- | This binary instance saves some space by making special cases -- of some commonly encountered structures in the trees. instance (Binary a, Binary b) => Binary (TernaryMap a b) where-    put TEnd = put (0 :: Word8)-    -- Quite common, so speecialised+    put TEnd = putWord8 0+    -- Quite common, so specialised     put (TNode ch TEnd TEnd TEnd) = do         putWord8 1         put ch

@@ -5,11 +5,13 @@  -- | Elem a is used to hold elements of a list after insertion, and -- indicate that we've reached the end of the list.-data Elem a = C !a | Null+data Elem a = C !a+            | Null              deriving (Show, Eq) -- | TernarySet a is ternary tree. It is commonly used for storing word lists -- like dictionaries.-data TernarySet a = TNode !(Elem a) !(TernarySet a) !(TernarySet a) !(TernarySet a) | TEnd+data TernarySet a = TNode !(Elem a) !(TernarySet a) !(TernarySet a) !(TernarySet a)+                  | TEnd                deriving (Show, Eq)  -- | All elements are greater than the Null Elem, otherwise they are

@@ -14,17 +14,22 @@         tree = fromList $ wds -- put them in the tree         newname = (file ++ ".bin")     -- print . treeSize $ tree+         putStr "All input words are in dictionary: "     print . all (`isElem` tree) $ wds -- make sure all words are actually in the tree+         putStr "Same number of words as input: "     print (numEntries tree == length wds) -- make sure the same number of words are in the tree+         putStr ("Writing " ++ newname ++ "... ")     encodeFile newname tree -- write the tree to a file as "filename.bin"+         putStr "done.\nReading data back in... "     ntree <- decodeFile newname -- read in the file and decode it+         putStr "done.\nRead in data matches original: "     print (tree == ntree) -- check the read in tree is the same as the one we wrote-    -- print tree+         putStrLn "\n-- Enter a word to see if it is in the dictionary (^C to exit):"     interact' (("-- " ++) . show . (`isElem` tree)) -- enter a word to see if it's in the tree 

@@ -1,31 +1,29 @@ Name:                   TernaryTrees-Version:                0.0.2.1+Version:                0.0.2.2 Category:               Data Structures-Synopsis:               Efficient pure ternary trees+Synopsis:               Efficient pure ternary tree Sets and Maps Description:            Ternary trees are an efficient structure often used for storing 			strings for fast lookups. This package implements a generic tree 			for storing lists of Ord instances, and a specialised String-			implementation which is about 30% faster than the generic version.-			<br/>+			implementation which is about 30% faster than the generic version.\+			 			An example program is provided what shows how to use the package 			as a dictionary program for spell checking, and how it can be -			used to serialise data with Don Stewart's Data.Binary package.-			<br/>+			used to serialise data with Don Stewart's Data.Binary package.\+			 			From my testing, using the /usr/shart/dict/words file on my system 			(over 230,000 words), inserting all words, checking they all exist 			in the tree, writing them to a binary file, reading them back in 			and checking the read in result is the same as the original takes 			slightly over 3 seconds using the StringSet. The written file is  			also slightly smaller than the input (by about 10% for shuffled data,-			and 7% for in order data).-			<br/>-			Future releases (coming very soon) will also have Map structures-			for key/value lookups.-			<br/>-			New n this version: <br/>-			<ul>-			    <li>Added Data.Map.TernaryMap</li>    -			</ul>+			and 7% for in order data).\+			+			New in this version: \+			\+			    * Added Data.Map.TernaryMap\+			    * (Hopefully fixed this .cabal file) +			 License:                BSD3 License-file:           LICENSE.txt Author:                 Alex Mason