TernaryTrees 0.1.3.3 → 0.1.3.4
raw patch · 5 files changed
+48/−44 lines, 5 filesdep ~binary
Dependency ranges changed: binary
Files
- Data/Map/TernaryMap.hs +0/−1
- Data/Map/TernaryMap/Internal.hs +5/−1
- Data/Set/StringSet/Internal.hs +7/−3
- Data/Set/TernarySet/Internal.hs +5/−1
- TernaryTrees.cabal +31/−38
Data/Map/TernaryMap.hs view
@@ -5,7 +5,6 @@ member, size, fromList,- empty, lookup, (!), findWithDefault,
Data/Map/TernaryMap/Internal.hs view
@@ -2,7 +2,11 @@ -- | TernaryMap k v is ternary tree. It is commonly used for storing word lists -- like dictionaries.-data TernaryMap k v = Node !k !(TernaryMap k v) !(TernaryMap k v) !(TernaryMap k v)+data TernaryMap k v = + -- | Nodes contain key elements only+ Node !k !(TernaryMap k v) !(TernaryMap k v) !(TernaryMap k v)+ -- | Null nodes contain the value pointed to by the key list | Null v !(TernaryMap k v)+ -- | An empty tree | End deriving (Show, Eq)
Data/Set/StringSet/Internal.hs view
@@ -3,9 +3,13 @@ -- | StringSet is ternary tree. It is commonly used for storing word lists -- like dictionaries for spell checking etc.-data StringSet = Node {-# UNPACK #-} !Char !StringSet !StringSet !StringSet -- | Tree node - | Null !StringSet -- | null nodes can only have a greater than branch by definition- | End -- | a branch that doesn’t contain anything+data StringSet = + -- | Tree node + Node {-# UNPACK #-} !Char !StringSet !StringSet !StringSet+ -- | null nodes can only have a greater than branch by definition+ | Null !StringSet + -- | a branch that doesn’t contain anything+ | End deriving (Show, Eq)
Data/Set/TernarySet/Internal.hs view
@@ -2,8 +2,12 @@ -- | TernarySet a is ternary tree. It is commonly used for storing word lists -- like dictionaries.-data TernarySet a = Node !a !(TernarySet a) !(TernarySet a) !(TernarySet a)+data TernarySet a = + -- | A Node has a less than, equal and greater than branch+ Node !a !(TernarySet a) !(TernarySet a) !(TernarySet a)+ -- | Null nodes only have a greater nbranch, by definition | Null !(TernarySet a)+ -- | An empty tree | End deriving (Show, Eq)
TernaryTrees.cabal view
@@ -1,35 +1,33 @@ Name: TernaryTrees-Version: 0.1.3.3+Version: 0.1.3.4 Category: Data Structures 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.- .- 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.- .- From my testing, using the \/usr\/share\/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 over 40% in some cases).- .- New in this version:- .- * (Added the empty function to TernaryMap's export list)- .- * Moved datatype definitions into .Internal modules so that- testing can be performed, without needing to export their definitions in the- main modules.- .- * Checked a lot of the source with HLint 1.6 and made some minor changes based on that ((mostly redundant brackets)).- .- © 2009 by Alex Mason (<http://random.axman6.com/blog/>). BSD3 license.- + 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.+ .+ 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.+ .+ From my testing, using the \/usr\/share\/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 over 40% in some cases).+ .+ New in this version:+ .+ * Moved datatype definitions into .Internal modules so that+ testing can be performed, without needing to export their definitions in the+ main modules.+ .+ * Checked a lot of the source with HLint 1.6 and made some minor changes based on that ((mostly redundant brackets)).+ .+ © 2009 by Alex Mason (<http://random.axman6.com/blog/>). BSD3 license.+ License: BSD3 License-file: LICENSE.txt Author: Alex Mason@@ -40,20 +38,15 @@ Data/Map/TernaryMap.hs Data/Set/TernarySet.hs Data/Set/StringSet.hs- Data/Set/StringSet/Internal.hs- Data/Set/TernarySet/Internal.hs- Data/Map/TernaryMap/Internal.hs+ Data/Set/StringSet/Internal.hs+ Data/Set/TernarySet/Internal.hs+ Data/Map/TernaryMap/Internal.hs Library Build-Depends:- base >= 4.0.0.0, base < 5.0.0.0, binary >= 0.4.4+ base >= 4.0.0.0, base < 5.0.0.0, binary >= 0.5.0.0 Exposed-modules:- Data.Set.TernarySet,- Data.Set.StringSet,- Data.Map.TernaryMap,- Data.Set.TernarySet.Internal,- Data.Set.StringSet.Internal,- Data.Map.TernaryMap.Internal+ Data.Set.TernarySet, Data.Set.StringSet, Data.Map.TernaryMap Executable tdict Main-Is: Main.hs