#include "list.h"

/* Fundamental */
void initList(List * L)
{

    // create new list
    L->sql = (Seq *) calloc (1,sizeof(Seq));
    if (!L->sql)
    {
        fprintf(stderr,"create list fail\n");
        exit(EXIT_FAILURE);
    }

    sqList tmp = L->sql;
    // allocate memory
    tmp->data = (int *) calloc (MAX, sizeof(int));
    if (!tmp->data)
    {
        fprintf(stderr,"allocate memory fail\n");
        exit(EXIT_FAILURE);
    }

    tmp->length = 0;
    tmp->maxSize = MAX;
}

int lengthList(List * L)
{
    return L->sql->length;
}

bool locateElem(List * L, int * i, int e)
{
    sqList tmp = L->sql;
    for (int j = 0; j < tmp->length; j++)
        if (tmp->data[j] == e)
        {
            *i = j + 1;
            return true;
        }
    return false;
}

bool getElem(List * L, int i, int * e)
{
    sqList tmp = L->sql;
    if (i < 1 || i > tmp->length)
    {
        fprintf(stderr,"Out of range\n");
        return false;
    }
    *e = tmp->data[i-1];

    return true;
}

bool insertElem(List * L, int i, int e)
{
    sqList tmp = L->sql;
    if (i < 1 || i > tmp->length+1)
    {
        fprintf(stderr, "Out of range\n");
        return false;
    }
    if (tmp->length == tmp->maxSize)
    {
        fprintf(stderr, "List full\n");
        return false;
    }
    for (int j = tmp->length; j >= i; j--)
        tmp->data[j] = tmp->data[j-1];
    tmp->data[i-1] = e;
    tmp->length++;

    return true;
}

bool deleteElem(List * L, int i, int * e)
{
    sqList tmp = L->sql;
    if (i < 1 || i > tmp->length)
    {
        fprintf(stderr,"Out of range\n");
        return false;
    }
    *e = tmp->data[i-1];

    for (int j = i; j < tmp->length; j++)
        tmp->data[j-1] = tmp->data[j];
    tmp->length--;
    return true;
}

void printList(List * L)
{
    sqList tmp = L->sql;
    for (int i = 0; i < tmp->length; i++)
        printf("%d  ",tmp->data[i]);
    putchar('\n');
}

bool emptyList(List * L)
{
    sqList tmp = L->sql;
    if (tmp->length == 0)
        return true;
    return false;
}

void deleteList(List * L)
{
    free(L->sql->data);
    free(L->sql);
}

/* homework */
// 1
int deleteMin(List * L)
{
    sqList tmp = L->sql;
    
    if (tmp->length == 0)
    {
        fprintf(stderr,"list is empty\n");
        exit(1);
    }
    int min = tmp->data[0], index = 0;

    for (int i = 1; i < tmp->length; i++)
        if (min > tmp->data[i])
        {
            min = tmp->data[i];
            index = i;
        }
    tmp->length--;
    for (int i = index; i < tmp->length; i++)
        tmp->data[i] = tmp->data[i+1];
    return min;
}

// 2
void reverse(List * L)
{
    sqList tmp = L->sql;
    for (int i = 0; i < tmp->length/2; i++)
    {
        int t = tmp->data[i];
        tmp->data[i] = tmp->data[tmp->length-1-i];
        tmp->data[tmp->length-1-i] = t;
    }
}

// 3
void deleteX(List * L, int e)
{
    sqList tmp = L->sql;
    int n = 0, index = -1, i;

    for (i = 0; i < tmp->length; i++)
    {
        if (tmp->data[i] == e)
            n++;
        if (tmp->data[i] == e && index == -1)
            index = i;      // get first element's index
    }

    for (i = index; i + n < tmp->length; i++)
        tmp->data[i] = tmp->data[i+n];
    tmp->length -= n;
}

// 10
// helper
void rev(sqList q, int low, int high)
{
    for (int i = low; i < (low+high)/2; i++)
    {
        int n = i - low;
        int tmp = q->data[i];
        q->data[i] = q->data[high-1-n];
        q->data[high-1-n] = tmp;
    }
}

// question answer
void loopLeftN(List * L, int n){
    sqList tmp = L->sql;
    rev(tmp,0,n);
    rev(tmp,n,tmp->length);
    rev(tmp,0,tmp->length);
}
// extra
void loopRightN(List * L, int n)
{
    sqList tmp = L->sql;
    n = tmp->length - n;
    rev(tmp,0,n);
    rev(tmp,n,tmp->length);
    rev(tmp,0,tmp->length);
}