参考号：EM13763

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.

这data structures are based on LinkedLists, ArrayLists, TreeSets, and PriorityQueues, as described below.

具体而言，分配的测试类A1假定了一个抽象类分配程序的子类ArrayListapportion，LinkedListapportioner，treeseTapportioner和PriorityqueEeAporpter的存在。根据以下规范定义这些子类中的最后三个。

• the Apportioner class
• the ArrayListApportioner subclass,
• 下面描述的CountingComparator类，
• the A1 test class, and
• 测试数据的各种文件

分配程序类和分配算法

分摊问题将国家及其人口的集合以及立法机关的总数。您要使用的算法（美国房屋使用）将这些座位分配给一个州之一

1.首先分配每个状态一个座位

2. then repeatedly assigning a seat to the state with the highest priority for it, until the seats are exhausted

每个州的优先级都被计算为其人口的商，也是根据当前分配的座位数量计算的除数。对于美国房屋使用的算法，您要使用的算法，此除数是R（r+1）的平方根。请注意，此值大约为R + 0.5。还要注意，每当一个州获得新的代表时，其除数会增加，因此优先级会减少。

这分配程序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.

这分配程序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.

分配示例

在一个大小，中和小的房屋大小为7和三个状态的示例中，各自种群的45、32和18，算法将通过与下表的行相对应的步骤迭代。

Apportionment			Priority
Large	中等的	小的	Large	中等的	小的
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	-	-	-

这分配程序子类

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.在这里，比较包括平等的比较 - 请勿使用equalsmethod 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 alargerpriority 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.

分配程序子类的初始化方法是假设单独的数据结构用于存储每个州的人群，当前的座位数量和当前优先级。即使在每种情况下都不会实现Java的MAP接口，也将这些数据汇总称为“地图”很方便。该方法不需要初始化每个子类中的所有地图 - 您可能会发现最好在定义，构造函数或ReadInput方法中初始化一些地图。如果您的子类具有不是地图或比较计数器的实例变量，则您可能还需要在Initializemaps中初始化它们。

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.

Getapportion方法是返回按状态排序的列表。如果需要明确的排序，则将通过计算比较的排序算法执行此类。这可能是通过collections.sort来完成的，也可以使用已使用CountingComparator参数构建的Treemet或Treemap来完成。

Each subclass may assume that the MiniScanner methods that appear in the superclass definition all work correctly.

对于每个子类,readInput方法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.

TROEDETAPPORTERTER类

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.

这PriorityQueueApportioner class

在PriorityQueueApporter类中，您应将优先数据表示为表示状态名称的字符串的优先级。人口数据和分配数据应像hashmaps一样表示，如thetreesetapportial案例中。您将需要一个类似于TreeseTapportioner类的比较类别类。