#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <gmp.h>
#include <unistd.h>

#define SIZE 4096

#define out_of_memory(n) do { printf("Out of memory: " n "\n"); exxx(1); } while(0)

typedef enum { DIGIT, NON_DIGIT } match;

union strnum {
    char **ptr;
    char *string;
    int *integer;
    void *generic;
    mpz_t *bignum;
};

typedef struct _linkedlist {
    union strnum data;
    struct _linkedlist *next;
} LinkedList;

void *pointers[1024 * 1024];
int pointer_size[1024 * 1024];
int pointer_count = 0;

void exxx(int i)
{
    exit(i);
}

void fprint_raw(char *p, int n)
{
    int i;

    for (i = 0; i < n; i++)
	fprintf(stderr, "%c", p[i]);
}

/* A far from great huge list of pointers,
 * used to verify that we aren't allocating
 * over an existing pointer as well as to
 * have a list to verify against when we try
 * to free a pointer.
 */
int add_pointer(void *p, int n)
{
    int i, match = 0, uhoh = 0;

    /* Verify it doesn't cross an existing pointer */
    for (i = 0; i < pointer_count; i++) {
	if (p > pointers[i] && p < pointers[i] + pointer_size[i]) {
	    fprintf(stderr, "Uh oh.  %p crosses %p (size %d) [%p-%p]! : [",
		    p, pointers[i], pointer_size[i], pointers[i],
		    pointers[i] + pointer_size[i]);
	    fprint_raw(pointers[i], 32);
	    fprintf(stderr, "] or from start position [");
	    fprint_raw(p, 32);
	    fprintf(stderr, "]\n");
	    uhoh = 1;
	    //exxx(2);
	}
    }

    fprintf(stderr, "Adding pointer %p of size %d.\n", p, n);
    /* Then add it */
    for (i = 0; i < pointer_count; i++) {
	if (pointers[i] == NULL) {
	    match = 1;
	    pointers[i] = p;
	    pointer_size[i] = n;
	    break;
	}
    }

    if (!match) {
	pointers[pointer_count] = p;
	pointer_size[pointer_count++] = n;
    }

    return uhoh;
}

static int string_number_cmp(const void *a, const void *b)
{
    char *temp_data;
    LinkedList *left = ((LinkedList *) a)->next, *right =
	((LinkedList *) b)->next;
    int i;
    match str = NON_DIGIT;

    while (1) {
	if (left == NULL && right == NULL) {
	    return 0;
	} else {
	    if (left == NULL && right != NULL)
		return -1;
	    else if (left != NULL && right == NULL) {
		return 1;
	    } else {
		if (str == NON_DIGIT) {
		    i = strcmp(left->data.string, right->data.string);
		    str = DIGIT;
		} else {
		    i = mpz_cmp(*(left->data.bignum),
				*(right->data.bignum));
		    str = NON_DIGIT;
		}
		if (i) {
		    return i;
		} else {
		    left = left->next;
		    right = right->next;
		}
	    }
	}
    }
}

LinkedList *alloc_linkedlist(LinkedList ** list, void *data)
{
    LinkedList *temp;
    int i, match = 0;

    assert(data != NULL);
    temp = malloc(sizeof(LinkedList));
    if (temp == NULL)
	return NULL;

    temp->data.generic = data;
    temp->next = NULL;

    if (add_pointer(temp, sizeof(LinkedList))) {
	fprintf(stderr, "Linkedlist data: ");
	fprint_raw(data, 8);
	fprintf(stderr, "\n");
    }
    //fprintf(stderr, " ]%p[ ", temp);
    *list = temp;

    return temp;
}

