/* -*- Mode: c++ -*-
 * @(#) CryptoGram.java 1.0 6/10/97 Ralph Morelli
 *
 * Classes: CryptoGram  FreqRecord FreqVector
 * Author: Ralph Morelli, Trinity College (ralph.morelli@trincoll.edu)
 * 
 * Copyright (c) 1996 Ralph Morelli. All Rights Reserved.
 *
 * Permission to use, copy, modify, and distribute this software
 * and its documentation for NON-COMMERCIAL purposes and
 * without fee is hereby granted provided that this copyright
 * notice appears in all copies. 
 */

/**
 * A class to store letter frequencies.
 */

class FreqRecord {
  int count;
  char letter;
  
  FreqRecord (int count, char letter) {
    this.count = count;
    this.letter = letter;
  }
} // FreqRecord

class FreqVector {
  private FreqRecord freq[];

  FreqVector() {
    freq = new FreqRecord[26];
    for (int k = 0; k < 26; k++) {
      freq[k] = new FreqRecord(0, (char)('a' + k)) ;
    }
  }

  public void reInitFreq() {
    for (int k = 0; k < 26; k++) {
      freq[k].count = 0;
      freq[k].letter = (char)('a' + k) ;
    }
  }
	
  /**
   * Counts the letters in the current cipher and
   * stores them in the frequency vector. 
   * Calls a sort to sort frequency vector.
   * @param s the cipher string
   */
  public void countLetters( String s ) {
    for (int k = 0; k < s.length(); k++) {
      char ch = s.charAt(k);
      if (ch >= 'A' && ch <= 'Z')
	ch = (char)(ch + 32);
      if (ch >= 'a' && ch <= 'z')
	freq[ ch  - 'a'].count += 1;
    }
    sortFreq(freq,freq.length-1);

  }
	
  /**
   * Returns the top 8 most frequent letters in 
   * the frequency vector.
   * @return a string of letters
   */
  public String getTopFreq() {
    String temp = "";
    for (int k = 0; k < 8; k++ )  {
      temp = temp + (char)(freq[k].letter - 32) + ", ";
      //  System.out.println(freq[k].count);
    }
    return temp;
  }
	
  /**
   * Sorts the frequency array using a recursive
   * selection sort.
   * @param a the frequency array
   * @param n the length of the array
   */
  private void sortFreq (FreqRecord a[], int n) {	// recursive selection sort
    FreqRecord temp;
    if (n == 0)
      return;
    else {		// recursive case
      int min = a[n].count;					// let nth be min so far
      int minL = n;
      for (int k = n-1; k >= 0;  k--) {   // for entire array
	int next = a[k].count;			// get next  
	if (next < min) {				// if greater than max
	  min = next;					//  remember it
	  minL = k;
	}	// if next
      } // for each card
      temp = a[n];					// swap max and nth
      a[n] = a[minL];	
      a[minL] = temp;
      sortFreq(a, n-1);					// sort the rest of the arr
    } // recursive case
  } //  sort
  

} // FreqVector class

/**
 * A class to support making and breaking of simple
 * substitution cryptograms. 
 * @version  1.0 6/10/97
 * @author Ralph Morelli
 */
class CryptoGram {
  public static char NULL_CHAR = '*';
  private int NHINTS = 8;
  
  private char theKey[] = new char[26];	      // key for 'a' to 'z'
  private FreqVector freq = new FreqVector(); // letter frequency vector
  
  private String cipherText;		// remains unchanged 
  private String plainText;
	
  String hint[];			// an array of hints
  int hintPtr;				// pointer to next hint
		
  CryptoGram ( )  {			// Default Constructor
    cipherText = new String("") ;			
    plainText = new String("") ;
    initKey();
    freq.reInitFreq();
    initHints();
  }

  /**
   * Construct the initial cryptogram from a String.
   * @param s the String
   */
  CryptoGram ( String s)  {	
    setCipherText( s ) ;			
    plainText = new String("") ;
    initKey();
    freq.reInitFreq();
    initHints();
  }
		
  /**
   * Resets the cryptogram. 
   */
  public void reset() {
    cipherText = "";
    plainText = "";
    initKey();
    freq.reInitFreq();
  }
	
  /**
   * Initializes the key
   */
  public void initKey() {
    for (int k = 0; k < 26; k++)
      theKey[k] = NULL_CHAR;
  }
	
  /**
   * Initializes an array of canned hints.
   */
  private void initHints() {
    hintPtr = 0;
    hint = new String[NHINTS];
    hint[0] = "Frequent English letters: E, T, A, O, N, R, I, S, H" ;
    hint[1] = "Frequent double letters: LL,EE,SS,OO,TT,FF,RR,NN,PP,CC,MM,GG" ;
    hint[2] = "Frequent 2 letter words: OF,TO,IN,IS,IT,BY,HE,AS,ON,AT,AN,OR" ;   
    hint[3] = "Frequent bigrams: TH,HE,AN,RE,ER,IN,ON,AT,ND,ST,ES,EN "  ;
    hint[4] = "Frequent 3 letter words: THE,AND,FOR,ARE,WAS,BUT,ONE,HIS,HAS,HAD"  ;
    hint[5] = "Frequent trigrams: ING,ION,ENT,ERE,TIO,THA,ATE,AND,EVE,HAT,VER,HER " ;
    hint[6] = "Frequent English initial letters: T,A,O,S,W,I,H,C,B,F,P,M"  ;
    hint[7] = "Frequent English terminal letters: E,S,D,T,N,Y,F,R,O,H,G,A"  ;
  }
	
