[Freeciv-Dev] (PR#9755) provide distribute() in the utility code

["Jason Short" <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

<URL: http://rt.freeciv.org/Ticket/Display.html?id=9755 >

This patch provides a function distribute() in the utility code:

   void distribute(int number, int groups, int *ratios, int *result);

This will distribute "number" elements into "groups" groups with ratios 
given by the elements in "ratios".  The resulting division is put into 
the "result" array.

The only user (so far) is the trade disribution code.  In this case 
"number" is the amount of trade, "groups" is 3, and ratios[3] = 
{sci_rate, tax_rate, lux_rate}.  At the end result[] holds the amount of 
sci/tax/luxury.

The algorithm used to determine the distribution is Hamilton's Method. 
When this code was rewritten a year or two ago there was a good 
discussion about this; read it if you want to know more.  Also of 
interest is 
http://www.cut-the-knot.org/Curriculum/SocialScience/AHamilton.shtml.

See PR#9741 for a second user.

(Technical notes: I put this in shared.c for lack of any better place. 
But surely that's not where it should go.  Also, I ran an autogame that 
showed savegames were unchanged, but I don't believe it.  I think since 
the AI cheats the science rate is always 100% so minor differences in 
the algorithm will not show up.  My implementation of the algorithm *I 
think* differs from the current implementation in that if there is a 
double-tie the tiebreaker will be granted to the first group in the tie, 
not the second one.)

jason

? diff
? freeciv-1.14.99-devel.tar.gz
? orig
? server/civmanual.c
Index: common/city.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/city.c,v
retrieving revision 1.236
diff -u -r1.236 city.c
--- common/city.c       20 Aug 2004 20:13:17 -0000      1.236
+++ common/city.c       21 Aug 2004 04:25:15 -0000
@@ -1811,98 +1811,32 @@
 void get_tax_income(struct player *pplayer, int trade, int *sci, 
                     int *lux, int *tax)
 {
-  int sci_rest, tax_rest, lux_rest, sci_rate, lux_rate, tax_rate, rate = trade;
+  const int SCIENCE = 0, TAX = 1, LUXURY = 2;
+  int rates[3], result[3];
 
   if (game.rgame.changable_tax) {
-    sci_rate = pplayer->economic.science;
-    lux_rate = pplayer->economic.luxury;
-    tax_rate = 100 - sci_rate - lux_rate;
+    rates[SCIENCE] = pplayer->economic.science;
+    rates[LUXURY] = pplayer->economic.luxury;
+    rates[TAX] = 100 - rates[SCIENCE] - rates[LUXURY];
   } else {
-    sci_rate = game.rgame.forced_science;
-    lux_rate = game.rgame.forced_luxury;
-    tax_rate = game.rgame.forced_gold;
+    rates[SCIENCE] = game.rgame.forced_science;
+    rates[LUXURY] = game.rgame.forced_luxury;
+    rates[TAX] = game.rgame.forced_gold;
   }
   
   /* ANARCHY */
   if (get_gov_pplayer(pplayer)->index == game.government_when_anarchy) {
-    sci_rate = 0;
-    lux_rate = 100;
-    tax_rate = 100 - sci_rate - lux_rate;
+    rates[SCIENCE] = 0;
+    rates[LUXURY] = 100;
+    rates[TAX] = 0;
   }
 
-  /* 
-   * Distribution of the trade among science, tax and luxury via a
-   * modified Hare/Niemeyer algorithm (also known as "Hamilton's
-   * Method"):
-   *
-   * 1) distributes the whole-numbered part of the three targets
-   * 2) sort the remaining fractions (called *_rest)
-   * 3) divide the remaining trade among the targets starting with the
-   * biggest fraction. If two targets have the same fraction the
-   * target with the smaller whole-numbered value is chosen.
-   */
+  distribute(trade, 3, rates, result);
+
+  *sci = result[SCIENCE];
+  *tax = result[TAX];
+  *lux = result[LUXURY];
 
-  *sci = (rate * sci_rate) / 100;
-  *tax = (rate * tax_rate) / 100;
-  *lux = (rate * lux_rate) / 100;
-
-  /* these are the fractions multiplied by 100 */
-  sci_rest = rate * sci_rate - (*sci) * 100;
-  tax_rest = rate * tax_rate - (*tax) * 100;
-  lux_rest = rate * lux_rate - (*lux) * 100;
-
-  rate -= ((*sci) + (*tax) + (*lux));
-
-  while (rate > 0) {
-    if (sci_rest > lux_rest && sci_rest > tax_rest) {
-      (*sci)++;
-      sci_rest = 0;
-      rate--;
-    }
-    if (tax_rest > sci_rest && tax_rest > lux_rest && rate > 0) {
-      (*tax)++;
-      tax_rest = 0;
-      rate--;
-    }
-    if (lux_rest > tax_rest && lux_rest > sci_rest && rate > 0) {
-      (*lux)++;
-      lux_rest = 0;
-      rate--;
-    }
-    if (sci_rest == tax_rest && sci_rest > lux_rest && rate > 0) {
-      if (*sci < *tax) {
-       (*sci)++;
-       sci_rest = 0;
-       rate--;
-      } else {
-       (*tax)++;
-       tax_rest = 0;
-       rate--;
-      }
-    }
-    if (sci_rest == lux_rest && sci_rest > tax_rest && rate > 0) {
-      if (*sci < *lux) {
-       (*sci)++;
-       sci_rest = 0;
-       rate--;
-      } else {
-       (*lux)++;
-       lux_rest = 0;
-       rate--;
-      }
-    }
-    if (tax_rest == lux_rest && tax_rest > sci_rest && rate > 0) {
-      if (*tax < *lux) {
-       (*tax)++;
-       tax_rest = 0;
-       rate--;
-      } else {
-       (*lux)++;
-       lux_rest = 0;
-       rate--;
-      }
-    }
-  }
   assert(*sci + *tax + *lux == trade);
 }
 
Index: utility/shared.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/utility/shared.c,v
retrieving revision 1.115
diff -u -r1.115 shared.c
--- utility/shared.c    20 Jul 2004 14:34:32 -0000      1.115
+++ utility/shared.c    21 Aug 2004 04:25:16 -0000
@@ -1320,3 +1320,101 @@
   }
   return group;
 }
