{-
	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 list of /prime factors/.

	* The product of this list of prime-factors represents the /composite/ integer from which they were originally extracted.
-}

module Factory.Data.PrimeFactors(
-- * Types
-- ** Type-synonyms
	Factors,
-- * Functions
	insert',
--	invert,
	product',
	reduce,
--	reduceSorted,
--	sumExponents,
-- ** Operators
	(>*<),
	(>/<),
	(>^)
) where

import qualified	Control.Arrow
import			Control.Arrow((&&&))
import qualified	Data.List
import qualified	Data.Ord
import qualified	Factory.Math.DivideAndConquer	as Math.DivideAndConquer
import qualified	Factory.Data.Exponential	as Data.Exponential
import			Factory.Data.Exponential((<^), (=~))
import qualified	ToolShed.Data.List

infixl 7 >/<, >*<	-- Same as (/).
infixr 8 >^		-- Same as (^).

{- |
	* Each element of this list represents one /prime-factor/, expressed as an /exponential/ with a /prime/ base, of the original integer.

	* Whilst it only makes sense for both the /base/ and /exponent/ to be integral, these constrains are applied at the function-level as required.
-}
type Factors base exponent	= [Data.Exponential.Exponential base exponent]

{- |
	* Sorts a list representing a product of /prime factors/ by increasing /base/.

	* Multiplies 'Data.Exponential.Exponential's of similar /base/.
-}
reduce :: (Ord base, Num exponent, Ord exponent) => Factors base exponent -> Factors base exponent
reduce :: Factors base exponent -> Factors base exponent
reduce	= Factors base exponent -> Factors base exponent
forall base exponent.
(Eq base, Num exponent) =>
Factors base exponent -> Factors base exponent
reduceSorted (Factors base exponent -> Factors base exponent)
-> (Factors base exponent -> Factors base exponent)
-> Factors base exponent
-> Factors base exponent
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Factors base exponent -> Factors base exponent
forall a. Ord a => [a] -> [a]
Data.List.sort {-primarily by base-}

-- | Multiplies 'Data.Exponential.Exponential's of similar /base/.
reduceSorted :: (Eq base, Num exponent) => Factors base exponent -> Factors base exponent
-- reduceSorted	= map (Data.Exponential.getBase . head &&& sumExponents) . Data.List.groupBy (=~)	-- Slow
reduceSorted :: Factors base exponent -> Factors base exponent
reduceSorted []	= []
reduceSorted (Exponential base exponent
x : Factors base exponent
xs)
	| Factors base exponent -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null Factors base exponent
matched	= Exponential base exponent
x Exponential base exponent
-> Factors base exponent -> Factors base exponent
forall a. a -> [a] -> [a]
: Factors base exponent -> Factors base exponent
forall base exponent.
(Eq base, Num exponent) =>
Factors base exponent -> Factors base exponent
reduceSorted Factors base exponent
remainder
	| Bool
otherwise	= (exponent -> exponent)
-> Exponential base exponent -> Exponential base exponent
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (d, b) (d, c)
Control.Arrow.second (exponent -> exponent -> exponent
forall a. Num a => a -> a -> a
+ Factors base exponent -> exponent
forall exponent base.
Num exponent =>
Factors base exponent -> exponent
sumExponents Factors base exponent
matched) Exponential base exponent
x Exponential base exponent
-> Factors base exponent -> Factors base exponent
forall a. a -> [a] -> [a]
: Factors base exponent -> Factors base exponent
forall base exponent.
(Eq base, Num exponent) =>
Factors base exponent -> Factors base exponent
reduceSorted Factors base exponent
remainder
	where
		(Factors base exponent
matched, Factors base exponent
remainder)	= (Exponential base exponent -> Bool)
-> Factors base exponent
-> (Factors base exponent, Factors base exponent)
forall a. (a -> Bool) -> [a] -> ([a], [a])
span (Exponential base exponent -> Exponential base exponent -> Bool
forall base exponent.
Eq base =>
Exponential base exponent -> Exponential base exponent -> Bool
=~ Exponential base exponent
x) Factors base exponent
xs

