ArrayListADT.java

public interface ArrayListADT<T> extends Cloneable
{
    public boolean isEmpty();
      //Method to determine whether the list is empty.
      //Postcondition: Returns true if the list is empty;
      //               otherwise, returns false.

    public boolean isFull();
      //Method to determine whether the list is full.
      //Postcondition: Returns true if the list is full;
      //               otherwise, returns false.

    public int listSize();
      //Method to return the number of elements in the list.
      //Postcondition: Returns the value of length.

    public int maxListSize();
      //Method to return the maximum size of the list.
      //Postcondition: Returns the maximum number of elements
      //               that can be inserted in the list.

    public void print();
      //Method to output the elements of the list.
      //Postcondition: Elements of the list are output on the
      //               standard output device.

    public Object clone();
      //Returns a copy of objects data in store.
      //This method clones only the references stored in
      //the array. The objects that the array references
      //point to are not cloned.

    public boolean isItemAtEqual(int location, T item);
      //Method to determine whether item is the same as the
      //item in the list at the position specified by location.
      //Postcondition: Returns true if the element in the list
      //               at the position specified by location is
      //               the same as item;
      //               otherwise, returns false.

    public void insertAt(int location, T insertItem);
      //Method to insert insertItem in the list at the position
      //specified by location.
      //Postcondition: Starting at location, the elements of
      //               the list are shifted to make room for
      //               insertItem; insertItem is inserted at
      //               the position specified by location and
      //               the length of the list is incremented
      //               by 1. If the list is full or location
      //               is out of range, an appropriate message
      //               is output.

    public void insertEnd(T insertItem);
      //Method to insert insertItem at the end of the list.
      //Postcondition: insertItem is inserted at the end of the
      //               list and the length of the list is
      //               incrmented by 1.
      //               If the list is full, an appropriate
      //               message is output.

    public void removeAt(int location);
      //Method to remove the item from the list at the
      //position specified by location.
      //Postcondition: The element at the position specified by
      //               location is removed from the list and
      //               the length of the list is decremented by 1.
      //               If location is out of range, an
      //               appropriate message is output.

    public T retrieveAt(int location);
      //Method to retrieve the element from the list at the
      //position specified by location.
      //Postcondition: A reference of the element at the
      //               position specified by location is
      //               returned. If location is out of range,
      //               an appropriate message is output and
      //               null is returned.

    public void replaceAt(int location, T repItem);
      //Method to replace the element in the list at
      //the position specified by location with repItem.
      //Postcondition: repItem is inserted in the list at the
      //               position specified by location.
      //               If location is out of range, an
      //               appropriate message is output.

    public void clearList();
      //Method to remove all the elements from the list.
      //Postcondition: The length of the list is 0.

    public int seqSearch(T searchItem);
      //Method to determine whether searchItem is in the list.
      //Postcondition: If searchItem is found, returns the
      //               location in the array where searchItem
      //               is found; otherwise, returns -1.

    public void remove(T removeItem);
      //Method to remove an item from the list.
      //The parameter removeItem specifies the item to
      //be removed.
      //Postcondition: If removeItem is found in the list, it
      //               is removed from the list and length is
      //               decremented by one.
}

ArrayListClass.java

