//
//	sort.c, ©2011 by Josh Moyer <JMoyer@nodmain.net>, all rights reserved.
//
//	An algorithm to: "sort numbers in an array (100 sized array) that
//	range between 1 – 4 (Inclusive)".
//
//	To do:
//	- add C++ template support to allow for types other than char

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

#define FALSE 0
#define TRUE -1

#define B 100 // beats/bytes
#define BPM 4 // beats per measure

#define TESTCASES 52

#define SORTASC 1
#define SORTDESC 2

#define ERRFILL 1
#define ERRSORT 2
#define ERRMEM 3
#define ERRTEST 4

typedef char i_t;

typedef struct l_t l_t;

struct l_t
{
	l_t *p;
	i_t *i;
	l_t *n;
};

char main(int argc, char argv[])
{
	int eq = B; // elements, quantity
	i_t *s = (i_t*)calloc(eq, sizeof(i_t)); // source array
	i_t *d = (i_t*)calloc(eq, sizeof(i_t)); // destination array

	if (s == 0 || d == 0)
	{
		printf("ERRMEM\n");
		return ERRMEM;
	}
	
	if (fill(s, eq))
	{
		printf("ERRFILL\n");
		return ERRFILL;
	}
	
	if (sort(s, d, SORTASC, eq))
	{
		printf("ERRSORT\n");
		return ERRSORT;
	}
	
	printf("Input buffer:\n");
	print(s, eq);
	
	printf("\n\nOutput buffer (ascending order):\n");
	print(d, eq);

	if (sort(s, d, SORTDESC, eq))
	{
		printf("ERRSORT\n");
		return ERRSORT;
	}
	
	printf("\n\nOutput buffer (descending order):\n");
	print(d, eq);

	printf("\n");
	test();
	
	return FALSE;
}

int fill(i_t *a, int n)
{
	int bc, bn, mn;

	for (bc=0,bn=1,mn=1 ; bc < n ; bc++,bn++)
	{
		if (bn == 1)
		{
			*(a+bc) = mn;
		}
		else
		{
			*(a+bc) = bn;
			if (bn==BPM) 
			{
				bn=0;
				mn++;
			}
		}
	}

	return FALSE;
}

int print(i_t *s, int n)
{
	int i;
	
	for (i=0 ; i < n ; i++)
	{
		printf("%d,", s[i]);
	}
	
	printf("\n\n");
	
	return FALSE;
}

int sort(i_t *s, i_t *d, int o, int n)
{
	int i;					// item/index/iterator/etc...
	l_t *lb, *lbi, *lh;		// list base, list base incremented, list head
	l_t *li, *lt;			// list item, list tail
	i_t *si;				// source incremented
	
	if (o != SORTASC && o != SORTDESC) return TRUE;

	if (!(lb = calloc(n, sizeof(l_t)))) return TRUE;
	
	lh = lb;
	li = lb;
	li->p = lb;
	li->i = s;
	li->n = lb;
	lt = lb;

	for (i=1; i < n ; i++)
	{
		lbi = lb+i;
		si = s+i;
		
		lbi->i = si;
		
		if (*si < *li->i)
		{
			while (TRUE)
			{
				if (li->p == li)
				{
					lbi->p = lbi;
					lh = lbi;
					break;
				}
				else
				{
					if (*si < *li->p->i)
					{
						li = li->p;
						continue;
					}
					else
					{
						li->p->n = lbi;
						lbi->p = li->p;
						break;
					}
				}
			}
			
			li->p = lbi;
			lbi->n = li;
		}
		else
		{		
			while (TRUE)
			{
			if (li->n == li)
				{
					lbi->n = lbi;
					lt = lbi;
					break;
				}
				else
				{
					if (*si >= *li->n->i)
					{
						li = li->n;
						continue;
					}
					else
					{
						li->n->p = lbi;
						lbi->n = li->n;
						break;
					}
				}
			}
			
			li->n = lbi;
			lbi->p = li;
		}
		
		li = lbi;
	}
	
	if (o == SORTASC)
	{
		i = 0;
		li = lh;
		while (TRUE)
		{
			*(d+i) = *li->i;
			if (li->n == li) break;
			i++;
			li = li->n;
		}
	}
	
	if (o == SORTDESC)
	{
		i = 0;
		li = lt;
		while (TRUE)
		{
			*(d+i) = *li->i;
			if (li->p == li) break;
			i++;
			li = li->p;
		}
	}
	
	free(lb);
	
	return FALSE;
}