/* Simple step through linkedlist to clear */
void free_linkedlist(LinkedList * list, int free_data)
{
    LinkedList *temp;
    int i, match;

    while (list != NULL) {
	if (free_data) {
	    free(list->data.generic);
	    fprintf(stderr, "Freeing data %p\n",
		    list->data.generic);
	}
	temp = list;
	list = list->next;
	match = 0;
	for (i = 0; i < pointer_count; i++) {
	    if (temp == pointers[i]) {
		match = 1;
		break;
	    }
	}
	if (!match) {
	    fprintf(stderr,
		    "Trying to deallocated %p, which was never allocated.\n",
		    temp);
	    exxx(2);
	}
	fprintf(stderr, "Freeing linkedlist %p\n", temp);
	free(temp);
	pointers[i] = NULL;
	//fprintf(stderr, " >%p< ", temp);
    }
    //fprintf(stderr, "\n");
}

/* Read in from stdin into an a linked list of the form
 * lines = [ count of lines | chain ]
 * chain = [ line of text | chain ]
 *
 * or NULL on failure
 */
LinkedList *read_in_lines(void)
{
    LinkedList *lines, **current_line;
    char buffer[SIZE], *current_pos, *rest, *line;
    int size, count, line_length;
    int *temp;

    current_line = &lines;

    temp = malloc(sizeof(int));

    if ((lines = alloc_linkedlist(current_line, temp)) == NULL) {
	return NULL;
    }

    current_line = &((*current_line)->next);

    if (temp == NULL) {
	fprintf(stderr, "Inappropriate free called.\n");
	//free(lines);
	return NULL;
    }

    if (add_pointer(temp, sizeof(int)))
	fprintf(stderr, "Allocating int for return.\n");

    line = NULL;
    line_length = count = 0;

    while ((size = read(STDIN_FILENO, buffer, SIZE)) > 0) {
	current_pos = buffer;
	while ((rest = memchr(current_pos, '\n', size)) != NULL) {
	    /* Append line. */
	    if ((line =
		 realloc(line,
			 line_length + (rest - current_pos + 1))) == NULL)
		out_of_memory("line");
	    memcpy(&line[line_length], current_pos, (rest - current_pos));

	    line_length += (rest - current_pos);
	    line[line_length] = '\0';
	    /* Add to chain */
	    count++;

	    if (add_pointer(line, line_length))
		fprintf(stderr, "Adding in read in line: %s\n", line);

	    if (alloc_linkedlist(current_line, line) == NULL) {
		free_linkedlist(lines, 1);
		return NULL;
	    }
	    current_line = &((*current_line)->next);

	    line_length = 0;
	    line = NULL;

	    /* Adjust buffer */
	    size -= (rest - current_pos + 1);
	    current_pos = rest + 1;
	}
	/* Append part of line */
	if (size > 0) {
	    if ((line = realloc(line, line_length + size)) == NULL)
		out_of_memory("line");
	    memcpy(&line[line_length], current_pos, size);
	    line_length += size;
	}
    }

    if (line_length > 0) {
	/* Add to chain */
	count++;
	if ((line = realloc(line, line_length + 1)) == NULL)
	    out_of_memory("line");
	line[line_length] = '\0';

	add_pointer(line, line_length);
	fprintf(stderr, "Adding in read in line: %s\n", line);

	if (alloc_linkedlist(current_line, line) == NULL) {
	    free_linkedlist(lines, 1);
	    return NULL;
	}
	//current_line = &((*current_line)->next);
    }

    *(lines->data.integer) = count;
    //fprintf(stderr, "\n");
    return lines;
}

/* Simple linked list to array move */
char **linkedlist_to_array(LinkedList * chain, int count)
{
    char **lines = malloc(sizeof(LinkedList) * count);
    int i = 0;

    if (lines == NULL)
	return NULL;

    if (add_pointer(lines, sizeof(LinkedList) * count))
	fprintf(stderr,
		"Adding in block for linkedlist to array conversion.\n");

    for (; chain != NULL; chain = chain->next)
	lines[i++] = chain->data.string;

    return lines;
}

