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

#if defined(bsdi)
#include "fdrand48.h"
#define srand48 fsrand48
#define drand48 fdrand48 
#endif

#define ALLOCATION_SIZE (1024*1024*8)
static unsigned long memsize = 0;
char* allocation_buffer = NULL;
int   allocation_index = 0;
#define PADDING 8

int verbose_mode = 0;

struct word_list
{
    char* word;
    struct word_list* next;
};


void init_buffer(void)
{
    if((allocation_buffer = malloc(ALLOCATION_SIZE)) == NULL)
    {
	perror("malloc");
	exit(1);
    }
    allocation_index = 0;
    if(verbose_mode)
	fprintf(stderr, "Memory allocation +%d\n", ALLOCATION_SIZE);
}

void* alloc_memory(long sz)
{
    void* ptr;

    if(allocation_index + sz + PADDING >= ALLOCATION_SIZE)
	init_buffer();
    ptr = (void *)(allocation_buffer + allocation_index);
    allocation_index += sz;
    allocation_index += (PADDING-1) - (allocation_index+PADDING-1)%PADDING;

    memsize += sz;

    return ptr;

}


FILE* file_open(const char* fname)
{
    if(!strcmp(fname, "-"))
	return stdin;
    return fopen(fname, "r");
}

void print_list(struct word_list* list)
{
    puts("(");
    while(list)
    {
	printf(" %s", list->word);
	list = list->next;
    }
    puts(")");
}

struct word_list* make_list(FILE* fp, struct word_list* list, long* len)
{
    struct word_list* p;
    static char buff[BUFSIZ];
    long n, linelen;

    n = 0;
    if(verbose_mode)
	fprintf(stderr, "make word list.\n(256 lines per `#')\n");

    while(fgets(buff, BUFSIZ, fp) != NULL)
    {
	p = (struct word_list *)alloc_memory(sizeof(struct word_list));
	linelen = strlen(buff);
	p->word = (char *)alloc_memory(linelen + 1);
	memcpy(p->word, buff, linelen + 1);
	p->next = list;
	list = p;
	if(verbose_mode)
	{
	    if(n % 256 == 0 && n > 0)
		fprintf(stderr, "#");
	}
	n++;
    }
    if(verbose_mode)
	fprintf(stderr, " done\n");
    *len = n;
    return list;
}

struct word_list* split_list(struct word_list* list,
			     long list_len,
			     long *len1,
			     long *len2)
{
    long i, n;
    struct word_list* ret;

    if(list_len == 1)
    {
	*len1 = 1;
	*len2 = 0;
	return NULL;
    }

    *len1 = list_len / 2;
    *len2 = list_len - *len1;

    n = *len1 - 1;
    for(i = 0; i < n; i++)
	list = list->next;
    ret = list->next;
    list->next = NULL;
    return ret;
}

struct word_list* merge(struct word_list* list1, struct word_list* list2)
			
{
    struct word_list* list;
    struct word_list* p;

    if(drand48() < 0.5)
    {
	list = list1;
	list1 = list2;
	list2 = list;
    }

    list = list1;
    list1 = list1->next;
    list->next = NULL;

    while(list1 && list2)
    {
	p = list2;
	list2 = list2->next;
	p->next = list;
	list = p;

	p = list1;
	list1 = list1->next;
	p->next = list;
	list = p;
    }

    while(list2)
    {
	p = list2;
	list2 = list2->next;
	p->next = list;
	list = p;
    }
    while(list1)
    {
	p = list1;
	list1 = list1->next;
	p->next = list;
	list = p;
    }

    return list;
}

struct word_list* shake(struct word_list* list, long len)
{
    struct word_list* ret;
    if(len > 256)
    {
	struct word_list* list2;
	long len1, len2;

	list2 = split_list(list, len, &len1, &len2);

	list = shake(list, len1);
	list2 = shake(list2, len2);
	return merge(list, list2);
    }

    if(verbose_mode)
	fprintf(stderr, "[%ld]", len);

    ret = NULL;
    while(--len >= 0)
    {
	long pos;
	struct word_list* cur;
	struct word_list* prev;

	pos = (long)(drand48() * (len + 1));
	cur = list;
	prev = NULL;
	while(--pos >= 0)
	{
	    prev = cur;
	    cur = cur->next;
	}
	if(prev == NULL)
	    list = list->next;
	else
	    prev->next = cur->next;
	cur->next = ret;
	ret = cur;
    }
    return ret;
}	

int main(int argc, char** argv)
{
    struct word_list* list;
    FILE* fp;
    long len;
    extern double drand48();
    extern void srand48();
    time_t t;
    time(&t);
    srand48(t);

    list = NULL;
    init_buffer();

    if(argc == 1)
	list = make_list(stdin, list, &len);
    else
    {
	int i = 1;

	if(!strcmp(argv[1], "-h"))
	{
	    fprintf(stderr, "%s [-h] [-v]\n", argv[0]);
	    return 0;
	}
	else if(!strcmp(argv[1], "-v"))
	{
	    verbose_mode = 1;
	    if(argc == 2)
		list = make_list(stdin, list, &len);
	    else
	    {
		i++;
		goto each_file;
	    }
	}
	else
	{
	  each_file:
	    len = 0;
	    for(; i < argc; i++)
	    {
		long n;

		if((fp = file_open(argv[i])) == NULL)
		{
		    perror(argv[i]);
		    continue;
		}
		if(verbose_mode)
		    fprintf(stderr, "Loading from %s\n",
			    fp == stdin ? "stdin" : argv[i]);
		list = make_list(fp, list, &n);
		len += n;
		if(fp != stdin)
		    fclose(fp);
	    }
	}
    }

    if(verbose_mode)
	fprintf(stderr, "Total list length: %ld\n", len);

    list = shake(list, len);

    while(--len >= 0)
    {
	fputs(list->word, stdout);
	list = list->next;
    }
    if(verbose_mode)
	fprintf(stderr, "\n");
    return 0;
}