CS U370 Extra Credit Assignment.
Assigned:  Tuesday, 7 December 2004
Due: Friday, 10 December 2004

You will modify and extend an implementation of the IntBag ADT
that was written by the instructor, and you will write three
specific classes that can be used with your extension.

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
design and your code, part of your grade will depend upon the
quality of the comments in your code, including documentation
of invariants, and part of your grade will depend upon the
formatting and readability of your code.

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 EC

and a body that consists of nothing but the IntBag.java file
with your modifications and extensions.  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 discarded.

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

Your assignment is to modify and to extend the code in a single
file, IntBag.java, that implements the IntBag ADT that was
specified for assignment 5.  The specific implementation you
are to modify is available in

    /course/csu370wc/Assignments/EC

No test code is provided for this assignment, but you may find
some use for the test code that was provided for assignment 5.

There are three parts to this assignment:

1.  Modify the instructor's code to compute the size and sum
    of every IntBag in constant time when the IntBag is
    created.  Modify the size and sum methods to return
    their results in constant time when they are called.

2.  Extend the instructor's code to support the following
    new operation, which is to be defined for every IntBag:

        // Calls the given visitor on every element of this
        // IntBag, in increasing order of elements.

        public void accept (IntVisitor v);

3.  Define the following non-public classes that implement
    the IntVisitor interface.  The code for these classes
    must go at the end of the IntBag.java file.

    CountOccurrences

        The Java constructor for this class takes one
        argument, an int n.  The visit method counts
        how many times n is visited.  The result method
        returns that count.

    CountInRange

        The Java constructor for this class takes two
        arguments, ints n1 and n2.  The visit method counts
        how many times an int in the half-open interval
        [n1, n2) is visited.  The result method returns
        that count.

    Uniquify

        The Java constructor for this class takes no
        arguments.  The visit method records the first
        occurrence of each int that is visited, but
        ignores repeated visits to the same int.  The
        result method returns an IntBag that consists
        of every visited int without duplicates.

For full credit, the following code must run in O(n) time for
every IntBag b that contains n elements:

        Uniquify u = new Uniquify();
        b.accept(u);
        u.result();

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