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

typedef struct Seito
{
    int num;
    char lname[20];
    char fname[20];
    int point;
} Seito;

typedef struct Cell
{
    void* car;
    struct Cell* cdr;
} Cell;

typedef struct SortResult
{
    int count;
    Cell* cell;
} SortResult;

void destroy_cell(Cell* cell)
{
    Cell* a;
    while (cell != NULL)
    {
        a = cell;
        cell = cell->cdr;
        free(a->car);
        free(a);
    }
}

Cell* loadData_(FILE* f)
{
    int num;
    char lname[20];
    char fname[20];
    int point;
    Cell* head = NULL;
    Cell* tail = NULL;
    Cell* cell = NULL;
    int success = 1;
    Seito* seito = NULL;
    
    while (fscanf(f, "%d%s%s%d", &num, lname, fname, &point) != EOF)
    {
        success = 0;
  
        seito = malloc(sizeof(Seito));
        if (seito != NULL)
        {
            seito->num = num;
            strcpy(seito->lname, lname);
            strcpy(seito->fname, fname);
            seito->point = point;
            
            cell = malloc(sizeof(Cell));
            if (cell != NULL)
            {
                cell->car = seito;
                cell->cdr = NULL;
                if (tail == NULL)
                {
                    tail = cell;
                    head = cell;
                }
                else
                {
                    tail->cdr = cell;
                    tail = cell;
                }
                success = 1;
            }
        }
        if (!success)
        {
            break;
        }
    }
    if (success)
    {
        return head;
    }
    else
    {
        free(seito);
        destroy_cell(head);
        return NULL;
    }
}

Cell* loadData()
{
    Cell* cell = NULL;
    FILE* f = fopen("seito.dat", "r");
    if (f != NULL)
    {
        cell = loadData_(f);
        fclose(f);
    }
    return cell;
}

SortResult* sort(Cell* cell, int (*cmp)(Cell*, Cell*))
{
    SortResult* result = malloc(sizeof(SortResult));
    if (result != NULL)
    {
        Cell* h = cell;
        Cell* c = NULL;
        Cell* n = NULL;
        int count = 0;
        
        if (h != NULL)
        {
            cell = h->cdr;
            h->cdr = NULL;
            while (cell != NULL)
            {
                n = cell->cdr;
                count++;
                if (cmp(cell, h) <= 0)
                {
                    cell->cdr = h;
                    h = cell;
                }
                else
                {
                    c = h;
                    while (c->cdr != NULL)
                    {
                        count++;
                        if (cmp(cell, c->cdr) <= 0)
                        {
                            cell->cdr = c->cdr;
                            c->cdr = cell;
                            break;
                        }
                        c = c->cdr;
                    }
                }
                cell = n;
            }
        }
        result->count = count;
        result->cell = h;
    }
    return result;
}

int bigToSmall(Cell* x, Cell* y)
{
    Seito* x1 = x->car;
    Seito* y1 = y->car;
    if (x1->point < y1->point)
    {
        return 1;
    }
    else if (x1->point > y1->point)
    {
        return -1;
    }
    else
    {
        return 0;
    }
}

int main(void)
{
    Seito* seito;
    Cell* cell;
    SortResult* result;
    Cell* head = loadData();
    if (head != NULL)
    {
        result = sort(head, bigToSmall);
        if (result != NULL)
        {
            head = result->cell;
            cell = head;
            printf("%4s %-20s %s\n", "番号", "氏名", "得点");
            while (cell != NULL)
            {
                seito = cell->car;
                printf("%d %-10s%-10s%3d\n", seito->num, seito->lname, seito->fname, seito->point);
                cell = cell->cdr;
            }
            printf("整列の為の比較回数=%d回\n", result->count);
            free(result);
        }
        destroy_cell(head);
    }
    return 0;
}