import algds.IOUtils;
/**
 * AlgDs, WS99, Aufgabe 19.
 * Zahlenkonvertierung von/in beliebige Basen.
 *
 * Erlaubte Basen sind >=2, nach oben keine Grenze (noch nicht).
 * Zahlen muessen >= Long.MIN_VALUE und <= Long.MAX_VALUE sein.
 *
 * Zahlen koennen "am Stueck" eingegeben werden fuer Basis<=36
 * (keine Leerzeichen!) (Variante 1):
 * die Ziffern sind dabei 0..9 und a..z (Gross-/Kleinschreibung egal)
 * z.B. "123456", "ab2d", "-1234" (die negative Zahl -1234)
 *
 * ODER jede Ziffer einzeln als Basis-10-Zahl, mit Leerzeichen getrennt
 * (fuer Basis>36 die einzige Moeglichkeit) (Variante 2):
 * Basis 30: "1 2 29" = "1 2 T" = 30*30+2*30+29 = 989, aber "1 2T" ist keine Zahl!
 * negative Zahlen brauchen in dieser Variante ein Leerzeichen nach dem Minus:
 * Basis 10: "- 1 0 1" = -(100+1) = -101, aber "-1 0 1" = -100+1 = -99
 *
 * Die Ausgabe hat fuer Basen <= 36 immer die Form V1 (Ziffern/Buchstaben)
 * fuer Basen > 37 die Form V2 (Zahlen+Leerzeichen)
 *
 * @author Christian Semrau, 21.11.1999, 26.12.1999
 * <a href="mailto:Christian.Semrau@Student.uni-magdeburg.de">
 * Christian.Semrau@Student.uni-magdeburg.de</a>
 */
class ChS_Tziffern {
// Datentyp fuer eine g-adische Ziffernfolge

