--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 GALPOLYU GaloisGroupPolynomialUtilities
++ Author: Frederic Lehobey
++ Date Created: 30 June 1994
++ Date Last Updated: 15 July 1994
++ Basic Operations:
++ Related Domains:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ Examples:
++ References:
++ Description: \spadtype{GaloisGroupPolynomialUtilities} provides useful
++ functions for univariate polynomials which should be added to 
++ \spadtype{UnivariatePolynomialCategory} or to \spadtype{Factored}
++ (July 1994).

GaloisGroupPolynomialUtilities(R,UP): Exports == Implementation where
  R : Ring
  UP : UnivariatePolynomialCategory R
  N ==> NonNegativeInteger
  P ==> PositiveInteger

  Exports ==> with
    monic?: UP -> Boolean
      ++ monic?(p) tests if p is monic (i.e. leading coefficient equal to 1).
    unvectorise: Vector R -> UP
      ++ unvectorise(v) returns the polynomial which has for coefficients the
      ++ entries of v in the increasing order.
    reverse: UP -> UP
      ++ reverse(p) returns the reverse polynomial of p.
    scaleRoots: (UP,R) -> UP
      ++ scaleRoots(p,c) returns the polynomial which has c times the roots
      ++ of p.
    shiftRoots: (UP,R) -> UP
      ++ shiftRoots(p,c) returns the polynomial which has for roots c added 
      ++ to the roots of p.
    degreePartition: Factored UP -> Multiset N
      ++ degreePartition(f) returns the degree partition (i.e. the multiset
      ++ of the degrees of the irreducible factors) of
      ++ the polynomial f.
    factorOfDegree: (P, Factored UP) -> UP
      ++ factorOfDegree(d,f) returns a factor of degree d of the factored
      ++ polynomial f. Such a factor shall exist.
    factorsOfDegree: (P, Factored UP) -> List UP
      ++ factorsOfDegree(d,f) returns the factors of degree d of the factored
      ++ polynomial f.

  Implementation ==> add

    import Factored UP

    factorsOfDegree(d:P,r:Factored UP):List UP ==
      lfact : List UP := empty()
      for fr in factors r | degree(fr.factor)=(d::N) repeat
        for i in 1..fr.exponent repeat
          lfact := cons(fr.factor,lfact)
      lfact

    factorOfDegree(d:P,r:Factored UP):UP ==
      factor : UP := 0
      for i in 1..numberOfFactors r repeat
        factor := nthFactor(r,i)
        if degree(factor)=(d::N) then return factor
      error "factorOfDegree: Bad arguments"

    degreePartition(r:Factored UP):Multiset N ==
      multiset([ degree(nthFactor(r,i)) for i in 1..numberOfFactors r ])

    monic?(p:UP):Boolean == one? leadingCoefficient p

    unvectorise(v:Vector R):UP ==
      p : UP := 0
      for i in 1..#v repeat p := p + monomial(v(i),(i-1)::N)
      p

    reverse(p:UP):UP ==
      r : UP := 0
      n := degree(p)
      for i in 0..n repeat r := r + monomial(coefficient(p,(n-i)::N),i)
      r

    scaleRoots(p:UP,c:R):UP ==
      one? c => p
      n := degree p
      zero? c => monomial(leadingCoefficient p,n)
      r : UP := 0
      mc : R := 1
      for i in n..0 by -1 repeat
        r := r + monomial(mc*coefficient(p,i),i)
        mc := mc*c
      r

    import UnivariatePolynomialCategoryFunctions2(R,UP,UP,
     SparseUnivariatePolynomial UP)

    shiftRoots(p:UP,c:R):UP == elt(map(coerce,p),monomial(1,1)$UP-c::UP)::UP

