-----------------------------------------------------------------------------
-- |
-- Module      :  Numeric.Search.Bounded
-- Copyright   :  (c) Ross Paterson 2008
-- License     :  BSD-style
-- Maintainer  :  ross@soi.city.ac.uk
-- Stability   :  experimental
-- Portability :  portable
--
-- Searching unbounded intervals within bounded integral types for the
-- boundary of an upward-closed set, using a combination of exponential
-- and binary search.
--
-----------------------------------------------------------------------------
--
module Numeric.Search.Bounded (search, searchFrom, searchTo) where

import Numeric.Search.Range

-- | /O(log(abs n))/.
-- Search a bounded integral type.
--
-- If @p@ is an upward-closed predicate, @search p@ returns
-- @Just n@ if and only if @n@ is the least such satisfying @p@.
search :: (Bounded a, Integral a) => (a -> Bool) -> Maybe a
search :: (a -> Bool) -> Maybe a
search a -> Bool
p
  | a -> Bool
p a
0 = a -> Maybe a
forall a. a -> Maybe a
Just ((a -> Bool) -> a -> a -> a
forall a. Integral a => (a -> Bool) -> a -> a -> a
searchDown a -> Bool
p a
forall a. Bounded a => a
minBound a
0)
  | Bool
otherwise = (a -> Bool) -> a -> a -> Maybe a
forall a. Integral a => (a -> Bool) -> a -> a -> Maybe a
searchUp a -> Bool
p a
1 a
forall a. Bounded a => a
maxBound

-- | /O(log(abs n))/.
-- Search the part of a bounded integral type from a given point.
--
-- If @p@ is an upward-closed predicate, @searchFrom p l@ returns
-- @Just n@ if and only if @n@ is the least @n >= l@ satisfying @p@.
searchFrom :: (Bounded a, Integral a) => (a -> Bool) -> a -> Maybe a
searchFrom :: (a -> Bool) -> a -> Maybe a
searchFrom a -> Bool
p a
l
  | a
l a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
0 Bool -> Bool -> Bool
&& a -> Bool
p a
0 = a -> Maybe a
forall a. a -> Maybe a
Just ((a -> Bool) -> a -> a -> a
forall a. Integral a => (a -> Bool) -> a -> a -> a
searchDown a -> Bool
p a
l a
0)
  | Bool
otherwise = (a -> Bool) -> a -> a -> Maybe a
forall a. Integral a => (a -> Bool) -> a -> a -> Maybe a
searchUp a -> Bool
p (a -> a -> a
forall a. Ord a => a -> a -> a
max a
1 a
l) a
forall a. Bounded a => a
maxBound

-- | /O(log(abs n))/.
-- Search the part of a bounded integral type up to a given point.
--
-- If @p@ is an upward-closed predicate, @searchTo p h@ returns
-- @Just n@ if and only if @n@ is the least @n <= h@ satisfying @p@.
searchTo :: (Bounded a, Integral a) => (a -> Bool) -> a -> Maybe a
searchTo :: (a -> Bool) -> a -> Maybe a
searchTo a -> Bool
p a
h
  | 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
searchDown a -> Bool
p a
forall a. Bounded a => a
minBound a
h')
  | Bool
otherwise = (a -> Bool) -> a -> a -> Maybe a
forall a. Integral a => (a -> Bool) -> a -> a -> Maybe a
searchUp a -> Bool
p a
1 a
h
  where h' :: a
h' = a -> a -> a
forall a. Ord a => a -> a -> a
min a
0 a
h

-- @h <= 0 && p h@
searchDown :: (Integral a) => (a -> Bool) -> a -> a -> a
searchDown :: (a -> Bool) -> a -> a -> a
searchDown a -> Bool
p a
l a
h
  | a
l a -> a -> a
forall a. Integral a => a -> a -> a
`quot` a
2 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
>= a
h = (a -> Bool) -> a -> a -> a
forall a. Integral a => (a -> Bool) -> a -> a -> a
searchSafeRange a -> Bool
p a
l a
h
  | a -> Bool
p a
h' = (a -> Bool) -> a -> a -> a
forall a. Integral a => (a -> Bool) -> a -> a -> a
searchDown a -> Bool
p a
l a
h'
  | Bool
otherwise = (a -> Bool) -> a -> a -> a
forall a. Integral a => (a -> Bool) -> a -> a -> a
searchSafeRange a -> Bool
p (a
h'a -> a -> a
forall a. Num a => a -> a -> a
+a
1) a
h
  where h' :: a
h' = a
ha -> a -> a
forall a. Num a => a -> a -> a
*a
2 a -> a -> a
forall a. Num a => a -> a -> a
- a
1

-- @0 < l@
searchUp :: (Integral a) => (a -> Bool) -> a -> a -> Maybe a
searchUp :: (a -> Bool) -> a -> a -> Maybe a
searchUp a -> Bool
p a
l a
h
  | a
h a -> a -> a
forall a. Integral a => a -> a -> a
`div` a
2 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
l = (a -> Bool) -> a -> a -> Maybe a
forall a. Integral a => (a -> Bool) -> a -> a -> Maybe a
searchFromTo a -> Bool
p a
l a
h
  | a -> Bool
p a
l' = 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
l')
  | Bool
otherwise = (a -> Bool) -> a -> a -> Maybe a
forall a. Integral a => (a -> Bool) -> a -> a -> Maybe a
searchUp a -> Bool
p (a
l'a -> a -> a
forall a. Num a => a -> a -> a
+a
1) a
h
  where l' :: a
l' = a
la -> a -> a
forall a. Num a => a -> a -> a
*a
2 a -> a -> a
forall a. Num a => a -> a -> a
+ a
1

-- | Like 'search', 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