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

    module Numeric.Search.Integer (
            -- * One-dimensional searches
            search, searchFrom, searchTo,
            -- * Two-dimensional searches
            search2) where

    import Data.Maybe (fromMaybe)

    -- | /O(log(abs n))/.
    -- Search the integers.
    --
    -- If @p@ is an upward-closed predicate, @search p@ returns the least
    -- @n@ satisfying @p@.  If no such @n@ exists, either because no integer
    -- satisfies @p@ or all do, @search p@ does not terminate.
    --
    -- For example, the following function computes discrete logarithms (base 2):
    --
    -- > discreteLog :: Integer -> Integer
    -- > discreteLog n = search (\ k -> 2^k <= n)
    --
    search :: (Integer -> Bool) -> Integer
    search :: (Integer -> Bool) -> Integer
    search Integer -> Bool
    p = Integer -> Maybe Integer -> Integer
    forall a. a -> Maybe a -> a
    fromMaybe ((Integer -> Bool) -> Integer -> Integer
    searchFrom Integer -> Bool
    p Integer
    1) ((Integer -> Bool) -> Integer -> Maybe Integer
    searchTo Integer -> Bool
    p Integer
    0)

    -- | /O(log(n-l))/.
    -- Search the integers from a given lower bound.
    --
    -- If @p@ is an upward-closed predicate,
    -- @searchFrom p l = 'search' (\\ i -> i >= l && p i)@.
    -- If no such @n@ exists (because no integer satisfies @p@),
    -- @searchFrom p@ does not terminate.
    searchFrom :: (Integer -> Bool) -> Integer -> Integer
    searchFrom :: (Integer -> Bool) -> Integer -> Integer
    searchFrom Integer -> Bool
    p = Integer -> Integer -> Integer
    search_from Integer
    1
      where search_from :: Integer -> Integer -> Integer
    search_from Integer
    step Integer
    l
              | Integer -> Bool
    p Integer
    l' = (Integer -> Bool) -> Integer -> Integer -> Integer
    searchIntegerRange Integer -> Bool
    p Integer
    l (Integer
    l'Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    -Integer
    1)
              | Bool
    otherwise = Integer -> Integer -> Integer
    search_from (Integer
    2Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    *Integer
    step) (Integer
    l'Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    +Integer
    1)
              where l' :: Integer
    l' = Integer
    l Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    + Integer
    step

    -- | /O(log(h-n))/.
    -- Search the integers up to a given upper bound.
    --
    -- If @p@ is an upward-closed predicate, @searchTo p h == 'Just' n@
    -- if and only if @n@ is the least number @n <= h@ satisfying @p@.
    searchTo :: (Integer -> Bool) -> Integer -> Maybe Integer
    searchTo :: (Integer -> Bool) -> Integer -> Maybe Integer
    searchTo Integer -> Bool
    p Integer
    h0
      | Integer -> Bool
    p Integer
    h0 = Integer -> Maybe Integer
    forall a. a -> Maybe a
    Just (Integer -> Integer -> Integer
    search_to Integer
    1 Integer
    h0)
      | Bool
    otherwise = Maybe Integer
    forall a. Maybe a
    Nothing
      where search_to :: Integer -> Integer -> Integer
    search_to Integer
    step Integer
    h                -- @step >= 1 && p h@
              | Integer -> Bool
    p Integer
    h' = Integer -> Integer -> Integer
    search_to (Integer
    2Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    *Integer
    step) Integer
    h'
              | Bool
    otherwise = (Integer -> Bool) -> Integer -> Integer -> Integer
    searchSafeRange Integer -> Bool
    p (Integer
    h'Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    +Integer
    1) Integer
    h
              where h' :: Integer
    h' = Integer
    h Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    - Integer
    step

    -- | /O(m log(n\/m))/.
    -- Two-dimensional search, using an algorithm due described in
    --
    -- * Richard Bird, /Saddleback search: a lesson in algorithm design/,
    --   in /Mathematics of Program Construction/ 2006,
    --   Springer LNCS vol. 4014, pp82-89.
    --
    -- If @p@ is closed upwards in each argument on non-negative integers,
    -- @search2 p@ returns the minimal non-negative pairs satisfying @p@,
    -- listed in order of increasing x-coordinate.
    --
    -- /m/ and /n/ refer to the smaller and larger dimensions of the
    -- rectangle containing the boundary.
    --
    -- For example,
    --
    -- > search2 (\ x y -> x^2 + y^2 >= 25)  ==  [(0,5),(3,4),(4,3),(5,0)]
    --
    search2 :: (Integer -> Integer -> Bool) -> [(Integer,Integer)]
    search2 :: (Integer -> Integer -> Bool) -> [(Integer, Integer)]
    search2 Integer -> Integer -> Bool
    p = (Integer -> Integer -> Bool)
    -> Integer
    -> Integer
    -> Integer
    -> Integer
    -> [(Integer, Integer)]
    -> [(Integer, Integer)]
    search2Rect Integer -> Integer -> Bool
    p Integer
    0 Integer
    0 Integer
    hx Integer
    hy []
      where
        hx :: Integer
    hx = (Integer -> Bool) -> Integer -> Integer
    searchFrom (\ Integer
    x -> Integer -> Integer -> Bool
    p Integer
    x Integer
    0) Integer
    0
        hy :: Integer
    hy = (Integer -> Bool) -> Integer -> Integer
    searchFrom (\ Integer
    y -> Integer -> Integer -> Bool
    p Integer
    0 Integer
    y) Integer
    0

    search2Rect :: (Integer -> Integer -> Bool) ->
            Integer -> Integer -> Integer -> Integer ->
            [(Integer,Integer)] -> [(Integer,Integer)]
    search2Rect :: (Integer -> Integer -> Bool)
    -> Integer
    -> Integer
    -> Integer
    -> Integer
    -> [(Integer, Integer)]
    -> [(Integer, Integer)]
    search2Rect Integer -> Integer -> Bool
    p Integer
    lx Integer
    ly Integer
    hx Integer
    hy
      | Integer
    lx Integer -> Integer -> Bool
    forall a. Ord a => a -> a -> Bool
    > Integer
    hx Bool -> Bool -> Bool
    || Integer
    ly Integer -> Integer -> Bool
    forall a. Ord a => a -> a -> Bool
    > Integer
    hy = [(Integer, Integer)] -> [(Integer, Integer)]
    forall a. a -> a
    id
      | Integer
    lx Integer -> Integer -> Bool
    forall a. Eq a => a -> a -> Bool
    == Integer
    hx Bool -> Bool -> Bool
    && Integer
    ly Integer -> Integer -> Bool
    forall a. Eq a => a -> a -> Bool
    == Integer
    hy = if Integer -> Integer -> Bool
    p Integer
    lx Integer
    ly then ((Integer
    lx, Integer
    ly) (Integer, Integer) -> [(Integer, Integer)] -> [(Integer, Integer)]
    forall a. a -> [a] -> [a]
    :) else [(Integer, Integer)] -> [(Integer, Integer)]
    forall a. a -> a
    id
      | Integer
    hxInteger -> Integer -> Integer
    forall a. Num a => a -> a -> a
    -Integer
    lx Integer -> Integer -> Bool
    forall a. Ord a => a -> a -> Bool
    > Integer
    hyInteger -> Integer -> Integer
    forall a. Num a => a -> a -> a
    -Integer
    ly =
            let        mx :: Integer
    mx = (Integer
    lxInteger -> Integer -> Integer
    forall a. Num a => a -> a -> a
    +Integer
    hx) Integer -> Integer -> Integer
    forall a. Integral a => a -> a -> a
    `div` Integer
    2
                       my :: Integer
    my = (Integer -> Bool) -> Integer -> Integer -> Integer
    searchIntegerRange (\ Integer
    y -> Integer -> Integer -> Bool
    p Integer
    mx Integer
    y) Integer
    ly Integer
    hy
            in (Integer -> Integer -> Bool)
    -> Integer
    -> Integer
    -> Integer
    -> Integer
    -> [(Integer, Integer)]
    -> [(Integer, Integer)]
    search2Rect Integer -> Integer -> Bool
    p Integer
    lx Integer
    my Integer
    mx Integer
    hy ([(Integer, Integer)] -> [(Integer, Integer)])
    -> ([(Integer, Integer)] -> [(Integer, Integer)])
    -> [(Integer, Integer)]
    -> [(Integer, Integer)]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Integer -> Integer -> Bool)
    -> Integer
    -> Integer
    -> Integer
    -> Integer
    -> [(Integer, Integer)]
    -> [(Integer, Integer)]
    search2Rect Integer -> Integer -> Bool
    p (Integer
    mxInteger -> Integer -> Integer
    forall a. Num a => a -> a -> a
    +Integer
    1) Integer
    ly Integer
    hx (Integer
    myInteger -> Integer -> Integer
    forall a. Num a => a -> a -> a
    -Integer
    1)
      | Bool
    otherwise =
            let        mx :: Integer
    mx = (Integer -> Bool) -> Integer -> Integer -> Integer
    searchIntegerRange (\ Integer
    x -> Integer -> Integer -> Bool
    p Integer
    x Integer
    my) Integer
    lx Integer
    hx
                       my :: Integer
    my = (Integer
    lyInteger -> Integer -> Integer
    forall a. Num a => a -> a -> a
    +Integer
    hy) Integer -> Integer -> Integer
    forall a. Integral a => a -> a -> a
    `div` Integer
    2
            in (Integer -> Integer -> Bool)
    -> Integer
    -> Integer
    -> Integer
    -> Integer
    -> [(Integer, Integer)]
    -> [(Integer, Integer)]
    search2Rect Integer -> Integer -> Bool
    p Integer
    lx (Integer
    myInteger -> Integer -> Integer
    forall a. Num a => a -> a -> a
    +Integer
    1) (Integer
    mxInteger -> Integer -> Integer
    forall a. Num a => a -> a -> a
    -Integer
    1) Integer
    hy ([(Integer, Integer)] -> [(Integer, Integer)])
    -> ([(Integer, Integer)] -> [(Integer, Integer)])
    -> [(Integer, Integer)]
    -> [(Integer, Integer)]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Integer -> Integer -> Bool)
    -> Integer
    -> Integer
    -> Integer
    -> Integer
    -> [(Integer, Integer)]
    -> [(Integer, Integer)]
    search2Rect Integer -> Integer -> Bool
    p Integer
    mx Integer
    ly Integer
    hx Integer
    my

    -- | Search a bounded interval of integers.
    --
    -- If @p@ is an upward-closed predicate,
    --
    -- > searchIntegerRange p l h = 'search' (\ i -> i >= l && p i || i > h)
    --
    -- Cost: /O(log(h-l))/ calls to @p@.
    searchIntegerRange :: (Integer -> Bool) -> Integer -> Integer -> Integer
    searchIntegerRange :: (Integer -> Bool) -> Integer -> Integer -> Integer
    searchIntegerRange Integer -> Bool
    p Integer
    l Integer
    h
      | Integer
    h Integer -> Integer -> Bool
    forall a. Ord a => a -> a -> Bool
    < Integer
    l = Integer
    hInteger -> Integer -> Integer
    forall a. Num a => a -> a -> a
    +Integer
    1
      | Integer -> Bool
    p Integer
    m = (Integer -> Bool) -> Integer -> Integer -> Integer
    searchIntegerRange Integer -> Bool
    p Integer
    l (Integer
    mInteger -> Integer -> Integer
    forall a. Num a => a -> a -> a
    -Integer
    1)
      | Bool
    otherwise = (Integer -> Bool) -> Integer -> Integer -> Integer
    searchIntegerRange Integer -> Bool
    p (Integer
    mInteger -> Integer -> Integer
    forall a. Num a => a -> a -> a
    +Integer
    1) Integer
    h
      where m :: Integer
    m = (Integer
    lInteger -> Integer -> Integer
    forall a. Num a => a -> a -> a
    +Integer
    h) Integer -> Integer -> Integer
    forall a. Integral a => a -> a -> a
    `div` Integer
    2

    -- | Like 'search', but assuming @l <= h && p h@.
    searchSafeRange :: (Integer -> Bool) -> Integer -> Integer -> Integer
    searchSafeRange :: (Integer -> Bool) -> Integer -> Integer -> Integer
    searchSafeRange Integer -> Bool
    p Integer
    l Integer
    h
      | Integer
    l Integer -> Integer -> Bool
    forall a. Eq a => a -> a -> Bool
    == Integer
    h = Integer
    l
      | Integer -> Bool
    p Integer
    m = (Integer -> Bool) -> Integer -> Integer -> Integer
    searchSafeRange Integer -> Bool
    p Integer
    l Integer
    m
      | Bool
    otherwise = (Integer -> Bool) -> Integer -> Integer -> Integer
    searchSafeRange Integer -> Bool
    p (Integer
    mInteger -> Integer -> Integer
    forall a. Num a => a -> a -> a
    +Integer
    1) Integer
    h
      where m :: Integer
    m = (Integer
    l Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    + Integer
    h) Integer -> Integer -> Integer
    forall a. Integral a => a -> a -> a
    `div` Integer
    2        -- If l < h, then l <= m < h