/**
 * This class implements an inefficient fixed size mutable binary string. The
 * bits of a BitString are indexed by non-negative integers. Individual bits 
 * can be examined, set (made true), cleared (made false), or flipped (set to
 * the opposite value). The logical AND, logical inclusive OR, and and other
 * operations can be used to combine two BitStrings of the same size and to 
 * manipulate BitStrings. By default, all bits in the string initially are 
 * false. Unlike text strings, bit strings indexes increase from right to left
 * i.e. the most significant bits have larger indexes. For example, the 
 * BitString 1011 has ones in indexes 0, 1, and 3. Do not use integer types, 
 * BitSet, or any other Java class to implement the missing methods. You may use
 * the Math Class if needed. 
 */
public class BitString implements Cloneable {
  // An array to hold the bits that make up the bit string.
  private boolean bits[];
  /**
   *  A constant that defines the size of the default bit string.
   */
  public static final int DEFAULT_SIZE = 8;

  /**
   * Creates a new, all false, bit string of the given size. 
   */
  public BitString(int size) {
    if(size < 1) throw new IllegalArgumentException("Size must be positive");
    bits = new boolean[size];
  }

  /**
   * Creates a new all false bit string of size DEFAULT_SIZE.
   */
  public BitString() {
    this(DEFAULT_SIZE);
  }

  /**
   * Creates a new bit string from the give text string of ones and zeros. This
   * method is only to be used for displaying BitStrings and for testing.
   * It is not to be use in implementing other methods.
   */
   public BitString(String s) {
     this(s.length());

     int index = s.length() - 1;
     for (char digit : s.toCharArray())
     {
       switch(digit)
       {
         case '0':
           bits[index] = false;
           break;
         case '1':
           bits[index] = true;
           break;
         default:
           throw new IllegalArgumentException("String " + s + 
                                              "may only contain 0's and 1's.");                 
       }
       --index;
     }
   }
   
  /**
   * Creates a copy of the given bit string.
   */
  @Override
  public Object clone() {
    BitString copy = new BitString(bits.length);
    copy.bits = Arrays.copyOf(bits, bits.length);
    return copy;
  }

  /**
   * Returns a representation of this BitString as a string of 1's and 0's.
   * This method is only to be used for displaying BitStrings and for testing.
   * It is not to be use in implementing other methods.
   */
  @Override
  public String toString() {
    StringBuilder out = new StringBuilder(bits.length);

    for (int index = bits.length - 1; index >= 0; --index) {
      out.append(bits[index] ? 1 : 0);
    }

    return out.toString();
  }

  /**
   * Return the value of a bit string at the given index.
   */
  public boolean get(int index) {
    return bits[index];
  }

  /**
   * Set the value of a bit string at the given index to true.
   */
  public void set(int index) {
    bits[index] = true;
  }

  /**
   * Set the value of a bit string at the given index to false.
   */
  public void clear(int index) {
    bits[index] = false;
  }

  /**
   * Set the value of a bit string at the given index to the opposite value.
   */
  public void flip(int index) {
    bits[index] = !bits[index];
  }

  /**
   * Returns the number of bits in this bit string.
   */
  public int size() {
    return bits.length;
  }

  /**
   * Returns the number of true bits.
   */
  public int populationCount() {
    int count = 0;

    // For each true bit increment count. 
    for (boolean bit : bits) {
      if (bit) {
        ++count;
      }
    }

    return count;
  }

  /**
   * Basic hash code that is compatible with equals.
   * @return 
   */
  @Override
  public int hashCode() {
    int hash = 5;
    hash = 29 * hash + Arrays.hashCode(this.bits);
    return hash;
  }

  /**
   * Two bit strings are equal if they have the same size and same bits.
   */
  @Override
  public boolean equals(Object obj) {
    if (!(obj instanceof BitString)) {
      throw new IllegalArgumentException("obj must be a BitString");
    }

    return Arrays.equals(bits, ((BitString) obj).bits);
  }

