/****************************************************************\
 * Program Name: DispConWeb                                     *
 * File: Normalize.java                                         *
 * Author: Steve Palmer                                         *
 * Date: 2/11/7                                                 *
 *                                                              *
 * Purpose:                                                     *
 * Mostly for play.                                             *
 *                                                              *
 * A set of functions to demonstrate some observed methods for  *
 * performing integer base conversion.  The first functions,    *
 * implemented 2/11/7 and before, perform base conversion when  *
 * one base is a multiple of another.                           *
 *                                                              *
 * To convert from base B to base B/F, the conversion is done   *
 * as follows. (ignore variable/parameter names for now)        *
 * B0 <- Source base.                                           *
 * B1 <- Target base.                                           *
 * F <- Factor which gives B0 when multiplied by B1             *
 * N <- Numeral                                                 *
 * {d_k, d_k-1, ... d_1, d_0} <- Digits of N.                   *
 * m_i in {m_k, m_k-1, ... m_1, m_0} <- F^i (i -> k...0)        *
 * C <- {d_k(m_k), d_k-1(m_k-1),... ,d_0(m_0)}                  *
 *                                                              *
 * At that point, C contains coefficients for a polynomial,     *
 * equivalent to N, but in terms of (X/F).                      *
 *                                                              *
 * Digit normalization utilizes borrowing and carrying to       *
 * convert a polynomial into a legal numeral in base B1.        *
 *                                                              *
 * Converting from base B to base B(F) is a little trickier.    *
 * The method is something like this:                           *
 * B0 <- Source base                                            *
 * B1 <- Target base                                            *
 * F  <- Integer that gives B1 when multiplied by B0.           *
 * N  <- Numeral.                                               *
 * {d_k, d_k-1, ... d_1, d_0} <- Digits of N.                   *
 * m_i in {m_k, m_k-1, ... m_1, m_0} <- F^i (i -> 0..k)         *
 * C0 <- { d_k(m_0), d_k-1(m_1), ..., d_k-1(m_k-1), d_0(m_k) }  *
 * C  <- for d_i in C0 (i->k,k-1,...0)                          *
 *    d1_i <- d_i/m_k                                           *
 *    d1_i-1 <- (d_i-1 + B1(d_i % m_k))/m_i-1                   *
 *                                                              *
 * Like before, C contains coefficients for a polynomial in     *
 * terms of B(F).  Digit normalization (borrowing/carrying)     *
 * makes it a legal numeral.                                    *
 *                                                              *
 * Revision History:                                            *
 *   2/10/7 - Base conversion methods written and string I/O    *
 *            enabled.                                          *
 *   2/16/7 - Modified to handle positive integers with         *
 *            negative bases.                                   *
 *   2/26/7 - Working on Pascal's Triangle conversion for       *
 *            non-multiple bases.                               *
 *            ^^^ Needs to be compiled with PascalT.java now ^^^*
 *   3/4/7  - It's not pretty, but I think it's working for     *
 *            both offsets and multiples.  If one base is a     *
 *            multiple of another, it uses the appropriate      *
 *            multiple routine.  Otherwise it uses powers of    *
 *            Pascal's Triangle matrices.                       *
 *   3/5/7  - Removed debugging print-outs.                     *
 *   5/6/7  - Removed oldmain loop.  This is now part of a GUI  *
 *            executable provided by DispCon.java. Put into RCS *
 *                                                              *
 * Known Problems:                                              *
 *   - Weak data validation.                                    *
 *   - Pass integer by reference kludge should be fixed,        *
 *     probably by a custom data type.  I kludged it because    *
 *     Vector.size() and Vector.remove*() seem not to do quite  *
 *     what I expected.  I had to manually track the number of  *
 *     digits/coefficients in the Vector.                       *
 *                                                              *
 * To-Do list:                                                  *
\***************************************************************/
import java.io.*;
import java.math.*;   // Needed for BigInteger
import java.util.*;   // Needed for Vector and/or ArrayList