  /**
   * Returns the next canned hint where hintPtr defines next.
   * @return the next hint in the hint array.
   */
  public String getHint() {
    String temp = hint[hintPtr];
    if (hintPtr == NHINTS-1) {
      hintPtr = 0;
      return "Most frequent letters in this cryptogram: " + freq.getTopFreq()  ;
    }
    else hintPtr++;
    return temp;
  }
  
  /**
   * Determines if the cryptogram key is consistent -- i.e.,
   * maintains a 1-1 mapping from {'A'..'Z'} to {'A'.. 'Z'}
   * @param key an integer array storing the key
   * @return true if the key is consistent and false otherwise
   */
  public boolean isValidKey( int key ) {     // works just for 'a' to 'z' 
    
    if (key >= 'a' && key <= 'z') {			// if key is a letter
      int k;
      for (k = 0; k < 26 && theKey[k] != (char)key; k++) ;	// bodyless loop
      if ( k < 26 )
	return false;
      else
	return true;
    }
    else if ( key == '*' )					// if key is NULL_CART
      return true;
    return false;
  } // isValidKey	
  
  /**
   * Creates a mapping between a cipher and plain character
   * and then applies the entire key to the cryptogram.
   * @param cipherCh is the cipher character
   * @param plainCh is the plaintext character
   */
  public void setKeyChar( int cipherCh, int plainCh) {
    theKey[ cipherCh ] = (char) plainCh ;
    translate();
  }
  
  /**
   * Generates an entire key from a keyword where the keyword
   * has been installed in the first k locations of theKey[].
   * This assumes that the first NULL_CHAR marks the end of 
   * the keyword.
   * @return the keyword
   */
  public String generateKey() {
    String keyWd = "";		  // initialize the KEYWORD

    for (int k = 0; k < 26; k++)  // find the end of the KEYWORD
      if (theKey[k] != NULL_CHAR)		
	keyWd = keyWd + theKey[k];
      else break; 
    int k = keyWd.length();
                                // fill in the rest of the KEY
    for (int ch = 'a'; ch <= 'z'; ch++ ) { 
      if (keyWd.indexOf(ch) == -1) 
	theKey[k++] = (char) ch;
    }
    return keyWd;
  }
  
  /**
   * Returns the mapping for a given character in theKey.
   * @param ch the character to be mapped
   * @return the character's mapping.
   */
  public char getPlainCh( int ch ) {
    return theKey[ch];
  }

  /**
   * Sets the ciphertext from a given string.
   * @param s the String
   */
  public void setCipherText( String s ) {
    cipherText = s;
    freq.countLetters( s );
  }
	
  /**
   * Gets the current plaintext for this cryptogram.
   * The key is first applied to generate an up-to-date
   * plaintext.
   * @return  the updated plaintext.
   */
  public String getPlainText( ) {
    translate();
    return plainText;	
  }

  /**
   * Gets the current ciphertext for this cryptogram.
   * @return  the current cipherText.
   */
  public String getCipherText( ) {
    return cipherText;	
  }

  /**
   * Translates ciphertext to plaintext using theKey[]
   */
  private void translate() {
    plainText = "";
    for (int k = 0; k < cipherText.length(); k++) {
      plainText = plainText + enCode( cipherText.charAt(k) ) ;
    }
  } // translate()


  /*----------------------------------------------*/
  // If the character's key is not NULL_CHAR, return its key,
  // otherwise return the original character.
  
  /**
   * Encodes a single character if it is in {a..z}.
   * Case insensitive. The mapping is performed by
   * lookup in theKey.
   * NULL_CHAR's are not encoded
   * @param inChar the character to be encoded.
   * @return the encoded character.
   */
  private char enCode(char inChar){
    char outChar = inChar;
    if (inChar == NULL_CHAR) return inChar;  // just return if NULL_CHAR
    
    if (inChar >= 'A' && inChar <= 'Z') {       // If UPPERCASE character
      inChar = (char)((int)inChar + 32);        //   convert to lowercase
      outChar = theKey[(int)inChar - (int)'a'];	//   and then encode
      
      if (outChar != NULL_CHAR)					// if not NULL
	outChar = (char) ((int)'A' + (int)outChar - (int)'a');	// convert back to UPPERCASE
    }
    else if (inChar >= 'a' && inChar <= 'z') {	// If LOWERCASE 
      outChar = theKey[(int)inChar - (int)'a']; //   just encode
    }
    return outChar;	
  } // Encode
  
}  // class CryptoGram