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

// Define List Node
typedef struct _Node *NodePtr;
typedef struct _Node {
    int data;                // Store value of the node
    NodePtr next;            // Store address of the next node
} Node;


//                            //
//       List functions       //
//                            //

// Purpose: Insert a new node with the given data "after the target" node.
// Returns: void
void insert(NodePtr *target, int data) {  // double pointer for adding first element
    NodePtr new_node = (NodePtr)malloc(sizeof(Node));
    new_node->data = data;
    new_node->next = NULL;

    // for empty list
    if (*target == NULL) {
        *target = new_node;
        return;
    }

    // for non-empty list
    new_node->next = (*target)->next;
    (*target)->next = new_node;
}

// Purpose: Delete the node "after the target" node and return the deleted node's data.
// Returns: The data of the deleted node.
int delete(NodePtr *target) {  // double pointer for deleting last element
    // for empty
    if (*target == NULL) {
        printf("List is empty!");
        exit(1);
    }

    // for the last element
    if ((*target)->next == NULL ||     // for normal list
        (*target)->next == *target) {  // for circular list
        NodePtr deleted = *target;
        int data = deleted->data;

        *target = NULL;
        free(deleted);
        return data;
    }

    // for other elements
    NodePtr deleted = (*target)->next;
    int data = deleted->data;

    (*target)->next = deleted->next;
    free(deleted);
    return data;
}

// Purpose: Find the first position in the list where the data is not less than the given value
//          and insert a new node with the given value at that position.
// Returns: A pointer to the newly inserted node.
NodePtr insertnum_s2b(NodePtr *head, int value) {
    NodePtr *current = head;  // Use an indirect pointer

    // Traverse the list to find the appropriate position
    while (*current != NULL && (*current)->data < value) {
        current = &((*current)->next);
    }

    // Create a new node and insert it into the list
    NodePtr new_node = (NodePtr)malloc(sizeof(Node));
    new_node->data = value;
    new_node->next = *current;
    *current = new_node;

    return new_node;
}

// Purpose: Find the first position in the list where the data is not less than the given value
//          and insert a new node with the given value at that position.
// Returns: A pointer to the newly inserted node.
NodePtr insertnum_b2s(NodePtr *head, int value) {
    NodePtr *current = head;  // Use an indirect pointer

    // Traverse the list to find the appropriate position
    while (*current != NULL && (*current)->data > value) {
        current = &((*current)->next);
    }

    // Create a new node and insert it into the list
    NodePtr new_node = (NodePtr)malloc(sizeof(Node));
    new_node->data = value;
    new_node->next = *current;
    *current = new_node;

    return new_node;
}

// Purpose: Concatenate two linked lists.
// Returns: A pointer to the concatenated linked list.

// concatenate 先放 p 再放 q 
NodePtr concatenate(NodePtr p, NodePtr q) {
    if (p == NULL)
        return q;

    NodePtr current = p;
    while (current->next != NULL)
        current = current->next;
    current->next = q;

    return p;
}

// Purpose: Reverse the linked list.
// Returns: A pointer to the head of the reversed linked list.
NodePtr invert(NodePtr head) {
    NodePtr prev = NULL;
    NodePtr current = head;
    NodePtr next_node;

    while (current != NULL) {
        next_node = current->next;
        current->next = prev;
        prev = current;
        current = next_node;
    }

    return prev;
}

// Purpose: Convert a linked list into a circular linked list.
// Returns: A pointer to the head of the circular linked list.
NodePtr Lin2Cir(NodePtr head) {
    NodePtr current = head;

    // get last node
    while (current->next != NULL)
        current = current->next;

    // last -> head
    current->next = head;

    return head;
}

// 線性的 linklist 打印機
// Returns: void
void printL(NodePtr head) {
    NodePtr current = head;
    int elements_in_current_line = 0;
    int elements_in_one_line = 10;

    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;

        if (++elements_in_current_line >= elements_in_one_line) {
            printf("\n");
            elements_in_current_line = 0;
        }
    }
    printf(elements_in_current_line ? "\n" : "");
}

