1{- | 2This creates a lazy Trie based on a finite range of Ints and is used to 3memorize a function over the subsets of this range. 4 5To create a Trie you need two supply 2 things 6 * Range of keys to bound 7 * A function or functions used to construct the value for a subset of keys 8 9The Trie uses the Array type internally. 10-} 11module Text.Regex.TDFA.IntArrTrieSet where 12 13{- By Chris Kuklewicz, 2007. BSD License, see the LICENSE file. -} 14 15import Data.Array.IArray(Array,(!),listArray) 16 17data TrieSet v = TrieSet { value :: v 18 , next :: Array Int (TrieSet v) } 19 20-- | This is the accessor for the Trie. The list of keys should be 21-- sorted. 22lookupAsc :: TrieSet v -> [Int] -> v 23lookupAsc (TrieSet {value=v,next=n}) = 24 (\keys -> case keys of [] -> v 25 (key:keys') -> lookupAsc (n!key) keys') 26 27-- | This is a Trie constructor for a complete range of keys. 28fromBounds :: (Int,Int) -- ^ (lower,upper) range of keys, lower<=upper 29 -> ([Int] -> v) -- ^ Function from list of keys to its value. 30 -- It must work for distinct ascending lists. 31 -> TrieSet v -- ^ The constructed Trie 32fromBounds (start,stop) keysToValue = build id start where 33 build keys low = TrieSet { value = keysToValue (keys []) 34 , next = listArray (low,stop) 35 [build (keys.(x:)) (succ x) | x <- [low..stop] ] } 36 37-- | This is a Trie constructor for a complete range of keys that uses 38-- a function from single values and a merge operation on values to 39-- fill the Trie. 40fromSinglesMerge :: v -- ^ value for (lookupAsc trie []) 41 -> (v->v->v) -- ^ merge operation on values 42 -> (Int,Int) -- ^ (lower,upper) range of keys, lower<=upper 43 -> (Int->v) -- ^ Function from a single key to its value 44 -> TrieSet v -- ^ The constructed Trie 45fromSinglesMerge emptyValue mergeValues bound keyToValue = trieSet where 46 trieSet = fromBounds bound keysToValue' 47 keysToValue' keys = 48 case keys of 49 [] -> emptyValue 50 [key] -> keyToValue key 51 _ -> mergeValues (keysToValue (init keys)) (keysToValue [last keys]) 52 keysToValue = lookupAsc trieSet 53 54-- | This is a Trie constructor for a complete range of keys that uses 55-- a function from single values and a sum operation of values to fill 56-- the Trie. 57fromSinglesSum :: ([v]->v) -- ^ summation operation for values 58 -> (Int,Int) -- ^ (lower,upper) range of keys, lower <= upper 59 -> (Int->v) -- ^ Function from a single key to its value 60 -> TrieSet v -- ^ The constructed Trie 61fromSinglesSum mergeValues bound keyToValue = trieSet where 62 trieSet = fromBounds bound keysToValue' 63 keysToValue' = mergeValues . map keyToValue 64