Compares the number of comparisons used by various data structures for a single algorithm. The algorithm is the one that is used to determine representation in the U.S. House of Representatives, and is described below.
The data structures are based on LinkedLists, ArrayLists, TreeSets, and PriorityQueues, as described below.
Specifically, the assignment's test class A1 assumes the existence of subclasses ArrayListApportioner, LinkedListApportioner, TreeSetApportioner, and PriorityQueueApportioner of an abstract class Apportioner. Define the last three of these subclasses according to the specifications below.
- the Apportioner class
- the ArrayListApportioner subclass,
- a CountingComparator class described below,
- the A1 test class, and
- various files of test data
The Apportioner class and the apportionment algorithm
The apportionment problem takes as input a collection of states and their populations, as well as a total number of seats in the legislature. The algorithm that you are to use (and that the U.S. House uses) assigns each of these seats to one of the states by
1. first assigning each state one seat
2. then repeatedly assigning a seat to the state with the highest priority for it, until the seats are exhausted
Each state's priority is computed as the quotient of its population and a divisor computed from the number r of seats that it is currently assigned. For the algorithm that the U.S. House uses, and that you are to use, this divisor is the square root of r(r+1). Note that this value is approximately r + 0.5. Also note that every time a state gets a new representative, its divisor increases and thus its priority decreases.
The Apportioner class has a simple concrete apportion method whose code corresponds to the simple high-level algorithm given above. The class also provides a concrete method for computing the divisor in the priority function, and a concrete method for reading the name and population of a single state. Otherwise the apportion method is based on specific abstract methods that subclasses need to define concretely. One of these methods returns the apportionment as a list of elements of class Map.Entry.
The Apportioner class also has two abstract methods for dealing with the number of comparisons of various types made during an apportionment. Its subclasses are to call these methods, as described below.
An apportionment example
In an example with a house size of 7 and three states Large, Medium, and Small, with respective populations 45, 32, and 18, the algorithm would iterate through steps corresponding to the rows of the table below.
|
Apportionment
|
Priority
|
|
Large
|
Medium
|
Small
|
Large
|
Medium
|
Small
|
|
1
|
1
|
1
|
32.8
|
21.6
|
12.7
|
|
2
|
1
|
1
|
18.4
|
21.6
|
12.7
|
|
2
|
2
|
1
|
18.4
|
13.1
|
12.7
|
|
3
|
2
|
1
|
13.0
|
13.1
|
12.7
|
|
3
|
3
|
1
|
-
|
-
|
-
|
The Apportioner subclasses
Each of your subclasses is to implement each of the abstract methods of the Apportioner class, based on a specified data type.
In addition, each subclass is to count the number of comparisons that it uses to peform apportionments, including those that it uses to initialize data structures. Here, comparisons include comparisons for equality -- do not use an equals method for these comparisons, or rely on a library method that does so. Each subclass is to count separately those comparisons used to update priorities, and those used for other purposes.
Specifically, the compare method for each of your CountingComparator subclasses is to increment the appropriate one of the two comparison counters. This method should return a negative number if the first argument has a larger priority than the second argument; this is particularly important for the priority queue data type. The resetComparisonCounters method of your Apportioner subclass is to set both of the class's counters to 0; the getComparisonCounters method is to return an array of size 2 that contains the two comparison counters, with the counter used for priorities appearing last.
The initializeMaps method of your Apportioner subclass is to assume that separate data structures are used to store each state's population, current number of seats, and current priority. It's convenient to call these data strucutres "maps", even though they will not implement Java's Map interface in each case. The method needn't initialize all maps in every subclass -- you may find it best to initialize some maps at definition, in a constructor, or in the readInput methods. If your subclasses have instance variables that aren't maps or comparison counters, you might want to initialize them in initializeMaps as well.
Note that, depending on the data type of the priority map and its entries, updating priorities in the assignRepAndUpdatePriority method may be possible by simply mutating an entry, or may need to be done by removing an entry and inserting an updated version of it into the map.
The getApportionment method is to return a list sorted by state. If an explicit sort is necessary, this sort is to be performed by a sorting algorithm that counts comparisons. This might be done by Collections.sort, or by using a TreeSet or TreeMap that has been constructed with a CountingComparator argument.
Each subclass may assume that the MiniScanner methods that appear in the superclass definition all work correctly.
For each subclass, the readInput method that takes a filename argument should check that the file of the given name is not empty. The readInput method that takes a list argument should check that the list is not empty. In each case, the method should throw an IOException with an informative message component. Neither method needs to handle any exceptions, or check for any other errors. In particular, you needn't check for repeated state names. The rest of the subclass's methods may assume that there is at least one state and that the population map is not empty.
The TreeSetApportioner class
In the TreeSetApportioner class, you are to represent the priority data as a TreeSet of Strings, constructed with a Comparator argument that compares strings by priority (where items of larger priority value precede items of smaller priority value). The population data and the apportionment data are to be represented as HashMaps from String to Long and Integer respectively. Note that here HashMaps are preferable to TreeMaps since the order of the state names is unimportant during apportionment.
The PriorityQueueApportioner class
In the PriorityQueueApportioner class, you are to represent priority data as a PriorityQueue of Strings that represent state names. Population data and apportionment data are to be represented as HashMaps as in theTreeSetApportioner case. You will need a Comparator class similar to that of the TreeSetApportioner class.