Package it.unimi.di.prog2.h11
Class SparsePoly
java.lang.Object
it.unimi.di.prog2.h11.SparsePoly
SparsePoly
s 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 \).
-
Nested Class Summary
Modifier and TypeClassDescriptionstatic final record
A record holding a term of the polynomial. -
Field Summary
Modifier and TypeFieldDescriptionprivate final List<SparsePoly.Term>
The array of terms (in increasing degree). -
Constructor Summary
ModifierConstructorDescriptionInitializes this to be the zero polynomial, that is \( p = 0 \).SparsePoly
(int c, int n) Initializes this to be the polynomial \(p = cx^n\).private
SparsePoly
(List<SparsePoly.Term> lst) Initializes this to be the polynomial from a list of terms in increasing degree order. -
Method Summary
Modifier and TypeMethodDescriptionadd
(SparsePoly q) Performs polynomial addition.private static void
addTerm
(List<SparsePoly.Term> lst, SparsePoly.Term term) Adds a term to a list of terms in increasing degree order.int
coeff
(int d) Returns the coefficient of the term of given exponent.int
degree()
Returns the degree of this polynomial.boolean
private int
findByDegree
(int d) Finds the index of a term of given degree.private static int
findByDegree
(List<SparsePoly.Term> lst, int d) Finds the index (or insertion point) of a term of given degree in a list of terms in increasing degree order.int
hashCode()
minus()
Returns the negate polynomial.mul
(SparsePoly q) Performs polynomial multiplication.sub
(SparsePoly q) Performs polynomial subtraction.toString()
-
Field Details
-
terms
The array of terms (in increasing degree).
-
-
Constructor Details
-
SparsePoly
public SparsePoly()Initializes this to be the zero polynomial, that is \( p = 0 \). -
SparsePoly
Initializes this to be the polynomial \(p = cx^n\).- Parameters:
c
- the coefficient.n
- the degree.- Throws:
NegativeExponentException
- ifn
< 0.IllegalArgumentException
-
SparsePoly
Initializes this to be the polynomial from a list of terms in increasing degree order.- Parameters:
lst
- the notnull
list, not containingnull
s and in increasing degree order.
-
-
Method Details
-
findByDegree
private int findByDegree(int d) Finds the index of a term of given degree.- Parameters:
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
.
-
findByDegree
Finds the index (or insertion point) of a term of given degree in a list of terms in increasing degree order.If the list contains a term of given degree, returns its index. Otherwise, returns
-(insertion_point) - 1
whereinsertion_point
is the index of the first term with degree greater thand
; note that this implies that the return value is non-negative iff the list contains a term of given degree.- Parameters:
lst
- the notnull
list of notnull
terms in increasing degree order.d
- the degree.- Returns:
- the index of the term of given degree, or
-insertion_point - 1
if none is present. - See Also:
-
addTerm
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 notnull
list of notnull
terms in increasing degree order.term
- the notnull
term.
-
add
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
- ifq
isnull
.
-
mul
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
- ifq
isnull
.
-
sub
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
- ifq
isnull
.
-
minus
Returns the negate polynomial.If \( p \) is this polynomial, returns \( -p \).
- Returns:
- this polynomial multiplied by \( -1 \).
-
equals
-
hashCode
public int hashCode() -
toString
-