public class Normalize
{
    /*
     * Convert between bases where the target is a multiple of the source.
     */
    public static void bGrow (Vector <BigInteger> numeral,
                              int rFactor,
                              int Base,
                              int termSize[])
    {
	BigInteger multBy=BigInteger.ONE;
	BigInteger Factor=new BigInteger (Integer.toString(rFactor));
	BigInteger Holder;

	/*
	 * Multiply digits, right to left, by
	 * increasing consecutive powers of rFactor.
	 */
	for ( int lcv=termSize[0]-1; lcv > -1; lcv-- ) {
	    Holder = numeral.elementAt(lcv);    // Leftmost unprocessed digit.
	    numeral.removeElementAt(lcv);       // Remove digit from list.
	    numeral.add(lcv, Holder.multiply(multBy));  // Multiply by corresponding power
                                                        // of inter-base factor.
	    multBy = multBy.multiply(Factor);           // Get next multiple.
	    /*
	     * Show steps if desired.
	     */
	    // showList(numeral, termSize);
	}
	multBy = multBy.divide(Factor);         // Get highest multiple.

	// Now we have digits that are multBy times too big.
	// Divide multBy out of each digit.
	BigInteger Remnant = BigInteger.ZERO;
	for (int lcv=termSize[0]-1;lcv>-1; lcv--) {
            /*
             * Get leftmost digit into Holder and remove it from the numeral.
             */
	    Holder = numeral.elementAt(lcv);
	    numeral.remove(lcv);

            /*
             * Add left-over from previous division, then divide by multBy.
             */
	    Holder = Holder.add(Remnant);
	    Remnant =
               Holder.remainder(multBy).multiply(BigInteger.valueOf(Base));
	    Holder = Holder.divide(multBy);

            /*
             * Put result into the numeral at the current position.
             */
	    numeral.add(lcv,Holder);
	    /*
	     * Show steps if desired.
	     */
	    // showList(numeral, termSize);
	}
    } // End bGrow()

    /*
     * Convert between bases where the source is a multiple of the target.
     */
    public static void bReduce (Vector <BigInteger> numeral, int rFactor, int Base, int termSize[])
    {
	BigInteger multBy=BigInteger.ONE;
	BigInteger Factor=new BigInteger (Integer.toString(rFactor));
	BigInteger Holder;

	for ( int lcv=0; lcv < termSize[0]; lcv++ ) {
            /*
             * Put leftmost digit into holder. Remove it from numeral.
             */
	    Holder = numeral.elementAt(lcv);
	    numeral.removeElementAt(lcv);
            
            /*
             * Multiply holder by corresponding power of interbase multiple.
             * Put result into numeral.
             */
	    numeral.add(lcv, Holder.multiply(multBy));
            
            /*
             * Get next power of interbase multiple.
             */
	    multBy = multBy.multiply(Factor);
	    
            /*
	     * Show steps if desired.
	     */
	    // showList(numeral, termSize);
	}
    } // End bReduce().

    /*
     * Return true if digits are legal.  False otherwise.
     */
    public static boolean isNormal( BigInteger Curr,
                                 BigInteger Prev, 
				 int base,
                                 int pass,
                                 int size)
    {
	BigInteger NormalBase = BigInteger.valueOf(base);

	if (
	    (Curr.abs().compareTo(NormalBase.abs()) >= 0) ||
	    (Prev.abs().compareTo(NormalBase.abs()) >= 0) ||
	    (Curr.compareTo(BigInteger.ZERO) < 0) ||
	    (Prev.compareTo(BigInteger.ZERO) < 0 ) ||
	    (pass < size)
	    ) {
	    return false;
	} else {
	    return true;
	}
    } // end isNormal()

    /*
     * Normalize digits in a base.  Make sure all coefficients are legal digits
     * in the base.
     */
    public static void normalDigs(Vector <BigInteger> C,
				  int Base, int termSize[])
    {
	int lcv = 0, lastInd=termSize[0]-1, lSize=lastInd+1;

	BigInteger Holder = C.elementAt(lcv);
	BigInteger Predecessor;
	if (lcv < lastInd) {
	    Predecessor = C.elementAt(lcv+1);
	} else {
	    Predecessor = BigInteger.ZERO;
	}

	while ( isNormal (Holder, Predecessor, Base, lcv, lSize) == false) {
	    if ( Holder.compareTo(BigInteger.ZERO) < 0) {
		// Borrowing to get digit above 0.
		Predecessor =
		    Predecessor.add (Holder.divide(BigInteger.valueOf(Base)));
		Holder = Holder.remainder(BigInteger.valueOf(Base));
		if ( Base > 0 ) {
                    // Positive bases
		    if ( Holder.compareTo(BigInteger.ZERO) < 0) {
			Holder = Holder.add(BigInteger.valueOf(Base));
			Predecessor = Predecessor.subtract(BigInteger.ONE);
		    }
		} else {
                    // Negative bases
		    if (Holder.compareTo(BigInteger.ZERO) != 0) {
			Holder = Holder.subtract(BigInteger.valueOf(Base));
			Predecessor = Predecessor.add(BigInteger.ONE);
		    }
		}
	    } else if
		(Holder.compareTo(BigInteger.valueOf(Base).abs()) >= 0) {
		// Carrying to get digit below <Base>
		Predecessor = Predecessor.add
		    (Holder.divide(BigInteger.valueOf(Base)));
		Holder = Holder.remainder(BigInteger.valueOf(Base));
	    }

	    C.removeElementAt(lcv);
	    C.add(lcv, Holder);
	    if (lcv < lastInd) {
		C.removeElementAt(lcv+1);
	    }
	    C.add(lcv+1, Predecessor);
            /*
             * Show steps if desired.
             */
            // showList(C,termSize);
	    // System.out.println("Added " + Holder + ", " + Predecessor);

	    lcv++;
	    Holder = Predecessor;
	    if (lcv < lastInd ) {
		Predecessor = C.elementAt(lcv+1);
	    } else {
		Predecessor = BigInteger.ZERO;
	    }
	}
	if (Holder.compareTo(BigInteger.ZERO) != 0)
	    lcv++;

	termSize[0] = lcv;
    }

