Nan Mihai - Structuri de date

#include <stdio.h>

#include <stdlib.h>

/** Structura implementeaza o coada de int folosind un tablou alocat dinamic.

 * Pentru a folosi mai bine memoria, zona de date se considera circulara (vezi breviar

 * laborator).

 */



struct queue_struct {

    /** Un pointer catre zona de date */

    int* data;

    /** Capacitatea zonei de date */

    int capacity;

    /** Pozitia primului element din coada */

    int front;

    /** Numarul de elemente din coada */

    int size;

};



typedef struct queue_struct* Queue;

#define QUEUE_INITIAL_CAPACITY 10



/**1.  Returneaza un pointer la o coada nou alocata*/

Queue newQueue()

{

    Queue nou;

    nou = (Queue) malloc(sizeof(struct queue_struct));

    nou->data = (int *) malloc(QUEUE_INITIAL_CAPACITY*sizeof(int));

    nou->front = 0;

    nou->size = 0;

    nou->capacity = QUEUE_INITIAL_CAPACITY;

    return nou;

}



/** 2. Elibereaza intreaga memorie alocata cozii*/

Queue deleteQueue(Queue q)

{

    if(q != NULL)

    {

        free(q->data);

        free(q);

    }

    return NULL;

}



/** 3. Returneaza True daca este goala */

int isEmpty(Queue q)

{

    if(q->size == 0)

    {

        return 1;

    }

    else

    {

        return 0;

    }

}



/** 4. Returneaza numarul de element din coada */

int size(Queue q)

{

    if(q != NULL)

        return q->size;

    else

        return 0;

}



/** 5. Se asigura ca respectiva coada are capacitatea cel putin minCapacity*/

Queue ensureCapacity(Queue q, int minCapacity)

{

        if(q->capacity < minCapacity)

        {

            q->capacity = minCapacity;

            q->data = (int *) realloc(q, minCapacity*sizeof(int));

            return q;

        }

        else

            return q;

}



/** 6. Adauga un element nou in coada*/

Queue enqueue(Queue q, int value)

{

    if(q->capacity == q->size)

        q = ensureCapacity(q, 2*q->capacity);

    q->data[(q->front+q->size)%q->capacity] = value;

    q->size = q->size + 1;

    q->capacity = q->capacity + 1;

    return q;

}



/** 7. Intoarce valoarea primului element din coada sau -1 daca coada este goala (Ar trebui sa returneze o eroare.

 * Cum facem in C??)

 * */

int front(Queue q)

{

    if(q->size == 0)

        return -1;

    else

    {

        return q->data[q->front];

    }

}



/** 8. Scoate din coada primul element si il returneaza*/

int dequeue(Queue q)

{

    int primul;

    if(q->size == 0)

    {

        return -1;

    }

    else

    {

        primul = front(q);

        q->front = (q->front+1)%q->capacity;

        q->size = q->size-1;

        return primul;

    }

}





/** Adauga intervalul [start, end) */

void addSome(Queue q, int start, int end) {

    int i;

    for (i = start; i < end; ++i) {

        enqueue(q, i);

    }

}



/** Testeaza ca poate extrage [start, end) din coada*/

int testDequeue(Queue q, int start, int end) {

    int ok = 1;

    int i;

    for (i = start; i < end; ++i) {

        int got = dequeue(q);

        if (got != i && ok) {

            ok = 0;

            printf("Dequeue, expected %5d, got %5d\n", i, got);

        }

    }

    if (!ok) {

        printf("Dequeue FAILED!\n");

    }

    return ok;

}





int main(int argc, char** argv) {

    Queue q;

    int i, start = 0, end = 100;

    int ok = 1;

    //Test 1 - Empty list:

    q = newQueue();

    printf("front on empty,   expected: %5d got: %5d\n", -1, front(q));

    printf("dequeue on empty, expected: %5d got: %5d\n", -1, dequeue(q));

    printf("isEmpty on empty, expected: %5d got: %5d\n",  1, isEmpty(q));

    printf("size on empty,    expected: %5d got: %5d\n",  0, size(q));



    deleteQueue(q);



    q = newQueue();



    //Test 2 - enqueue, and dequeue

    addSome(q, 0, 5);       //q = [0, 5)

    printf("front on some,   expected: %5d got: %5d\n", 0, front(q));

    printf("isEmpty on some, expected: %5d got: %5d\n", 0, isEmpty(q));

    printf("size on some,    expected: %5d got: %5d\n", 5, size(q));





    testDequeue(q, 0, 3);   //q = [3, 5)

    addSome(q, 5, 12);          //q = [3, 12)



    printf("front on some (1),   expected: %5d got: %5d\n", 3, front(q));

    printf("isEmpty on some (1), expected: %5d got: %5d\n", 0, isEmpty(q));

    printf("size on some (1),    expected: %5d got: %5d\n", 9, size(q));





    addSome(q, 12, 200);        // q = [3, 200)

    testDequeue(q, 3, 200); // q = empty

    printf("isEmpty on empty, expected: %5d got: %5d\n",  1, isEmpty(q));



    deleteQueue(q);



    return 0;

}