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

typedef unsigned int u32;

#define TRIES 10000
#define COUNT 1000

unsigned long qrand()
{
	static unsigned long seed = 1;
	return ( ((seed = seed * 214013L + 2531011L) >> 16) & 0x7fff );
}

struct Sortable
{
	u32 sortKey;
	Sortable *next;
};

struct Object : public Sortable
{
	void init()
	{
		sortKey = qrand() * qrand() * qrand();
		data = qrand();
	}

	int data;
};

Object *objects = NULL;

void makelist()
{
	objects = NULL;
	for(int n=0;n<COUNT;n++)
	{
		Object *o = new Object;
		o->next = objects;
		objects = o;
	}
}

template<int shift>
Sortable *rsorti(Sortable *head, Sortable lists[], Sortable *tails[])
{
	while(head)
	{
		u32 bucket = (head->sortKey >> shift) & 0xff;

		tails[bucket]->next = head;
		tails[bucket] = head;
		head = head->next;
	}

	Sortable list;
	Sortable *prev = &list;
	for (unsigned int n=0;n<256;n++)
	{
		if (lists[n].next)
		{
			prev->next = lists[n].next;
			prev = tails[n];
			lists[n].next = NULL;
			tails[n] = &lists[n];
		}
	}
	prev->next = NULL;
	return list.next;
}

template<typename T>
T *rsort(T *head)
{
	Sortable lists[256];
	Sortable *tails[256];

	if (!head)
		return NULL;

	for (unsigned int n=0;n<256;n++)
	{
		lists[n].next = NULL;
		tails[n] = &lists[n];
	}

	Sortable *sorted = head;
	sorted = rsorti<0>(sorted, lists, tails);
	sorted = rsorti<8>(sorted, lists, tails);
	sorted = rsorti<16>(sorted, lists, tails);
	sorted = rsorti<24>(sorted, lists, tails);
	return (T *)sorted;
}

int main(int argc, char *argv[])
{
	int tries;
	makelist();

	clock_t rb = clock();
	tries = TRIES;
	while(tries--)
	{
		Object *o = objects;
		while(o)
		{
			o->init();
			o = (Object *)o->next;
		}

		objects = rsort(objects);
	}
	clock_t re = clock();

	printf("radix sort: %f\n", float(re-rb)/CLOCKS_PER_SEC);

	return 0;
}