import java.util.StringTokenizer;

/**
 * The <code>Spy</code> class contains methods to encrypt and decrypt messages,
 * as well as information about the secret code names of Spies that are already operating. <P>
 * 
 * This class should have ONE instance variable (you must <B>not</B> add any other
 * instance variables):<P>
 * <ul>
 * <li>the secret code number of the Spy, with EXACTLY 4 digits (as an <code>int</code>).<P>
 * </ul>
 * 
 * This class should also have ONE static variable (you must <B>not</B> add any other
 * static variables):<P>
 * <ul>
 * <li>the code numbers of all existing Spies (as a <code>String</code>).<BR>
 * <BR>
 * The <code>String</code> has zero or more items stored
 * in this form:<BR>
 * <BR>
 * <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; number:number:etc.</code>
 * <P>
 * where <I>number</I> is the secret code number of a Spy. Each item is separated by a colon (with
 * <B>no</B> space before or after the colon). Also, there should <B>not</B> be a 
 * colon at the beginning or end of the <code>String</code>. 
 * <P>
 * All the numbers in this <code>String</code> must be unique (i.e., no duplicates). Also, the numbers
 * must be ordered (from left to right) in decreasing order: the highest code numbers come first. 
 * 
 * Here is an example:
 * <P>
 * <code>"9076:9075:1234"</code>
 * <P>
 * If there are no Spies, then the <code>String</code> is empty ("").
 * </ul>
 */
public class Spy {
  
  /** The secret code number of the Spy. */
  private int codeNumber;
  
  /** The secret code numbers of all existing Spies. */
  private static String allCodeNums = "";
  
  /**
   * Create a new Spy with code number <I>n</I>;
   * Update the record of all existing code numbers according to the description above;
   * If the specified code number already exists in the record, print a warning message to the
   * user (<B>hint</B>: use System.out.println); You can assume that the user's input will be
   * a 4-digit integer.
   */
  public Spy(int n) {
    this.codeNumber = n;
    this.addCodeNumber(n);
  }
 
  /**
   * Add the specified code number n to the record of all 
   * the code numbers for existing Spies.
   */
  private void addCodeNumber(int n) {
    StringTokenizer st = new StringTokenizer(allCodeNums, ":");
    
    String newCodes = "";
    boolean done = false;
    boolean duplicate = false;
    
    while (st.hasMoreTokens() && !done) {
      int num = Integer.parseInt(st.nextToken()); // get the code number
      
      if (n > num) {
        newCodes = newCodes + n + ":" + num + ":";
        done = true;
      } else if (n == num) {
        // found a duplicate
        System.out.println("This code number already exists in the record!");
        duplicate = true;
        done = true;
      } else {
        newCodes = newCodes + num + ":";
      }
    }
   
    if (done && !duplicate) {
      while (st.hasMoreTokens()) {
        newCodes = newCodes + st.nextToken() + ":";
      }
      allCodeNums = newCodes.substring(0, newCodes.length() - 1);
    } else if (!duplicate) {
      allCodeNums = newCodes + n;
    } else {
      // don't do anything if it's a duplicate - code num already exists!
    }
  }
  
  /**
   * Return the secret code number of this Spy. 
   */
  public int getCodeNumber() {
    return this.codeNumber;
  }
  
  /**
   * Return the code numbers of all existing Spies. 
   */
  public static String getAllCodeNumbers() {
    return allCodeNums;
  }
  
  /**
   * Remove the specified code number <I>c</I> from the record of all
   * existing code numbers; Return <code>true</code> once this is done; 
   * if the specified code number does not exist in the record, return <code>false</code>.
   */
  public static boolean removeCodeNumber(int c) {
    StringTokenizer st = new StringTokenizer(allCodeNums, ":");
    
    String newCodes = "";
    boolean found = false;
    
    while (st.hasMoreTokens()) {
       int num = Integer.parseInt(st.nextToken()); // get the code number
       
       if (num ==  c) { // if the code number to remove is found
         // do nothing - omit this number!
         found = true;
       } else {
         newCodes = newCodes + num + ":";
       }
    }
    
    if (found) {
      if (newCodes.equals("")) { // if only 1 code num existed, and it was removed
        allCodeNums = newCodes;
      } else {
        allCodeNums = newCodes.substring(0, newCodes.length() - 1);
      }
      
      return true;
    } else {
      // do nothing and return false.
      return false;
    }
  }
  
  /**
   * Return the binary representation of character <I>c</I>; 
   * You must do this by first converting the character into an integer ASCII value, and then 
   * converting that integer into an 8-bit binary value; Note that the return type <B>must</B>
   * be a <code>String</code> of length 8; This means that the ASCII value of the given character
   * cannot be more than 255 -- if the character's ASCII value is greater than 255,
   * then return the empty String ("").
   */
  public static String charToBinary(char c) {
    int ascii = (int) c; // get the ASCII value of this character
    
    if (ascii > 255) {
      return "";
    } else {
      return intToBin(ascii, 8);
    }
  }
  
  /**
   * Return the binary representation of integer <I>n</I>, with <I>d</I> digits.
   */
  private static String intToBin(int n, int d) {
    String bin = "";
    int r = 0;
    int q = n;
    
    for (int i = 0; i < d; i++) {
      r = q % 2;
      bin = r + bin;
      q = q / 2;
    }
    
    return bin;
  }
  
