diff options
| author | markus <unknown> | 2003-11-11 11:59:21 +0000 |
|---|---|---|
| committer | markus <unknown> | 2003-11-11 11:59:21 +0000 |
| commit | 9b47b4aa128a5cbee74aa99e5494a0b76890ec4a (patch) | |
| tree | 0a870fa527b8fea0c98d6906d90ebac72872504a /src/GF/Data | |
| parent | b5685411125cb5cafe86c7761b0632b83c25f449 (diff) | |
Added a collapse function to Trie
Diffstat (limited to 'src/GF/Data')
| -rw-r--r-- | src/GF/Data/Map.hs | 1 | ||||
| -rw-r--r-- | src/GF/Data/RedBlack.hs | 5 | ||||
| -rw-r--r-- | src/GF/Data/Trie.hs | 9 |
3 files changed, 15 insertions, 0 deletions
diff --git a/src/GF/Data/Map.hs b/src/GF/Data/Map.hs index 1adc0523a..fdaad857c 100644 --- a/src/GF/Data/Map.hs +++ b/src/GF/Data/Map.hs @@ -12,6 +12,7 @@ module Map ( Map, empty, + isEmpty, (!), -- lookup operator. (!+), -- lookupMany operator. (|->), -- insert operator. diff --git a/src/GF/Data/RedBlack.hs b/src/GF/Data/RedBlack.hs index 8a24c07a3..4ee1f92a6 100644 --- a/src/GF/Data/RedBlack.hs +++ b/src/GF/Data/RedBlack.hs @@ -10,6 +10,7 @@ module RedBlack ( emptyTree, + isEmpty, Tree, lookupTree, insertTree, @@ -32,6 +33,10 @@ balance color a x b = T color a x b emptyTree :: Tree key el emptyTree = E +isEmpty :: Tree key el -> Bool +isEmpty (E) = True +isEmpty _ = False + lookupTree :: Ord a => a -> Tree a b -> Maybe b lookupTree _ E = Nothing lookupTree x (T _ a (y,z) b) diff --git a/src/GF/Data/Trie.hs b/src/GF/Data/Trie.hs index 0a0a4472b..724df0761 100644 --- a/src/GF/Data/Trie.hs +++ b/src/GF/Data/Trie.hs @@ -10,6 +10,7 @@ module Trie ( tcompile, + collapse, Trie, trieLookup, decompose, @@ -35,6 +36,14 @@ optimize :: TrieT -> Trie optimize (TrieT (xs,res)) = Trie ([(c,optimize t) | (c,t) <- xs] |->+ empty, res) +collapse :: Trie -> [(String,[(Attr,String)])] +collapse trie = collapse' trie [] + where collapse' (Trie (map,(x:xs))) s = if (isEmpty map) then [(reverse s,(x:xs))] + else (reverse s,(x:xs)): + concat [ collapse' trie (c:s) | (c,trie) <- flatten map] + collapse' (Trie (map,[])) s + = concat [ collapse' trie (c:s) | (c,trie) <- flatten map] + tcompile :: [(String,[(Attr,String)])] -> Trie tcompile xs = optimize $ build xs emptyTrie |