public abstract class ArrayListClass<T>
                      implements ArrayListADT<T>, Cloneable
{
    protected int length;  //to store the length of the list
    protected int maxSize; //to store the maximum size of
                           //the list
    protected T[] list;    //array to hold the list elements


       //Default constructor
       //Creates an array of size 100
       //Postcondition: list points to the array, length = 0,
       //               and maxSize = 100
    public ArrayListClass()
    {
        maxSize = 100;

        length = 0;
        list = (T[]) new Object[maxSize];
    }

       //Constructor with a parameter
       //Creates an array of the size specified by the
       //parameter size.
       //Postcondition: list points to the array, length = 0,
       //               and maxSize = size
    public ArrayListClass(int size)
    {
        if (size <= 0)
        {
            System.err.println("The array size must be positive. "
                             + "Creating an array of size 100. ");
             maxSize = 100;
        }
        else
            maxSize = size;

        length = 0;
        list = (T[]) new Object[maxSize];
    }

       //Method to determine whether the list is empty.
       //Postcondition: Returns true if the list is empty;
       //               otherwise, returns false.
    public boolean isEmpty()
    {
        return (length == 0);
    }

       //Method to determine whether the list is full.
       //Postcondition: Returns true if the list is full;
       //               otherwise, returns false.
    public boolean isFull()
    {
        return (length == maxSize);
    }

       //Method to return the number of elements in the list.
       //Postcondition: Returns the value of length.
    public int listSize()
    {
        return length;
    }

       //Method to return the maximum size of the list.
       //Postcondition: Returns the value of maxSize.
    public int maxListSize()
    {
        return maxSize;
    }

       //Method to output the elements of the list.
       //Postcondition: Elements of the list are output on the
       //standard output device.
    public void print()
    {
        for (int i = 0; i < length; i++)
            System.out.println(list[i]);
        System.out.println();
    }

       //Returns a copy of objects data in store.
       //This method clones only the references stored in
       //the array. The objects that the array references
       //point to are not cloned.
    public Object clone()
    {
        ArrayListClass<T> copy = null;

        try
        {
            copy = (ArrayListClass<T>) super.clone();
        }
        catch (CloneNotSupportedException e)
        {
            return null;
        }

        copy.list = (T[]) list.clone();

        return copy;
    }

       //Method to determine whether item is the same as the item
       //in the list at the position specified by location.
       //Postcondition: Returns true if list[location] is the
       //               same as item; otherwise, returns false.
    public boolean isItemAtEqual(int location, T item)
    {
        if (location < 0 || location >= length)
        {
            System.err.println("The location of the item to "
                             + "be compared is out of range.");
            return false;
        }

        return (list[location].equals(item));
    }

       //Method to remove all the elements from the list.
       //Postcondition: length = 0
    public void clearList()
    {
        for (int i = 0; i < length; i++)
            list[i] = null;

          length = 0;

        System.gc();   //invoke garbage collector
    } //end clearList

       //Method to remove the item from the list at the position
       //specified by location.
       //Postcondition: The list element at list[location] is
       //               removed and length is decremented by 1.
       //               If location is out of range, an
       //               appropriate message is output.
    public void removeAt(int location)
    {
        if (location < 0 || location >= length)
            System.err.println("The location of the item to "
                             + "be removed is out of range.");
        else
        {
            for (int i = location; i < length - 1; i++)
                  list[i] = list[i + 1];

            list[length - 1] = null;

            length--;
        }
    } //end removeAt

       //Method to retrieve the element from the list at the
       //position specified by location.
       //Postcondition: A reference of the element at the
       //               position specified by location is
       //               returned. If location is out of range,
       //               an appropriate message is output and
       //               null is returned.
    public T retrieveAt(int location)
    {
        if (location < 0 || location >= length)
        {
            System.err.println("The location of the item to be "
                             + "retrieved is out of range.");
            return null;
        }
        else
            return list[location];
    } //end retrieveAt


       //Method to insert insertItem in the list at the position
       //specified by location.
       //Postcondition: Starting at location, the elements of
       //               the list are shifted to make room for
       //               insertItem, list[location] = insertItem;,
       //               and length++;
       //               If the list is full or location is out
       //               of range, an appropriate message is
       //               output.
    public abstract void insertAt(int location, T insertItem);

       //Method to insert insertItem at the end of the list.
       //Postcondition: list[length] = insertItem; and length++;
       //               If the list is full, an appropriate
       //               message is output.
    public abstract void insertEnd(T insertItem);

        //Method to replace the element in the list at
        //the position specified by location with repItem.
        //Postcondition: list[location] = repItem
        //               If location is out of range, an
        //               appropriate message is output.
    public abstract void replaceAt(int location, T repItem);

       //Method to determine whether searchItem is in the list.
       //Postcondition: If searchItem is found, returns the
       //               location in the array where searchItem
       //               is found; otherwise, returns -1.
    public abstract int seqSearch(T searchItem);

       //Method to remove an item from the list.
       //The parameter removeItem specifies the item to
       //be removed.
       //Postcondition: If removeItem is found in the list, it
       //               is removed from the list and length is
       //               decremented by one.
    public abstract void remove(T removeItem);
}

