#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#ifndef MYALGORITHMS_H
#define MYALGORITHMS_H

#include <stdlib.h>

#define STRINGIZE(x) #x

/* Bitwise operations */
#define setbit(number, bit) ((number) |= 1 << (bit))
#define clearbit(number, bit) ((number) &= ~(1 << (bit)))
#define switchbit(number, bit) ((number) ^= 1 << (bit))
#define checkbit(number, bit) ((number) & (1 << bit))

typedef struct NODE* link;
typedef struct NODE {
    int data;
    link next;
} NODE;

char* repr_array(const int* A, const size_t N);
void print_array(const int* A, const size_t N);
void insertion_sort(int* A, const size_t N);
void insertion_sort_2(int* A, const size_t N);
int randrange(unsigned int n);
int random_in_range(unsigned int min, unsigned int max);
int rand_range(unsigned int n);
inline void swap(void* A, void* B, size_t bytes);
void shuffle(void* A, size_t membercount, size_t membersize);
void my_bubble_sort(int* A, const size_t N);
void bubble_sort(int* A, const size_t N);
void selection_sort(int* A, const size_t N);
void merge(int* left, int n_left, int* right, int n_right, int* out);
void recurse(int* A, int* temp, int N);
void merge_sort(int* A, int N);
int* range(size_t N);
inline void reverse(void* sequence, const size_t membercount, const size_t membersize);
void test_reverse(void);
char* getstring(void);
int getinteger(void);
void sort_trial(void);
link insert_node(link A, link newnode);
int delete_node(link A, link unwanted_node);
int pop_node(link list);
link append_node(link list, link newnode);
void print_node(link node);
void traverse_list(link node);
link reverse_list(link head);
link create_empty_node(void);
link append_new_node(link tail, int data);
link create_list_from_array(const int* A, const size_t N);
size_t list_length(NODE const *list);
void delete_list(link head);
inline void swap_node(link A, link B);
link getnode(const link head, size_t N);
void* list_to_array(NODE const *list, const size_t list_length, const size_t data_size);
link* create_link_array(link head, size_t length);
inline int cmp_int_asc(const void* A, const void* B);
inline int cmp_int_desc(const void* A, const void* B);

/* Generic insertion sort algorithm. */
#define isort(base, num, size, comparator) \
{ \
    void *left, *right, *key; \
    if ((key = malloc(size))) \
    { \
        for (right = (base + size); ((size_t) right - (size_t) base)/size < num; right += size) \
        { \
            memcpy(key, right, size); \
            for (left = right; (size_t) left > (size_t) base && comparator((left - size), key) > 0; left -= size) \
            { \
                memcpy(left, left - size, size); \
            } \
            memcpy(left, key, size); \
        } \
        free(key); \
    } \
}

#endif // MYALGORITHMS_H




#define PLACES_MAX (strlen(STRINGIZE(INT_MAX)) + 1)
#define ARRLEN(A) (sizeof(A) / sizeof(0[A]))

char* repr_array(const int* A, const size_t N)
{
    char* result;
    size_t len_result, p;
#define ARRAY_BEGIN '['
#define DELIMITERS ", "
#define ARRAY_END "]"
    result = NULL;
    len_result = ((N - 1) * (PLACES_MAX + strlen(DELIMITERS))) + PLACES_MAX;
    len_result += 3;
    if ((result = realloc(result, sizeof(*result) * len_result)))
    {
        char* s;
        s = result + 1;
        result[0] = ARRAY_BEGIN;
        for (p = 0; p < (N-1); ++p)
        {
            s += sprintf(s, "%d"DELIMITERS, A[p]);
        }
        sprintf(s, "%d"ARRAY_END, A[p]);
    }
    else
    {
        fprintf(stderr, "\n%s\n", "repr_array malloc failed: out of memory.");
    }
    return result;
#undef ARRAY_END
#undef DELIMITERS
#undef ARRAY_BEGIN
}

void print_array(const int* A, const size_t N)
{
    char* a = repr_array(A, N);
    printf("%s\n", a);
    free(a);
}

