    -----------------------------------------------------------------------------
    -- |
    -- 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 :: forall a. (Bounded a, Integral a) => (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 :: forall a. (Bounded a, Integral a) => (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 :: forall a. (Bounded a, Integral a) => (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 :: forall a. Integral a => (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 :: forall a. Integral a => (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 :: forall a. Integral a => (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