    public static BigInteger[][] stuffMat(Vector<BigInteger> Cset, int lSize[]) {
	BigInteger[][] LocalDigits = new BigInteger[1][lSize[0]];
	for (int lcv=0; lcv<lSize[0]; lcv++)
	    LocalDigits[0][lcv] = Cset.elementAt(lSize[0] - lcv - 1);
	return LocalDigits;
    }

    public static Vector<BigInteger> dumpMat(BigInteger[][] HeldMat, int lSize[]) {
	Vector<BigInteger> LocalDigits = new Vector<BigInteger> ();

	for (int lcv=0; lcv<lSize[0]; lcv++) {
	    LocalDigits.add(lcv, HeldMat[0][lSize[0] - lcv - 1]);
	}

	return LocalDigits;
    }

    /*
     * Display a list of coefficients and/or digits.
     * The rightmost digit is in position 0.
     */
    public static void showList( Vector <BigInteger> Cset, int lSize[])
    {
	System.out.print("[");
	for (int lcv=lSize[0]-1; lcv>-1; lcv--) {
	    System.out.print(Cset.elementAt(lcv));
	    if (lcv > 0)
		System.out.print (" ");
	}
	System.out.println("]");
    }

    public static String Digits()
    {
	return ("0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ" +
                "abcdefghijklmnopqrstuvwxyz" +
		"`~!@#$%^&*()-_=+[]{}\\|;:,.<>/?\'\"");
    }

    public static String listToNum (Vector <BigInteger> L, int Size[]) {
	String tempStr="", DL=Digits();
	int fnum=0;

        for (int lcv=Size[0]-1; lcv>-1; lcv--) {
	    if ( L.elementAt(lcv).compareTo(BigInteger.ZERO) == 0 ) {
		fnum++;
	    } else {
		break;
	    }
	}

	for (int lcv=Size[0]-fnum-1;lcv>-1;lcv--) {
	    int spos=L.elementAt(lcv).intValue();
	    int epos=spos+1;
	    if (epos > DL.length()) {
		System.err.println("I don't have that many digits");
		System.exit(-1);
	    }
	    tempStr = tempStr + DL.substring(spos,epos);
	}
	// System.out.print(tempStr);
        return tempStr;
    }

    public static void printRuler()
    {
	int nextTen = 1;
	for (int lcv=0;lcv<94;lcv++) {
	    if ((lcv % 10) == 0) {
		if (lcv != 0) {
		    System.out.print(nextTen++);
		} else {
		    System.out.print(" ");
		}
	    } else {
		System.out.print(" ");
	    }
	}
	System.out.println("");

	for (int lcv=0;lcv<94;lcv++)
	    System.out.print(lcv%10);

	System.out.println("");
	System.out.println(Digits());
	System.out.println("");
    }
		
    public static Vector<BigInteger> strToList (String Numeral)
    {
	String DL = Digits();
	Vector<BigInteger> digitList = new Vector<BigInteger>();

	// for (int lcv = Numeral.length(); lcv > -1; lcv--)
	for (int lcv=0; lcv<Numeral.length(); lcv++ )
	    for (int lcv1=0; lcv1<DL.length(); lcv1++) {
		int left=Numeral.length() - lcv - 1;
		int right = left+1;
		if (DL.substring(lcv1,lcv1+1).equals(Numeral.substring(left, right))) {
		    digitList.add(lcv, BigInteger.valueOf(lcv1));
		}
	    }
        return (digitList);
        // Returns list of digits in reverse order.
    }
}