void insertion_sort(int* A, const size_t N)
{
    size_t i, j;
    int key;
    for (i = 1; i < N; ++i)
    {
        key = A[i];
        for (j = i; j > 0 && A[j - 1] > key; --j)
        {
            A[j] = A[j - 1];
        }
        A[j] = key;
    }
}

void insertion_sort_2(int* A, const size_t N)
{
    size_t i, j;
    int key;
    for (i = 1; i < N; ++i)
    {
        //key = A[i];
        memcpy(&key, A+i, sizeof(*A));
        for (j = i; j > 0 && A[j - 1] > key; --j)
        {
            //A[j] = A[j - 1];
            memcpy(A+j, A+j-1, sizeof(*A));
        }
        //A[j] = key;
        memcpy(A+j, &key, sizeof(*A));
    }
}

int randrange(unsigned int n)
{
    int randint, rand_max;
    rand_max = RAND_MAX - (RAND_MAX % n);
    while ((randint = rand()) >= rand_max);
    return randint / (rand_max / n);
}

int random_in_range(unsigned int min, unsigned int max)
{
    int base_random, range, remainder, bucket;
    base_random = rand();
    if (RAND_MAX == base_random)
    {
        return random_in_range(min, max);
    }
    range = max - min;
    remainder = RAND_MAX % range;
    bucket = RAND_MAX / range;

    if (base_random < (RAND_MAX - remainder))
    {
        return min + (base_random / bucket);
    }
    else
    {
        return random_in_range(min, max);
    }
}

int rand_range(unsigned int n)
{
    return random_in_range(0, n);
}

inline void swap(void* A, void* B, size_t bytes)
{
    void* temp;
    temp = malloc(bytes);
    if (temp)
    {
        memcpy(temp, A, bytes);
        memcpy(A, B, bytes);
        memcpy(B, temp, bytes);
        free(temp);
    }
}

void shuffle(void* A, size_t membercount, size_t membersize)
{
    size_t k;
    while (membercount > 1)
    {
        k = rand_range(membercount);
        --membercount;
        swap(A + (membercount * membersize), A + (k * membersize), membersize);
    }
}

void my_bubble_sort(int* A, const size_t N)
{
    size_t i, j;
    int *keydex, *next;
    for (i = 0; i < N; ++i)
    {
        for (j = 0; j < (N - i - 1); ++j)
        {
            keydex = A + j;
            next = keydex + 1;
            if (*keydex > *next)
            {
                swap(keydex, next, sizeof(*A));
            }
        }
    }
}

void bubble_sort(int* A, const size_t N)
{
    int n, i, newn;
    n = N;
    do
    {
        newn = 0;
        for (i = 1; i < n; ++i)
        {
            if (A[i-1] > A[i])
            {
                swap(A + i - 1, A + i, sizeof(*A));
                newn = i;
            }
        }
        n = newn;
    } while (n > 0);
}

void selection_sort(int* A, const size_t N)
{
    int *keydex, *mindex, *index;
    for (keydex = A; keydex - N < A; ++keydex)
    {
        mindex = keydex;
        for (index = (keydex + 1); index < (A + N); ++index)
        {
            if (*index < *mindex)
            {
                mindex = index;
            }
        }
        if (keydex != mindex)
        {
            swap(keydex, mindex, sizeof(*A));
        }
    }
}

void merge(int* left, int n_left, int* right, int n_right, int* out)
{
    int i, j, k;
    for (i = j = k = 0; i < n_left && j < n_right; ++k)
    {
        if (left[i] < right[j])
        {
            out[k] = left[i];
            ++i;
        }
        else
        {
            out[k] = right[j];
            ++j;
        }
    }
    while (i < n_left)
    {
        out[k] = left[i];
        ++i;
        ++k;
    }
    while (j < n_right)
    {
        out[k] = right[j];
        ++j;
        ++k;
    }
}

void recurse(int* A, int* temp, int N)
{
    int mid;
    mid = N / 2;
    if (N <= 1)
    {
        return;
    }
    recurse(temp, A, mid);
    recurse(temp + mid, A + mid, N - mid);
    merge(temp, mid, temp + mid, N - mid, A);
}

