/*
   Problem 3.1 CES 512 - D. Bozarth - Spring 2005
      Square a polynomial by mimicking Karatsuba's algorithm 
*/

import java.io.*;
import java.util.*;

public class Ex_3_1 {

  /**
   * Main routine.
   * Accepts the coefficients of a polynomial from the keyboard.
   * Accepts from the keyboard the number of times the polynomial should be squared.
   * Displays the entered coefficients.
   * Displays the coefficients of the repeatedly squared polynomial.
   */
	public static void main(String args[]) throws IOException {
	
	   ArrayList arl = new ArrayList();
      int limit = 0;
      
      try {	   
	      limit = getInput(arl);
	   }
	   catch (IOException ex) {
			System.out.println( ex.getMessage() );		
		}
      
      arl = trimPoly(arl);
	   System.out.println();
      System.out.println("p(x):");
      System.out.println("----");
      showPoly(arl);
	   
	   ArrayList arlSqr = new ArrayList(arl);
	   
	   for (int i = 0; i < limit; ++i) {
	      arlSqr = squarePoly(arlSqr);
	   }
	  
      System.out.println();
      System.out.println("{[p(x)]^2}^" + limit + " :");
      System.out.println("-------------");
		showPoly(arlSqr);
		
	}

   
  /**
   * Accept numeric keyboard input, and populate arrayList with Double objects.
   */ 
   public static int getInput( ArrayList arrayList ) throws IOException {

		BufferedReader kb 
			= new BufferedReader( new InputStreamReader(System.in) );

		boolean loop = true;
		double myNum = 0.0;

		while (loop == true) {
		   StringBuffer sb = new StringBuffer();
		   if ( arrayList.size() == 0 ) {
		      sb.append( new String("Enter the zero-order coefficient -or- <Enter> to quit: ") );
		   } 
		   else {
		      sb.append( new String("Enter the next-higher-order coefficient -or- <Enter> to quit: ") );
		   }   

         System.out.println();
   		System.out.print( sb.toString() );
   		System.out.flush();
   		String string = new String( kb.readLine().toString().trim() );
   		
   		if ( string.length() > 0 ) {  		   
   		   arrayList.add( new Double(Double.parseDouble(string)) );
   		}
   		else {
   		   loop = false;
   		}
   		
		}

      System.out.println();
		System.out.print("Enter the number of times to square the polynomial: ");
		System.out.flush();
		String string = new String( kb.readLine().toString().trim() );
		
		Integer myInt = new Integer( Integer.parseInt(string) );
		
		return myInt.intValue();
		  
   }
   

  /** Pre:  All input list elements are Double objects.
   *  Post: If arrayList is empty, then the returned list is empty.
   *          Otherwise, the return value is the polynomial square of arrayList.
   */
   public static ArrayList squarePoly( ArrayList arrayList ) {
      int size = arrayList.size();
      
      if (size == 0) {      
         return new ArrayList();
      }         
       
      if (size == 1) {
         ArrayList arrayListNew = new ArrayList();
         double dub = getDoubleFromArrayList(0, arrayList);
         dub = dub*dub;       
         arrayListNew.add( new Double(dub) );         
         return arrayListNew;
      }
      
      ArrayList arrayListEven = new ArrayList();
      ArrayList arrayListOdd  = new ArrayList();
      
      for ( int i = 0; i < size; ++i) {
         if ( i % 2 == 0 ) {
            arrayListEven.add( arrayList.get(i) ); 
         }
         else {
            arrayListOdd.add( arrayList.get(i) ); 
         }
      }

      arrayListEven = trimPoly(arrayListEven);
      arrayListOdd  = trimPoly(arrayListOdd);
      
      ArrayList arrayListEvenSqr = squarePoly(arrayListEven);
      ArrayList arrayListOddSqr = squarePoly(arrayListOdd);
      ArrayList arrayListSqrSum = sumPlusDouble(arrayListEvenSqr, arrayListOddSqr);
      ArrayList arrayListSumSqr = squarePoly( sumPlusDouble(arrayListEven, arrayListOdd) );
      ArrayList arrayListSqrDif = sumMinusDouble(arrayListSumSqr, arrayListSqrSum);

      // convert y to x^2
      arrayListEvenSqr = y2x(arrayListEvenSqr);
      arrayListOddSqr = shiftRight( 2, y2x(arrayListOddSqr) );
      arrayListSqrDif = shiftRight( 1, y2x(arrayListSqrDif) );    
  
      return trimPoly( sumPlusDouble(  arrayListEvenSqr, 
                                       sumPlusDouble(arrayListOddSqr, arrayListSqrDif) 
                     ));

   }

   
  /** Pre:  arrayList has size greater than the value of n.
   *  Post: The returned list is left-padded with Double objects,
   *           each of whose value is zero. The number of Doubles added
   *           is given by n.        
   */
   public static ArrayList shiftRight( int n, ArrayList arrayList ) {
      ArrayList arrayListNew = new ArrayList(arrayList);
      
      for (int i = 0; i < n; ++i) {
         arrayListNew.add( 0, new Double(0) );
      }
      
      return arrayListNew;
     
   }
    

