{- |
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 { TrieSet v -> v
value :: 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 :: 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 :: (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 :: forall v. v -> Array Int (TrieSet v) -> TrieSet v
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 :: 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. [a] -> [a]
init [Int]
keys)) ([Int] -> v
keysToValue [[Int] -> Int
forall a. [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 :: ([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