void merge_sort(int* A, int N)
{
    int* temp;
    temp = malloc(sizeof(*A) * N);
    if (temp)
    {
        memcpy(temp, A, sizeof(*A) * N);
        recurse(A, temp, N);
        free(temp);
    }
}

/*typedef void(*sorting_algorithm)(int*, size_t);
void test_sorting_algorithm(int* A, const size_t N, sorting_algorithm sort, const char* sort_name)
{
    printf("Before %s: ", sort_name);
    print_array(A, N);
    sort(A, N);
    printf("After %s: ", sort_name);
    print_array(A, N);
}*/

#define test_sorting_algorithm(A, N, sort, sort_name) \
{ \
    printf("Before %s: ", sort_name); \
    print_array(A, N); \
    sort(A, N); \
    printf("After %s: ", sort_name); \
    print_array(A, N); \
}
#define test_sort(A, N, name) test_sorting_algorithm(A, N, name, STRINGIZE(name))

int* range(size_t N)
{
    int* result;
    if ((result = malloc(sizeof(*result) * N)))
    {
        int* i, num;
        num = 0;
        for (i = result; i < (result + N); ++i)
        {
            *i = num;
            ++num;
        }
    }
    return result;
}

inline void reverse(void* sequence, const size_t membercount, const size_t membersize)
{
    void *left, *right;
    right = sequence + ((membercount - 1) * membersize);
    left = sequence;
    while (left < right)
    {
        swap(left, right, membersize);
        left += membersize;
        right -= membersize;
    }
}

void test_reverse(void)
{
    int* A = range(10);
    reverse(A, 10, sizeof(*A));
    print_array(A, 10);
    free(A);
}

char* getstring(void)
{
    char* strbuffer = NULL;
    size_t strbuffercapacity = 0;
    size_t strbuffercharcount = 0;
    int character;
    while ((character = fgetc(stdin)) != '\n' && character != EOF)
    {
        if (strbuffercharcount + 1 > strbuffercapacity)
        {
            if (strbuffercapacity == 0)
            {
                strbuffercapacity = sizeof(char) * 4;
            }
            else if (strbuffercapacity < (UINT_MAX / 2))
            {
                strbuffercapacity *= 2;
            }
            else
            {
                free(strbuffer);
                return NULL;
            }
            char* tempbuffer = realloc(strbuffer, sizeof(char) * strbuffercapacity);
            if (tempbuffer == NULL)
            {
                return NULL;
            }
            else
            {
                strbuffer = tempbuffer;
            }
        }
        strbuffer[strbuffercharcount] = character;
        ++strbuffercharcount;
    }
    if (strbuffercharcount == 0 && character == EOF)
    {
        return NULL;
    }
    char* minstrbuffer = malloc(sizeof(char) * (strbuffercharcount + 1));
    strncpy(minstrbuffer, strbuffer, strbuffercharcount);
    free(strbuffer);
    minstrbuffer[strbuffercharcount] = '\0';
    return minstrbuffer;
}

int getinteger(void)
{
    for(;;)
    {
        char* integers = getstring();
        if (integers == NULL)
        {
            return INT_MAX;
        }
        int integer;
        char character;
        if (sscanf(integers, " %d %c", &integer, &character) == 1)
        {
            free(integers);
            return integer;
        }
        else
        {
            free(integers);
            printf("Retry: ");
        }
    }
}

void sort_trial(void)
{
    int LEN, choice;
    srand(time(NULL));
    printf("Enter the size of the integer array you want: ");
    LEN = getinteger();
    int* A = range(LEN);
    printf("\n1. Random array\n2. Reversed array\n3. Sorted array\n");
    choice = getinteger();
    switch (choice)
    {
        case 1:
            shuffle(A, LEN, sizeof(*A));
            break;
        case 2:
            reverse(A, LEN, sizeof(*A));
            break;
        case 3:
            break;
        default:
            break;
    }
    printf("\n1. Insertion sort\n2. Bubble sort 1\n3. Bubble sort 2\n4. Selection sort\n");
    choice = getinteger();
    switch (choice)
    {
        case 1:
            test_sort(A, LEN, insertion_sort);
            break;
        case 2:
            test_sort(A, LEN, my_bubble_sort);
            break;
        case 3:
            test_sort(A, LEN, bubble_sort);
            break;
        case 4:
            test_sort(A, LEN, selection_sort);
            break;
        default:
            break;
    }
    free(A);
}

