// ------------------------------------------------------------
// IntegerSet.java
//   (Problem 6.17 in Deitel and Deitel)
//
// Paul McNamee  (7/14/98)
// ------------------------------------------------------------

// ------------------------------------------------------------
// A more general class wouldn't restrict the permissible inputs
// to 0 - 100, but by doing this we can perform some algorithmic
// tricks in computing set intersection, union, and differences.
//
// In this representation, if a[i] is 1, then i is a member of the
// set.  if a[i] is 0, then i is not a member of the set. 
//
// subset and set difference are missing, but should be easy to add.
// ------------------------------------------------------------

public class IntegerSet {
  private int [] a;  // holds a set of numbers from 0 - 100

  public IntegerSet () {
    // an empty set, all a[i] are set to 0
    a = new int [101];
  }

  // A constructor that copies from an existing set.
  public IntegerSet (IntegerSet existingSet) {
    a = new int [101];
    for(int i=0; i<a.length; i++)
      a[i] = existingSet.a[i];
  }

  public void deleteElement(int i) {
    if ((i >= 0) && (i < a.length))
      a[i] = 0;  // set to 1
  }

  public void insertElement(int i) {
    if ((i >= 0) && (i < a.length))
      a[i] = 1;  // set to 1
  }

  public boolean isSet(int i) {
    return (a[i] == 1);
  }
  
  // The union of this set and another set
  public IntegerSet unionOfIntegerSets(IntegerSet otherSet) {
    IntegerSet newSet = new IntegerSet(this);

    // newSet is now a copy of the current set,  Next we
    // want to union with set a

    for(int i=0; i<a.length; i++) {
      if (otherSet.isSet(i))
        newSet.insertElement(i);
    }

    return newSet;
  }

  // The intersection of this set and another set
  public IntegerSet intersectionOfIntegerSets(IntegerSet otherSet) {
    IntegerSet newSet = new IntegerSet(this);

    // newSet is now a copy of the current set,  Next we
    // want to intersect with set a

    for(int i=0; i<a.length; i++) {
      if (!otherSet.isSet(i))
        newSet.deleteElement(i);
    }

    return newSet;
  }
  
  
  // return true if the set has no elements
  public boolean isEmpty() {
    for (int i=0; i<a.length; i++)
      if (isSet(i)) return false;
    return true;
  }

  // return the 'length' of a set
  public int cardinality() {
    int count = 0;
    for (int i=0; i<a.length; i++)
      if (isSet(i))
        count++;
    return count;
  }

  // Print a set to System.out
  public void setPrint() {
    System.out.print("[Set:");

    if (isEmpty())
      System.out.print("---");

    for (int i=0; i<a.length; i++) {
      if (isSet(i))
        System.out.print(" " + i);
    }

    System.out.print("]\n");
  }

  // return true if two sets are equal
  public boolean isEqualTo(IntegerSet otherSet) {
    for(int i=0; i<a.length; i++) {
      if (otherSet.isSet(i) != isSet(i))
        return false;
    }
    return true;
  }
  
  // ------------------------------------------------------------
  // Small test program to verify that IntegerSet works!
  public static void main (String [] args) {
    IntegerSet smallEvens = new IntegerSet();
    IntegerSet smallOdds = new IntegerSet();
    for (int i=0; i<10; i++)
      if ((i % 2) == 0)
        smallEvens.insertElement(i);
      else
        smallOdds.insertElement(i);
    
    System.out.print("smallEvens: ");
    smallEvens.setPrint();

    System.out.print("smallOdds: ");
    smallOdds.setPrint();

    IntegerSet union = smallEvens.unionOfIntegerSets(smallOdds);
    System.out.print("union: ");
    union.setPrint();

    IntegerSet intersection = smallEvens.intersectionOfIntegerSets(smallOdds);
    System.out.print("intersection: ");
    intersection.setPrint();

  }

  // Output:
  //   paulmac@nautilus: java IntegerSet
  //   smallEvens: [Set: 0 2 4 6 8]
  //   smallOdds: [Set: 1 3 5 7 9]
  //   union: [Set: 0 1 2 3 4 5 6 7 8 9]
  //   intersection: [Set:---]
}