  short signum; // Vorzeichen
  int basis;    // Basis des Stellensystems
  int top;      // Anzahl der Ziffern (max. 64 Ziffern: Long.MAX_VALUE basis 2)
  int[] a;      // hoechstwertige Stelle an kleinstem Index

/**
 * Umrechnungstabelle zw. Ziffern+Buchstaben und Zahlen (s. string2ziff und ziff2string)
 */
static final String zahl2ziff = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

/*
 * Konstruktor setzt die Basis auf 10 und initialisiert die anderen Felder.
 */
public ChS_Tziffern() {
  signum=1; basis=10; top=0; a = new int[64];
}

/**
 * Konstruktor &uuml;bernimmt die Basis.
 *
 * @exception NumberFormatException "Basis <=1."
 */
public ChS_Tziffern(int b)
throws NumberFormatException {
  this();
  if (b<=1) throw new NumberFormatException(
	"Basis ("+b+") muss >1 sein.");
  basis = b;
}

/*
 * Verschluesselung der Zahl in Ziffern des neuen Stellensystems.
 *
 * @exception NumberFormatException "Basis <=1."
 */
public ChS_Tziffern(long zahl, int basis)
throws NumberFormatException {
  this(basis);
  // NumberFormatException wenn basis<=1

  if (zahl==0) {  // Sonderfall
	top=1; a[0]=0; return;
  };

  if (zahl<0) { zahl=-zahl; signum = -1; }

  while (zahl!=0) {
  // Abtrennen der Stellen von der kleinsten zur groessten
	a[top++] = (int)(zahl%basis);	// Rest = Stelle
	zahl = zahl/basis;		// Quotient wird weiter bearbeitet
  };

  for (int i=0; i<top/2; i++) {
  // Umkehrung der Ziffernreihenfolge
	int h = a[i];
	a[i] = a[top-i-1];
	a[top-i-1] = h;
  };
  return;
}

/*
 * Umwandung des <code>String</code> in das Stellensystem zur Basis <code>basis</code>.
 *
 * @exception NumberFormatException "Keine Ziffer"
 */
public ChS_Tziffern(String s, int basis)
throws NumberFormatException {
  this(basis);

  int i, v;  String s2;

  s = s.toUpperCase();

  if ((s.indexOf(" ")<0) && (basis<=36)) {
  // keine Leerzeichen und basis<=36 -> Ziffern/Buchstaben
  // Umwandeln in Zahlen+Leerzeichen
	s2 = "";
	if (s.charAt(0)=='-'){
	  signum = -1;
	  s = s.substring(1);  // erstes Zeichen entfernen
	}
	for (i=0; i<s.length(); i++) {
	  char c=s.charAt(i);
	  if (c=='-')  // Minus uebernehmen
	    s2 = s2+'-';
	  else {
	    v = zahl2ziff.indexOf(c);
	    if (v<0) throw new NumberFormatException("Keine Ziffer: "+c);
	    s2 = s2 + v + " ";
	  }
	};
	s = s2;
  };

  while ((s.length()>0) && (s.endsWith(" ")))
	s = s.substring(0,s.length()-1);  // letztes Zeichen entfernen
  s = s+" ";  // genau ein Leerzeichen am Ende

  // die Zeichenkette durchgehen und die einzelnen Zahlen an z anhaengen
  do {
	while ((s.length()>0) && (s.startsWith(" "))) s = s.substring(1);
	// Leerzeichen am Anfang entfernen

	s2 = s.substring(0, s.indexOf(" "));  // einzelne Zahl rausschreiben
	s = s.substring(s.indexOf(" "));      // diese Zahl abtrennen
	if (s2.length()==1) {
	// nur eine Ziffer
	  char c = s2.charAt(0);
	  if (top==0 && c=='-') { // erste "Ziffer" ist nur Minus
		signum = -1;
	  }else{
	    v = zahl2ziff.indexOf(c);
	    if (v<0) throw new NumberFormatException("Keine Ziffer: "+s2);
		a[top++] = v;
	  }
	}else
	if (s2.length()==2 && s2.charAt(0)=='-') {
	// einzelne Ziffer mit Minus
	  char c = s2.charAt(1);
	  v = zahl2ziff.indexOf(c);
	  if (v<0) throw new NumberFormatException("Keine Ziffer: "+s2);
	  v = -v;
	  a[top++] = v;
	}else
	// mehrstellige Zahl Basis 10 mit/ohne Minus
	  try {
	    v = new Integer(s2).intValue();
		a[top++] = v;
	  } catch (NumberFormatException e) {
	  // keine Zahl zur Basis 10
	    throw new NumberFormatException("Keine Zahl: "+s2);
	  }
  } while (!s.equals(" "));

  return;
}

/**
 * Liefert die String-Darstellung der Datenfelder (fuer Tests).
 */
public String Internal() {
  String s = "(basis=" + basis + ", sgn=" + signum + ",";
  for (int i=0; i < top; i++) s = s + " " + a[i];
  return s + ")";
}

/*
 * Erlaubt die Umwandlung einer Zahl beliebiger Basis
 * in eine Zahl beliebiger Basis.
 */
public static void main(String[] args) {
  System.out.println("Umwandlung von Zahlen aus/in beliebige Stellensysteme");
  System.out.println("AlgDs WS99, Aufgabe 19. Christian Semrau");

  String zs;  // String fuer Ein- und Ausgabe
  int b1, b2; // Eingabebasis, Ausgabebasis

  do {
	System.out.print("Basis der Eingabe (0=Ende): ");
	do{ b1 = IOUtils.readInt(); } while(b1<=1 && b1!=0);
	if (b1==0) break; // 0 = Ende
	System.out.print("Basis der Ausgabe: ");
	do{ b2 = IOUtils.readInt(); } while(b2<=1);

	System.out.println("Ziffern der Eingabe (nur Enter=Ende):");
	zs = IOUtils.readString();  // Eingabe der Ziffern als String
	if (zs.length()==0) break;  // Enter = Ende

	try { // es gibt viele Quellen fuer Ausnahmen
	  zs = (new ChS_Tziffern((new ChS_Tziffern(zs, b1)).toLong(), b2)).toString();
	  System.out.println("Ziffern der Ausgabe zur Basis "+b2+":");
	  System.out.println(zs); // Ausgabe der Ziffern als string
	}
	catch (NumberFormatException e) {
	  // z.B. Fehlerhaftes Zahlenformat
	  System.out.println(e.getMessage());
	}
	catch (ArithmeticException e) {
	  // z.B. Zahl zu gross
	  System.out.println(e.getMessage());
	}
  } while(true); // Endlosschleife
  // Abbruch mit Eingabebasis=0 oder Eingabeziffern=""
} // main()

/*
 * Entschluesselung der Ziffern als Ganzzahl.
 *
 * @exception ArithmeticException "Zahl zu gross."
 */
public long toLong()
throws ArithmeticException {
  int i;  long l = 0;

  for (i=0; i<top; i++) {
	if (l>Long.MAX_VALUE/basis)  // naechste Potenz ist zu gross
	  throw new ArithmeticException("Zahl zu gross."
	   +"("+l+">"+Long.MAX_VALUE/basis+")"  );
	l = l*basis;
	if (a[i]>0 && l>Long.MAX_VALUE-a[i])   // naechste Stelle passt nicht mehr
	  throw new ArithmeticException("Zahl zu gross."
	   +"("+l+">"+(Long.MAX_VALUE-a[i])+")"  );
	l = l+a[i];
	// HORNER-Schema: zahl = zahl * basis + ziffer[i];
  };
  return l * signum;
}

/*
 * Liefert die Stringdarstellung der Zahl im <code>basis</code>-Stellensystem.
 */
public String toString() {
  int i;
  String s = "";

  if (basis<=36) {   // Ziffern/Buchstaben
	if (signum==-1) s = s+"-";
	for (i=0; i<top; i++)
	  s = s+zahl2ziff.charAt(a[i]);
  }else{               // Zahlen+Leerzeichen
	if (signum==-1) s = s+"- ";
	for (i=0; i<top; i++)
	  s = s+a[i]+" ";
  }
  return s;
}
} // class tziffern