Package it.unimi.di.prog2.s09

Class SparsePoly

java.lang.Object
it.unimi.di.prog2.s09.SparsePoly
public class SparsePoly extends Object
SparsePolys are immutable polynomials with integer coefficients such that the number of nonzero coefficient is small with respect to the degree.

A typical Poly is \( p = c_0 + c_1 x + c_2 x^2 + \cdots + c_n x^n \).

  • Field Details

  • Constructor Details

    • SparsePoly

      public SparsePoly()
      Initializes this to be the zero polynomial, that is \( p = 0 \).

    • SparsePoly

      public SparsePoly(int c, int n) throws NegativeExponentException
      Initializes this to be the polynomial \(p = cx^n\).
      Parameters:
      c - the coefficient.
      n - the degree.
      Throws:
      NegativeExponentException - if n < 0.

    • SparsePoly

      private SparsePoly(List<SparsePoly.Term> lst)
      Initializes this to be the polynomial from a list of terms in increasing degree order.
      Parameters:
      lst - the not null list, not containing nulls and in increasing degree order.

  • Method Details

    • findByDegree

      private static int findByDegree(List<SparsePoly.Term> lst, int d)
      Finds the index of a term of given degree in a list of terms in increasing degree order.
      Parameters:
      lst - the not null list of not null terms and in increasing degree order.
      d - the degree.
      Returns:
      the index of a term of given degree, or -1 if none is present.

    • coeff

      public int coeff(int d)
      Returns the coefficient of the term of given exponent.
      Parameters:
      d - the exponent of the term to consider.
      Returns:
      the coefficient of the considered term.

    • degree

      public int degree()
      Returns the degree of this polynomial.
      Returns:
      the largest exponent with a non-zero coefficient; returns 0 if this is the zero Poly.

    • addTerm

      private static void addTerm(List<SparsePoly.Term> lst, SparsePoly.Term term)
      Adds a term to a list of terms in increasing degree order.

      The list will remain in increasing degree order, in case a term with the same degree was present, the two will be added (and removed if the coefficient will become 0).

      Parameters:
      lst - the not null list of not null terms in increasing degree order.
      term - the not null term.

    • add

      public SparsePoly add(SparsePoly q) throws NullPointerException
      Performs polynomial addition.

      If \( p \) is this polynomial, returns \( p + q \).

      Parameters:
      q - the polynomial to add to this one.
      Returns:
      the sum among this and the given polynomial.
      Throws:
      NullPointerException - if q is null.

    • mul

      public SparsePoly mul(SparsePoly q) throws NullPointerException
      Performs polynomial multiplication.

      If \( p \) is this polynomial, returns \( p q \).

      Parameters:
      q - the polynomial to multiply by this one.
      Returns:
      the product among this and the given polynomial.
      Throws:
      NullPointerException - if q is null.

    • sub

      public SparsePoly sub(SparsePoly q) throws NullPointerException
      Performs polynomial subtraction.

      If \( p \) is this polynomial, returns \( p - q \).

      Parameters:
      q - the polynomial to subtract from this one.
      Returns:
      the subtraction among this and the given polynomial.
      Throws:
      NullPointerException - if q is null.

    • minus

      public SparsePoly minus()
      Returns the negate polynomial.

      If \( p \) is this polynomial, returns \( -p \).

      Returns:
      this polynomial multiplied by \( -1 \).