//
// Diese Klasse implementiert die Mengenoperationen auf 
// einer Repraesentation der natuerlichen Zahlen  durch bits
// eines integer-Arrays. Dabei ist ein Maximalwert MAX_ELEMS
// vorgegeben.




class BitVector {

final static int MAX_ELEM = 232; 
    //
    // final, um zu verdeutlichen, dass MAX_ELEM eine Konstante ist,
    // static, damit andere static Methoden diese verwenden koennen.

// ---------------------------------------------------------------

    // isInSet testet, ob die Zahl value im Array bitset
    // repraesentiert wird.

  public static boolean isInSet(int value, int[] bitset) {
      int localvector;
      if (value >= MAX_ELEM) {
	  System.out.println("Zu grosser Wert! :" + value);
          return false;}
      else {
      localvector = bitset[value/32];
      return (localvector & (1<<(value%32))) != 0;}
    }
    
// ---------------------------------------------------------------

    // PrintSet gibt die durch das Array bitset repraesentierte
    // Menge aus.

   public static void printSet( int[] bitset) {
	System.out.print("{");
	boolean needKomma = false;
	for (int i=0; i<MAX_ELEM; i++) {
	    if (isInSet(i, bitset)) {
		if (needKomma)
		    System.out.print(",");
		System.out.print(i);
		needKomma = true;
	    }
	}
	System.out.println("}");
    }

// -------------------------------------------------------------

    // insertToSet fuegt eine Zahl value in die Menge bitset ein.
    //

public static void insertToSet(int value, int[] bitset){
	if (value < MAX_ELEM) 
        bitset[value/32] = bitset[value/32] | (1<<(value%32));
        else 
     	System.out.println("Zu grosser Wert! :" + value);
	    }

    
//---------------------------------------------------------------

    // removeFromSet entfernt den Wert value aus der Menge
    // bitset - falls dieser ueberhaupt enthalten war.

    public static void removeFromSet(int value, int[] bitset) {
  	if (value < MAX_ELEM) 
       bitset[value/32] = bitset[value/32] & ~(1<<(value%32));
    else 
     	System.out.println("Zu grosser Wert! :" + value);
	    }
    
//--------------------------------------------------------------

    // union liefert die Vereinigung zweier Mengen.
    // Um zu verhindern, dass die als Parameter uebergebenen
    // Mengen veraendert werden, wird eine weitere Menge lokal
    // definiert (fuer den Rueckgabewert).

public static int[] union( int[] bitset, int[] other) {
 int size = MAX_ELEM/32;
        if (MAX_ELEM%32 >0)
            size = size + 1;
    int [] local = new int[size]; 
	for (int i=0; i<size; i++) {
		local[i] = bitset[i] | other[i];
	};
                return local;
	
    }
  
 //------------------------------------------------------------

    // Intersection: Analog zu union als Schnittemenge 

 public static int[] intersection(int[] bitset, int[] other) {
       int size = MAX_ELEM/32;
        if (MAX_ELEM%32 >0)
            size = size + 1;
    int [] local = new int[size];
	for (int i=0; i<size; i++) 
		local[i] = bitset[i] & other[i];
	return local;

    }


//----------------------------------------------------------------

    // difference liefert bitset \ other, 
    // d.h. bitset - (intersection(bitset, other)

 public static int[] difference(int[] bitset, int[] other) {
       int size = MAX_ELEM/32;
        if (MAX_ELEM%32 >0)
            size = size + 1;
    int [] local = new int[size];
    for (int i=0; i<size; i++) {
	local[i] = (bitset[i] & ~other[i]);
    };
    return local;
    }
    









  
//------------------------------------------------------------------
    public static void main(String args[]) {
       
        int [] set_array;
        int calcsize = MAX_ELEM/32;
        if (MAX_ELEM%32 >0)
            calcsize = calcsize + 1;
        set_array = new int[calcsize];
        int [] nochein_array =  new int[calcsize];
       




   insertToSet(54, set_array);
	insertToSet(6, set_array);
        insertToSet(4, set_array);
	insertToSet(120, nochein_array);
        insertToSet(54, nochein_array);

	printSet(union( set_array, nochein_array));
        printSet(intersection( set_array, nochein_array));
        printSet(difference( set_array, nochein_array));

    }
}


// Version 1.1 vom 6. Januar 2003
 
// Fuer das PI1 Team:
//  Ulrich Hannemann
//  ulrichh@informatik.uni-bremen.de