blub

queue.c

#include <stdlib.h>
#include "queue.h"

/* Implementera interface från queue.h här */

struct qelementstruct {
    struct qelementstruct *next, *prev;
    int prio;
    DATA *data;
};

struct qstruct {
    struct qelementstruct *head;
    int length;
};

struct qiteratorstruct {
    struct qstruct *q;
    struct qelementstruct *curr;
};

typedef struct qelementstruct *Element;

Element new_element() {
    Element e = malloc(sizeof(struct qelementstruct));
    e->next = e;
    e->prev = e;
    e->prio = 0;
    e->data = 0;
    return e;
}

Queue new_queue() {
    Queue q = malloc(sizeof(struct qstruct));
    q->head = new_element();
    q->length = 0;
    return q;
}

void add(Queue q, int priority, DATA *d) {
    Element e = q->head;
    Element new_e = new_element();
    new_e->prio = priority;
    new_e->data = d;
    
    while (priority > e->prev->prio && e->prev != q->head) {
        e = e->prev;
    }

    new_e->next = e;
    new_e->prev = e->prev;

    e->prev->next = new_e;
    e->prev = new_e;

    q->length++;
}

int size(Queue q) {
    return q->length;
}

void remove_first(Queue q) {
    Iterator it = new_iterator(q);
    remove_current(it);
    delete_iterator(it);
}

void clear(Queue q) {
    while (size(q) > 0) {
        remove_first(q);
    }
}

void delete_queue(Queue q) {
    clear(q);
    free(q->head);
    free(q);
}

DATA *get_first(Queue q) {
    return q->head->next->data;
}

Iterator new_iterator(Queue q) {
    Iterator it = malloc(sizeof(struct qiteratorstruct));
    it->q = q;
    it->curr = q->head->next;
    return it;
}

void delete_iterator(Iterator it) {
    free(it);
}

int is_valid(Iterator it) {
    return it->curr != it->q->head;
}

void go_to_first(Iterator it) {
    it->curr = it->q->head->next;
}

void go_to_last(Iterator it) {
    it->curr = it->q->head->prev;
}

void go_to_next(Iterator it) {
    if (is_valid(it)) {
        it->curr = it->curr->next;
    }
}

void go_to_previous(Iterator it) {
    if (is_valid(it)) {
        it->curr = it->curr->prev;
    }
}

DATA *get_current(Iterator it) {
    return it->curr->data;
}

void change_current(Iterator it, DATA *d) {
    if (is_valid(it)) {
        it->curr->data = d;
    }
}

void remove_current(Iterator it) {
    if (is_valid(it)) {
        Element e = it->curr;
        go_to_next(it);
        e->prev->next = e->next;
        e->next->prev = e->prev;
        it->q->length--;
        free(e);
    }
}

void find(Iterator it, DATA *d) {
    go_to_first(it);
    while (get_current(it) != d && is_valid(it)) {
        go_to_next(it);
    }
}