[Corrected version.  The correction is marked by an exclamation point (!)
in column 79.]

CS U370 Assignment #4.
Assigned: Tuesday, 19 October 2004
Due: Monday, 26 October 2004

You will write client code that implements several additional
operations for the IntSet ADT that was specified in the previous
assignment.  These new operations are specified below.

Collaboration between students is forbidden on this assignment.
You are responsible for keeping your code hidden from all other
students.  Part of your grade will be determined by how well
you hide your code, part of your grade will be determined by
how well you follow the instructions for submitting your code,
part of your grade will depend upon the correctness of your
code, and part of your grade will depend upon the readability
of your code (e.g. formatting and comments).

Turn in your work on this assignment before 4 pm on the due
date by sending electronic mail to

    will@ccs.neu.edu

with subject

    CSU370 assignment 4

and a body that consists of nothing but your IntSetOps.java
file.  That file should begin with a block comment that lists

    1.  Your name, as you want the instructor to write it.
    2.  Your email address.
    3.  Any remarks that you wish to make to the instructor.

Late assignments may be discounted, and very late assignments
may be discarded.

--------------------------------------------------

Your assignment is to write the code for a single file,
IntSetOps.java, that implements the operations specified below.
IntSetOps.java must consist of client code that will work with
every correct implementation of the IntSet ADT.  A small test
program will be made available in

    /course/csu370wc/Assignments/A4/testIntSetOps.java

That directory also contains IntIterator.java, which defines
the IntIterator interface, and a by-the-recipe implementation
of the IntSet ADT.

--------------------------------------------------

Specification of the additional operations.

These operations shall be implemented as public static methods
of a public class named IntSetOps that is defined within a
single file named IntSetOps.java.  This code shall be within
the default package.

    public static boolean isElementOf (int, IntSet);
    public static IntSet  intersection (IntSet, IntSet);
    public static IntSet  difference (IntSet, IntSet);
    public static boolean isSubsetOf (IntSet, IntSet);
    public static boolean areEqual (IntSet, IntSet);

    public static IntIterator iterator (IntSet);

The iterator method is specified informally.  The other five
operations are specified by the algebraic specification below.
That specification relies on the fact that every nonempty IntSet
s can be written as

    s = union (singleton (least (s)), butLeast (s))


Algebraic specification:

    isElementOf (n, emptySet()) = false

    isElementOf (n, union (singleton (least (s)), butLeast (s)))
        = (n = least (s)) or isElementOf (n, butLeast (s))

    intersection (emptySet(), s2) = emptySet()

    intersection (union (singleton (least (s1)), butLeast (s1)),
                  s2)
        = adjoin (least (s1), intersection (butLeast (s1), s2))
                                 if isElementOf (least (s1), s2)

    intersection (union (singleton (least (s1)), butLeast (s1)), s2)
        = intersection (butLeast (s1), s2)             otherwise

    difference (emptySet(), s2) = emptySet()

    difference (union (singleton (least (s1)), butLeast (s1)), s2)
        = adjoin (least (s1), difference (butLeast (s1), s2))
                             if not isElementOf (least (s1), s2)              !

    difference (union (singleton (least (s1)), butLeast (s1)), s2)
        = difference (butLeast (s1), s2)               otherwise

    isSubsetOf (emptySet(), s2) = true

    isSubsetOf (union (singleton (least (s1)), butLeast (s1)), s2)
        = isElementOf (least (s1), s2)
                & isSubsetOf (butLeast (s1), s2)

    areEqual (s1, s2) = isSubsetOf (s1, s2) & isSubsetOf (s2, s1)


Informal specification of the iterator operation:

iterator(s) returns an IntIterator that generates the elements
of s in increasing order beginning with the least element of s.
The IntIterator interface is defined in IntIterator.java, which
is provided by the instructor.

****************************************************************