#include <stdio.h>
#include <stdlib.h>

struct task {
	unsigned int weight, weight_inv;
	int active;

	unsigned int time, time_avg;
	int time_norm, avg_fract;
} task[10]  = {
	{ .weight = 10 },
	{ .weight = 40 },
	{ .weight = 80 },
};

#define MIN_S		100
#define MAX_S		1000

#define SLICE(x)	(MAX_S * task[x].weight_inv)
#define MINSLICE(x)	(MIN_S * task[x].weight_inv)

#define WEIGTH0		40
#define WEIGTH0_INV	((1 << 16) / WEIGTH0)

unsigned int time_avg, time_norm_sum;
int avg_fract, weight_sum_inv;

static void normalize_avg(int i)
{
	if (!weight_sum_inv)
		return;
	/* assume the common case of 0/1 first, then fallback */
	if (task[i].avg_fract < 0 || task[i].avg_fract >= WEIGTH0_INV * MAX_S) {
		task[i].time_avg++;
		task[i].avg_fract -= WEIGTH0_INV * MAX_S;
		if (task[i].avg_fract < 0 || task[i].avg_fract >= WEIGTH0_INV * MAX_S) {
			task[i].time_avg += task[i].avg_fract / (WEIGTH0_INV * MAX_S);
			task[i].avg_fract %= WEIGTH0_INV * MAX_S;
		}
	}
	if (avg_fract < 0 || avg_fract >= weight_sum_inv) {
		time_avg++;
		avg_fract -= weight_sum_inv;
		if (avg_fract < 0 || avg_fract >= weight_sum_inv) {
			time_avg += avg_fract / weight_sum_inv;
			avg_fract %= weight_sum_inv;
		}
	}
}

int main(void)
{
	int i, j, l, task_cnt;
	unsigned int s;
	unsigned int time_sum, time_sum2;

	task_cnt = time_avg = 0;
	for (i = 0; i < 10; i++) {
		if (!task[i].weight)
			continue;
		task[i].active = 1;
		task_cnt++;
		task[i].weight_inv = (1 << 16) / task[i].weight;
	}
	weight_sum_inv = task_cnt * WEIGTH0_INV * MAX_S;
	printf("w: %u,%u\n", WEIGTH0_INV * MAX_S, weight_sum_inv);

	time_norm_sum = avg_fract = 0;
	l = 0;
	s = 0;
	while (1) {
		j = -1;
		for (i = 0; i < 10; i++) {
			if (i == l)
				continue;
			if (!task[i].active && task[i].weight) {
				if (!(rand() % 30)) {
					normalize_avg(i);
					task[i].active = 1;
					if (!task_cnt)
						goto done;
#if 1
					if ((int)(task[i].time_avg - time_avg) < 0) {
						task[i].time_norm -= (int)(task[i].time_avg - time_avg) * WEIGTH0_INV * MAX_S + task[i].avg_fract;
						task[i].time_avg = time_avg;
						task[i].avg_fract = 0;
					}
#else
					unsigned int new_time_avg = time_avg;
					int new_avg_fract = avg_fract / task_cnt - task[i].weight_inv * MAX_S;
					while (new_avg_fract < 0) {
						new_time_avg--;
						new_avg_fract += WEIGTH0_INV * MAX_S;
					}
					if ((int)(task[i].time_avg - new_time_avg) < 0 ||
					    ((int)(task[i].time_avg - new_time_avg) == 0 &&
					     task[i].avg_fract < new_avg_fract)) {
						task[i].time_norm += (int)(new_time_avg - task[i].time_avg) * WEIGTH0_INV * MAX_S +
							new_avg_fract - task[i].avg_fract;
						task[i].time_avg = new_time_avg;
						task[i].avg_fract = new_avg_fract;
					}
#endif
				done:
					task_cnt++;
					weight_sum_inv += WEIGTH0_INV * MAX_S;
					avg_fract += (int)(task[i].time_avg - time_avg) * WEIGTH0_INV * MAX_S + task[i].avg_fract;
					time_norm_sum += task[i].time_norm;
				}
			}
			if (!task[i].active)
				continue;
			if (j < 0 ||
			    (int)(task[i].time_norm + MINSLICE(i) - (task[j].time_norm + MINSLICE(j))) < 0)
				j = i;
		}

		if (!task[l].active) {
			if (j < 0)
				continue;
			goto do_switch;
		}

		if (!(rand() % 100)) {
			task[l].active = 0;
			task_cnt--;
			weight_sum_inv -= WEIGTH0_INV * MAX_S;
			avg_fract -= (int)(task[l].time_avg - time_avg) * WEIGTH0_INV * MAX_S + task[l].avg_fract;
			time_norm_sum -= task[l].time_norm;
			if (j < 0)
				continue;
			goto do_switch;
		}

		if (j >= 0 &&
		    ((int)(task[l].time_norm - (task[j].time_norm + SLICE(j))) >= 0 ||
		     ((int)(task[l].time_norm - task[j].time_norm) >= 0 &&
		      (int)(task[l].time_norm - (s + SLICE(l))) >= 0))) {
			int prev_time_avg;
		do_switch:
			prev_time_avg = time_avg;
			normalize_avg(l);
			if (prev_time_avg < time_avg)
				printf("-\n");
			l = j;
			s = task[l].time_norm;
		}
		task[l].time += MIN_S;
		task[l].time_norm += MINSLICE(l);
		task[l].avg_fract += MINSLICE(l);
		time_norm_sum += MINSLICE(l);
		avg_fract += MINSLICE(l);

		printf("%u", l);
		time_sum = time_sum2 = 0;
		for (i = 0; i < 10; i++) {
			if (!task[i].active) {
				if (task[i].weight)
					printf("\t%3u/%u: -\t", i, task[i].weight);
				continue;
			}
			time_sum += task[i].time_norm;
			time_sum2 += task[i].time_avg * WEIGTH0_INV * MAX_S + task[i].avg_fract;
			printf("\t%3u/%u:%5u/%-7g/%-7g", i, task[i].weight, task[i].time,
				(double)task[i].time_norm / (1 << 16),
				task[i].time_avg + (double)task[i].avg_fract / (WEIGTH0_INV * MAX_S));
		}
		if (time_sum != time_norm_sum)
			abort();
		if (time_sum2 != time_avg * weight_sum_inv + avg_fract)
			abort();
		if (time_sum != time_sum2)
			abort();
		printf("\t| %g/%g\n", (double)time_norm_sum / task_cnt / (1 << 16),
			time_avg + (double)(int)avg_fract / weight_sum_inv);
	}
}