/* distribute -- put P copies of N things in M buckets without duplicates
 *
 * This can be used, e.g. to assign papers to a committee of
 * reviewers: There are N papers, M reviewers, each paper must be
 * reviewed by P reviewers. And we want all reviewers review (about)
 * the same number of papers.
 *
 * Obviously P <= M and M > 0. (P = 0 or N = 0 is allowed, but not
 * very interesting.)
 *
 * To do: scanf() doesn't detect overflow.
 *
 * Copyright © 2014 World Wide Web Consortium
 * See http://www.w3.org/Consortium/Legal/2002/copyright-software-20021231
 *
 * Author: bert Bos <bert@w3.org>
 * Created: 24 jan 2014
 */

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <err.h>
#include <time.h>


/* random_uniform -- return random number in range 0..(n-1) */
static int random_uniform(int n)
{
  int r, m = RAND_MAX - (RAND_MAX % n);

  do {r = random();} while (r >= m); /* Avoid "modulo bias" */
  return r % n;
}


int main(int argc, char *argv[])
{
  int nitems, nbuckets, ncopies, i, j, maxitems, k, p, q;
  static int **bucket;

  /* Read three numbers from stdin or from the command line arguments */
  if (argc == 1) {
    if (isatty(0)) printf("Number of items: ");
    if (scanf(" %i", &nitems) < 1) errx(1, "Expected a number");
    if (isatty(0)) printf("Number of buckets: ");
    if (scanf(" %i", &nbuckets) < 1) errx(1, "Expected a number");
    if (isatty(0)) printf("Number of copies: ");
    if (scanf(" %i", &ncopies) < 1) errx(1, "Expected a number");
  } else if (argc == 4) {
    if (sscanf(argv[1]," %u",&nitems)<1) errx(1,"<items> must be a number");
    if (sscanf(argv[2]," %u",&nbuckets)<1) errx(1,"<buckets> must be a number");
    if (sscanf(argv[3]," %u",&ncopies)<1) errx(1,"<copies> must be a number");
  } else {
    fprintf(stderr, "Usage: %s [items buckets copies]\n", argv[0]);
    exit(1);
  }
  if (nitems < 0) errx(1, "<items> is too big or too small");
  if (nbuckets <= 0) errx(1, "<buckets> is too big or too small");
  if (ncopies < 0) errx(1, "<copies> is too big or too small");
  if (ncopies > nbuckets) errx(1, "<copies> cannot be greater than <buckets>");

  /* Each bucket will get maxitems or (maxitems - 1) items */
  maxitems = (nitems * ncopies + nbuckets - 1) / nbuckets;

  /* Allocate an array of buckets */
  bucket = malloc(nbuckets * sizeof(*bucket));
  if (!bucket) err(1, NULL);

  for (i = 0; i < nbuckets; i++) {
    bucket[i] = malloc(maxitems * sizeof(**bucket));
    if (!bucket[i]) err(1, NULL);
  }

  /* Place maxitems * nbuckets items (which may be a few too many) */
  srandom(time(NULL));
  p = 1;			/* Item to place */
  q = 0;			/* Copies of item p already placed */
  for (j = 0; j < maxitems; j++) {
    for (i = 0; i < nbuckets; i++) {
      k = random_uniform(nbuckets - i); /* Choose a bucket */
      bucket[k][j] = p;		     /* Put p in that bucket */

      /* Move the bucket to the end of the list */
      int *h = bucket[k];
      bucket[k] = bucket[nbuckets-1-i];
      bucket[nbuckets-1-i] = h;

      /* If p has been placed ncopies times, go to next p */
      if (++q == ncopies) {p++; q = 0;}
    }
  }

  /* Print result (omitting the items that were too many) */
  for (i = 0; i < nbuckets; i++) {
    printf("Bucket %u:", i + 1); /* Number them 1,2... instead of 0,1... */
    for (j = 0; j < maxitems; j++)
      if (bucket[i][j] <= nitems) printf(" %u", bucket[i][j]);
    printf("\n");
  }

  return 0;
}