-----------------------------------------------------------------------------
-- |
-- 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