[lmi-commits] [lmi] master f8f44aa 5/5: Force stability upon a priority queue

[Greg Chicares]

branch: master
commit f8f44aa65af04c93a4b490f674aa828421e9b343
Author: Gregory W. Chicares <address@hidden>
Commit: Gregory W. Chicares <address@hidden>

    Force stability upon a priority queue
---
 report_table.cpp      | 17 ++++++++++++++++-
 report_table_test.cpp |  6 ++++++
 2 files changed, 22 insertions(+), 1 deletion(-)

diff --git a/report_table.cpp b/report_table.cpp
index a40c68a..0f87a52 100644
--- a/report_table.cpp
+++ b/report_table.cpp
@@ -45,6 +45,21 @@
 /// "A Geometric View of Some Apportionment Paradoxes", 65 Mathematics
 /// Magazine 1, 16 (1992).
 ///
+/// If two elements of the 'votes' argument have the same value, then
+/// any "residue" is arbitrarily apportioned to the earlier one first.
+/// (Without such a rule, the result is indeterminate.) The present
+/// implementation uses a priority queue, which is based on heapsort,
+/// which is not a stable (order-preserving) algorithm--so, where the
+/// priority of element j would naively be 'remainder' below ("giving
+/// preference to the greatest remainders"), it subtracts a penalty
+/// that increases with each successive element, yet is never so large
+/// as to cross equivalence classes: notionally,
+///   adjusted priority = remainder - double(j / cardinality)
+/// (where the fraction is strictly less than unity, so the integer
+/// part of the adjusted priority is still 'remainder'), although
+/// actually it multiplies that expression by 'cardinality' in order
+/// to avoid floating point.
+///
 /// Asserted postcondition: All seats are apportioned--i.e., the sum
 /// of the returned vector equals the 'total_seats' argument--unless
 /// the sum of the 'votes' argument is zero, in which case zero seats
@@ -61,7 +76,7 @@ std::vector<int> apportion(std::vector<int> const& votes, int 
total_seats)
         {
         seats[j]            = (votes[j] * total_seats) / total_votes;
         int const remainder = (votes[j] * total_seats) % total_votes;
-        queue.push({remainder, j});
+        queue.push({cardinality * remainder - j, j});
         }
     int const dealt_seats = std::accumulate(seats.begin(), seats.end(), 0);
     for(int j = 0; j < total_seats - dealt_seats; ++j)
diff --git a/report_table_test.cpp b/report_table_test.cpp
index 0f9cadd..5327a15 100644
--- a/report_table_test.cpp
+++ b/report_table_test.cpp
@@ -135,6 +135,12 @@ void report_table_test::test_apportion()
     std::vector<int> const votes5 = {};
     std::vector<int> const seats5 = {};
     BOOST_TEST(seats5 == apportion(votes5, 7));
+
+    // Test with an equal number of "voters" in each "state".
+
+    std::vector<int> const votes6 = {5, 5, 5};
+    std::vector<int> const seats6 = {3, 2, 2};
+    BOOST_TEST(seats6 == apportion(votes6, 7));
 }
 
 void report_table_test::test_bloat()