// 環狀的 linklist 打印機
// Returns: void
void printC(NodePtr head) {
    // Empty List
    if (head == NULL) {
        return;
    }

    int elements_in_one_line = 10;
    int elements_in_current_line = 0;
    NodePtr current = head;

    do {
        printf("%d ", current->data);
        current = current->next;

        if (++elements_in_current_line >= elements_in_one_line) {
            printf("\n");
            elements_in_current_line = 0;
        }
    } while (current != head);

    printf(elements_in_current_line ? "\n" : "");
}

// Purpose: Create an empty linked list.
// Returns: A NULL pointer representing an empty linked list.
NodePtr create_list() { return NULL; }


//                            //
//         Extensions         //
//                            //

// Purpose: Append a new node with the given data to the end of the linked list.
// Returns: void
void append(NodePtr *target, int data) {
    // Traverse the list until the end is reached
    while (*target != NULL)
        // Move to the next node using its next pointer
        target = &((*target)->next);

    NodePtr new_node = (NodePtr)malloc(sizeof(Node));
    new_node->data = data;
    new_node->next = NULL;

    *target = new_node;
}

// Purpose: Move the pointer to the specified number of steps in the linked list.
// Returns: A pointer to the new position after moving the specified steps.
NodePtr advance(NodePtr current, int steps) {
    int i;
    for (i = 0; i < steps && current != NULL; i++)
        current = current->next;
    return current;
}

// Purpose: Free the memory allocated for the linked list.
// Returns: void
void free_list(NodePtr *head) {
    NodePtr current = *head;       // Current list node, used for traversing the list

    while (current != NULL) {
        NodePtr temp = current;    // Temporarily store the current node
        current = current->next;   // Move to the next node
        free(temp);                // Free the memory of the node
    }

    *head = NULL;                  // Set the external pointer (list->head) to NULL
}

// Purpose: Filter elements in the linked list based on a given condition.
// Returns: A pointer to the new linked list containing filtered elements.
NodePtr filter(int (*condition)(int), NodePtr head) {
    NodePtr result = create_list();
    NodePtr current = head;

    while (current != NULL) {
        if (condition(current->data)) {
            append(&result, current->data);
        }
        current = current->next;
    }

    return result;
}

//                            //
//        Self-Defined        //
//                            //

// Purpose: Check if a number is odd (used as a condition for filtering).
// Returns: 1 if the number is odd, 0 otherwise.
int is_odd(int value) {
    return value % 2 == 1;
}

// Purpose: Check if a number is even (used as a condition for filtering).
// Returns: 1 if the number is even, 0 otherwise.
int is_even(int value) {
    return value % 2 == 0;
}

// Function to filter elements in the linked list based on a given condition
// and insert the filtered elements using a specified insert function.
// Returns: A pointer to the new linked list containing filtered elements.

//filter_and_insert(要操作的, 插入奇數還是偶數, insertnum_s2b OR b2s)	
NodePtr filter_and_insert(NodePtr source, int (*condition)(int), NodePtr (*insert)(NodePtr*, int)) {
    NodePtr filtered = create_list();
    NodePtr current = source;

    while (current != NULL) {
        if (condition(current->data)) {
            insert(&filtered, current->data);
        }
        current = current->next;
    }

    return filtered;
}

// Purpose: Generate a linked list with random numbers within a specified range.
// Returns: void
void random_number_generator(NodePtr *head, int range, int offset, int len) {
    srand(time(NULL));
    free_list(head);
    int i;
    for (i = 0; i < len; i++)
        insertnum_s2b(head, rand() % range + offset);
}

// Purpose: Perform the "Eeny, meeny, miny, moe" algorithm on a circular linked list.
// Returns: A pointer to result.
NodePtr emmm(NodePtr *head, int steps) {
    NodePtr result = create_list();

    NodePtr *current = head;                      // move current to 1st
    while ((*current)->next != *current) {
        *current = advance(*current, steps - 2);  // move current to 5th

        int deleted = delete(current);            // delete 6th
        append(&result, deleted);
        *current = advance(*current, 1);          // move current to deleted + 1
    }

    // the last element in the circular list
    int last_deleted = delete(current);
    append(&result, last_deleted);

    return result;
}

