/**
 * Die Klasse BitSet 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 BitSet implements Cloneable {

  /**
   * in diesem booleschen Array, das als "dynamisches Array" realisiert
   * wird, werden die gesetzten Bits vermerkt, und zwar derart, dass
   * das Array immer nur die gesetzten Bits enthaelt; das Array ist
   * sortiert
   */
  protected int[] bits;

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

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

  public String toString() {
    if (this.bits.length == 0) {
      return "";
    }
    StringBuffer buffer = new StringBuffer();
    for (int j=1; j<this.bits[0]; j++) {
      buffer.append("0");
    }
    buffer.append("1");
    for (int i=1; i<this.bits.length; i++) {
      for (int j=1; j<this.bits[i]-this.bits[i-1]; j++) {
        buffer.append("0");
      }
      buffer.append("1");
    }
    return new String(buffer);
  }

  public boolean equals(Object obj) {
    if ((obj == null) || !(obj instanceof BitSet)) {
      return false;
    }
    BitSet set = ((BitSet)obj);
    if (this.bits.length != set.bits.length) {
      return false;
    }
    for (int i=0; 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 (this.get(bit)) return; // ist bereits gesetzt

    // Array vergroessern (ueber Hilfsarray) und bit sortiert einfuegen
    int[] buffer = new int[this.bits.length+1];
    int i;
    for (i=0; (i<this.bits.length) && (this.bits[i]<bit); i++) {
      buffer[i] = this.bits[i];
    }
    buffer[i] = bit;
    for (; i<this.bits.length; i++) {
      buffer[i+1] = this.bits[i];
    }
    this.bits = buffer;
  }

  public void clear(int bit) throws IllParamException {
    if (bit <= 0) throw new IllParamException();
    if (!this.get(bit)) return; // ist gar nicht gesetzt

    // Array verkleinern (ueber Hilfsarray) und bit entfernen
    int[] buffer = new int[this.bits.length-1];
    int i;
    for (i=0; this.bits[i]!=bit; i++) {
      buffer[i] = this.bits[i];
    }
    i++;
    for (; i<this.bits.length; i++) {
      buffer[i-1] = this.bits[i];
    }
    this.bits = buffer;
  }

  public void and(BitSet set) {
    try {
      for (int i=0; i<this.bits.length; ) {
        if (!set.get(this.bits[i])) {
          this.clear(this.bits[i]);
        } else {
          i++;
        }
      }
    } catch (IllParamException e) {} // kann nicht auftreten
  }

  public void or(BitSet set) {
    try {
      for (int i=0; i<set.bits.length; i++) {
        this.set(set.bits[i]);
      }
    } catch (IllParamException e) {} // kann nicht auftreten
  }

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

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

      BitSet set1 = new BitSet();
      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

      BitSet set2 = new BitSet(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

      BitSet set3 = new BitSet(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 {}