  /** Pre:  All input list elements are Double objects.
   *  Post: The returned list elements are each the Double-value sum of the 
   *           corresponding input list elements.
   *           Whenever one input list contains an element that has
   *           no corresponding position in the "other" list, a corresponding "other"
   *           list element is presumed to exist with value 0.      
   */
   public static ArrayList sumPlusDouble( ArrayList arrayListOne, ArrayList arrayListTwo ) {      
      return sumDouble(true, arrayListOne, arrayListTwo);
     
   }


  /** Pre:  All input list elements are Double objects.
   *  Post: The returned list elements are each the Double-value difference of the 
   *           corresponding input list elements. arrayListOne contains the minuends.
   *           Whenever one input list contains an element that has
   *           no corresponding position in the "other" list, a corresponding "other"
   *           list element is presumed to exist with value 0.      
   */
   public static ArrayList sumMinusDouble( ArrayList arrayListOne, ArrayList arrayListTwo ) {      
      return sumDouble(false, arrayListOne, arrayListTwo);
     
   }

   
  /** Pre:  All input list elements are Double objects.
   *  Post: If plus is true, then the conditions for sumPlusDouble are implemented.
   *        Otherwise, the conditions for sumMinusDouble are implemented.      
   */
   public static ArrayList sumDouble(  boolean plus, 
                                       ArrayList arrayListOne, ArrayList arrayListTwo ) {
      ArrayList arrayListNew = new ArrayList();
      int one = arrayListOne.size();
      int two = arrayListTwo.size();
      int max = one;
      if (max < two) {
         max = two;
      }
      
      for (int i = 0; i < max; ++i) {
         double sum = 0;
         if (i < one) {
            sum += getDoubleFromArrayList(i, arrayListOne);
         }
         if (i < two) {
            if (plus == true) {
               sum += getDoubleFromArrayList(i, arrayListTwo);
            } 
            else {
               sum -= getDoubleFromArrayList(i, arrayListTwo);
            }
         }
         arrayListNew.add( new Double(sum) );
      }
            
      return arrayListNew;
     
   }


  /** Pre:  All input list elements are Double objects.
   *  Post: The returned list represents all ascending-order coefficients
   *           of a polynomial in x, where the input list is taken to
   *           represent all ascending-order coefficients of
   *           the identical polynomial in y = x*x.      
   */
   public static ArrayList y2x( ArrayList arrayList ) {
      int size = arrayList.size();
      ArrayList arrayListNew = new ArrayList();
      
      for (int i = 0; i < size; ++i) {
         arrayListNew.add(new Double( getDoubleFromArrayList(i, arrayList) ));
         if ( (i + 1) < size ) {
            arrayListNew.add( new Double(0) );
         }
      }
      
      return arrayListNew;   
   }


  /** Pre:  All input list elements are Double objects.
   *  Post: The returned list is identical in numeric value to the input list.
   *        Each zero-value element to the right of the rightmost non-zero-value
   *        element, has been removed from the returned list.      
   */
   public static ArrayList trimPoly( ArrayList arrayList ) {
      ArrayList arrayListNew = new ArrayList(arrayList);
      int right = arrayList.size() - 1;
      
      for (int i = right; i > 0; --i) {
         double dub = getDoubleFromArrayList(i, arrayList);
         if (dub == 0) {
            arrayListNew.remove(i);
         } 
         else {
            break;
         }
      }
      
      return arrayListNew;      

   }
   

  /** Pre:  All input list elements are Double objects.
   *  Post: The value of each element has been sent to the screen in ascending order.      
   */      
   public static void showPoly( ArrayList arrayList ) {
      int size = arrayList.size();
      for (int i = 0; i < size; ++i) {
         System.out.println( getDoubleFromArrayList(i, arrayList) );
      }

   }

   
  /** Pre:  All input list elements are Double objects.
   *  Post: The returned value is that of the Double object contained in the
   *           list element indexed by n.      
   */     
   public static double getDoubleFromArrayList( int n, ArrayList arrayList ) {     
         String string = arrayList.get(n).toString();
         Double ddd = new Double(string);
         return ddd.doubleValue();
         
   }
   
         
}