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

/* Node of a doubly linked list */
// A complete working C program to demonstrate all insertion methods
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    char name[80];
    char author[80];
    int year;
} Item;

// A linked list node
struct Node {
    Item data;
    struct Node *next;
    struct Node *prev;
};

//*Функция для создания элемента списка (тип элемента MusicalComposition)**/
struct Node *getNewNode(char *name, char *author, int year) {
    struct Node *newNode = (struct Node *) malloc(sizeof(struct Node));
    newNode->next = NULL;
    newNode->prev = NULL;
    strcpy(newNode->data.name, name);
    strcpy(newNode->data.author, author);
    newNode->data.year = year;
    return newNode;
}

/* Given a reference (pointer to pointer) to the head of a list
   and an int, inserts a new node on the front of the list. */
//void push(struct Node** head_ref,struct Node* node_to_insert)
//{
//    /* 1. allocate node */
//    struct Node* new_node = node_to_insert;
//
//    /* 3. Make next of new node as head and previous as NULL */
//    new_node->next = (*head_ref);
//    new_node->prev = NULL;
//
//    /* 4. change prev of head node to new node */
//    if((*head_ref) !=  NULL)
//        (*head_ref)->prev = new_node ;
//
//    /* 5. move the head to point to the new node */
//    (*head_ref) = new_node;
//    printf("%s",(*head_ref)->data.name);
//}

//* Given a node as prev_node, insert a new node after the given node */
void insertAfter(struct Node *prev_node, struct Node *node_to_insert) {
    /*1. check if the given prev_node is NULL */
    if (prev_node == NULL) {
        printf("the given previous node cannot be NULL");
        return;
    }
    /* 2. allocate new node */
    struct Node *new_node = node_to_insert;

    /* 3. put in the data  */
//    new_node->data  = new_data;

    /* 4. Make next of new node as next of prev_node */
    new_node->next = prev_node->next;

    /* 5. Make the next of prev_node as new_node */
    prev_node->next = new_node;

    /* 6. Make prev_node as previous of new_node */
    new_node->prev = prev_node;

    /* 7. Change previous of new_node's next node */
    if (new_node->next != NULL)
        new_node->next->prev = new_node;
}

//* #3 добавляет element  в конец списка musical_composition_list//
void append(struct Node **head_ref, struct Node *node_to_insert) {
    /* 1. allocate node */
//    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));

    struct Node *last = *head_ref;  /* used in step 5*/

    /* 2. put in the data  */
    struct Node *new_node = node_to_insert;

    /* 3. This new node is going to be the last node, so
          make next of it as NULL*/
    new_node->next = NULL;

    /* 4. If the Linked List is empty, then make the new
          node as head */
    if (*head_ref == NULL) {
        printf("%s", "THIS!");
        new_node->prev = NULL;
        *head_ref = new_node;
        return;
    }

    /* 5. Else traverse till the last node */
    while (last->next != NULL)
        last = last->next;

    /* 6. Change the next of last node */
    last->next = new_node;

    /* 7. Make last node as previous of new node */
    new_node->prev = last;

    return;
}

// #6 Выводит названия композиций /
void printList(struct Node *head) {
    struct Node *currentNode = head;
    if (currentNode == NULL) return;
    while (currentNode != NULL) {
        printf(" %s ", currentNode->data.name);
        currentNode = currentNode->next;
    }
    printf("\n");
}

//
struct Node *getNodeByIndex(struct Node *head, int index) {
    struct Node *tmp = head;
    int i = 0;
    while (tmp && i < index) {
        tmp = tmp->next;
        i++;
    }

    return tmp;
}

int getIndexByName(struct Node *head, char *name) {
    int index = 0;
    struct Node *tmp = head;
    struct Node *next = NULL;
    while (tmp) {
        if (strcmp(name, tmp->data.name) == 0) return index;
        next = tmp->next;
        tmp = next;
        index++;
    }
    return -1;
}

/* Function to delete a node in a Doubly Linked List.
   head_ref --> pointer to head node pointer.
   del  -->  pointer to node to be deleted. */
void deleteNode(struct Node **head_ref, struct Node *del) {
    /* base case */
    if (*head_ref == NULL || del == NULL)
        return;

    /* If node to be deleted is head node */
    if (*head_ref == del)
        *head_ref = del->next;

    /* Change next only if node to be deleted is NOT the last node */
    if (del->next != NULL)
        del->next->prev = del->prev;

    /* Change prev only if node to be deleted is NOT the first node */
    if (del->prev != NULL)
        del->prev->next = del->next;

    /* Finally, free the memory occupied by del*/
    free(del);

}


void deleteNodeByIndex(struct Node **head_ref, int index) {
    deleteNode(head_ref, getNodeByIndex(*head_ref, index));
}

//* #4 удаляет элемент element списка, у которого значение name равно значению  name_for_remove*/
void deleteNodeByName(struct Node **head_ref, char *name) {
    deleteNodeByIndex(head_ref, getIndexByName(*head_ref, name));
}

// Создает двусвязный списоk, returns ptr to HEAD
struct Node *createDLL() {
    struct Node *head = malloc(sizeof(struct Node));
    head->next = NULL;
    head->prev = NULL;
    return head;
}