  /**
   * An object factory method that creates a bit string corresponding to the 
   * non-negative decimal value n, using size bits. If size is too small to 
   * hold n an InsuffisantNumberOfBitsException is thrown.
   */
  public static BitString decimalToUnsigned(int n, int size) {
    throw new UnsupportedOperationException("This function needs to be completed!");
  }

  /**
   * Turns the bit string into its binary successor. For example, the successor
   * of 101011 is 101100. Returns reference to self for object chains.
   */
  public BitString successor() {
    throw new UnsupportedOperationException("This function needs to be completed!");
  }

  /**
   * Turns bit string into its binary complement. For example, the complement of
   * 101011 is 010100. Returns reference to self for object chains.
   */
  public BitString complement() {
    throw new UnsupportedOperationException("This function needs to be completed!");
  }

  /**
   * Turns bit string into its two's complement. For example, the two's 
   * complement of 101011 is 010101. Returns reference to self for object 
   * chains.
   */
  public BitString twosComplement() {
    throw new UnsupportedOperationException("This function needs to be completed!");
  }

  /**
   * Returns the value of this bit string when interpreted as an unsigned
   * decimal. For example, the string 111 has unsigned value 7.
   */
  public int unsignedValue() {
    throw new UnsupportedOperationException("This function needs to be completed!");
  }

  /**
   * Returns the value of this bit string when interpreted as a signed
   * decimal with the MSB being the sign bit. For example, the string 111 has
   * unsigned value -3.
   */
  public int signedValue() {
    throw new UnsupportedOperationException("This function needs to be completed!");
  }

  /**
   * Returns the value of this bit string when interpreted as a decimal in 
   * one's complement form. For example, in one's complement form the string
   * 111 has the value 0.
   */
  public int onesComplementValue() {
    throw new UnsupportedOperationException("This function needs to be completed!");
  }

  /**
   * Returns the value of this bit string when interpreted as a decimal in 
   * two's complement form. For example, in two's complement form the string
   * 111 has the value -1.
   */
  public int twosComplementValue() {
    throw new UnsupportedOperationException("This function needs to be completed!");
  }

  /**
   * Performs binary addition on bit strings of the same size. If they are
   * not of the same size then a BitSizeMismatchException is thrown. Does not
   * change the receiver.
   */
  public BitString add(BitString rightSummand) {
    throw new UnsupportedOperationException("This function needs to be completed!");
  }

  /**
   * Performs binary subtraction on bit strings of the same size. If they are
   * not of the same size then a BitSizeMismatchException is thrown. Does not
   * change the receiver.
   */
  public BitString subtract(BitString subtrahend) {
    throw new UnsupportedOperationException("This function needs to be completed!");
  }

  /**
   * Performs "logical and" on bit strings of the same size. If they are
   * not of the same size then a BitSizeMismatchException is thrown. Does not
   * change the receiver.
   */
  public BitString logicalAnd(BitString operand) {
    throw new UnsupportedOperationException("This function needs to be completed!");
  }

  /**
   * Performs "logical inclusive or" on bit strings of the same size. If they
   * are not of the same size then a BitSizeMismatchException is thrown. Does not
   * change the receiver.
   */
  public BitString logicalOr(BitString operand) {
    throw new UnsupportedOperationException("This function needs to be completed!");
  }

  /**
   * Performs a left shift by the given non negative amount. For example, the 
   * left shift of 01101 by 2 is 10100. Returns reference to self for object 
   * chains. 
   */
  public BitString leftShift(int amount) {
    throw new UnsupportedOperationException("This function needs to be completed!");
  }

  /**
   * Performs a sign extension by the given non negative amount. For example,
   * the extension of 10101 by 2 is 1110101. Returns reference to self for object 
   * chains.
   */
  public BitString signExtension(int amount) {
    throw new UnsupportedOperationException("This function needs to be completed!");
  }

  /**
   * A run time exception that should be thrown whenever a method does not have
   * enough bits to successfully execute.
   */
  public static class InsufficientNumberOfBitsException extends RuntimeException {}

  /**
   * A run time exception that should be thrown whenever two bit strings should 
   * be of the same size but are not.
   */
  public static class BitSizeMismatchException extends RuntimeException {}
}