/**
 * Die Klasse BitSet2 realisiert eine Bitmenge, d.h. eine
 * Datenstruktur, in der einzelne Bits gesetzt (1), andere
 * nicht gesetzt sind (0). Bspw. repraesentiert die Bitfolge 10011, 
 * dass die Bits 1, 4 und 5 gesetzt und alle anderen Bits
 * nicht gesetzt sind.
 *
 * @version     1.0, 18.02.1998
 * @author      Dietrich Boles
 */
public class BitSet2 implements Cloneable {

  /**
   * in diesem booleschen Array, das als "dynamisches Array" realisiert
   * wird, werden die gesetzten Bits vermerkt, und zwar derart, dass
   * gilt: genau dann, wenn Bit n gesetzt ist, ist bits[n] = true;
   * dabei ist das Array immer genauso gross wie das groesste gesetzte
   * Bit; es wird natuerlich viel Speicher verschwendet, wenn wenige bzw.
   * nur grosse Bits gesetzt sind
   */
  protected boolean[] bits;

  /**
   * Initialisieren einer leeren Bitmenge, d.h. kein Bit ist gesetzt
   * (Default-Konstruktor)
   */
  public BitSet2() {
    this.bits = new boolean[0];
  }

  /**
   * Initialisieren einer Bitmenge mit einer bereits existierenden
   * Bitmenge (Copy-Konstruktor)
   */
  public BitSet2(BitSet2 other) {
    this.bits = new boolean[other.bits.length];
    for (int i=1; i<this.bits.length; i++) {
      this.bits[i] = other.bits[i];
    }
  } 
  
  public Object clone() {
    return new BitSet2(this);
  }

  public String toString() {
    char[] str = new char[this.bits.length];
    for (int i=1; i<this.bits.length; i++) {
      if (this.bits[i]) {
        str[i] = '1';
      } else {
        str[i] = '0';
      }
    }
    return new String(str);
  }

  public boolean equals(Object obj) {
    if ((obj == null) || !(obj instanceof BitSet2)) {
      return false;
    }
    BitSet2 set = ((BitSet2)obj);
    if (this.bits.length != set.bits.length) {
      return false;
    }
    for (int i=1; i<this.bits.length; i++) {
      if (this.bits[i] != set.bits[i]) {
        return false;
      }
    }
    return true;
  }

  /**
   * Setzen eines einzelnen Bits der Bitmenge.
   * @param bit das zu setzende Bit
   * @exception IllParamException falls kein positiver int-Wert als
   *    Parameter uebergeben wird
   */
  public void set(int bit) throws IllParamException {
    if (bit <= 0) throw new IllParamException();
    if (bit >= this.bits.length) {
      this.adapt(bit+1);
    }
    this.bits[bit] = true;
  }

  public void clear(int bit) throws IllParamException {
    if (bit <= 0) throw new IllParamException();
    if (bit < this.bits.length) {
      this.bits[bit] = false;
    }
    this.adapt(this.highest_bit()+1);
  }

  public void and(BitSet2 set) {
    int m = min(this.bits.length, set.bits.length);
    for (int i=1; i<m; i++) {
      this.bits[i] = (this.bits[i] && set.bits[i]);
    }
    for (int i=m; i<this.bits.length; i++) {
      this.bits[i] = false;
    }
    this.adapt(this.highest_bit()+1);
  }

  public void or(BitSet2 set) {
    int m = min(this.bits.length, set.bits.length);
    for (int i=1; i<m; i++) {
      this.bits[i] = (this.bits[i] || set.bits[i]);
    }
    if (set.bits.length > m) {
      this.adapt(set.bits.length);
      for (int i=m; i<set.bits.length; i++) {
        this.bits[i] = set.bits[i];
      }
    }
  }

  public boolean get(int bit) throws IllParamException {
    if (bit <= 0) throw new IllParamException();
    if (bit >= this.bits.length) {
      return false;
    }
    return this.bits[bit];
  }

  // Implementierung des "dynamischen Arrays"
  private void adapt(int new_size) {
    if (this.bits.length != new_size) {
      boolean[] speicher = new boolean[new_size];
      for (int i=1; i<min(speicher.length, this.bits.length); i++) {
        speicher[i] = this.bits[i];
      }
      if (speicher.length > this.bits.length) {
        for (int i=this.bits.length; i<speicher.length; i++) {
          speicher[i] = false;
        }
      }
      this.bits = speicher;
    }
  }

  private int highest_bit() {
    for (int i=this.bits.length-1; i>0; i--) {
      if (this.bits[i]) return i;
    }
    return 0;
  }

  private static int min(int v1, int v2) {
    if (v1 <= v2)
      return v1;
    else
      return v2;
  }

  // sehr einfaches Testprogramm der Klasse BitSet2
  public static void main(String[] args) {
    try {

      BitSet2 set1 = new BitSet2();
      System.out.println(set1);
      // als Ausgabe wird '' erwartet

      set1.set(3);
      set1.set(1);
      set1.set(3);
      set1.set(5);
      set1.set(4);
      set1.set(7);
      System.out.println(set1);
      // als Ausgabe wird '1011101' erwartet

      BitSet2 set2 = new BitSet2(set1);
      set2.clear(1); 
      set2.clear(3);
      set2.clear(7);
      set2.set(6); 
      set2.set(2);
      System.out.println(set2);
      // als Ausgabe wird '010111' erwartet

      BitSet2 set3 = new BitSet2(set2);
      set2.and(set1);
      System.out.println(set2);
      // als Ausgabe wird '00011' erwartet
 
      set3.or(set1);
      System.out.println(set3);
      // als Ausgabe wird '1111111' erwartet

    } catch (IllParamException obj) {
      System.out.println("Ungueltiger Parameter!");
    } catch (Exception obj) {
      System.out.println(obj);
    }
  }

}

class IllParamException extends Exception {}