{-
	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  = reduceSorted . 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 [] = []
reduceSorted (x : xs)
        | null matched  = x : reduceSorted remainder
        | otherwise     = Control.Arrow.second (+ sumExponents matched) x : reduceSorted remainder
        where
                (matched, remainder)    = span (=~ x) 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' e []            = [e]
insert' e l@(x : xs)    = case Data.Ord.comparing Data.Exponential.getBase e x of
        LT      -> e : l
        GT      -> x : insert' e xs     -- Recurse.
        _       -> Control.Arrow.second (+ Data.Exponential.getExponent e) x : 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
l >*< r = reduceSorted $ ToolShed.Data.List.merge l 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  = map 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.
numerator >/< denominator       = filter (
        (> 0) . Data.Exponential.getExponent
 ) &&& invert . filter (
        (< 0) . Data.Exponential.getExponent
 ) $ numerator >*< invert 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 >^ power        = map (<^ power) factors

-- | Sum the /exponents/ of the specified list; as required to multiply exponentials with identical /base/.
sumExponents :: Num exponent => Factors base exponent -> exponent
sumExponents    = foldr ((+) . Data.Exponential.getExponent) 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       = Math.DivideAndConquer.product' bisectionRatio minLength . map Data.Exponential.evaluate