package chiffre;

/**
 * Funktionen zur statistischen Auswertung des Geheimtextes
 * 
 * @author Christian Semrau
 * <a href="mailto:Christian.Semrau@student.uni-magdeburg.de">
 * Christian.Semrau@student.uni-magdeburg.de</a>
 */
import java.util.*;
class Statistik{
	private String text; // zu untersuchender String
	int[] haufigkeiten; // Haeufigkeiten der Buchstaben
	Hashtable folgen; // Haeufigkeiten von Zeichenfolgen


	private class Haeuf{
		String anz;
		String text;
		String dist;
		Haeuf(String a, String t, String d){anz = a; text = t; dist = d;}
		public String toString(){ return anz+" - "+text+dist;}
	}

	int calcIndex;
	private static String cspc = "        ";
/**
 * 
 * @param s java.lang.String
 */
public Statistik(String s) {
	text = s;
	haufigkeiten = new int[26];
	folgen = new Hashtable(300,0.80f);

	for (int i=0; i<text.length(); i++){
		char c = text.charAt(i);
		if ((c>='a' && c<='z') || (c>='A' && c<='Z'))
			haufigkeiten[(c>='a' && c<='z') ? (c-'a') : (c-'A')]++;
	}

	calcIndex = 0;
}
/**
 * 
 */
public boolean calculate() {
	if (text==null) return false;
	if (text.length()<6) return false;

	int fin = Math.min(text.length()-3,calcIndex+10+(100000/text.length()));
	for (int i=calcIndex; i<fin; i++){
		for (int j=i+3; j<text.length(); j++){
			StringBuffer buf = new StringBuffer();
			int k = 0;
			while ((j+k<text.length()) && text.charAt(i+k)==text.charAt(j+k)) {
				buf.append(text.charAt(i+k));
				k++;
			};
			if (k<3) continue;

			String z = buf.toString();
			Vector v;
			if (!folgen.containsKey(z)){
				v = new Vector();
				folgen.put(z, v);
			}else{
				v = (Vector)folgen.get(z);
			}
			v.addElement(new Integer(j-i));
		}
	}
	calcIndex = fin;
	if (text.length()-3==fin)
		return false;
	else
		return true;
}
/**
 * 
 * @return int
 * @param h1 Haeuf
 * @param h2 Haeuf
 */
public static int compare(Haeuf h1, Haeuf h2) {
	int l = h2.anz.compareTo(h1.anz);
	if (l!=0) return l;
	l = compare(h1.text, h2.text);
	return l;
}
/**
 * 
 * @return int
 * @param s1 java.lang.String
 * @param s2 java.lang.String
 */
public static int compare(String s1, String s2) {
	int l = s1.length()-s2.length();
	if (l!=0) return l;
	l = s1.toUpperCase().compareTo(s2.toUpperCase());
	if (l!=0) return l;
	return s1.compareTo(s2);
}
/**
 * 
 * @return java.lang.String
 */
public String getGGTs() {
	// alle Distanzen sammeln
	Vector vl = new Vector();
	for (Enumeration enum = folgen.keys(); enum.hasMoreElements(); ){
		Vector v = (Vector)folgen.get(enum.nextElement());
		for (Enumeration el = v.elements(); el.hasMoreElements(); )
			vl.addElement(el.nextElement());
	}
	// die Distanzen in ein Feld kopieren
	int[] liste = new int[vl.size()];
	int index = 0;
	for (Enumeration enum = vl.elements(); enum.hasMoreElements(); ){
		liste[index++] = ((Integer)enum.nextElement()).intValue();
	}
	// GGTs berechnen
	int[] GGTs = new int[100];
	int delta = 5;
	for (int i=0; i<liste.length-delta; i++){
		int ggt = liste[i];
		for (int j = 1; j<delta; j++)
			ggt = ggT(ggt, liste[i+j]);
		if (ggt>1 && ggt<100)
			GGTs[ggt]++;
	}
	// sortieren
	String[] sListe = new String[GGTs.length];
	for (int i=0; i<GGTs.length; i++)
		sListe[i] = right(Integer.toString(GGTs[i]),5) + " -" + right(Integer.toString(i),3);
	sortQuick(sListe);
	// in einem String sammeln
	StringBuffer buf = new StringBuffer();
	index = 0;
	while(index<100 && !sListe[index].startsWith("    0")) {
		buf.append(sListe[index++]);
		buf.append("\n");
	}
	return buf.toString();
}
/**
 * 
 * @return java.lang.String
 */
public String getOnes() {
	// Haeufigkeiten zu Strings machen
	Haeuf[] liste = new Haeuf[26];
	for (int i=0; i<26; i++){
		liste[i] = new Haeuf(
			right(Integer.toString(haufigkeiten[i]),5),
			(char)(i+'a')+"",
			"");
	}
	sortQuick(liste);
	// in einem String sammeln
	StringBuffer buf = new StringBuffer();
	for (int i=0; i<26; i++){
		buf.append(liste[i]);
		buf.append("\n");
	}
	return buf.toString();
}
/**
 * 
 * @return java.lang.String[]
 */
public String getSorted() {
	// Liste mit Strings der Zeichenfolgen und Distanzen anlegen
	Enumeration enum = folgen.keys();
	Haeuf[] liste = new Haeuf[folgen.size()];
	int[] haufigkeit = new int[folgen.size()];
	// alle Zeichenfolgen durchlaufen
	for (int i=0; enum.hasMoreElements(); i++){
		String s = (String)enum.nextElement();
		Vector v = (Vector)folgen.get(s);
		haufigkeit[i] = (v).size();
		String anz = right(Integer.toString(haufigkeit[i]), 4);
		String text = s;
		StringBuffer b = new StringBuffer();
		// die Distanzen durchlaufen
		for (Enumeration el = v.elements(); el.hasMoreElements(); )
			b.append(", ").append(el.nextElement());
		String dist = b.toString();
		liste[i] = new Haeuf(anz, text, dist);
	}
	sortQuick(liste);
	// in einem String sammeln
	StringBuffer buf = new StringBuffer();
	for (int i=0; i<liste.length; i++){
		buf.append(liste[i]);
		buf.append("\n");
	}
	return buf.toString();
}
/**
 * Liefert den gr&ouml;&szlig;ten gemeinsamen Teiler zweier
 * <code>int</code>-Zahlen.
 */
public static int ggT(int a, int b) {
  int r;
  do {
	r = a % b;		// Rest bilden
	a = b; b = r;	// Vorbereitung fuer naechsten Schritt
  } while (r != 0);	// solange Rest ungleich 0
  // der ggT ist jetzt in a
  return(a);
}
/**
 * 
 * @return int
 */
public int percDone() {
	if (text==null!=text.length()<=0) return 0;
	return (int)(((float)calcIndex/text.length())*100);
}
/**
 * Gibt einen rechtsbuendig auf n Zeichen formatieren <code>String</code> zurueck.
 * Ist der <code>String</code> s zu lang, wird er unveraendert zurueckgegeben.
 * Zahlen kann man mit right(long, int) rechtsbuendig ausgeben.
 * @return String - rechtsbuendig formatierter String
 * @param s String - der zu formatierende String
 * @param n int - die Anzahl der Zeichen (wird links mit Leerzeichen aufgefuellt)
 */
public static String right(String s, int n) {
	return (spc(n-s.length()) + s);
}

static void sortQuick (int[] array) {
  sortQuick2(array, 0, array.length - 1);
}

static void sortQuick (Haeuf[] S) {
  sortQuick2(S, 0, S.length - 1);
}

static void sortQuick (String[] S) {
  sortQuick2(S, 0, S.length - 1);
}
static void sortQuick2(int[] array, int l, int r) {
  int lo = l,hi = r;
  if (hi > lo) {
	// Pivotelement bestimmen
	int mid = array[(lo + hi) / 2];
//	System.out.println(feldOut(array)+" "+mid);
	while (lo <= hi) {
	  while ((lo < r) && ((array[lo]-mid)<0)) lo++; 
	  while (( hi > l ) && ((array[hi]-mid)>0)) hi--;
	  if (lo <= hi) {
		if (lo<hi) {
	      int tmp = array[lo]; array[lo] = array[hi]; array[hi] = tmp;
		};
		lo++; hi--;
	  }
	}
//	System.out.println(feldOut(array));
	// linke Partition sortieren
	if (l < hi) sortQuick2(array, l, hi);
	// rechte Partition sortieren
	if (lo < r) sortQuick2(array, lo, r);
  }
}

static void sortQuick2(Haeuf[] S, int l, int r) {
  int lo = l,hi = r;
  if (hi > lo) {
	// Pivotelement bestimmen
	Haeuf mid = S[(lo + hi) / 2];
	while (lo <= hi) {
	  while ((lo < r) && compare(S[lo],mid)<0) lo++;
	  while (( hi > l ) && compare(S[hi],mid)>0) hi--;
	  if (lo <= hi) {
		if (lo < hi) {
			Haeuf s = S[lo]; S[lo] = S[hi]; S[hi] = s;
		}
		lo++; hi--;
	  }
	}
	// linke Partition sortieren
	if (l < hi) sortQuick2(S, l, hi);
	// rechte Partition sortieren
	if (lo < r) sortQuick2(S, lo, r);
  }
}

static void sortQuick2(String[] S, int l, int r) {
  int lo = l,hi = r;
  if (hi > lo) {
	// Pivotelement bestimmen
	String mid = S[(lo + hi) / 2];
	while (lo <= hi) {
	  while ((lo < r) && compare(S[lo],mid)<0) lo++;
	  while (( hi > l ) && compare(S[hi],mid)>0) hi--;
	  if (lo <= hi) {
		if (lo < hi) {
			String s = S[lo]; S[lo] = S[hi]; S[hi] = s;
		}
		lo++; hi--;
	  }
	}
	// linke Partition sortieren
	if (l < hi) sortQuick2(S, l, hi);
	// rechte Partition sortieren
	if (lo < r) sortQuick2(S, lo, r);
  }
}
/**
 * Liefert einen <code>String</code>, der <code>len</code> Mal das Leerzeichen enthaelt.
 * @return String
 * @param len int - Die gewuenschte Laenge der Zeichenkette
 */
public static String spc(int len) {
  if (len<=0) return "";
  while (len>cspc.length())
	cspc += cspc;
  return cspc.substring(0,len);
}
}