/*
// 插入新節點到目標節點之後
// 參數：target - 目標節點的指針，data - 新節點的數據
// 返回值：void
void insert(NodePtr *target, int data)
    // 實現細節參見函數定義
}

// 刪除目標節點之後的節點並返回被刪除節點的數據
// 參數：target - 目標節點的指針
// 返回值：被刪除節點的數據
int delete(NodePtr *target) {
    // 實現細節參見函數定義
}

// 將新節點插入到線性鏈表中，按照升序排序
// 參數：head - 鏈表的頭指針，value - 新節點的數值
// 返回值：插入的新節點的指針
NodePtr insertnum_s2b(NodePtr *head, int value) {
    // 實現細節參見函數定義
}

// 將新節點插入到線性鏈表中，按照降序排序
// 參數：head - 鏈表的頭指針，value - 新節點的數值
// 返回值：插入的新節點的指針
NodePtr insertnum_b2s(NodePtr *head, int value) {
    // 實現細節參見函數定義
}

// 連接兩個鏈表
// 參數：p - 第一個鏈表的頭指針，q - 第二個鏈表的頭指針
// 返回值：連接後的新鏈表的頭指針
NodePtr concatenate(NodePtr p, NodePtr q) {
    // 實現細節參見函數定義
}

// 反轉線性鏈表
// 參數：head - 鏈表的頭指針
// 返回值：反轉後的新鏈表的頭指針
NodePtr invert(NodePtr head) {
    // 實現細節參見函數定義
}

// 將線性鏈表轉換為環狀鏈表
// 參數：head - 鏈表的頭指針
// 返回值：環狀鏈表的頭指針
NodePtr Lin2Cir(NodePtr head) {
    // 實現細節參見函數定義
}

// 打印線性鏈表中的所有元素，每行最多打印10個元素
// 參數：head - 鏈表的頭指針
// 返回值：void
void printL(NodePtr head) {
    // 實現細節參見函數定義
}

// 打印環狀鏈表中的所有元素，每行最多打印10個元素
// 參數：head - 環狀鏈表的頭指針
// 返回值：void
void printC(NodePtr head) {
    // 實現細節參見函數定義
}

// 創建一個空的線性鏈表
// 參數：無
// 返回值：空鏈表的頭指針，即 NULL
NodePtr create_list() {
    // 實現細節參見函數定義
}

// 在鏈表尾部添加一個新節點
// 參數：target - 鏈表尾部節點的指針，data - 新節點的數據
// 返回值：void
void append(NodePtr *target, int data) {
    // 實現細節參見函數定義
}

// 將指針在鏈表中移動指定步數
// 參數：current - 當前節點的指針，steps - 移動的步數
// 返回值：新位置的節點的指針
NodePtr advance(NodePtr current, int steps) {
    // 實現細節參見函數定義
}

// 釋放分配給鏈表節點的內存
// 參數：head - 鏈表的頭指針
// 返回值：void
void free_list(NodePtr *head) {
    // 實現細節參見函數定義
}

// 根據給定的條件過濾鏈表中的元素
// 參數：condition - 過濾條件的函數指針，head - 鏈表的頭指針
// 返回值：新鏈表的頭指針，包含過濾的元素
NodePtr filter(int (*condition)(int), NodePtr head) {
    // 實現細節參見函數定義
}

// 檢查數字是否為奇數（用作過濾條件）
// 參數：value - 要檢查的數字
// 返回值：1表示奇數，0表示偶數
int is_odd(int value) {
    // 實現細節參見函數定義
}

// 檢查數字是否為偶數（用作過濾條件）
// 參數：value - 要檢查的數字
// 返回值：1表示偶數，0表示奇數
int is_even(int value) {
    // 實現細節參見函數定義
}

// 根據給定的條件過濾鏈表中的元素並使用指定的插入函數插入過濾的元素
// 參數：source - 源鏈表，condition - 過濾條件的函數指針，insert - 插入函數的指針
// 返回值：新鏈表的頭指針，包含過濾並插入的元素
NodePtr filter_and_insert(NodePtr source, int (*condition)(int), NodePtr (*insert)(NodePtr*, int)) {
    // 實現細節參見函數定義
}

// 生成具有指定範圍內的隨機數的線性鏈表
// 參數：head - 鏈表的頭指針，range - 隨機數的範圍，offset - 隨機數的偏移量，len - 鏈表的長度
// 返回值：void
void random_number_generator(NodePtr *head, int range, int offset, int len) {
    // 實現細節參見函數定義
}

// 執行"Eeny, meeny, miny, moe"算法
// 參數：head - 環狀鏈表的頭指針，steps - 每次移動的步數
// 返回值：包含刪除的元素的新鏈表的頭指針

//emmm 每幾個取一次 
NodePtr emmm(NodePtr *head, int steps) {
    // 實現細節參見函數定義
}

// 主函數
int main() {
    // 實現細節參見 main 函數定義
    return 0;
}

*/