Complex.java

public class Complex
{
    private double a;
    private double b;
    
    public Complex()
    {
        a = 0;
        b = 0;
    }
    
    //Constructor with parameters
    //parameter a is Real
    //parameter b is Imaginary
    public Complex(double a, double b)
    {
        
        this.a = a;
        this.b = b;

    }
    
    //Method to return the real part
    //In (a + bi), a is the real part
    public double getReal()
    {
        return a;
    }
    
    //Method to return the imaginary part
    //In (a + bi), b is the imaginary part
    public double getImaginary()
    {
        return b;
    }
    
    //Method to return the sum of two complex numbers
    //(a + bi) + (c + di) = (a + c) + (b + d)i
    public Complex addComplex(Complex right)
    {
        return new Complex(a + right.getReal(), b + right.getImaginary());
    }
    
    //Method to return the difference of two complex numbers
    //(a + bi) - (c + di) = (a - c) + (b - d)i
    public Complex subtractComplex(Complex right)
    {
        return new Complex(a - right.getReal(), b - right.getImaginary());
    }
    
    //Method to return the product of two complex numbers
    //(a + bi) * (c + di) = (ac - bd) + (ad + bc)i
    public Complex multiplyComplex(Complex right)
    {
        return new Complex(a * right.getReal() - b * right.getImaginary(), a * right.getImaginary() + b * right.getReal());
    }
    
    public String toString()
    {
        if (a == 0)
        {
            return b + "i";
        }
        if (b == 0)
        {
            return String.valueOf(b);
        }
        if (a != 0 && b>0)
        {
            return a + " + " + b + "i";
        }
        else
        {
            return a + " - " + (-b) + "i";
        }
    }
        
        
}

Polynomial.java

import java.util.*;

public class Polynomial extends UnorderedArrayList<Complex>
{
       //Default constructor
       //Postcondition: An array of the size 100, and
       //             length and maxSize are set to 100
    public Polynomial()
    {
         super();
         length = 100;
    }

      //Constructor with a parameter
      //Postcondition: An array of the size specified by
      //               the parameter size is created, length
      //               and maxSize are initialized to size
    public Polynomial(int size)
    {
         super(size);
         length = size;
    }

       //Method to evaluate a polynomial at a given value
       //Postcondition: The polynomial is evaluated at x and
       //               the value is returned
    public Complex evaluate(Double x)
    {
        Complex value = new Complex();

        Complex coeff;
        
        Complex zeroComplex = new Complex(0, 0);
        
        Double xEvaluated;
        Complex xComplex;

        for (int i = 0; i < length; i++)
        {
            coeff = retrieveAt(i);

            if (coeff != zeroComplex){
               xEvaluated = Math.pow(x, i);
               xComplex = new Complex((coeff.getReal())*xEvaluated, (coeff.getImaginary())*xEvaluated);
               value = value.addComplex(xComplex);
            }
        }

        return value;
    }

       //Method to add two polynomials
       //Postcondition: This polynomial is added with the polynomial
       //               specified by the parameter right. A
       //               reference of the result is returned.
    public Polynomial add(Polynomial right)
    {
        int size = max(length, right.length);
        int i;
        Complex sumCoeff;

        Complex coeffP = new Complex();
        Complex coeffQ = new Complex();
        
        Complex z;

        Polynomial temp = new Polynomial(size);

        for (i = 0; i < min(length, right.length); i++)
        {
            coeffP = retrieveAt(i);
            coeffQ = right.retrieveAt(i);

            sumCoeff = coeffP.addComplex(coeffQ);
            temp.replaceAt(i, sumCoeff);
        }

        if (size == length){
            for (i = min(length, right.length); i < length; i++)
                temp.replaceAt(i, retrieveAt(i));
            }
        else
            for (i = min(length, right.length);
                                  i < right.length; i++)
                temp.replaceAt(i, right.retrieveAt(i));

        return temp;
    }

