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

    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)
		{
			printf("inside first loop\n");
			payload = cell->payload;
			printf("searching for %s",payload);
			del = linlistFind(payload, *anchor);
			printf("del: %p\n",del);
			while(del)
			{
				printf("inside second loop\n");
				linlistExtract(*anchor,del);
				del = linlistFind(payload, anchor_adr);
			}
			break;
		}
}

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 linlistFind(char* payload,linlist_p anchor){
    while(anchor != NULL && strcmp(strdup((*anchor).payload), payload) != 0){ //pointer nicht null und das element
        anchor = anchor->next;
        
    }
    if(anchor != NULL){
        printf("Found: %s",(*anchor).payload);
        return anchor;
    }
    else{
        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 linlist_extract_first(linlist_p *anchor)
{
   linlist_p res = *anchor;

   if(res)
   {
      *anchor = res->next;
      res->next = NULL;
   }
   return res;
}

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 = linlist_extract_first(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;
    }
}