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

["Mateusz Stefek" <mstefek@xxxxxxxxx>]

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

Can someone else test attached patch ?
(Only if it compiles)
--
mateusz

diff -ur --new-file -Xdiff_ignore freeorig/client/Makefile.am 
freeciv/client/Makefile.am
--- freeorig/client/Makefile.am 2004-08-26 19:15:25.000000000 +0200
+++ freeciv/client/Makefile.am  2004-08-26 19:42:15.000000000 +0200
@@ -193,12 +193,12 @@
        audio_none.h
 
 civclient_LDFLAGS = @CLIENT_LDFLAGS@
-civclient_DEPENDENCIES = @gui_sources@/libguiclient.a \
-       ../utility/libcivutility.a ../common/libcivcommon.a agents/libagents.a \
-        ../common/aicore/libaicore.a $(LIBFTWL)
-
-civclient_LDADD        = @gui_sources@/libguiclient.a \
-       @INTLLIBS@ ../common/aicore/libaicore.a \
-        ../utility/libcivutility.a ../common/libcivcommon.a \
-        agents/libagents.a ../common/aicore/libaicore.a \
-        $(LIBFTWL) @CLIENT_LIBS@ @SOUND_LIBS@
+fc_civclient_libs =    ../utility/libcivutility.a      \
+                       $(LIBFTWL)                      \
+                       ../common/libcivcommon.a        \
+                       ../common/aicore/libaicore.a    \
+                       agents/libagents.a              \
+                       @gui_sources@/libguiclient.a
+civclient_DEPENDENCIES = $(fc_civclient_libs)
+civclient_LDADD        = $(fc_civclient_libs) $(fc_civclient_libs) \
+       @INTLLIBS@ @CLIENT_LIBS@ @SOUND_LIBS@
diff -ur --new-file -Xdiff_ignore freeorig/common/city.c freeciv/common/city.c
--- freeorig/common/city.c      2004-08-26 19:15:28.000000000 +0200
+++ freeciv/common/city.c       2004-08-26 19:40:35.000000000 +0200
@@ -19,14 +19,16 @@
 #include <stdlib.h>
 #include <string.h>
 
+#include "distribute.h"
 #include "fcintl.h"
+#include "log.h"
+#include "support.h"
+
 #include "game.h"
 #include "government.h"
-#include "log.h"
 #include "map.h"
 #include "mem.h"
 #include "packets.h"
-#include "support.h"
 
 #include "cm.h"
 
@@ -1811,98 +1813,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;
-  } else {
-    sci_rate = game.rgame.forced_science;
-    lux_rate = game.rgame.forced_luxury;
-    tax_rate = game.rgame.forced_gold;
+    rates[SCIENCE] = pplayer->economic.science;
+    rates[LUXURY] = pplayer->economic.luxury;
+    rates[TAX] = 100 - rates[SCIENCE] - rates[LUXURY];
+  } else {
+    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);
 }
 
diff -ur --new-file -Xdiff_ignore freeorig/utility/distribute.c 
freeciv/utility/distribute.c
--- freeorig/utility/distribute.c       1970-01-01 01:00:00.000000000 +0100
+++ freeciv/utility/distribute.c        2004-08-26 19:41:01.000000000 +0200
@@ -0,0 +1,119 @@
+/********************************************************************** 
+ Freeciv - Copyright (C) 2004 - The Freeciv Project
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2, or (at your option)
+   any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+***********************************************************************/
+
+#ifdef HAVE_CONFIG_H
+#include <config.h>
+#endif
+
+#include <assert.h>
+
+#include "distribute.h"
+
+/****************************************************************************
+  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
+}
+
diff -ur --new-file -Xdiff_ignore freeorig/utility/distribute.h 
freeciv/utility/distribute.h
--- freeorig/utility/distribute.h       1970-01-01 01:00:00.000000000 +0100
+++ freeciv/utility/distribute.h        2004-08-26 19:41:04.000000000 +0200
@@ -0,0 +1,20 @@
+/********************************************************************** 
+ Freeciv - Copyright (C) 2004 - The Freeciv Project
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2, or (at your option)
+   any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+***********************************************************************/
+
+#ifndef FC__DISTRIBUTE_H
+#define FC__DISTRIBUTE_H
+
+void distribute(int number, int groups, int *ratios, int *result);
+
+#endif
+
diff -ur --new-file -Xdiff_ignore freeorig/utility/Makefile.am 
freeciv/utility/Makefile.am
--- freeorig/utility/Makefile.am        2004-08-26 19:15:40.000000000 +0200
+++ freeciv/utility/Makefile.am 2004-08-26 19:40:35.000000000 +0200
@@ -13,6 +13,8 @@
                astring.h       \
                capability.c    \
                capability.h    \
+               distribute.c    \
+               distribute.h    \
                fcintl.c        \
                fcintl.h        \
                genlist.c       \