Engr 691: Special Topics in Engineering Science
Software Architecture
Spring Semester 1998

Revised Assignment #1
Due Midnight, Thursday, 12 February

Note: Because of a few difficulties with the Pizza language software, I redefined this programming assignment to use Java instead of Pizza.

A bag (or multiset) is a collection of elements; each element may occur one or more times in the bag. The goal of this assignment is to develop a generic bag class in Java and use it to count the number of occurrences of words in a document.

1. Using Java, define an abstract container class Bag. Concrete instances of this abstract class should be able to store and retrieve any Java object. The bag class should have the following operations:

   isEmpty

   returns true if the bag instance is empty and false otherwise.

   size

   returns the size (i.e., the number of distinct element values) of the bag instance.

   cardinality

   returns the cardinality (i.e., the total number of occurrences of all elements) of the bag instance.

   contains

   takes an element and returns true if the element occurs (at least once) in the bag instance and false otherwise.

   occurrences

   takes an element and returns the number of times the element occurs in the bag instance.

   equals

   takes a second bag and returns true if the argument bag equals the current bag instance (i.e., the same elements and same number of occurrences of each) and false otherwise.

   union

   takes a second bag and returns the union of the current bag instance and the argument bag. The union of bags X and Y contains all elements that occur in X or Y; the number of occurrences of an element is the sum of the number of occurrences in X and Y.

   intersection

   takes a second bag and returns the intersection of the current bag instance and the argument bag. The intersection of bags X and Y contains all elements that occur in both X and Y; the number of occurrences of an element in the intersection is the number in X or in Y, whichever is lesser.

   insert

   takes an element and returns the bag instance with the element inserted. Bag insertion either adds a single occurrence of a new element to the bag or increases the number of occurrences of an existing element by one.

   delete

   takes an element and returns the bag with the element deleted. Bag deletion either removes a single occurrence of the element from the bag or decreases the number of occurrences of the element by one.

   elements

   returns a java.util.Enumeration object for the bag instance. That is, the object returned implements the Enumeration interface. This interface requires that methods nextElement and hasMoreElements be implemented.

   You may make your bags either immutable or mutable, but be sure to be consistent.

   Challenge: Try to make the class more like a Pizza parameterized class. For example, you might pass the name of the element class into the constructor and store it away. Your class could then check to make sure that the objects being inserted into the bag are of the proper type using the facilities of classes Object and Class and the reflection API.

   Another challenge: Implement a map method that takes a simple (single-argument) function closure object and applies the function to every element of the bag container.

2. Develop a concrete class that extends the abstract class (or implements the interface) Bag.

   Include a zero-argument constructor that initializes the empty bag.

   You are free to implement the bag class internally in any way that you find convenient. Try to make the bag implementation elegant and reasonably efficient.

   Ideas: You might wantf to consider using one of the API classes in the Java API (e.g., java.util.Vector You might also consider representing the bag as a ordered collection of element/occurrence-count pairs. Perhaps you can take advantage of private methods to factor out common processing from the public methods of the class.

3. Document and test your package carefully.

4. Write a Java program that reads text from a file (or Web page) and uses a bag of strings to construct and print a word-frequency table. (You might find the program URLSearcher useful.)

5. When complete, submit a paper listing of your source code. Also submit a listing showing your testing of the package. I may also ask you to submit an electronic copy, but I don't have the details worked out on that yet.