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

typedef unsigned short int boolean;
#define TRUE 1
#define FALSE 0

struct list {
    int value;
    struct list * next_ptr;
};

void init(struct list ** ptr);
boolean pre_insert(struct list **ptrptr, int value);
boolean suf_insert(struct list **ptrptr, int value);
boolean ord_insert(struct list **ptrptr, int value);
boolean pre_remove(struct list **ptrptr, int * value);
boolean suf_remove(struct list **ptrptr, int * value);
boolean ord_remove(struct list **ptrptr, int target);
void visit(struct list *ptr);
void visit_back(struct list * ptr);
boolean search(struct list * ptr, int target);
boolean clone(struct list * src_ptr, struct list ** dst_ptr);
boolean clone2(struct list * src_ptr, struct list ** dst_ptr);

void function(struct list ** L, int *V, int N, int M){
    int i;
    *L= NULL;
    struct list ** restart = L;
    struct list ** start;
    struct list * app2;
    for(i=0;i<M;i++){
        struct list * new=(struct list *)malloc(sizeof(struct list));
        new->value=V[i];
        new->next_ptr=NULL;
        *L = new;
        //(*L)=(*L)->next_ptr;
        L = &((*L)->next_ptr);
    }
    L = restart;
    for(i=M;i<N;i++){
        struct list * new=(struct list *)malloc(sizeof(struct list));
        new->value=V[i];
        new->next_ptr=(*L);
        if(app2==NULL)
            app2->next_ptr=new;
        else
            start=&new;
        app2=(*L);
        (*L)=(*L)->next_ptr;
    }
    L=start;
}

void eserizio3(struct list ** ptr, int *V, int N, int M) {

    for (int i = 0; i < M - 1;i++) {
        suf_insert(ptr, V[M + i]);
        suf_insert(ptr, V[i]);
    }
    for (int i = M - 1 + M; i < N;i++) {
        suf_insert(ptr, V[i]);
    }
}



int main() {
    struct list * ptr;
    int value;

    // init the list
    init(&ptr);

    int array[] = {5,1,3,4,6,2,7,9};

    function(&ptr, array, 8, 3);

    visit(ptr);

    //system("pause");
    return 0;
}

void init(struct list ** ptr)
{
    *ptr = NULL;
}

boolean pre_insert(struct list **ptrptr, int value)
{
    struct list * tmp_ptr;
    tmp_ptr = (struct list *)malloc(sizeof(struct list));
    if ( tmp_ptr != NULL ) {
        tmp_ptr->value = value;
        tmp_ptr->next_ptr = *ptrptr;
        *ptrptr = tmp_ptr;
        return TRUE;
    }
    else
        return FALSE;

}

boolean suf_insert(struct list **ptrptr, int value)
{
    while( *ptrptr != NULL )
        ptrptr = &((*ptrptr)->next_ptr);
    if ( pre_insert(ptrptr,value) )
        return TRUE;
    else
        return FALSE;
}

boolean ord_insert(struct list **ptrptr, int value)
{
    while( *ptrptr != NULL && (*ptrptr)->value < value )
        ptrptr = &((*ptrptr)->next_ptr);
    if ( pre_insert(ptrptr,value) )
        return TRUE;
    else
        return FALSE;
}

boolean pre_remove(struct list **ptrptr, int * value)
{
    struct list * tmp_ptr;

    if ( *ptrptr != NULL ) {
        tmp_ptr = *ptrptr;
        *value = tmp_ptr->value;
        *ptrptr = (*ptrptr)->next_ptr;
        free(tmp_ptr);
        return TRUE;
    }
    else
        return FALSE;
}

boolean suf_remove(struct list ** ptrptr, int * value)
{
    if ( *ptrptr != NULL ) {
        while( (*ptrptr)->next_ptr != NULL ) {
            ptrptr = &((*ptrptr)->next_ptr);
        }
        pre_remove(ptrptr,value);
        return TRUE;
    }
    else
        return FALSE;
}

boolean ord_remove(struct list ** ptrptr, int target)
{
    int value;
    boolean found = FALSE;

    if ( *ptrptr != NULL ) {
        while( *ptrptr != NULL && found == FALSE ) {
            if ((*ptrptr)->value == target) {
                pre_remove(ptrptr, &value);
                printf("\nValue %d has been removed from the list",value);
                found = TRUE;
            }
            else
                ptrptr = &((*ptrptr)->next_ptr);
        }
    }
    return found;
}

void visit(struct list * ptr)
{
    printf("\nList: ");
    while ( ptr != NULL ) {
        printf("%d ", ptr->value);
        ptr = ptr->next_ptr;
    }
}

// backward visit of the list. Elements are printed in reverse order
void visit_back(struct list * ptr)
{
    struct list * tmp_ptr;

    init(&tmp_ptr);
    while ( ptr != NULL ) {
        pre_insert(&tmp_ptr,ptr->value);
        ptr = ptr->next_ptr;
    }
    visit(tmp_ptr);
}

boolean search(struct list * ptr, int target)
{
    boolean found = FALSE;

    while( ptr != NULL && found == FALSE ) {
        if ( ptr->value == target )
            found = TRUE;
        else
            ptr = ptr->next_ptr;
    }
    return found;
}

boolean clone(struct list * src_ptr, struct list ** dst_list)
{
    boolean is_correct = TRUE;
    init(dst_list);
    // insert all the elements of the source list in the destination list
    while ( src_ptr != NULL && is_correct == TRUE ) {
        is_correct = suf_insert(dst_list,src_ptr->value);
        src_ptr = src_ptr->next_ptr;
    }
    return is_correct;
}

// clone with linear cost
boolean clone2(struct list * src_ptr, struct list ** dst_ptr)
{
    boolean is_correct = TRUE;
    init(dst_ptr);
    // insert all the elements of the source list in the destination list
    while ( src_ptr != NULL && is_correct == TRUE ) {
        is_correct = suf_insert(dst_ptr,src_ptr->value);
        // advance the pointer to the next_ptr filed of the last element of the list
        dst_ptr = &((*dst_ptr)->next_ptr);
        src_ptr = src_ptr->next_ptr;
    }
    return is_correct;
}