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