link insert_node(link A, link newnode)
{
    newnode->next = A->next;
    A->next = newnode;
    return newnode;
}

int delete_node(link A, link unwanted_node)
{
    int data;
    A->next = unwanted_node->next;
    data = unwanted_node->data;
    free(unwanted_node);
    return data;
}

int pop_node(link list)
{
    int data;
    while (list->next)
    {
        list = list->next;
    }
    data = list->data;
    free(list);
    return data;
}

link append_node(link list, link newnode)
{
    while (list->next)
    {
        list = list->next;
    }
    insert_node(list, newnode);
    return newnode;
}

void print_node(link node)
{
    printf("%p [%d] -> %p\n", node, node->data, node->next);
}

void traverse_list(link node)
{
    for (; node->next; node = node->next)
    {
        print_node(node);
    }
    print_node(node);
}

link reverse_list(link head)
{
    link new_head, next;
    new_head = NULL;
    while (head)
    {
        next = head->next;
        head->next = new_head;
        new_head = head;
        head = next;
    }
    return new_head;
}

link create_empty_node(void)
{
    return malloc(sizeof(NODE));
}

link append_new_node(link tail, int data)
{
    link newnode;
    newnode = create_empty_node();
    newnode->data = data;
    append_node(tail, newnode);
    return tail->next;
}

link create_list_from_array(const int* A, const size_t N)
{
    link head, tail;
    size_t end;
    head = create_empty_node();
    if (head)
    {
        head->data = *A;
        ++A;
        tail = head;
        tail->next = NULL;
        for (end = (size_t) (A + N - 1); (size_t) A < end; ++A)
        {
            tail = append_new_node(tail, *A);
        }
    }
    return head;
}

size_t list_length(NODE const *list)
{
    size_t length;
    length = 0;
    while (list)
    {
        list = list->next;
        ++length;
    }
    return length;
}

void delete_list(link head)
{
    while (head->next)
    {
        delete_node(head, head->next);
    }
    free(head);
}

inline void swap_node(link A, link B)
{
    swap(A, B, sizeof(link));
}

link getnode(const link head, size_t N)
{
    link node;
    node = head;
    size_t index;
    index = 0;
    while (index < N)
    {
        node = node->next;
        ++index;
    }
    return node;
}

void* list_to_array(NODE const *list, const size_t list_length, const size_t data_size)
{
    void* array;
    array = malloc(data_size * list_length);
    if (array)
    {
        void* block;
        size_t index;
        index = 0;
        block = array;
        while (index < list_length)
        {
            memcpy(block, &(list->data), data_size);
            block += data_size;
            list = list->next;
            ++index;
        }
    }
    return array;
}

link* create_link_array(link head, size_t length)
{
    link *array, *ptr;
    array = malloc(sizeof(*array) * length);
    ptr = array;
    while (head->next)
    {
        *ptr = head;
        ++ptr;
        head = head->next;
    }
    return array;
}

/*void isort(void* base, size_t num, size_t size, int (*comparator) (const void*, const void*))
{
    void *left, *right, *key;
    if ((key = malloc(size)))
    {
        for (right = (base + size); ((size_t) right - (size_t) base)/size < num; right += size)
        {
            memcpy(key, right, size);
            for (left = right; (size_t) left > (size_t) base && comparator((left - size), key) > 0; left -= size)
            {
                memcpy(left, left - size, size);
            }
            memcpy(left, key, size);
        }
        free(key);
    }
}*/

inline int cmp_int_asc(const void* A, const void* B)
{
    int I = *((int*) A);
    int J = *((int*) B);
    return I < J ? -1 : I > J;
}

inline int cmp_int_desc(const void* A, const void* B)
{
    int I = *((int*) A);
    int J = *((int*) B);
    return I > J ? -1 : I < J;
}

int main(void)
{
    int A[] = {9,8,7,6,5,4,3,2,1,0};
    print_array(A, 10);
    insertion_sort(A, 10);
    print_array(A, 10);
    return 0;
}