{-
	Copyright (C) 2011 Dr. Alistair Ward

	This program is free software: you can redistribute it and/or modify
	it under the terms of the GNU General Public License as published by
	the Free Software Foundation, either version 3 of the License, or
	(at your option) any later version.

	This program is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU General Public License for more details.

	You should have received a copy of the GNU General Public License
	along with this program.  If not, see <http://www.gnu.org/licenses/>.
-}
{- |
 [@AUTHOR@]	Dr. Alistair Ward

 [@DESCRIPTION@]

	* Describes a bounded set of, typically integral, quantities.

	* Operations have been defined, on the list of /consecutive/ quantities delimited by these endpoints.

	* The point is that if the list is composed from /consecutive/ quantities, the intermediate values can be inferred, rather than physically represented.

 [@CAVEATS@]

	* The API was driven top-down by its caller's requirements, rather than a bottom-up attempt to provide a complete interface.
	consequently there may be omissions from the view point of future callers.

	* Thought similar to the mathematical concept of an /interval/, the latter technically relates to /real/ numbers; <https://en.wikipedia.org/wiki/Interval_%28mathematics%29>.

	* No account has been made for /semi-closed/ or /open/ intervals.
-}

module Factory.Data.Interval(
-- * Types
-- ** Type-synonyms
	Interval,
-- * Constants
	closedUnitInterval,
	mkBounded,
-- * Functions
--	divideAndConquer,
	elem',
--	getLength,
	normalise,
	product',
	shift,
	splitAt',
	toList,
-- ** Accessors
	getMinBound,
	getMaxBound,
-- ** Constructor
	precisely,
-- ** Predicates
	isReversed
) where

import			Control.Arrow((***), (&&&))
import qualified	Control.Parallel.Strategies
import qualified	Data.Monoid
import qualified	Data.Ratio
import qualified	Data.Tuple
import qualified	ToolShed.Data.Pair

-- | Defines a closed (inclusive) interval of consecutive values.
type Interval endPoint	= (endPoint, endPoint)

-- | Accessor.
{-# INLINE getMinBound #-}
getMinBound :: Interval endPoint -> endPoint
getMinBound :: Interval endPoint -> endPoint
getMinBound	= Interval endPoint -> endPoint
forall a b. (a, b) -> a
fst

-- | Accessor.
{-# INLINE getMaxBound #-}
getMaxBound :: Interval endPoint -> endPoint
getMaxBound :: Interval endPoint -> endPoint
getMaxBound	= Interval endPoint -> endPoint
forall a b. (a, b) -> b
snd

-- | Construct the /unsigned closed unit-interval/; <https://en.wikipedia.org/wiki/Unit_interval>.
closedUnitInterval :: Num n => Interval n
closedUnitInterval :: Interval n
closedUnitInterval	= (n
0, n
1)

-- | Construct an /interval/ from a bounded type.
mkBounded :: Bounded endPoint => Interval endPoint
mkBounded :: Interval endPoint
mkBounded	= (endPoint
forall a. Bounded a => a
minBound, endPoint
forall a. Bounded a => a
maxBound)

-- | Construct an /interval/ from a single value.
precisely :: endPoint -> Interval endPoint
precisely :: endPoint -> Interval endPoint
precisely	= endPoint -> endPoint
forall a. a -> a
id (endPoint -> endPoint)
-> (endPoint -> endPoint) -> endPoint -> Interval endPoint
forall (a :: * -> * -> *) b c c'.
Arrow a =>
a b c -> a b c' -> a b (c, c')
&&& endPoint -> endPoint
forall a. a -> a
id

-- | Shift of both /end-points/ of the /interval/ by the specified amount.
shift :: Num endPoint
	=> endPoint		-- ^ The magnitude of the require shift.
	-> Interval endPoint	-- ^ The interval to be shifted.
	-> Interval endPoint
shift :: endPoint -> Interval endPoint -> Interval endPoint
shift endPoint
i	= (endPoint -> endPoint) -> Interval endPoint -> Interval endPoint
forall a b. (a -> b) -> (a, a) -> (b, b)
ToolShed.Data.Pair.mirror (endPoint -> endPoint -> endPoint
forall a. Num a => a -> a -> a
+ endPoint
i)

-- | True if the specified value is within the inclusive bounds of the /interval/.
elem' :: Ord endPoint => endPoint -> Interval endPoint -> Bool
elem' :: endPoint -> Interval endPoint -> Bool
elem' endPoint
x	= (Bool -> Bool -> Bool) -> (Bool, Bool) -> Bool
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry Bool -> Bool -> Bool
(&&) ((Bool, Bool) -> Bool)
-> (Interval endPoint -> (Bool, Bool)) -> Interval endPoint -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((endPoint -> endPoint -> Bool
forall a. Ord a => a -> a -> Bool
<= endPoint
x) (endPoint -> Bool)
-> (endPoint -> Bool) -> Interval endPoint -> (Bool, Bool)
forall (a :: * -> * -> *) b c b' c'.
Arrow a =>
a b c -> a b' c' -> a (b, b') (c, c')
*** (endPoint
x endPoint -> endPoint -> Bool
forall a. Ord a => a -> a -> Bool
<=))

-- | True if 'getMinBound' exceeds 'getMaxBound' extent.
isReversed :: Ord endPoint => Interval endPoint -> Bool
isReversed :: Interval endPoint -> Bool
isReversed	= (endPoint -> endPoint -> Bool) -> Interval endPoint -> Bool
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry endPoint -> endPoint -> Bool
forall a. Ord a => a -> a -> Bool
(>)

-- | Swap the /end-points/ where they were originally reversed, but otherwise do nothing.
normalise :: Ord endPoint => Interval endPoint -> Interval endPoint
normalise :: Interval endPoint -> Interval endPoint
normalise Interval endPoint
b
	| Interval endPoint -> Bool
forall endPoint. Ord endPoint => Interval endPoint -> Bool
isReversed Interval endPoint
b	= Interval endPoint -> Interval endPoint
forall a b. (a, b) -> (b, a)
Data.Tuple.swap Interval endPoint
b
	| Bool
otherwise	= Interval endPoint
b

-- | Bisect the /interval/ at the specified /end-point/; which should be between the two existing /end-points/.
splitAt' :: (
	Enum	endPoint,
	Ord	endPoint,
	Show	endPoint
 ) => endPoint -> Interval endPoint -> (Interval endPoint, Interval endPoint)
