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

#define bool int
#define false 0
#define true 1

typedef struct linlist{
    char *payload;
    struct linlist *next;
}linlist_cell, *linlist_p ;

linlist_p anchor;
linlist_p *anchor_adr = &anchor;

void linlist_free_cell(linlist_p junk);
void linlist_free(linlist_p *junk);
linlist_p linlist_alloc_cell(char* payload);
linlist_p linlist_insert_first(linlist_p *anchor, linlist_p newcell);
linlist_p linlist_extract_first(linlist_p *anchor);
linlist_p linlistFind(char* payload, linlist_p anchor);
linlist_p linlistExtract(linlist_p *anchor, linlist_p cell);
void linlist_sort(linlist_p *anchor);

int main() {
    linlist_p i;

    char buffer[255];
    char reverse_buffer[255][255];
    FILE *in = stdin;

    while (fgets(buffer, 255, in))
    {
        linlist_p newcell = linlist_alloc_cell(buffer);
       	linlist_insert_first(anchor_adr,newcell);
    }
	
	linlist_sort(anchor);

    printf("\nSORTED OUTPUT\n");
    for (i = anchor; i != NULL; i = i->next)
    {
        fprintf(stdout, "%s", i->payload);
    }
    linlist_free(&anchor);
}


void linlist_sort(linlist_p *anchor)
{
	bool swapped = true;
	linlist_p cell = anchor;
	linlist_p dump;
	while(swapped)
	{
		swapped = false;
		cell = anchor;
		while(cell->next)
		{
			if(strcmp(cell->payload,cell->next->payload) > 0)
			{
			//	printf("swapping %s and %s",cell->payload,cell->next->payload);
				dump = cell->next->payload;
				cell->next->payload = cell->payload;
				cell->payload = dump;
				swapped = true;
			}else
			{
				
			}	
			cell = cell->next;
		}
	}
}


linlist_p linlistExtract(linlist_p *anchor, linlist_p cell)
{
	if(*anchor == cell)
	{
		anchor=cell->next;
		return cell;
	}else
	{
		
	}
}

linlist_p linlistFind(char* payload, linlist_p anchor)
{
	printf("find\n");
	linlist_p cell = anchor;

	if(cell == NULL)
	{
		printf("anchor is null");
		return NULL;
	}
	
	while(cell)
	{
		printf("to search %s \n",payload);
		if(strcmp(payload,cell->payload))
		{	
		printf("found same\n");
			return cell;
		}
		else
		{
			printf("found nothing\n");
			cell = cell->next;
		}
	}
	return NULL;
}


void linlist_free_cell(linlist_p junk)
{
    free(junk);
}

void linlist_free(linlist_p *junk){

    if ((*junk)->next == NULL)
    {
        free(*junk);
        return;
    }
    else
    {
        linlist_free(&((*junk)->next));
        free(*junk);
    }
}

linlist_p linlist_alloc_cell(char* payload)
{
    linlist_p newcell = malloc(sizeof(linlist_p));
    char *value;
    newcell->payload = strdup(payload);
    newcell->next = NULL;
    return (newcell);

}

linlist_p linlist_insert_first(linlist_p *anchor, linlist_p newcell)
{
    newcell->next = *anchor;
    *anchor = newcell;
    return(*anchor);
}

linlist_p linlist_extract_first(linlist_p *anchor)
{
    if (*anchor == NULL)
    {
        return NULL;
    }
    else
    {
        linlist_p *return_var;
        return_var = anchor;
        *anchor = (*anchor)->next;
        return (*return_var);
    }

}