    {- |
    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 { forall v. TrieSet v -> v
    value :: v
                             , forall v. TrieSet v -> Array Int (TrieSet 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 :: forall v. TrieSet v -> [Int] -> v
    lookupAsc (TrieSet {value :: forall v. TrieSet v -> v
    value=v
    v,next :: forall v. TrieSet v -> Array Int (TrieSet v)
    next=Array Int (TrieSet v)
    n}) =
      (\[Int]
    keys -> case [Int]
    keys of [] -> v
    v
                             (Int
    key:[Int]
    keys') -> TrieSet v -> [Int] -> v
    forall v. TrieSet v -> [Int] -> v
    lookupAsc (Array Int (TrieSet v)
    nArray Int (TrieSet v) -> Int -> TrieSet v
    forall (a :: * -> * -> *) e i.
    (IArray a e, Ix i) =>
    a i e -> i -> e
    !Int
    key) [Int]
    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 :: forall v. (Int, Int) -> ([Int] -> v) -> TrieSet v
    fromBounds (Int
    start,Int
    stop) [Int] -> v
    keysToValue = ([Int] -> [Int]) -> Int -> TrieSet v
    build [Int] -> [Int]
    forall a. a -> a
    id Int
    start where
      build :: ([Int] -> [Int]) -> Int -> TrieSet v
    build [Int] -> [Int]
    keys Int
    low = TrieSet { value :: v
    value = [Int] -> v
    keysToValue ([Int] -> [Int]
    keys [])
                               , next :: Array Int (TrieSet v)
    next = (Int, Int) -> [TrieSet v] -> Array Int (TrieSet v)
    forall (a :: * -> * -> *) e i.
    (IArray a e, Ix i) =>
    (i, i) -> [e] -> a i e
    listArray (Int
    low,Int
    stop)
                                        [([Int] -> [Int]) -> Int -> TrieSet v
    build ([Int] -> [Int]
    keys([Int] -> [Int]) -> ([Int] -> [Int]) -> [Int] -> [Int]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    .(Int
    xInt -> [Int] -> [Int]
    forall a. a -> [a] -> [a]
    :)) (Int -> Int
    forall a. Enum a => a -> a
    succ Int
    x) | Int
    x <- [Int
    low..Int
    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 :: forall v.
    v -> (v -> v -> v) -> (Int, Int) -> (Int -> v) -> TrieSet v
    fromSinglesMerge v
    emptyValue v -> v -> v
    mergeValues (Int, Int)
    bound Int -> v
    keyToValue = TrieSet v
    trieSet where
      trieSet :: TrieSet v
    trieSet = (Int, Int) -> ([Int] -> v) -> TrieSet v
    forall v. (Int, Int) -> ([Int] -> v) -> TrieSet v
    fromBounds (Int, Int)
    bound [Int] -> v
    keysToValue'
      keysToValue' :: [Int] -> v
    keysToValue' [Int]
    keys =
        case [Int]
    keys of
          [] -> v
    emptyValue
          [Int
    key] -> Int -> v
    keyToValue Int
    key
          [Int]
    _ -> v -> v -> v
    mergeValues ([Int] -> v
    keysToValue ([Int] -> [Int]
    forall a. HasCallStack => [a] -> [a]
    init [Int]
    keys)) ([Int] -> v
    keysToValue [[Int] -> Int
    forall a. HasCallStack => [a] -> a
    last [Int]
    keys])
      keysToValue :: [Int] -> v
    keysToValue = TrieSet v -> [Int] -> v
    forall v. TrieSet v -> [Int] -> v
    lookupAsc TrieSet v
    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 :: forall v. ([v] -> v) -> (Int, Int) -> (Int -> v) -> TrieSet v
    fromSinglesSum [v] -> v
    mergeValues (Int, Int)
    bound Int -> v
    keyToValue = TrieSet v
    trieSet where
      trieSet :: TrieSet v
    trieSet = (Int, Int) -> ([Int] -> v) -> TrieSet v
    forall v. (Int, Int) -> ([Int] -> v) -> TrieSet v
    fromBounds (Int, Int)
    bound [Int] -> v
    keysToValue'
      keysToValue' :: [Int] -> v
    keysToValue' = [v] -> v
    mergeValues ([v] -> v) -> ([Int] -> [v]) -> [Int] -> v
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Int -> v) -> [Int] -> [v]
    forall a b. (a -> b) -> [a] -> [b]
    map Int -> v
    keyToValue