/* Two part divide of text into numbers and non-numbers */
LinkedList *string_and_numbers(char *text)
{
    LinkedList *san, **san_temp;
    char *temp, *mt_c;
    mpz_t *mt_m;
    match str = NON_DIGIT;

    san = NULL;
    san_temp = &san;

    fprintf(stderr, "%s\n", text);
    while (*text != '\0') {
	/* String */
	temp = text;
	if (str == DIGIT) {
	    for (; *temp != '\0' && strchr("0123456789", *temp) != NULL;
		 temp++);
	    if ((mt_m = malloc(temp - text + 1)) == NULL)
		out_of_memory("san");
	    if (add_pointer(mt_m, sizeof(mpz_t)))
		fprintf(stderr, "Adding in big int.\n");
	    mpz_init(*mt_m);
	    gmp_sscanf(text, "%Zd", *mt_m);
	    if (alloc_linkedlist(san_temp, mt_m) == NULL)
		out_of_memory("san, n");
	    str = NON_DIGIT;
	} else {
	    for (; *temp != '\0' && strchr("0123456789", *temp) == NULL;
		 temp++);
	    if ((mt_c = malloc(sizeof(mpz_t))) == NULL)
		out_of_memory("san");
	    memcpy(mt_c, text, temp - text);
	    mt_c[temp - text] = '\0';
	    fprintf(stderr, "%s\n", mt_c);
	    if (add_pointer(mt_c, temp - text + 1))
		fprintf(stderr, "Adding in text fragment: %s.\n", mt_c);
	    if (alloc_linkedlist(san_temp, mt_c) == NULL)
		out_of_memory("san, n");
	    str = DIGIT;
	}
	san_temp = &((*san_temp)->next);
	text = temp;
    }

    //fprintf(stderr, "\n");
    return san;
}

/* Stuff pointers into array so string_number_cmp
 * can manually shuffle them around as appropriate.
 */
void sort_by_string_number(char **chain, int count)
{
    LinkedList array[count], *temp, *temp2;
    int i;

    printf("((((\n");
    for (i = 0; i < count; i++) {
	printf("%d : %s\n", i, chain[i]);
	array[i].data.string = chain[i];
	array[i].next = string_and_numbers(chain[i]);
    }
    printf("))))\n");

    printf("<<<<\n");
    for (i = 0; i < count; i++)
	printf("%d : %s\n", i, chain[i]);
    printf(">>>>\n");

    qsort(array, count, sizeof(LinkedList), string_number_cmp);

    for (i = 0; i < count; i++) {
	chain[i] = array[i].data.string;
	free_linkedlist(array[i].next, 0);
	/* Special clean-up for bignums. */
	/*temp = array[i].next;
	   while (temp != NULL) {
	   free(temp->data.string);
	   temp2 = temp->next;
	   free(temp);
	   if (temp2 == NULL)
	   temp = NULL;
	   else {
	   mpz_clear(*(temp2->data.bignum));
	   free(temp2->data.bignum);
	   temp = temp2->next;
	   free(temp2);
	   }
	   } */
    }
}

/* Print array */
void print_lines_as_array(char **array, int count)
{
    int i;
    // Print the sorted list, using the original lines.
    for (i = 0; i < count; i++) {
	printf("%s\n", array[i]);
    }
}

int main()
{
    LinkedList *lines;
    char **lines_as_array;
    int count;

    fprintf(stderr, "read_in_lines()\n");
    lines = read_in_lines();

    if (lines == NULL)
	out_of_memory("ril");

    count = *(lines->data.integer);

    fprintf(stderr, "linkedlist_to_array(...)\n");
    lines_as_array = linkedlist_to_array(lines->next, count);

    if (lines_as_array == NULL)
	out_of_memory("lta");

    fprintf(stderr, "print_lines_as_array(...)\n");
    print_lines_as_array(lines_as_array, count);
    printf("------\n");
    /* We never reallocated the text data, so don't clear it */
    free_linkedlist(lines, 0);

    fprintf(stderr, "print_lines_as_array(...)\n");
    print_lines_as_array(lines_as_array, count);
    printf("++++++\n");
    fprintf(stderr, "sort_by_string_number(...)\n");
    sort_by_string_number(lines_as_array, count);

    fprintf(stderr, "print_lines_as_array(...)\n");
    print_lines_as_array(lines_as_array, count);

    return 0;
}