  /**
   * Return the result of applying the "exclusive-or" (XOR) operator to integers <I>i</I> and <I>j</I>;
   * You can assume that the input integers will be either 1 or 0, representing true and false, respectively; 
   * This means that this method <B>must</B> return either 1 or 0, depending on the result of 
   * <code>"i XOR j"</code>.
   */
  public static int exclusiveOr(int i, int j) {
    if (i != j) {
      return 1;
    } else {
      return 0;
    }
  }
  
  /**
   * Return a new key that is the result of stretching the given <I>binKey</I> to be AT LEAST as long as
   * the given <I>length</I>; The given <I>binKey</I> must be a String of bits!<BR><BR>
   * The algorithm for this "stretching" is as follows: divide the binary key into two even
   * halves (you can assume that the key has an even number of bits), 
   * then XOR the corresponding bits of each half to produce a new String of bits, and append this
   * new String of bits to the <B>end</B> of the key; If the resulting key is still not as long as the given length,
   * then repeat the process until the key is at least as long as the given length.
   */
  public static String stretch(String binKey, int length) {
    while (binKey.length() < length) {
      String half1 = binKey.substring(0, binKey.length() / 2);
      String half2 = binKey.substring(binKey.length() / 2);
      
      String half3 = "";
      
      for (int i = 0; i < half1.length(); i++) {
        int m = Integer.parseInt(String.valueOf(half1.charAt(i)));
        int k = Integer.parseInt(String.valueOf(half2.charAt(i)));
        
        String e = String.valueOf(exclusiveOr(m, k));
        
        half3 = half3 + e;      
      }
      
      binKey = binKey + half3;
    }
    
    return binKey;
  }
  
  /**
   * Return the encrypted version of the <I>msg</I>, using the given <I>key</I>, according
   * to this <a href="APS101_A2_encrypt.txt">encryption algorithm</a>.
   */
  public static String encrypt(String msg, int key) {
    
    // convert the message into a String of 8-bit binary values
    String binMsg = "";
    
    for (int i = 0; i < msg.length(); i++) {
      char c = msg.charAt(i);
      binMsg = binMsg + charToBinary(c);
    }
    
    // convert the integer key into a 16-bit binary String value
    String binKey = intToBin(key, 16);
    
    // stretch the binary key, from 16-bit to 128-bit
    for (int i = 0; i < 3; i++) {
      binKey = binKey + binKey;
    }
    
    // if the key is shorter than the message
    if (binMsg.length() > binKey.length()) {
      // stretch the key to be AT LEAST the length of the message
      binKey = stretch(binKey, binMsg.length());
    }
    
    // create an encrypted binary String by XOR'ing each bit of the
    // msg and key with each other.
    String encrypted = "";
    for (int i = 0; i < binMsg.length(); i++) {
      int m = Integer.parseInt(String.valueOf(binMsg.charAt(i)));
      int k = Integer.parseInt(String.valueOf(binKey.charAt(i)));
      
      String e = String.valueOf(exclusiveOr(m, k));
      
      encrypted = encrypted + e;      
    }
    
    // return the encrypted binary String
    return encrypted;
  }
  
  /**
   * Return the message that is encoded by binary String <I>e</I>, or 
   * "cannot decrypt" if String e is not composed of 8-bit binary Strings.
   */
  private static String binToMsg(String e) {
    if ((e.length() % 8) != 0) {
      return "cannot decypt";
    }
    
    String msg = "";
    
    for (int i = 0; i < e.length(); i += 8) {
      String nextChar = e.substring(i, i + 8);
      
      int x = 0;
      int y = 128;
      for (int j = 0; j < 8; j++) {
        x += Integer.parseInt(String.valueOf(nextChar.charAt(j))) * y;
        y = y / 2;
      }
      msg = msg + (char) x;
    }
    
    return msg;
  }
  
  /**
   * Return the decrypted version of the <I>encrypted</I> String, using the given <I>key</I>;
   * You should assume that the String was encrypted using Spy's <code>encrypt</code> method;
   * If the encrypted String is not valid (i.e., it is not composed of 8-bit binary Strings), then return
   * <B>"cannot decrypt"</B>.
   */
  public static String decrypt(String encrypted, int key) {
    // convert the integer key into a 16-bit binary String value
    String binKey = intToBin(key, 16);
    
    // stretch the binary key, from 16-bit to 128-bit
    for (int i = 0; i < 3; i++) {
      binKey = binKey + binKey;
    }
    
    // if the key is shorter than the encrypted String
    if (encrypted.length() > binKey.length()) {
      // stretch the key to be AT LEAST the length of the message
      binKey = stretch(binKey, encrypted.length());
    }
    
    // create a decrypted binary String by XOR'ing each bit of the
    // encrypted msg and key with each other.
    String decrypted = "";
    for (int i = 0; i < encrypted.length(); i++) {
      int d = Integer.parseInt(String.valueOf(encrypted.charAt(i)));
      int k = Integer.parseInt(String.valueOf(binKey.charAt(i)));
      
      String e = String.valueOf(exclusiveOr(d, k));
      
      decrypted = decrypted + e;      
    }
    
    String msg = binToMsg(decrypted);
    return msg;
  }
  
}