{- |
This creates a lazy Trie based on a finite range of Ints and is used to
memorize a function over the subsets of this range.

To create a Trie you need two supply 2 things
  * Range of keys to bound
  * A function or functions used to construct the value for a subset of keys

The Trie uses the Array type internally.
-}
module Text.Regex.TDFA.IntArrTrieSet where

{- By Chris Kuklewicz, 2007. BSD License, see the LICENSE file. -}

import Data.Array.IArray(Array,(!),listArray)

data TrieSet v = TrieSet { value :: v
                         , next :: Array Int (TrieSet v) }

-- | This is the accessor for the Trie. The list of keys should be
-- sorted.
lookupAsc :: TrieSet v -> [Int] -> v
lookupAsc (TrieSet {value=v,next=n}) =
  (\keys -> case keys of [] -> v
                         (key:keys') -> lookupAsc (n!key) keys')

-- | This is a Trie constructor for a complete range of keys.
fromBounds :: (Int,Int)     -- ^ (lower,upper) range of keys, lower<=upper
           -> ([Int] -> v)  -- ^ Function from list of keys to its value.
                            --   It must work for distinct ascending lists.
           -> TrieSet v     -- ^ The constructed Trie
fromBounds (start,stop) keysToValue = build id start where
  build keys low = TrieSet { value = keysToValue (keys [])
                           , next = listArray (low,stop)
                                    [build (keys.(x:)) (succ x) | x <- [low..stop] ] }

-- | This is a Trie constructor for a complete range of keys that uses
-- a function from single values and a merge operation on values to
-- fill the Trie.
fromSinglesMerge :: v          -- ^ value for (lookupAsc trie [])
                 -> (v->v->v)  -- ^ merge operation on values
                 -> (Int,Int)  -- ^ (lower,upper) range of keys, lower<=upper
                 -> (Int->v)   -- ^ Function from a single key to its value
                 -> TrieSet v  -- ^ The constructed Trie
fromSinglesMerge emptyValue mergeValues bound keyToValue = trieSet where
  trieSet = fromBounds bound keysToValue'
  keysToValue' keys =
    case keys of
      [] -> emptyValue
      [key] -> keyToValue key
      _ -> mergeValues (keysToValue (init keys)) (keysToValue [last keys])
  keysToValue = lookupAsc trieSet

-- | This is a Trie constructor for a complete range of keys that uses
-- a function from single values and a sum operation of values to fill
-- the Trie.
fromSinglesSum :: ([v]->v)   -- ^ summation operation for values
               -> (Int,Int)  -- ^ (lower,upper) range of keys, lower <= upper
               -> (Int->v)   -- ^ Function from a single key to its value
               -> TrieSet v  -- ^ The constructed Trie
fromSinglesSum mergeValues bound keyToValue = trieSet where
  trieSet = fromBounds bound keysToValue'
  keysToValue' = mergeValues . map keyToValue