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

["Jason Short" <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

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

Mateusz Stefek wrote:

> I like distribute.c

OK, here's a patch.

> If someone finds generalization in the future, file name will be
> changed. Renaming source file is an easy task.

Not that easy.  Either CVS history is lost or the file is copied and cvs 
-D no longer works right.  (The latter was used in creating the utility 
directory.  But IMO it causes more problems than it solves.)

We discussed switching over to subversion.  But nobody seems to have any 
experience with it.

jason

? diff
? utility/distribute.c
? utility/distribute.h
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       25 Aug 2004 17:17:48 -0000
@@ -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);
 }
 
Index: utility/Makefile.am
===================================================================
RCS file: /home/freeciv/CVS/freeciv/utility/Makefile.am,v
retrieving revision 1.5
diff -u -r1.5 Makefile.am
--- utility/Makefile.am 18 Aug 2004 05:24:46 -0000      1.5
+++ utility/Makefile.am 25 Aug 2004 17:17:48 -0000
@@ -13,6 +13,8 @@
                astring.h       \
                capability.c    \
                capability.h    \
+               distribute.c    \
+               distribute.h    \
                fcintl.c        \
                fcintl.h        \
                genlist.c       \

/********************************************************************** 
 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
}

/********************************************************************** 
 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