//random_number_generator(&list, 100, 1, 40);
//filter_and_insert(list, is_odd, insertnum_s2b);
//printL(list1);
//NodePtr p = concatenate(list1, list2);
//NodePtr invlist = invert(p);
//list = Lin2Cir(invlist);
//printC(list);
//NodePtr result = emmm(&list, 6);

int main() {
    NodePtr list = create_list();
    NodePtr list1 = create_list();
    NodePtr list2 = create_list();

    // 1.
    // Use rand()%100+1 to get 40 random numbers, 
    // output the numbers (one by one, one space in between, 
    // and 10 numbers in one line), insert the odd numbers into a created linear list (listPointer list1) one by one 
    // (sorted in ascending order – from small to big), 
    // and insert the even numbers into another created linear list (listPointer list2) one by one 
    // (sorted in ascending order – from big to small). 
    // (Note: Be sure to use the two functions void insertnum_s2b(listPointer *p, int x) and void insertnum_b2s(listPointer *p, int x).)
    random_number_generator(&list, 100, 1, 40);
    printf("List:\n");
    printL(list);
    printf("\n");

    list1 = filter_and_insert(list, is_odd, insertnum_s2b);
    list2 = filter_and_insert(list, is_even, insertnum_b2s);

    // 2. output the linear list data from list1 and list2
    // (one by one from the first to the last, one space in between, and 10 numbers in one line). 
    // (Note: Be sure to use the function void printL(listPointer p). )
    printf("List1:\n");
    printL(list1);
    printf("\n");
    printf("List2:\n");
    printL(list2);
    printf("\n");

    // 3.
    // produce a new linear list (listPointer p) that contains the linear list list1 followed by the linear list list2, 
    // and output data from the new linear list list (one by one from the first to the last, one space in between, and 10 numbers in one line). 
    // (Note: Be sure to use the function listPointer concatenate(listPointer p1, listPointer p2). )
    NodePtr p = concatenate(list1, list2);
    printf("Concatenated List:\n");
    printL(p);
    printf("\n");

    // 4.
    // invert the linear list list to form a new linear list invlist 
    // and output the linear list data from the new linear list invlist 
    // (one by one from the first to the last, one space in between, and 10 numbers in one line). 
    // (Note: Be sure to use the function listPointer invert(listPointer p). )
    NodePtr invlist = invert(p);
    printf("Inverted List:\n");
    printL(invlist);
    printf("\n");

    // 5.
    // change the linear list invlist to a circular list. 
    // (Note: Be sure to use the function listPointer Lin2Cir(listPointer p). )
    list = Lin2Cir(invlist);

    // 6.
    // output the circular list data 
    // (one by one from the first to the last, one space in between, and 10 numbers in one line). 
    // (Note: Be sure to use the function void printC(listPointer p). )
    printf("Circular List:\n");
    printC(list);
    printf("\n");

    // 7.
    // After it becomes a circular list, 
    // start counting from the first node. 
    // When it reaches the sixth element, 
    // use delete() to delete the node 
    // and output the content of the node 
    // until the entire circular list has no nodes.
    printf("Eeny, meeny, miny, moe Result:\n");
    NodePtr result = emmm(&list, 6);  // list was cleared
    printL(result);

    // Free memory
    free_list(&result);

    return 0;
}