+
+/****************************************************************************
+  Distribute "number" elements into "groups" groups with ratios given by
+  the elements in "ratios".  The resulting division is put into the "result"
+  array.
+
+  For instance this code is used to distribute trade among science, tax, and
+  luxury.  In this case "number" is the amount of trade, "groups" is 3,
+  and ratios[3] = {sci_rate, tax_rate, lux_rate}.
+
+  The algorithm used to determine the distribution is Hamilton's Method.
+****************************************************************************/
+void distribute(int number, int groups, int *ratios, int *result)
+{
+  int i, sum = 0, rest[groups], max_groups[groups], max_count, max;
+  const int original_number = number;
+
+  /* 
+   * Distribution of a number of items into a number of groups with a given
+   * ratio.  This follows a modified Hare/Niemeyer algorithm (also known
+   * as "Hamilton's Method"):
+   *
+   * 1) distribute the whole-numbered part of the targets
+   * 2) sort the remaining fractions (called rest[])
+   * 3) divide the remaining source among the targets starting with the
+   *    biggest fraction. (If two targets have the same fraction the
+   *    target with the smaller whole-numbered value is chosen.  If two
+   *    values are still equal it is the _first_ group which will be given
+   *    the item.)
+   */
+
+  for (i = 0; i < groups; i++) {
+    assert(ratios[i] >= 0);
+    sum += ratios[i];
+  }
+
+  /* 1.  Distribute the whole-numbered part of the targets. */
+  for (i = 0; i < groups; i++) {
+    result[i] = number * ratios[i] / sum;
+  }
+
+  /* 2a.  Determine the remaining fractions. */
+  for (i = 0; i < groups; i++) {
+    rest[i] = number * ratios[i] - result[i] * sum;
+  }
+
+  /* 2b. Find how much source is left to be distributed. */
+  for (i = 0; i < groups; i++) {
+    number -= result[i];
+  }
+
+  while (number > 0) {
+    max = max_count = 0;
+
+    /* Find the largest remaining fraction(s). */
+    for (i = 0; i < groups; i++) {
+      if (rest[i] > max) {
+       max_count = 1;
+       max_groups[0] = i;
+       max = rest[i];
+      } else if (rest[i] == max) {
+       max_groups[max_count] = i;
+       max_count++;
+      }
+    }
+
+    if (max_count == 1) {
+      /* Give an extra source to the target with largest remainder. */
+      result[max_groups[0]]++;
+      rest[max_groups[0]] = 0;
+      number--;
+    } else {
+      int min = result[max_groups[0]], which_min = max_groups[0];
+
+      /* Give an extra source to the target with largest remainder and
+       * smallest whole number. */
+      assert(max_count > 1);
+      for (i = 1; i < max_count; i++) {
+       if (result[max_groups[i]] < min) {
+         min = result[max_groups[i]];
+         which_min = max_groups[i];
+       }
+      }
+      result[which_min]++;
+      rest[which_min] = 0;
+      number--;
+    }
+  }
+
+#ifndef NDEBUG
+  number = original_number;
+  for (i = 0; i < groups; i++) {
+    assert(result[i] >= 0);
+    number -= result[i];
+  }
+  assert(number == 0);
+#endif
+}
Index: utility/shared.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/utility/shared.h,v
retrieving revision 1.128
diff -u -r1.128 shared.h
--- utility/shared.h    24 Jul 2004 12:26:07 -0000      1.128
+++ utility/shared.h    21 Aug 2004 04:25:17 -0000
@@ -243,4 +243,6 @@
 
 char *get_multicast_group(void);
 
+void distribute(int number, int groups, int *ratios, int *result);
+
 #endif  /* FC__SHARED_H */