--Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd.
--All rights reserved.
--
--Redistribution and use in source and binary forms, with or without
--modification, are permitted provided that the following conditions are
--met:
--
--    - Redistributions of source code must retain the above copyright
--      notice, this list of conditions and the following disclaimer.
--
--    - Redistributions in binary form must reproduce the above copyright
--      notice, this list of conditions and the following disclaimer in
--      the documentation and/or other materials provided with the
--      distribution.
--
--    - Neither the name of The Numerical ALgorithms Group Ltd. nor the
--      names of its contributors may be used to endorse or promote products
--      derived from this software without specific prior written permission.
--
--THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
--IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
--TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
--PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
--OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
--EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
--PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
--PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
--LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
--NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
--SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

)abbrev package FSUPFACT FunctionSpaceUnivariatePolynomialFactor
++ Used internally by IR2F
++ Author: Manuel Bronstein
++ Date Created: 12 May 1988
++ Date Last Updated: 22 September 1993
++ Keywords: function, space, polynomial, factoring
FunctionSpaceUnivariatePolynomialFactor(R, F, UP):
 Exports == Implementation where
  R : Join(IntegralDomain, RetractableTo Integer)
  F : FunctionSpace R
  UP: UnivariatePolynomialCategory F

  Q   ==> Fraction Integer
  K   ==> Kernel F
  AN  ==> AlgebraicNumber
  PQ  ==> SparseMultivariatePolynomial(Q, K)
  PR  ==> SparseMultivariatePolynomial(R, K)
  UPQ ==> SparseUnivariatePolynomial Q
  UPA ==> SparseUnivariatePolynomial AN
  FR  ==> Factored UP
  FRQ ==> Factored UPQ
  FRA ==> Factored UPA

  Exports ==> with
    ffactor: UP -> FR
      ++ ffactor(p) tries to factor a univariate polynomial p over F
    qfactor: UP -> Union(FRQ, "failed")
      ++ qfactor(p) tries to factor p over fractions of integers,
      ++ returning "failed" if it cannot
    UP2ifCan: UP  -> Union(overq: UPQ, overan: UPA, failed: Boolean)
      ++ UP2ifCan(x) should be local but conditional.
    if F has RetractableTo AN then
      anfactor: UP -> Union(FRA, "failed")
        ++ anfactor(p) tries to factor p over algebraic numbers,
        ++ returning "failed" if it cannot

  Implementation ==> add
    import AlgFactor(UPA)
    import RationalFactorize(UPQ)

    P2QifCan : PR  -> Union(PQ, "failed")
    UPQ2UP   : (SparseUnivariatePolynomial PQ, F) -> UP
    PQ2F     : (PQ, F) -> F
    ffactor0 : UP -> FR

    dummy := kernel(new()$Symbol)$K

    if F has RetractableTo AN then
      UPAN2F: UPA -> UP
      UPQ2AN: UPQ -> UPA

      UPAN2F p ==
        map(#1::F, p)$UnivariatePolynomialCategoryFunctions2(AN,UPA,F,UP)

      UPQ2AN p ==
        map(#1::AN, p)$UnivariatePolynomialCategoryFunctions2(Q,UPQ,AN,UPA)

      ffactor p ==
        (pq := anfactor p) case FRA =>
                         map(UPAN2F, pq::FRA)$FactoredFunctions2(UPA, UP)
        ffactor0 p

      anfactor p ==
        (q := UP2ifCan p) case overq =>
                     map(UPQ2AN, factor(q.overq))$FactoredFunctions2(UPQ, UPA)
        q case overan => factor(q.overan)
        "failed"

      UP2ifCan p ==
        ansq := 0$UPQ ; ansa := 0$UPA
        goforq? := true
        while p ~= 0 repeat
          if goforq? then
            rq := retractIfCan(leadingCoefficient p)@Union(Q, "failed")
            if rq case Q then
              ansq := ansq + monomial(rq::Q, degree p)
              ansa := ansa + monomial(rq::Q::AN, degree p)
            else
              goforq? := false
              ra := retractIfCan(leadingCoefficient p)@Union(AN, "failed")
              if ra case AN then ansa := ansa + monomial(ra::AN, degree p)
                            else return [true]
          else
            ra := retractIfCan(leadingCoefficient p)@Union(AN, "failed")
            if ra case AN then ansa := ansa + monomial(ra::AN, degree p)
                          else return [true]
          p := reductum p
        goforq? => [ansq]
        [ansa]

    else
      UPQ2F: UPQ -> UP

      UPQ2F p ==
        map(#1::F, p)$UnivariatePolynomialCategoryFunctions2(Q,UPQ,F,UP)

      ffactor p ==
        (pq := qfactor p) case FRQ =>
                         map(UPQ2F, pq::FRQ)$FactoredFunctions2(UPQ, UP)
        ffactor0 p

      UP2ifCan p ==
        ansq := 0$UPQ
        while p ~= 0 repeat
          rq := retractIfCan(leadingCoefficient p)@Union(Q, "failed")
          if rq case Q then ansq := ansq + monomial(rq::Q, degree p)
                       else return [true]
          p := reductum p
        [ansq]

    ffactor0 p ==
      smp := numer(ep := p(dummy::F))
      (q := P2QifCan smp) case "failed" => p::FR
      map(UPQ2UP(univariate(#1, dummy), denom(ep)::F), factor(q::PQ
             )$MRationalFactorize(IndexedExponents K, K, Integer,
                  PQ))$FactoredFunctions2(PQ, UP)

    UPQ2UP(p, d) ==
      map(PQ2F(#1, d), p)$UnivariatePolynomialCategoryFunctions2(PQ,
                                   SparseUnivariatePolynomial PQ, F, UP)

    PQ2F(p, d) ==
      map(#1::F, #1::F, p)$PolynomialCategoryLifting(IndexedExponents K,
                                                K, Q, PQ, F) / d

    qfactor p ==
      (q := UP2ifCan p) case overq => factor(q.overq)
      "failed"

    P2QifCan p ==
      and/[retractIfCan(c::F)@Union(Q, "failed") case Q
           for c in coefficients p] =>
            map(#1::PQ, retract(#1::F)@Q :: PQ,
              p)$PolynomialCategoryLifting(IndexedExponents K,K,R,PR,PQ)
      "failed"

