1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74
|
-----------------------------------------------------------------------------
-- |
-- 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 p
| p 0 = Just (searchDown p minBound 0)
| otherwise = searchUp p 1 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 p l
| l <= 0 && p 0 = Just (searchDown p l 0)
| otherwise = searchUp p (max 1 l) 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 p h
| p h' = Just (searchDown p minBound h')
| otherwise = searchUp p 1 h
where h' = min 0 h
-- @h <= 0 && p h@
searchDown :: (Integral a) => (a -> Bool) -> a -> a -> a
searchDown p l h
| l `quot` 2 >= h = searchSafeRange p l h
| p h' = searchDown p l h'
| otherwise = searchSafeRange p (h'+1) h
where h' = h*2 - 1
-- @0 < l@
searchUp :: (Integral a) => (a -> Bool) -> a -> a -> Maybe a
searchUp p l h
| h `div` 2 <= l = searchFromTo p l h
| p l' = Just (searchSafeRange p l l')
| otherwise = searchUp p (l'+1) h
where l' = l*2 + 1
-- | Like 'search', but assuming @l <= h && p h@.
searchSafeRange :: Integral a => (a -> Bool) -> a -> a -> a
searchSafeRange p l h
| l == h = l
| p m = searchSafeRange p l m
| otherwise = searchSafeRange p (m+1) h
-- Stay within @min 0 l .. max 0 h@ to avoid overflow.
where m = l `div` 2 + h `div` 2 -- If l < h, then l <= m < h
|