# NCKU CSIE PD1 Week15

👉[中文](https://hackmd.io/@zhu424/NCKU-CSIE-PD1-2023-week-15)

> If you already know what **Generic Programming** is,
> you can jump directly to [Lab](#Lab).

## If we want to write a function to swap two variables...

For `int`, we can write it like this:

void my_swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

int main() {
    int a = 1, b = 2;
    my_swap(&a, &b);
    printf("%d %d\n", a, b);
    return 0;
}

For `float`, we can write it like this:

void my_swap(float *a, float *b) {
    float tmp = *a;
    *a = *b;
    *b = tmp;
}

But what if we want to swap variables of these types?
- `long long`
- `unsigned int`
- `char`
- `char *`
- ```c
struct student {
char name[20];
int age;
};

-  ```c
    struct Node {
        int data;
        struct Node *next;
    };

Do we need to write a separate `my_swap` function for each type?

void my_swap(long long *a, long long *b);
void my_swap(unsigned int *a, unsigned int *b);
void my_swap(char *a, char *b);
void my_swap(char **a, char **b);
void my_swap(struct student *a, struct student *b);
void my_swap(struct Node *a, struct Node *b);
// ... 

// Implementations
void my_swap(long long *a, long long *b) {
    long long tmp = *a;
    *a = *b;
    *b = tmp;
}
// ...

## Generic Programming

**Generic** is a programming technique that allows code to be more flexible and reduces redundant code.

In the C language, we can use `void *` to implement generics.

Before we write a generic function, let's review the characteristics of `void *`.

## Characteristics of `void *`

- `void *` is a special type of pointer that can point to data of any type.

int a = 1;
float b = 2.0;
char c = '3';

void *ptr;

ptr = &a;
printf("%d\n", *(int *)ptr);

ptr = &b;
printf("%f\n", *(float *)ptr);

ptr = &c;
printf("%c\n", *(char *)ptr);

- `void *` cannot be dereferenced directly; it must be cast to the correct type first.

int a = 1;
void *ptr = &a;

printf("%d\n", *ptr); // Error
printf("%d\n", *(int *)ptr); // Correct

## Have We Used Generic Functions?

Unbeknownst to us, we have already used many generic functions.

int cmp(const void *a, const void *b){
    return *(int *)a - *(int *)b;
}

int main() {
    int arr[10] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};

    qsort(arr, 10, sizeof(int), cmp);

    for (int i = 0; i < 10; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

<br>

In fact, **`qsort`** itself is a generic function! Let's take a look at the declaration of `qsort`:

<br>

void qsort( void *ptr, size_t count, size_t size,
            int (*comp)(const void *, const void *) );

> [c reference : qsort](https://en.cppreference.com/w/c/algorithm/qsort)

When an array is passed to `qsort`, it is cast to `void *`:
- `count` is the length of the array.
- `size` is used to slice the array (where `size` represents the size of each element in bytes).
- `comp` is used to determine the sorting criteria (here, `comp` is a function pointer).

## Implementation of Generic Functions

By observing `qsort`, we can identify several characteristics of generic functions:
- Input of type `void *`
- Slicing data using `size`
- Determining operations with a function pointer

## Generic Swap

Now, let's attempt to implement a generic swap.

> **Hint**:
- Input of type `void *`
- Slicing data using `size`

void my_swap(void *a, void *b, size_t size) {
    void *tmp = malloc(size);
    memcpy(tmp, a, size);
    memcpy(a, b, size);
    memcpy(b, tmp, size);
    free(tmp);
}

> [c reference : memcpy](https://en.cppreference.com/w/c/string/byte/memcpy) ( need `#include <string.h>` )

implement it using `strcpy`

void my_swap(void *a, void *b, size_t size) {
    char *tmp = malloc(size);
    strcpy(tmp, a);
    strcpy(a, b);
    strcpy(b, tmp);
    free(tmp);
}

implement it using `for loop`

void my_swap(void *a, void *b, size_t size) {
    for(int i = 0; i < size; i++){
        *((char *)tmp + i) = *((char *)a + i);
        *((char *)a + i) = *((char *)b + i);
        *((char *)b + i) = *((char *)tmp + i);
    }
    free(tmp);
}

> Since the size of `char` is 1 byte,
> we can use a loop to swap one byte at a time.

## Lab

Please implement a **Generic Bubble Sort** and:
- Sort `students` based on `id` in ascending order.

    struct student {
        char name[20];
        int id;
        int age;
    };

- Sort `points` based on `x` in ascending order.

    struct point {
        float x;
        float y;
    };

<br>

**TODO** :

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

typedef struct student {
    char name[20];
    int id;
    int age;
} student;

typedef struct point {
    float x;
    float y;
} point;

void swap(void *a, void *b, size_t size) {
    // TODO
}


void bubble_sort(void *ptr, size_t count, size_t size,
                 int (*comp)(const void *, const void *)) {
    // TODO
    
}

int cmp_student(/* TODO */) {
    // TODO
}

int cmp_point(/* TODO */) {
    // TODO
}

int main(){
    student students[10] = {
        {"Henry", 8, 25},
        {"Alice", 1, 18},
        {"David", 4, 21},
        {"Eason", 5, 22},
        {"Jason", 10, 27},
        {"Bob", 2, 19},
        {"Frank", 6, 23},
        {"Cindy", 3, 20},
        {"Iris", 9, 26},
        {"Gina", 7, 24}
    };

    point points[10] = {
        {19.0, 20.0},
        {1.0, 2.0},
        {5.0, 6.0},
        {3.0, 4.0},
        {13.0, 14.0},
        {9.0, 10.0},
        {15.0, 16.0},
        {11.0, 12.0},
        {17.0, 18.0},
        {7.0, 8.0}
    };

    bubble_sort(students,/* TODO */);
    bubble_sort(points,/* TODO */);

    for (int i = 0; i < 10; i++) {
        printf("student(name=%s,id=%d,age=%d)\n", students[i].name, students[i].id, students[i].age);
    }

    printf("====================================\n");

    for (int i = 0; i < 10; i++) {
        printf("point(x=%f,y=%f)\n", points[i].x, points[i].y);
    }

    return 0;
}

> **Hint** : int 的 bubble sort 如下

void bubble_sort_int(int *arr, int n) {
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arr[i] > arr[j]) {
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
    }
}

The expected results should be as follows:

student(name=Alice,id=1,age=18)
student(name=Bob,id=2,age=19)
student(name=Cindy,id=3,age=20)
student(name=David,id=4,age=21)
student(name=Eason,id=5,age=22)
student(name=Frank,id=6,age=23)
student(name=Gina,id=7,age=24)
student(name=Henry,id=8,age=25)
student(name=Iris,id=9,age=26)
student(name=Jason,id=10,age=27)
====================================
point(x=1.000000,y=2.000000)
point(x=3.000000,y=4.000000)
point(x=5.000000,y=6.000000)
point(x=7.000000,y=8.000000)
point(x=9.000000,y=10.000000)
point(x=11.000000,y=12.000000)
point(x=13.000000,y=14.000000)
point(x=15.000000,y=16.000000)
point(x=17.000000,y=18.000000)
point(x=19.000000,y=20.000000)

## What Can We Achieve with Generic Programming?

Algorithms like `qsort` can be written as generic functions for reusability. <br>
Similarly, upcoming concepts like `linked list` can also be implemented as generic types for reuse. <br>

<br>

:::spoiler Generic Linked List

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

// Define the student structure
typedef struct student {
    char name[20];
    int id;
    int age;
} student;

// Define the node structure for the linked list
typedef struct Node {
    void *data;
    struct Node *next;
} Node;

// Function to create a new node with data
Node *createNode(void *data) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    if (newNode == NULL) {
        perror("Memory allocation error");
        exit(EXIT_FAILURE);
    }

    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Function to insert a new node at the beginning of the linked list
Node *insertNodeAtBeginning(Node *head, void *data) {
    Node *newNode = createNode(data);
    newNode->next = head;
    return newNode;
}

// Function to print a student's information
void printStudent(const void *data) {
    const student *s = (const student *)data;
    printf("ID: %d, Name: %s, Age: %d\n", s->id, s->name, s->age);
}

// Function to print the linked list
void printList(Node *head, void (*print)(const void *)) {
    Node *current = head;
    while (current != NULL) {
        print(current->data);
        current = current->next;
    }
}

// Function to free the linked list
void freeList(Node *head) {
    Node *current = head;
    while (current != NULL) {
        Node *next = current->next;
        free(current->data);
        free(current);
        current = next;
    }
}

int main() {
    // Example usage with the student structure
    Node *head = NULL;

    // Create and insert student nodes
    student *s1 = (student *)malloc(sizeof(student));
    strcpy(s1->name, "Alice");
    s1->id = 1;
    s1->age = 20;
    head = insertNodeAtBeginning(head, s1);

    student *s2 = (student *)malloc(sizeof(student));
    strcpy(s2->name, "Bob");
    s2->id = 2;
    s2->age = 22;
    head = insertNodeAtBeginning(head, s2);

    student *s3 = (student *)malloc(sizeof(student));
    strcpy(s3->name, "Charlie");
    s3->id = 3;
    s3->age = 21;
    head = insertNodeAtBeginning(head, s3);

    // Print the linked list
    printf("Linked List of Students:\n");
    printList(head, printStudent);

    // Clean up the linked list
    freeList(head);

    return 0;
}

:::

<br>

Moreover, more complex data structures, such as `AVL Tree`, can also be implemented as generic types for reusability. <br>

:::spoiler Generic AVL Tree

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

typedef struct AVLNode {
    void *data;
    struct AVLNode *left;
    struct AVLNode *right;
    int height;
} AVLNode;

// Function pointer type for data comparison
typedef int (*CompareFunction)(const void *, const void *);

// Function pointer type for data printing
typedef void (*PrintFunction)(const void *);

// Function to get the height of a node
int getHeight(AVLNode *node) {
    return (node == NULL) ? 0 : node->height;
}

// Function to update the height of a node
void updateHeight(AVLNode *node) {
    if (node != NULL) {
        int leftHeight = getHeight(node->left);
        int rightHeight = getHeight(node->right);
        node->height = 1 + ((leftHeight > rightHeight) ? leftHeight : rightHeight);
    }
}

// Function to get the balance factor of a node
int getBalanceFactor(AVLNode *node) {
    return (node == NULL) ? 0 : getHeight(node->left) - getHeight(node->right);
}

// Right rotate a subtree rooted with y
AVLNode *rightRotate(AVLNode *y) {
    AVLNode *x = y->left;
    AVLNode *T2 = x->right;

    // Perform rotation
    x->right = y;
    y->left = T2;

    // Update heights
    updateHeight(y);
    updateHeight(x);

    // Return new root
    return x;
}

// Left rotate a subtree rooted with x
AVLNode *leftRotate(AVLNode *x) {
    AVLNode *y = x->right;
    AVLNode *T2 = y->left;

    // Perform rotation
    y->left = x;
    x->right = T2;

    // Update heights
    updateHeight(x);
    updateHeight(y);

    // Return new root
    return y;
}

// Balance the AVL tree after an insertion or deletion
AVLNode *balanceNode(AVLNode *node) {
    // Update height of the current node
    updateHeight(node);

    // Get the balance factor of this node
    int balance = getBalanceFactor(node);

    // Left Heavy (Left-Left Case)
    if (balance > 1 && getBalanceFactor(node->left) >= 0) {
        return rightRotate(node);
    }

    // Left Heavy (Left-Right Case)
    if (balance > 1 && getBalanceFactor(node->left) < 0) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    // Right Heavy (Right-Right Case)
    if (balance < -1 && getBalanceFactor(node->right) <= 0) {
        return leftRotate(node);
    }

    // Right Heavy (Right-Left Case)
    if (balance < -1 && getBalanceFactor(node->right) > 0) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    // No rotation needed
    return node;
}

// Insert a node into the AVL tree
AVLNode *insertNode(AVLNode *node, void *data, CompareFunction compare) {
    // Standard BST insertion
    if (node == NULL) {
        AVLNode *newNode = (AVLNode *)malloc(sizeof(AVLNode));
        newNode->data = data;
        newNode->left = newNode->right = NULL;
        newNode->height = 1;
        return newNode;
    }

    // Perform standard BST insert
    int cmpResult = compare(data, node->data);
    if (cmpResult < 0) {
        node->left = insertNode(node->left, data, compare);
    } else if (cmpResult > 0) {
        node->right = insertNode(node->right, data, compare);
    } else {
        // Duplicate data is not allowed
        return node;
    }

    // Update height of the current node
    updateHeight(node);

    // Balance the tree
    return balanceNode(node);
}

// Find target node in the AVL tree
AVLNode *findNode(AVLNode *node, void *target, CompareFunction compare) {
    if (node == NULL) {
        return NULL;
    }

    int cmpResult = compare(target, node->data);
    if (cmpResult < 0) {
        return findNode(node->left, target, compare);
    } else if (cmpResult > 0) {
        return findNode(node->right, target, compare);
    } else {
        return node;
    }
}

// Function to free the AVL tree nodes
void freeAVLTree(AVLNode *root) {
    if (root != NULL) {
        freeAVLTree(root->left);
        freeAVLTree(root->right);
        free(root);
    }
}

typedef struct student {
    char name[20];
    int id;
    int age;
} student;

// Compare function for student
int compareStudent(const void *a, const void *b) {
    return ((student *)a)->id - ((student *)b)->id;
}

// Compare function for finding student
int compareStudentId(const void *target_id, const void *p) {
    return *((int *)target_id) - ((student *)p)->id;
}

// Print function for student
void printStudent(const void *data) {
    student *s = (student *)data;
    printf("Name: %s, ID: %d, Age: %d\n", s->name, s->id, s->age);
}

// Print AVL tree in-order
void printAVLTree(AVLNode *root, PrintFunction print) {
    if (root != NULL) {
        printAVLTree(root->left, print);
        print(root->data);
        printAVLTree(root->right, print);
    }
}

int main() {
    AVLNode *root = NULL;

    student students[10] = {
        {"Henry", 8, 25},
        {"Alice", 1, 18},
        {"David", 4, 21},
        {"Eason", 5, 22},
        {"Jason", 10, 27},
        {"Bob", 2, 19},
        {"Frank", 6, 23},
        {"Cindy", 3, 20},
        {"Iris", 9, 26},
        {"Gina", 7, 24}
    };

    // Insert 10 students into the AVL tree
    for (int i = 0; i < 10; i++) {
        printf("Inserting student %d %s\n", students[i].id, students[i].name);  
        root = insertNode(root, &students[i], (CompareFunction)compareStudent);
    }

    // Print the AVL tree in-order
    printf("Printing AVL tree in-order:\n");
    printAVLTree(root, (PrintFunction)printStudent);

    // Check student id = 5
    printf("Checking student id = 5\n");
    int target_id = 5;
    AVLNode* result = (AVLNode *)findNode(root, &target_id, (CompareFunction)compareStudentId);
    if (result == NULL) {
        printf("Student not found\n");
    } else {
        printStudent(result->data);
    }

    // Check student id = 99
    printf("Checking student id = 99\n");
    target_id = 99;
    result = (AVLNode *)findNode(root, &target_id, (CompareFunction)compareStudentId);
    if (result == NULL) {
        printf("Student not found\n");
    } else {
        printStudent(result->data);
    }

    // Clean up
    freeAVLTree(root);

    return 0;
}

:::

<!--

https://gist.github.com/jason810496/073978e521feb5cdab41ec81fe56ae6b

-->