       //Method to subtract two polynomials
       //Postcondition: The polynomial specified by the
       //               parameter right is subtracted from this
       //               polynomial. A reference of the result
       //               is returned.
    public Polynomial subtract(Polynomial right)
    {
        int size = max(length, right.length);
        int i;
        Complex diffCoeff;

        Complex coeffP = new Complex();
        Complex coeffQ = new Complex();

        Polynomial temp = new Polynomial(size);
        

        for (i = 0; i < min(length, right.length); i++)
        {
            coeffP = retrieveAt(i);
            coeffQ = right.retrieveAt(i);

            diffCoeff = coeffP.subtractComplex(coeffQ);
            temp.replaceAt(i, diffCoeff);
        }

        if (size == length)
           for (i = min(length, right.length); i < length; i++)
               temp.replaceAt(i, retrieveAt(i));
        else
           for (i = min(length, right.length);
                                    i < right.length; i++)
           {
               Complex coeff;
               coeff = right.retrieveAt(i);
               Complex negativeCoeff = new Complex (-coeff.getReal(), -coeff.getImaginary());                      
               temp.replaceAt(i, negativeCoeff); //changd from negativeCoeff
           }

        return temp;
    }

       //Method to multiply two polynomials
       //Postcondition: This polynomial is multiplied with the
       //               polynomial specified by the parameter right.
       //               A reference of the result is returned.
    public Polynomial multiply(Polynomial right)
    {
        int size = right.length + length -1;
        int i;
        int r;
        Complex productCoeff;
        
        Complex coeffP = new Complex();
        Complex coeffQ = new Complex();
        Complex currentValue;

        Polynomial temp = new Polynomial(size);
        
            for (i = 0; i < length; i++)
            {
                for (r = 0; r < right.length; r++) {
                    coeffP = (retrieveAt(i));
                    coeffQ = (right.retrieveAt(r));
                
                    productCoeff = coeffP.multiplyComplex(coeffQ);
                    
                    
                    if (temp.retrieveAt(i+r) == null)
                        currentValue = productCoeff;
                    
                    else
                        
                        currentValue = (temp.retrieveAt(i+r));
                        currentValue = currentValue.addComplex(productCoeff);
                    
                    temp.replaceAt(i+r, currentValue);
                
                }
            }

        return temp;
    }

       //Method to read the coefficients of a polynomial
    public void read()
    {
        Scanner console = new Scanner(System.in);

        Double a;
        Double b;

        System.out.println("The degree of this polynomial is: "
                         + (length - 1));
        for (int i = 0; i < length; i++)
        {
            System.out.print("Enter the real part of x^"
                             + i + ": ");                            
            a = console.nextDouble();
            
            System.out.print("Enter the imaginary part of x^"
                             + i + ": ");
            b = console.nextDouble();
            
            Complex x = new Complex(a, b);
            
            replaceAt(i, x);
        }
    }

       //Method to return the string containing the polynomial
    public String toString()
    {
        int i;
        int firstNonzeroCoeff = 0;
        Complex coeff = new Complex();
        Complex complexZero = new Complex(0, 0);
        String str = "";
        Complex negativeCoeff = new Complex(-coeff.getReal(), -coeff.getImaginary());

        for (i = 0; i < length; i++)
        {
            coeff = retrieveAt(i);

            if (coeff != complexZero)
            {
               firstNonzeroCoeff = i;
               break;
            }
        }

        if (firstNonzeroCoeff < length)
        {
           if (firstNonzeroCoeff == 0)
              str = retrieveAt(firstNonzeroCoeff) + " ";
           else
              str = retrieveAt(firstNonzeroCoeff) + "x^"
                       + firstNonzeroCoeff + " ";

           for (i = firstNonzeroCoeff + 1; i < length; i++)
           {
               coeff = retrieveAt(i);

               if (coeff.getReal() != 0 || coeff.getImaginary() !=0 ) //used to be coeff != complexZero
                  if (coeff.getReal() > 0 || coeff.getImaginary() > 0) //used to be ...> complexZero.getReal()
                     str += "+ (" + coeff + ")" + "x^" + i + " ";
                  else
                     str += "+ (" + coeff + ")" + "x^" + i + " "; //changed from negativeCoeff
           }
        }

        return str;
    }

