utility/distribute.c

   1 /**********************************************************************
   2  Freeciv - Copyright (C) 2004 - The Freeciv Project
   3    This program is free software; you can redistribute it and/or modify
   4    it under the terms of the GNU General Public License as published by
   5    the Free Software Foundation; either version 2, or (at your option)
   6    any later version.
   7
   8    This program is distributed in the hope that it will be useful,
   9    but WITHOUT ANY WARRANTY; without even the implied warranty of
  10    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11    GNU General Public License for more details.
  12 ***********************************************************************/
  13
  14 #ifdef HAVE_CONFIG_H
  15 #include <fc_config.h>
  16 #endif
  17
  18 #include "log.h"                /* fc_assert */
  19
  20 #include "distribute.h"
  21
  22 /****************************************************************************
  23   Distribute "number" elements into "groups" groups with ratios given by
  24   the elements in "ratios".  The resulting division is put into the "result"
  25   array.
  26
  27   For instance this code is used to distribute trade among science, tax, and
  28   luxury.  In this case "number" is the amount of trade, "groups" is 3,
  29   and ratios[3] = {sci_rate, tax_rate, lux_rate}.
  30
  31   The algorithm used to determine the distribution is Hamilton's Method.
  32 ****************************************************************************/
  33 void distribute(int number, int groups, int *ratios, int *result)
  34 {
  35   int i, sum = 0, rest[groups], max_groups[groups], max_count, max;
  36 #ifdef DEBUG
  37   const int original_number = number;
  38 #endif
  39
  40   /*
  41    * Distribution of a number of items into a number of groups with a given
  42    * ratio.  This follows a modified Hare/Niemeyer algorithm (also known
  43    * as "Hamilton's Method"):
  44    *
  45    * 1) distribute the whole-numbered part of the targets
  46    * 2) sort the remaining fractions (called rest[])
  47    * 3) divide the remaining source among the targets starting with the
  48    *    biggest fraction. (If two targets have the same fraction the
  49    *    target with the smaller whole-numbered value is chosen.  If two
  50    *    values are still equal it is the _first_ group which will be given
  51    *    the item.)
  52    */
  53
  54   for (i = 0; i < groups; i++) {
  55     fc_assert(ratios[i] >= 0);
  56     sum += ratios[i];
  57   }
  58
  59   /* 1.  Distribute the whole-numbered part of the targets. */
  60   for (i = 0; i < groups; i++) {
  61     result[i] = number * ratios[i] / sum;
  62   }
  63
  64   /* 2a.  Determine the remaining fractions. */
  65   for (i = 0; i < groups; i++) {
  66     rest[i] = number * ratios[i] - result[i] * sum;
  67   }
  68
  69   /* 2b. Find how much source is left to be distributed. */
  70   for (i = 0; i < groups; i++) {
  71     number -= result[i];
  72   }
  73
  74   while (number > 0) {
  75     max = max_count = 0;
  76
  77     /* Find the largest remaining fraction(s). */
  78     for (i = 0; i < groups; i++) {
  79       if (rest[i] > max) {
  80         max_count = 1;
  81         max_groups[0] = i;
  82         max = rest[i];
  83       } else if (rest[i] == max) {
  84         max_groups[max_count] = i;
  85         max_count++;
  86       }
  87     }
  88
  89     if (max_count == 1) {
  90       /* Give an extra source to the target with largest remainder. */
  91       result[max_groups[0]]++;
  92       rest[max_groups[0]] = 0;
  93       number--;
  94     } else {
  95       int min = result[max_groups[0]], which_min = max_groups[0];
  96
  97       /* Give an extra source to the target with largest remainder and
  98        * smallest whole number. */
  99       fc_assert(max_count > 1);
 100       for (i = 1; i < max_count; i++) {
 101         if (result[max_groups[i]] < min) {
 102           min = result[max_groups[i]];
 103           which_min = max_groups[i];
 104         }
 105       }
 106       result[which_min]++;
 107       rest[which_min] = 0;
 108       number--;
 109     }
 110   }
 111
 112 #ifdef DEBUG
 113   number = original_number;
 114   for (i = 0; i < groups; i++) {
 115     fc_assert(result[i] >= 0);
 116     number -= result[i];
 117   }
 118   fc_assert(number == 0);
 119 #endif /* DEBUG */
 120 }