#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 ;

typedef struct countlist{
	char *payload;
	int occurence;
    	struct countlist *next;
}countlist_cell, *countlist_p ;

countlist_p count_anchor;

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);
countlist_p countlist_alloc_cell(char* payload);
countlist_p linlist_count(linlist_p *anchor);

int main() {
    linlist_p i;

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

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

    printf("\nSORTED OUTPUT\n");
    for (i = anchor; i != NULL; i = i->next)
    {
        fprintf(stdout, "%s", i->payload);
    }
    linlist_free(&anchor);
}
countlist_p linlist_count(linlist_p *anchor)
{
	linlist_p cell = *anchor;
	linlist_p del;
	char* payload;
	while(cell)
		{
			payload = cell->payload;
			del = linlist_find(payload, 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);
}

countlist_p countlist_alloc_cell(char* payload)
{
    countlist_p newcell = malloc(sizeof(countlist_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);
}

countlist_p countlist_insert_first(countlist_p *anchor, countlist_p newcell)
{
    newcell->next = *anchor;
    *anchor = newcell;
    return(*anchor);
}

LinList_p LinListExtract(LinList_p* anchor,LinList_p cell){
    if(*anchor == NULL){
        printf("liste ist leer");
        return NULL;
    }
    if((*anchor)->next == NULL){ //wenn liste nur ein element hat
        if(*anchor == cell){
            return NULL;
        }
        else{
            printf("element nicht in der liste enthalten");
            return *anchor;
        }
    }
    if(*anchor == cell){
        LinList_p ret = LinListExtractFirst(anchor);
        return ret;
    }
    
    while(*anchor != NULL && (*anchor)->next != cell){ //springe bis letztes element
        anchor = &(*anchor)->next;
    }  
    LinList_p tmp = *anchor;
    if((*anchor)->next == cell){ //zelle gefunden

        tmp->next = cell->next;
        cell->next = NULL;
        return cell;
    }
    else{ //keine zelle gefunden
        return NULL;
    }
}