int test()
{
	int i;
	
	typedef struct tc tc;
	struct tc	// test case
	{
		int s;	// sort order
		int i;	// input
		int e;	// expected
		int a;	// actual
	};

	tc ts[TESTCASES];
	// some cases may fail due to processor and/or compiler specific issues,
	// such as endianness or signed vs unsigned chars
	ts[ 0].s = SORTASC;  ts[ 0].i = 0x04030201; ts[ 0].e = 0x04030201; ts[ 0].a = 0;
	ts[ 1].s = SORTDESC; ts[ 1].i = 0x04030201; ts[ 1].e = 0x01020304; ts[ 1].a = 0;
	ts[ 2].s = SORTASC;  ts[ 2].i = 0x01020304; ts[ 2].e = 0x04030201; ts[ 2].a = 0;
	ts[ 3].s = SORTDESC; ts[ 3].i = 0x01020304; ts[ 3].e = 0x01020304; ts[ 3].a = 0;
	ts[ 4].s = SORTASC;  ts[ 4].i = 0x00000001; ts[ 4].e = 0x01000000; ts[ 4].a = 0;
	ts[ 5].s = SORTDESC; ts[ 5].i = 0x00000001; ts[ 5].e = 0x00000001; ts[ 5].a = 0;
	ts[ 6].s = SORTASC;  ts[ 6].i = 0x01000000; ts[ 6].e = 0x01000000; ts[ 6].a = 0;
	ts[ 7].s = SORTDESC; ts[ 7].i = 0x01000000; ts[ 7].e = 0x00000001; ts[ 7].a = 0;
	ts[ 8].s = SORTASC;  ts[ 8].i = 0x01000100; ts[ 8].e = 0x01010000; ts[ 8].a = 0;
	ts[ 9].s = SORTDESC; ts[ 9].i = 0x01000100; ts[ 9].e = 0x00000101; ts[ 9].a = 0;
	ts[10].s = SORTASC;  ts[10].i = 0x01010201; ts[10].e = 0x02010101; ts[10].a = 0;
	ts[11].s = SORTDESC; ts[11].i = 0x01010201; ts[11].e = 0x01010102; ts[11].a = 0;
	ts[12].s = SORTASC;  ts[12].i = 0x01000201; ts[12].e = 0x02010100; ts[12].a = 0;
	ts[13].s = SORTDESC; ts[13].i = 0x01000201; ts[13].e = 0x00010102; ts[13].a = 0;
	ts[14].s = SORTASC;  ts[14].i = 0x01030204; ts[14].e = 0x04030201; ts[14].a = 0;
	ts[15].s = SORTDESC; ts[15].i = 0x01030204; ts[15].e = 0x01020304; ts[15].a = 0;
	ts[16].s = SORTASC;  ts[16].i = 0x01020304; ts[16].e = 0x04030201; ts[16].a = 0;
	ts[17].s = SORTDESC; ts[17].i = 0x01020304; ts[17].e = 0x01020304; ts[17].a = 0;
	ts[18].s = SORTASC;  ts[18].i = 0x02010403; ts[18].e = 0x04030201; ts[18].a = 0;
	ts[19].s = SORTDESC; ts[19].i = 0x02010403; ts[19].e = 0x01020304; ts[19].a = 0;
	ts[20].s = SORTASC;  ts[20].i = 0x03040102; ts[20].e = 0x04030201; ts[20].a = 0;
	ts[21].s = SORTDESC; ts[21].i = 0x03040102; ts[21].e = 0x01020304; ts[21].a = 0;
	ts[22].s = SORTASC;  ts[22].i = 0x04030201; ts[22].e = 0x04030201; ts[22].a = 0;
	ts[23].s = SORTDESC; ts[23].i = 0x04030201; ts[23].e = 0x01020304; ts[23].a = 0;
	ts[24].s = SORTASC;  ts[24].i = 0x04020301; ts[24].e = 0x04030201; ts[24].a = 0;
	ts[25].s = SORTDESC; ts[25].i = 0x04020301; ts[25].e = 0x01020304; ts[25].a = 0;
	ts[26].s = SORTASC;  ts[26].i = 0x04040104; ts[26].e = 0x04040401; ts[26].a = 0;
	ts[27].s = SORTDESC; ts[27].i = 0x04040104; ts[27].e = 0x01040404; ts[27].a = 0;
	ts[28].s = SORTASC;  ts[28].i = 0x01010104; ts[28].e = 0x04010101; ts[28].a = 0;
	ts[29].s = SORTDESC; ts[29].i = 0x01010104; ts[29].e = 0x01010104; ts[29].a = 0;
	ts[30].s = SORTASC;  ts[30].i = 0x01010401; ts[30].e = 0x04010101; ts[30].a = 0;
	ts[31].s = SORTDESC; ts[31].i = 0x01010401; ts[31].e = 0x01010104; ts[31].a = 0;
	ts[32].s = SORTASC;  ts[32].i = 0x04010101; ts[32].e = 0x04010101; ts[32].a = 0;
	ts[33].s = SORTDESC; ts[33].i = 0x04010101; ts[33].e = 0x01010104; ts[33].a = 0;
	ts[34].s = SORTASC;  ts[34].i = 0x0206B500; ts[34].e = 0x060200B5; ts[34].a = 0;
	ts[35].s = SORTDESC; ts[35].i = 0x0206B500; ts[35].e = 0xB5000206; ts[35].a = 0;
	ts[36].s = SORTASC;  ts[36].i = 0xB5060200; ts[36].e = 0x060200B5; ts[36].a = 0;
	ts[37].s = SORTDESC; ts[37].i = 0xB5060200; ts[37].e = 0xB5000206; ts[37].a = 0;
	ts[38].s = SORTASC;  ts[38].i = 0x020600B5; ts[38].e = 0x060200B5; ts[38].a = 0;
	ts[39].s = SORTDESC; ts[39].i = 0x020600B5; ts[39].e = 0xB5000206; ts[39].a = 0;
	ts[40].s = SORTASC;  ts[40].i = 0x000602B5; ts[40].e = 0x060200B5; ts[40].a = 0;
	ts[41].s = SORTDESC; ts[41].i = 0x000602B5; ts[41].e = 0xB5000206; ts[41].a = 0;
	ts[42].s = SORTASC;  ts[42].i = 0x00000005; ts[42].e = 0x05000000; ts[42].a = 0;
	ts[43].s = SORTDESC; ts[43].i = 0x00000005; ts[43].e = 0x00000005; ts[43].a = 0;
	ts[44].s = SORTASC;  ts[44].i = 0xFF000000; ts[44].e = 0xFF000000; ts[44].a = 0;
	ts[45].s = SORTDESC; ts[45].i = 0xFF000000; ts[45].e = 0x000000FF; ts[45].a = 0;
	ts[46].s = SORTASC;  ts[46].i = 0xFF000000; ts[46].e = 0x000000FF; ts[46].a = 0;
	ts[47].s = SORTDESC; ts[47].i = 0xFF000000; ts[47].e = 0xFF000000; ts[47].a = 0;
	ts[48].s = SORTASC;  ts[48].i = 0x0000FF00; ts[48].e = 0xFF000000; ts[48].a = 0;
	ts[49].s = SORTDESC; ts[49].i = 0x0000FF00; ts[49].e = 0x000000FF; ts[49].a = 0;
	ts[50].s = SORTASC;  ts[50].i = 0x00FF0000; ts[50].e = 0xFF000000; ts[50].a = 0;
	ts[51].s = SORTDESC; ts[51].i = 0x00FF0000; ts[51].e = 0x000000FF; ts[51].a = 0;

	for (i=0 ; i < TESTCASES ; i++)
	{
		if (sort((i_t*)&ts[i].i, (i_t*)&ts[i].a, ts[i].s, 4))
			printf("Case %*d failed.  sort() encountered an error.\n", 2, i);
		
		if (memcmp(&ts[i].a, &ts[i].e, sizeof(ts[i].i)))
		{
			printf("Case %*d failed.  Expected 0x%0*X.  Actual 0x%0*X.\n", 2, i, 8, ts[i].e, 8, ts[i].a);
		}
		else
		{
			printf("Case %*d passed.\n", 2, i);
		}
	}
	
	return FALSE;	
}