{- |
	* Insert a 'Data.Exponential.Exponential', into a list representing a product of /prime factors/, multiplying with any incumbent of like /base/.

	* The list should be sorted by increasing /base/.

	* Preserves the sort-order.

	* CAVEAT: this is tolerably efficient for sporadic insertion; to insert a list, use '>*<'.
-}
insert' :: (Ord base, Num exponent) => Data.Exponential.Exponential base exponent -> Factors base exponent -> Factors base exponent
insert' :: Exponential base exponent
-> Factors base exponent -> Factors base exponent
insert' Exponential base exponent
e []		= [Exponential base exponent
e]
insert' Exponential base exponent
e l :: Factors base exponent
l@(Exponential base exponent
x : Factors base exponent
xs)	= case (Exponential base exponent -> base)
-> Exponential base exponent
-> Exponential base exponent
-> Ordering
forall a b. Ord a => (b -> a) -> b -> b -> Ordering
Data.Ord.comparing Exponential base exponent -> base
forall base exponent. Exponential base exponent -> base
Data.Exponential.getBase Exponential base exponent
e Exponential base exponent
x of
	Ordering
LT	-> Exponential base exponent
e Exponential base exponent
-> Factors base exponent -> Factors base exponent
forall a. a -> [a] -> [a]
: Factors base exponent
l
	Ordering
GT	-> Exponential base exponent
x Exponential base exponent
-> Factors base exponent -> Factors base exponent
forall a. a -> [a] -> [a]
: Exponential base exponent
-> Factors base exponent -> Factors base exponent
forall base exponent.
(Ord base, Num exponent) =>
Exponential base exponent
-> Factors base exponent -> Factors base exponent
insert' Exponential base exponent
e Factors base exponent
xs	-- Recurse.
	Ordering
_	-> (exponent -> exponent)
-> Exponential base exponent -> Exponential base exponent
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (d, b) (d, c)
Control.Arrow.second (exponent -> exponent -> exponent
forall a. Num a => a -> a -> a
+ Exponential base exponent -> exponent
forall base exponent. Exponential base exponent -> exponent
Data.Exponential.getExponent Exponential base exponent
e) Exponential base exponent
x Exponential base exponent
-> Factors base exponent -> Factors base exponent
forall a. a -> [a] -> [a]
: Factors base exponent
xs	-- Multiply by adding exponents.

{- |
	* Multiplies two lists each representing a product of /prime factors/, and sorted by increasing /base/.

	* Preserves the sort-order.
-}
(>*<) :: (Ord base, Num exponent, Ord exponent) => Factors base exponent -> Factors base exponent -> Factors base exponent
Factors base exponent
l >*< :: Factors base exponent
-> Factors base exponent -> Factors base exponent
>*< Factors base exponent
r	= Factors base exponent -> Factors base exponent
forall base exponent.
(Eq base, Num exponent) =>
Factors base exponent -> Factors base exponent
reduceSorted (Factors base exponent -> Factors base exponent)
-> Factors base exponent -> Factors base exponent
forall a b. (a -> b) -> a -> b
$ Factors base exponent
-> Factors base exponent -> Factors base exponent
forall a. Ord a => [a] -> [a] -> [a]
ToolShed.Data.List.merge Factors base exponent
l Factors base exponent
r

-- | Invert the product of a list /prime factors/, by negating each of the /exponents/.
invert :: Num exponent => Factors base exponent -> Factors base exponent
invert :: Factors base exponent -> Factors base exponent
invert	= (Exponential base exponent -> Exponential base exponent)
-> Factors base exponent -> Factors base exponent
forall a b. (a -> b) -> [a] -> [b]
map Exponential base exponent -> Exponential base exponent
forall exponent base.
Num exponent =>
Exponential base exponent -> Exponential base exponent
Data.Exponential.invert

{- |
	* Divides two lists, each representing a product of /prime factors/, and sorted by increasing /base/.

	* Preserves the sort-order.
-}
(>/<) :: (Integral base, Integral exponent)
	=> Factors base exponent				-- ^ The list of /prime factors/ in the /numerator/.
	-> Factors base exponent				-- ^ The list of /prime factors/ in the /denominator/.
	-> (Factors base exponent, Factors base exponent)	-- ^ The ratio of /numerator/ and /denominator/, after like /prime factors/ are cancelled.
Factors base exponent
numerator >/< :: Factors base exponent
-> Factors base exponent
-> (Factors base exponent, Factors base exponent)
>/< Factors base exponent
denominator	= (Exponential base exponent -> Bool)
-> Factors base exponent -> Factors base exponent
forall a. (a -> Bool) -> [a] -> [a]
filter (
	(exponent -> exponent -> Bool
forall a. Ord a => a -> a -> Bool
> exponent
0) (exponent -> Bool)
-> (Exponential base exponent -> exponent)
-> Exponential base exponent
-> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Exponential base exponent -> exponent
forall base exponent. Exponential base exponent -> exponent
Data.Exponential.getExponent
 ) (Factors base exponent -> Factors base exponent)