       //Method to determine the smaller of x and y
       //Postcondition: The smaller of x and y is returned
    public int min(int x, int y)
    {
        if (x <= y)
           return x;
        else
           return y;
    }

       //Method to determine the larger of x and y
       //Postcondition: The larger of x and y is returned
    public int max(int x, int y)
    {
        if (x >= y)
            return x;
        else
            return y;
    }
}

UnorderedArrayList.java

public class UnorderedArrayList<T> extends ArrayListClass<T>
{
	   //Default constructor
    public UnorderedArrayList()
    {
        super();
    }

       //Constructor with a parameter
    public UnorderedArrayList(int size)
    {
        super(size);
    }

       //Method to determine whether searchItem is in the list.
       //Postcondition: If searchItem is found, returns the
       //               location in the array where searchItem
       //               is found; otherwise, returns -1.
    public int seqSearch(T searchItem)
    {
        int loc;
        boolean found = false;

        for (loc = 0; loc < length; loc++)
            if (list[loc].equals(searchItem))
            {
                found = true;
                break;
            }

        if (found)
            return loc;
        else
            return -1;
    } //end seqSearch

       //Method to insert insertItem in the list at the position
       //specified by location.
       //Postcondition: Starting at location, the elements of
       //               the list are shifted to make room for
       //               insertItem, list[location] = insertItem;,
       //               and length++;
       //               If the list is full or location is out
       //               of range, an appropriate message is
       //               output.
    public void insertAt(int location, T insertItem)
    {
        if (location < 0 || location >= maxSize)
            System.err.println("The position of the item to "
                             + "be inserted is out of range.");
        else
            if (length >= maxSize)  //list is full
                System.err.println("Cannot insert in a full "
                                 + "list.");
            else
            {
                for (int i = length; i > location; i--)
                    list[i] = list[i - 1];  //move the
                                            //elements down

                list[location] = insertItem;
                length++;   //increment the length
            }
    } //end insertAt

       //Method to insert insertItem at the end of the list.
       //Postcondition: list[length] = insertItem; and length++;
       //               If the list is full, an appropriate
       //               message is output.
    public void insertEnd(T insertItem)
    {
        if (length >= maxSize)  //the list is full
            System.err.println("Cannot insert in a full list.");
        else
        {
              list[length] = insertItem;  //insert the
                                          //item at the end
              length++; //increment the length
        }
    } //end insertEnd


       //Method to replace the element in the list at
       //the position specified by location with repItem.
       //Postcondition: list[location] = repItem
       //               If location is out of range, an
       //               appropriate message is output.
    public void replaceAt(int location, T repItem)
    {
        if (location < 0 || location >= length)
            System.err.println("The location of the item to "
                             + "be replaced is out of range.");
        else
            list[location] = repItem;
    } //end replaceAt

       //Method to remove an item from the list.
       //The parameter removeItem specifies the item to
       //be removed.
       //Postcondition: If removeItem is found in the list, it
       //               is removed from the list and length is
       //               decremented by one.
    public void remove(T removeItem)
    {
        int loc;

        if (length == 0)
            System.err.println("Cannot delete from an "
                             + "empty list.");
        else
        {
            loc = seqSearch(removeItem);

            if (loc != -1)
                removeAt(loc);
            else
                System.out.println("The item to be deleted "
                                 + "is not in the list.");
        }
    } //end remove
}