TernaryTrees 0.0.1 → 0.0.2

raw patch · 3 files changed

+139/−7 lines, 3 filesPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

API changes (from Hackage documentation)

Files

• Data/Map/TernaryMap.hs +126/−0
• Data/Set/TernarySet.hs +1/−1
• TernaryTrees.cabal +12/−6

@@ -0,0 +1,126 @@+module Data.Map.TernaryMap where+import Data.Binary+import Control.Monad+++-- | 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+             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+               deriving (Show, Eq)+++instance Eq a => Eq (Elem2 a b) where+    (Val _) == (Val _) = True+    (Val _) == x        = False+    x        == (Val _) = False+    (C a)    == (C b)    = a == b++-- | All elements are greater than the Val Elem, otherwise they are+-- ordered according to their own ord instance (for the `compare (C x) (C y)` case).+instance (Ord a) => Ord (Elem2 a b) where+    compare (Val _) (Val _)   = EQ+    compare (Val _) x          = LT+    compare x        (Val _)   = GT+    compare (C x) (C y)         = compare x y++isVal (Val _) = True+isVal _        = False++-- | Quickly build a tree without an initial tree. This should be used+-- to create an initial tree, using insert there after.+insert' :: Ord a => [a] -> b -> TernaryMap a b+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.+insert :: Ord a => [a] -> b -> TernaryMap a b -> TernaryMap a b+-- General case+insert xss@(x:xs) b (TNode ele l e h) =+    case compare (C x) ele of+        LT -> TNode ele (insert xss b l) e h+        EQ -> TNode ele l (insert xs b e) h+        GT -> TNode ele l e (insert xss b h)+-- Insert new elements quickly+insert xss@(x:xs) b TEnd =+    insert' xss b+-- TEnd 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+insert [] b TEnd =+    TNode (Val b) TEnd TEnd TEnd+++-- | Returns true if the `[a]` is in the TernaryMap+isKey :: Ord a => [a] -> TernaryMap a b -> Bool+isKey          _ TEnd              = False+isKey         [] (TNode ele l e h) = isVal ele || isKey [] l+isKey xss@(x:xs) (TNode ele l e h) = +    case compare (C x) ele of+        LT -> isKey xss l+        EQ -> isKey  xs e+        GT -> isKey xss h++-- | Returns the number of non-Val Elems+treeSize :: TernaryMap a b -> Int+treeSize TEnd = 0+treeSize (TNode (Val _) l e h) = treeSize l + treeSize e + treeSize h+treeSize (TNode _ l e h) = 1 + treeSize l + treeSize e + treeSize h++-- | Counts how many entries there are in the tree.+numEntries :: TernaryMap a b -> Int+numEntries TEnd = 0+numEntries (TNode (Val _) l e h) = 1 + numEntries l + numEntries e + numEntries h+numEntries (TNode _ l e h) = numEntries l + numEntries e + numEntries h++-- | Creates a new tree from a list of 'strings'+fromList :: Ord a => [([a],b)] -> TernaryMap a b+fromList = foldl (\tree (as,b) -> insert as b tree) TEnd++instance (Binary a, Binary b) => Binary (Elem2 a b) where+    put (C x) = putWord8 0 >> put x+    put (Val b) = putWord8 1 >> put b+    get = do+        n <- getWord8+        case n of+            0 -> liftM C get+            1 -> liftM Val get++-- | 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 (TNode ch TEnd TEnd TEnd) = do+        putWord8 1+        put ch+    -- Also common, basically what insert' produces.+    put (TNode ch TEnd e TEnd) = do+        putWord8 2+        put ch+        put e+    -- General case+    put (TNode ch l e h) = do+        putWord8 3+        put ch+        put l+        put e+        put h+    get = do+        tag <- getWord8+        case tag of+            0 -> return TEnd+            1 -> do+                ch <- get+                return (TNode ch TEnd TEnd TEnd)+            2 -> do+                ch <- get+                e <- get+                return (TNode ch TEnd e TEnd)+            3 -> liftM4 TNode get get get get

@@ -22,7 +22,7 @@  -- | Quickly build a tree without an initial tree. This should be used -- to create an initial tree, using insert there after.-insert' :: [a] -> TernarySet a+insert' :: Ord a => [a] -> TernarySet a insert' (x:xs) = TNode (C x) TEnd (insert' xs) TEnd insert' []     = TNode Null TEnd TEnd TEnd 

@@ -1,16 +1,16 @@ Name:                   TernaryTrees-Version:                0.0.1+Version:                0.0.2 Category:               Datatypes Synopsis:               Efficient pure ternary trees 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/> 			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/> 			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@@ -18,16 +18,22 @@ 			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> License:                BSD3 License-file:           LICENSE.txt Author:                 Alex Mason-Maintainer:             Alex Mason <axman6@gmail.com>+Maintainer:             Alex Mason (irc: Axman6) <axman6@gmail.com> build-type:             Simple Cabal-Version:          >= 1.2 Extra-Source-Files:+        Data/Map/TernaryMap.hs         Data/Set/TernarySet.hs         Data/Set/StringSet.hs @@ -35,7 +41,7 @@         Build-Depends:                 base >= 4.0.0.0, base < 5.0.0.0, binary >= 0.5.0.0         Exposed-modules:-                Data.Set.TernarySet, Data.Set.StringSet+                Data.Set.TernarySet, Data.Set.StringSet, Data.Map.TernaryMap  Executable tdict   Main-Is:        Main.hs