-> (Factors base exponent -> Factors base exponent)
-> Factors base exponent
-> (Factors base exponent, Factors base exponent)
forall (a :: * -> * -> *) b c c'.
Arrow a =>
a b c -> a b c' -> a b (c, c')
&&& Factors base exponent -> Factors base exponent
forall exponent base.
Num exponent =>
Factors base exponent -> Factors base exponent
invert (Factors base exponent -> Factors base exponent)
-> (Factors base exponent -> Factors base exponent)
-> Factors base exponent
-> Factors base exponent
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Exponential base exponent -> Bool)
-> Factors base exponent -> Factors base exponent
forall a. (a -> Bool) -> [a] -> [a]
filter (
	(exponent -> exponent -> Bool
forall a. Ord a => a -> a -> Bool
< exponent
0) (exponent -> Bool)
-> (Exponential base exponent -> exponent)
-> Exponential base exponent
-> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Exponential base exponent -> exponent
forall base exponent. Exponential base exponent -> exponent
Data.Exponential.getExponent
 ) (Factors base exponent
 -> (Factors base exponent, Factors base exponent))
-> Factors base exponent
-> (Factors base exponent, Factors base exponent)
forall a b. (a -> b) -> a -> b
$ Factors base exponent
numerator Factors base exponent
-> Factors base exponent -> Factors base exponent
forall base exponent.
(Ord base, Num exponent, Ord exponent) =>
Factors base exponent
-> Factors base exponent -> Factors base exponent
>*< Factors base exponent -> Factors base exponent
forall exponent base.
Num exponent =>
Factors base exponent -> Factors base exponent
invert Factors base exponent
denominator

{- |
	* Raise the product of a list /prime factors/ to the specified power.

	* CAVEAT: this merely involves raising each element to the specified power; cf. raising a /polynomial/ to a power.
-}
(>^) :: Num exponent => Factors base exponent -> exponent -> Factors base exponent
Factors base exponent
factors >^ :: Factors base exponent -> exponent -> Factors base exponent
>^ exponent
power	= (Exponential base exponent -> Exponential base exponent)
-> Factors base exponent -> Factors base exponent
forall a b. (a -> b) -> [a] -> [b]
map (Exponential base exponent -> exponent -> Exponential base exponent
forall exponent base.
Num exponent =>
Exponential base exponent -> exponent -> Exponential base exponent
<^ exponent
power) Factors base exponent
factors

-- | Sum the /exponents/ of the specified list; as required to multiply exponentials with identical /base/.
sumExponents :: Num exponent => Factors base exponent -> exponent
sumExponents :: Factors base exponent -> exponent
sumExponents	= (Exponential base exponent -> exponent -> exponent)
-> exponent -> Factors base exponent -> exponent
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (exponent -> exponent -> exponent
forall a. Num a => a -> a -> a
(+) (exponent -> exponent -> exponent)
-> (Exponential base exponent -> exponent)
-> Exponential base exponent
-> exponent
-> exponent
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Exponential base exponent -> exponent
forall base exponent. Exponential base exponent -> exponent
Data.Exponential.getExponent) exponent
0

-- | Multiply a list of /prime factors/.
product' :: (Num base, Integral exponent)
	=> Math.DivideAndConquer.BisectionRatio
	-> Math.DivideAndConquer.MinLength
	-> Factors base exponent		-- ^ The list on which to operate.
	-> base					-- ^ The result.
product' :: BisectionRatio -> MinLength -> Factors base exponent -> base
product' BisectionRatio
bisectionRatio MinLength
minLength	= BisectionRatio -> MinLength -> [base] -> base
forall n. Num n => BisectionRatio -> MinLength -> [n] -> n
Math.DivideAndConquer.product' BisectionRatio
bisectionRatio MinLength
minLength ([base] -> base)
-> (Factors base exponent -> [base])
-> Factors base exponent
-> base
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Exponential base exponent -> base)
-> Factors base exponent -> [base]
forall a b. (a -> b) -> [a] -> [b]
map Exponential base exponent -> base
forall base exponent.
(Num base, Integral exponent) =>
Exponential base exponent -> base
Data.Exponential.evaluate