splitAt' :: endPoint
-> Interval endPoint -> (Interval endPoint, Interval endPoint)
splitAt' endPoint
i interval :: Interval endPoint
interval@(endPoint
l, endPoint
r)
	| ((endPoint -> Bool) -> Bool) -> [endPoint -> Bool] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any ((endPoint -> Bool) -> endPoint -> Bool
forall a b. (a -> b) -> a -> b
$ endPoint
i) [(endPoint -> endPoint -> Bool
forall a. Ord a => a -> a -> Bool
< endPoint
l), (endPoint -> endPoint -> Bool
forall a. Ord a => a -> a -> Bool
>= endPoint
r)]	= [Char] -> (Interval endPoint, Interval endPoint)
forall a. HasCallStack => [Char] -> a
error ([Char] -> (Interval endPoint, Interval endPoint))
-> [Char] -> (Interval endPoint, Interval endPoint)
forall a b. (a -> b) -> a -> b
$ [Char]
"Factory.Data.Interval.splitAt':\tunsuitable index=" [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ endPoint -> [Char]
forall a. Show a => a -> [Char]
show endPoint
i [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ [Char]
" for interval=" [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ Interval endPoint -> [Char]
forall a. Show a => a -> [Char]
show Interval endPoint
interval [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ [Char]
"."
	| Bool
otherwise			= ((endPoint
l, endPoint
i), (endPoint -> endPoint
forall a. Enum a => a -> a
succ endPoint
i, endPoint
r))

{- |
	* The distance between the endpoints,
	which for 'Integral' quantities is the same as the number of items in closed interval; though the latter concept would return type 'Int'.

	* CAVEAT: the implementation accounts for the potential fence-post error, for closed intervals of integers,
	but this results in the opposite error when used with /Fractional/ quantities.
	So, though most of the module merely requires 'Enum', this function is further restricted to 'Integral'.
-}
{-# INLINE getLength #-}
getLength :: Integral endPoint => Interval endPoint -> endPoint
getLength :: Interval endPoint -> endPoint
getLength (endPoint
l, endPoint
r)	= endPoint -> endPoint
forall a. Enum a => a -> a
succ endPoint
r endPoint -> endPoint -> endPoint
forall a. Num a => a -> a -> a
- endPoint
l

{- |
	* Converts 'Interval' to a list by enumerating the values.

	* CAVEAT: produces rather odd results for 'Fractional' types, but no stranger than considering such types Enumerable in the first place.
-}
{-# INLINE toList #-}
toList :: Enum endPoint => Interval endPoint -> [endPoint]
toList :: Interval endPoint -> [endPoint]
toList	= (endPoint -> endPoint -> [endPoint])
-> Interval endPoint -> [endPoint]
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry endPoint -> endPoint -> [endPoint]
forall a. Enum a => a -> a -> [a]
enumFromTo	-- CAVEAT: in this eta-reduced form, it'll only be inlined when called without arguments.

{- |
	* Reduces 'Interval' to a single integral value encapsulated in a 'Data.Monoid.Monoid',
	using a /divide-and-conquer/ strategy,
	bisecting the /interval/ and recursively evaluating each part; <https://en.wikipedia.org/wiki/Divide_and_conquer_algorithm>.

	* By choosing a 'ratio' other than @(1 % 2)@, the bisection can be made asymmetrical.
	The specified ratio represents the length of the left-hand portion over the original list-length;
	eg. @(1 % 3)@ results in the first part, half the length of the second.

	* This process of recursive bisection, is terminated beneath the specified minimum length,
	after which the 'Interval' are expanded into the corresponding list, and the /monoid/'s binary operator is directly /folded/ over it.

	* One can view this as a <https://en.wikipedia.org/wiki/Hylomorphism_%28computer_science%29>,
	in which 'Interval' is exploded into a binary tree-structure
	(each leaf of which contains a list of up to 'minLength' integers, and each node of which contains an associative binary operator),
	and then collapsed to a scalar, by application of the operators.
-}
divideAndConquer :: (Data.Monoid.Monoid monoid, Integral i, Show i)
	=> (i -> monoid)	-- ^ The monoid's constructor.
	-> Data.Ratio.Ratio i	-- ^ The ratio of the original span, at which to bisect the 'Interval'.
	-> i			-- ^ For efficiency, the /interval/ will not be bisected, when it's length has been reduced to this value.
	-> Interval i
	-> monoid		-- ^ The resulting scalar.
divideAndConquer :: (i -> monoid) -> Ratio i -> i -> Interval i -> monoid
divideAndConquer i -> monoid
monoidConstructor Ratio i
ratio i
minLength
	| ((Ratio i -> Bool) -> Bool) -> [Ratio i -> Bool] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any ((Ratio i -> Bool) -> Ratio i -> Bool
forall a b. (a -> b) -> a -> b
$ Ratio i
ratio) [
		(Ratio i -> Ratio i -> Bool
forall a. Ord a => a -> a -> Bool
< Ratio i
0),
		(Ratio i -> Ratio i -> Bool
forall a. Ord a => a -> a -> Bool
>= Ratio i
1)
	]		= [Char] -> Interval i -> monoid
forall a. HasCallStack => [Char] -> a
error ([Char] -> Interval i -> monoid) -> [Char] -> Interval i -> monoid
forall a b. (a -> b) -> a -> b
$ [Char]
"Factory.Data.Interval.divideAndConquer:\tunsuitable ratio='" [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ Ratio i -> [Char]
forall a. Show a => a -> [Char]
show Ratio i
ratio [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ [Char]
"'."
	| i
minLength i -> i -> Bool
forall a. Ord a => a -> a -> Bool
< i
1	= [Char] -> Interval i -> monoid
forall a. HasCallStack => [Char] -> a
error ([Char] -> Interval i -> monoid) -> [Char] -> Interval i -> monoid
forall a b. (a -> b) -> a -> b
$ [Char]
"Factory.Data.Interval.divideAndConquer:\tunsuitable minLength=" [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ i -> [Char]
forall a. Show a => a -> [Char]
show i
minLength [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ [Char]
"."
	| Bool
otherwise	= Interval i -> monoid
slave
	where
		slave :: Interval i -> monoid
slave interval :: Interval i
interval@(i
l, i
r)
			| Interval i -> i
forall endPoint. Integral endPoint => Interval endPoint -> endPoint
getLength Interval i
interval i -> i -> Bool
forall a. Ord a => a -> a -> Bool
<= i
minLength	= [monoid] -> monoid
forall a. Monoid a => [a] -> a
Data.Monoid.mconcat ([monoid] -> monoid) -> ([i] -> [monoid]) -> [i] -> monoid
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (i -> monoid) -> [i] -> [monoid]
forall a b. (a -> b) -> [a] -> [b]
map i -> monoid
monoidConstructor ([i] -> monoid) -> [i] -> monoid
forall a b. (a -> b) -> a -> b
$ Interval i -> [i]
forall endPoint. Enum endPoint => Interval endPoint -> [endPoint]
toList Interval i
interval	-- Fold the monoid's binary operator over the delimited list.
			| Bool
otherwise				= (monoid -> monoid -> monoid) -> (monoid, monoid) -> monoid
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry monoid -> monoid -> monoid
forall a. Monoid a => a -> a -> a
Data.Monoid.mappend ((monoid, monoid) -> monoid)
-> ((Interval i, Interval i) -> (monoid, monoid))
-> (Interval i, Interval i)
-> monoid
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Strategy (monoid, monoid) -> (monoid, monoid) -> (monoid, monoid)
forall a. Strategy a -> a -> a
Control.Parallel.Strategies.withStrategy (
				Strategy monoid -> Strategy monoid -> Strategy (monoid, monoid)
forall a b. Strategy a -> Strategy b -> Strategy (a, b)
Control.Parallel.Strategies.parTuple2 Strategy monoid
forall a. Strategy a
Control.Parallel.Strategies.rseq Strategy monoid
forall a. Strategy a
Control.Parallel.Strategies.rseq
			) ((monoid, monoid) -> (monoid, monoid))
-> ((Interval i, Interval i) -> (monoid, monoid))
-> (Interval i, Interval i)
-> (monoid, monoid)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Interval i -> monoid)
-> (Interval i, Interval i) -> (monoid, monoid)
forall a b. (a -> b) -> (a, a) -> (b, b)
ToolShed.Data.Pair.mirror Interval i -> monoid
slave ((Interval i, Interval i) -> monoid)
-> (Interval i, Interval i) -> monoid
forall a b. (a -> b) -> a -> b
$ i -> Interval i -> (Interval i, Interval i)
forall endPoint.
(Enum endPoint, Ord endPoint, Show endPoint) =>
endPoint
-> Interval endPoint -> (Interval endPoint, Interval endPoint)
splitAt' (
				i
l i -> i -> i
forall a. Num a => a -> a -> a
+ (i
r i -> i -> i
forall a. Num a => a -> a -> a
- i
l) i -> i -> i
forall a. Num a => a -> a -> a
* Ratio i -> i
forall a. Ratio a -> a
Data.Ratio.numerator Ratio i
ratio i -> i -> i
forall a. Integral a => a -> a -> a
`div` Ratio i -> i
forall a. Ratio a -> a
Data.Ratio.denominator Ratio i
ratio	-- Use the ratio to generate the split-index.
			) Interval i
interval	-- Apply the monoid's binary operator to the two operands resulting from bisection.

{- |
	* Multiplies the consecutive sequence of integers within 'Interval'.

	* Since the result can be large, 'divideAndConquer' is used to form operands of a similar order of magnitude,
	thus improving the efficiency of the big-number multiplication.
-}
product' :: (Integral i, Show i)
	=> Data.Ratio.Ratio i	-- ^ The ratio at which to bisect the 'Interval'.
	-> i			-- ^ For efficiency, the /interval/ will not be bisected, when it's length has been reduced to this value.
	-> Interval i
	-> i			-- ^ The resulting product.
product' :: Ratio i -> i -> Interval i -> i
product' Ratio i
ratio i
minLength Interval i
interval
	| i -> Interval i -> Bool
forall endPoint.
Ord endPoint =>
endPoint -> Interval endPoint -> Bool
elem' i
0 Interval i
interval	= i
0
	| Bool
otherwise		= Product i -> i
forall a. Product a -> a
Data.Monoid.getProduct (Product i -> i) -> Product i -> i
forall a b. (a -> b) -> a -> b
$ (i -> Product i) -> Ratio i -> i -> Interval i -> Product i
forall monoid i.
(Monoid monoid, Integral i, Show i) =>
(i -> monoid) -> Ratio i -> i -> Interval i -> monoid
divideAndConquer i -> Product i
forall a. a -> Product a
Data.Monoid.Product Ratio i
ratio i
minLength Interval i
interval