-----------------------------------------------------------------------------
-- |
-- Module      :  Numeric.Search.Range
-- Copyright   :  (c) Ross Paterson 2008
-- License     :  BSD-style
-- Maintainer  :  ross@soi.city.ac.uk
-- Stability   :  experimental
-- Portability :  portable
--
-- Binary search of a bounded interval of an integral type for the
-- boundary of an upward-closed set, using a combination of exponential
-- and binary search.
--
-----------------------------------------------------------------------------

module Numeric.Search.Range (searchFromTo) where

-- | /O(log(h-l))/.
-- Search a bounded interval of some integral type.
--
-- If @p@ is an upward-closed predicate, @searchFromTo p l h == Just n@
-- if and only if @n@ is the least number @l <= n <= h@ satisfying @p@.
--
-- For example, the following function determines the first index (if any)
-- at which a value occurs in an ordered array:
--
-- > searchArray :: Ord a => a -> Array Int a -> Maybe Int
-- > searchArray x array = do
-- >   let (lo, hi) = bounds array
-- >   k <- searchFromTo (\ i -> array!i >= x) lo hi
-- >   guard (array!k == x)
-- >   return k
--
searchFromTo :: Integral a => (a -> Bool) -> a -> a -> Maybe a
searchFromTo :: (a -> Bool) -> a -> a -> Maybe a
searchFromTo a -> Bool
p a
l a
h
  | a
l a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
h = Maybe a
forall a. Maybe a
Nothing
  | a -> Bool
p a
h = a -> Maybe a
forall a. a -> Maybe a
Just ((a -> Bool) -> a -> a -> a
forall a. Integral a => (a -> Bool) -> a -> a -> a
searchSafeRange a -> Bool
p a
l a
h)
  | Bool
otherwise = Maybe a
forall a. Maybe a
Nothing

-- | Like 'searchFromTo', but assuming @l <= h && p h@.
searchSafeRange :: Integral a => (a -> Bool) -> a -> a -> a
searchSafeRange :: (a -> Bool) -> a -> a -> a
searchSafeRange a -> Bool
p a
l a
h
  | a
l a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
h = a
l
  | a -> Bool
p a
m = (a -> Bool) -> a -> a -> a
forall a. Integral a => (a -> Bool) -> a -> a -> a
searchSafeRange a -> Bool
p a
l a
m
  | Bool
otherwise = (a -> Bool) -> a -> a -> a
forall a. Integral a => (a -> Bool) -> a -> a -> a
searchSafeRange a -> Bool
p (a
ma -> a -> a
forall a. Num a => a -> a -> a
+a
1) a
h
  -- Stay within @min 0 l .. max 0 h@ to avoid overflow.
  where m :: a
m = a
l a -> a -> a
forall a. Integral a => a -> a -> a
`div` a
2 a -> a -> a
forall a. Num a => a -> a -> a
+ a
h a -> a -> a
forall a. Integral a => a -> a -> a
`div` a
2	-- If l < h, then l <= m < h