//* #2 создает список музыкальных композиций MusicalCompositionList*/
struct Node *getListOfNodes(char **array_names, char **array_authors, const int *array_years, int n) {
    struct Node *head = NULL;
    int i;
    for (i = 0; i < n; i++) {
        struct Node *insertedNode = malloc(sizeof(struct Node));
        int len = strlen(array_names[i]);
        strcpy(insertedNode->data.author, array_authors[i]);
        strcpy(insertedNode->data.name, array_names[i]);
        insertedNode->data.year = array_years[i];
        append(&head, insertedNode);
    }
    return head;
}

//* #5 возвращает количество элементов списка */
int count(struct Node *head) {
    int count = 0;
    struct Node *tmp = head;
    struct Node *next = NULL;
    while (tmp) {
        count++;
        next = tmp->next;
        tmp = next;
    }
    return count;
}
/*sorting */
struct Node *split(struct Node *head);

// Function to merge two linked lists
struct Node *merge(struct Node *first, struct Node *second)
{
    // If first linked list is empty
    if (!first)
        return second;

    // If second linked list is empty
    if (!second)
        return first;

    // Pick the smaller value
    if (first->data.year > second->data.year)
    {
        first->next = merge(first->next,second);
        first->next->prev = first;
        first->prev = NULL;
        return first;
    }
    else
    {
        second->next = merge(first,second->next);
        second->next->prev = second;
        second->prev = NULL;
        return second;
    }
}

// Function to do merge sort
struct Node *mergeSort(struct Node *head)
{
    if (!head || !head->next)
        return head;
    struct Node *second = split(head);

    // Recur for left and right halves
    head = mergeSort(head);
    second = mergeSort(second);

    // Merge the two sorted halves
    return merge(head,second);
}

// Utility function to swap two integers
void swap(int *A, int *B)
{
    int temp = *A;
    *A = *B;
    *B = temp;
}

// Split a doubly linked list (DLL) into 2 DLLs of
// half sizes
struct Node *split(struct Node *head)
{
    struct Node *fast = head,*slow = head;
    while (fast->next && fast->next->next)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    struct Node *temp = slow->next;
    slow->next = NULL;
    return temp;
}

/*
char **add_string(char **array, const char *word)
{

  char *word[80];
  char *term = ":"; // termination char
  char *prnt = "print";

  while (strcmp(term, word) != 0)
{

  scanf("%s", word);
  if (strcmp(term, word) == 0)
    {
    printf("Terminate\n");
    }

  else if (strcmp(prnt, word) == 0)
  {
    printf("Enumerate\n");

    int i;

    for (i=0; i<count; i++)
    {
      printf("Slot %d: %s\n",i, array[i]);
    }

  }
  else
  {
    printf("String added to array\n");
    count++;
    array = (char**)realloc(array, (count+1)*sizeof(*array));
    array[count-1] = (char*)malloc(sizeof(word));
    strcpy(array[count-1], word);
  }

}
}
*/




char** add_string(char** array, int* size, const char* string)
{   printf("%s", size);
    printf("%s", string);
    char* newArray = realloc(array, (*size + 1) *sizeof(char*) );
    newArray[*size] = malloc(strlen(string)+1);
    strcpy(newArray[*size], string);
    *size += 1;
}



int main() {

    struct Node *head = NULL;
    int array_size =0;
    int len = 1;
    int i = 0;
    int j = 0, k = 0;
    int count_till_three = 0;
    int c;
    char* buffer = NULL;

    int curr_year = -1;
    char* curr_name;
    char* curr_author;

    while((c = getchar()) != EOF){
        buffer = realloc(buffer,len*sizeof(char));
        buffer[i] =(char)c;
        i++;
        len++;
        if(c == ':') {
            if(count_till_three == 0){
                curr_name = malloc(sizeof(char)*strlen(buffer));
                strcpy(curr_name,buffer);

            }
            if(count_till_three == 1){
               curr_author = (char*)malloc(sizeof(char)*strlen(buffer));

                    strcpy(curr_author,buffer);

            }
            count_till_three++;
            free(buffer);
            buffer = NULL;
            len =1;
            i = 0;
        }
        if(c == '\n'){
            curr_year = atoi(buffer);
            free(buffer);
            buffer = NULL;
            len =1;
            i = 0;
            count_till_three = 0;

        }

        if(curr_year != -1) {

            struct Node *insertedNode = malloc(sizeof(struct Node));
            printf("%s",curr_author);
            strcpy(insertedNode->data.author, curr_author);
            strcpy(insertedNode->data.name, curr_name);
            insertedNode->data.year = curr_year;
            append(&head, insertedNode);


            curr_year = -1;

            free(curr_author);
            free(curr_name);
            curr_author = NULL;
            curr_name = NULL;
            count_till_three = 0;
            break;
        }
    }
    printf("%s", "HERsE!");
    printList(head);
    //  ///   Future House:FrankJavCee:2015//
    printf("%s", "HsdadsdasdasdaERsE!");

    return 0;
}