-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | A library that can be used for multiple Ord a => a -> b transformations.
--   
--   A library that can be used as a <tt>case ... of</tt> construction
--   replacement for various cases. Since the 0.2.0.0 version also uses the
--   cuckoo hashtables in the respective module. Since the 0.3.0.0 version
--   the hashing functionality moved to the separate package
--   mmsyn2-hashable.
@package mmsyn2-array
@version 0.3.1.0


-- | A library that can be used as a <tt>case ... of</tt> constuction
--   analogue for the multiple <tt>Ord a =&gt; a -&gt; b</tt>
--   transformations and data representation. Uses <a>Array</a> internally.
--   If you use the module in GHCi, then, please, run the interpreter with
--   the flag <tt>-fobject-code</tt>.
module CaseBi.Arr

-- | The function that can be used instead of the 'case ... of' function
--   <tt> case var of { a1 -&gt; b1 ; a2 -&gt; b2 ; a3 -&gt; b3 ; ... ; an
--   -&gt; bn ; ~z -&gt; defaultValue } </tt> If we follow a lot of
--   teaching materials that explain the workflow of the construction we
--   think that the complexity of it is about <i>O(n)</i> for the
--   transformation of <tt>a</tt> to <tt>b</tt> here. David Feuer
--   (david.feuer (at) gmail.com) said that 'case ... of' is already
--   optimized in GHC. Some benchmarks show that its behaviour tends to be
--   about of <i>O(log n)</i> complexity, the same as the proposed function
--   <a>getBFst'</a>. Nevertheless, the last one shows better performance
--   in some situations, is rather general and can be used for another data
--   representation. Therefore, it can be preferred in some situations.
--   <a>getBFst'</a> uses binary search algorithm and an <a>Array</a> of
--   <tt>(a, b)</tt> as somewhat like a complicated filter or like a
--   special sieve. The array must be sorted in ascending order here for
--   the algorithm to be used correctly. For this you can use the function
--   <a>listArrSortedByFst</a> or the similar ones. If you would like to
--   use them both, please, consider usage of the <a>getBFstLSorted'</a> or
--   <a>getBFstL'</a> instead. The function <a>getBFst''</a> is used
--   internally in the <a>getBFst'</a> that is recommended to be used in
--   most cases. Nevertheless, it is provided here if you have precomputed
--   the first two arguments or at least some parts of them so that you can
--   reduce the needed amount of computations in the <a>getBFst'</a>.
getBFst'' :: (Ord a, Ix i) => (# Int, (a, b) #) -> (# Int, (a, b) #) -> Array i (a, b) -> b -> a -> b

-- | A generally written without extending variant of the <a>getBFst''</a>.
getBFst' :: Ord a => (b, Array Int (a, b)) -> a -> b

-- | Sorts the list of pairs by the first element in the tuples, then
--   transforms them into an immutable array. Can be used only if the list
--   contains no more than 2^31 - 1 elements though this is not checked, it
--   is up to user to check this constraint before or provide its
--   correctness by design.
listArrSortedByFst :: Ord a => [(a, b)] -> Array Int (a, b)

-- | If the list argument is sorted in the ascending order by the first
--   element in every tuple, then to reduce computations instead of <tt>
--   \def xs x -&gt; getBFst' (def, listArray (0,length xs - 1) xs) x </tt>
--   you can use this function.
getBFstLSorted' :: Ord a => b -> [(a, b)] -> a -> b

-- | If it is unknown whether the list argument is sorted in the ascending
--   order by the first element in every tuple (or, definitely, it is not,
--   speaking generally), then instead of <tt> \def xs x -&gt; getBFst'
--   (def, listArray (0,length xs - 1) . sortBy (comparing fst) $ xs) x
--   </tt> you can use this function.
getBFstL' :: Ord a => b -> [(a, b)] -> a -> b