Define a class IntegerSet with methods and constructors as given below. Instances of this class are to represent possible subsets of a given universal set U of integers. At any point during the lifetime of an instance, there is to be one "current subset". This current subset is to be updatable as described below, in a way similar to but not identical to the way an Iterator steps through elements of a collection.
Your class is to have methods getCurrentSubset(), getCurrentSum(), isCurrentSubsetEmpty(), nextSubset(), getSubsetWithSum, getMembershipCounter(), and getAdditionCounter() which work as specified below. It may have as many private methods as you see fit. Like your public methods, these private methods are to be documented with javadoc (and any other appropriate comments).
Your class is to have a zero-argument constructor, and a constructor that takes an array of ints and interprets it as the universal set U. This second constructor need not check to see whether the array members are all distinct, so in fact the instances of the class represent bags of integers rather than sets. However the constructor should preserve the ordering given by the array, since this ordering will define a lexicographical ordering on the subsets of U (where elements with smaller indices vary most quickly). Both constructors should initialize the current subset to be the empty set.
The method getCurrentSubset() is to return an ArrayList representation of the current subset. The method getCurrentSum() is to return, in time O(1), the sum of the members of the current subset. The boolean-valued method isCurrentSubsetEmpty() is to return true if and only if the current set is empty. In any case, it should take O(1) time.
The method nextSubset() is to update the current subset to be the next subset (of the universal set) in lexicographical order. When invoked on the last set in lexicographical order, this method should update the current subset to the empty subset. For this method, you are to use a bit map representation for subsets, and use the binary counter algorithm described in the text (and in Chapter 17 of the text by Cormen et al) to update the bit map. Note that using this algorithm should have amortized time complexity O(1), provided that the subset remains in the bit map representation rather than being converted to an ArrayList or other explicit list. It is acceptable to use an array of booleans for the bit map.
The getSubsetWithSum method is to take an integer argument and find and return a subset (represented as an ArrayList of integers) whose members sum to the given integer. If no such subset exists, it is to return null. For full credit, it is to have time complexity O(2n) for a universal set of size n.
To help verify the desired time complexity of the nextSubset() and getSubsetWithSum methods, you are to maintain a counter of the number of times that a bit (or boolean) in the bit map representation changes value, and a counter of the number of times an addition or subtraction operation is performed when computing the sum of a subset. The method getMembershipCounter() is to return the current value of the first of these counters, and the method getAdditionCounter() is to return the current value of second of these counters. You needn't provide any methods for resetting the counters.
Since your class is to obey slightly different constraints from that of the Iterator interface, it need not implement this interface.
Test your class definition by executing the A1 class, available on the class web site. You are to turn in hard and soft copies of your class definitions -- these include any additional classes you may choose to define, but do not turn in the A1 class unless you change it. You are also to turn in a hard copy of the results of your tests.