Set.c

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

// Tipo de dado set (Conjunto).
// Para garantir o ecapsulamento, 'struct SetStruct' só é definido em set.c.
struct SetStruct{
    SetType *v;
    int size;
    int capacity;
};

// Cria um conjunto vazio.
set new_set(){
    set s = malloc(sizeof(struct SetStruct));
    s->size = 0;
    s->capacity = 20;
    s->v = (SetType *)malloc(sizeof(SetType) * s->capacity);

    return s;
}

// Testa se o cojunto está vazio.
int empty(set s){
    return s->size > 0 ? 1 : 0;
}

// Retorna o número de elementos no conjunto.
int size(set s){
    return s->size;
}

// Retorna um iterador para o primeiro (menor) elemento do conjunto.
// Caso o conjunto esteja vazio, rentorna um ponteiro para end(s).
iterator begin(set s){
    return size(s) ? &s->v[0] : end(s);
}

// Retorna um iterador para o "marcador de fim" do conjunto.
iterator end(set s){
    return &s->v[size(s)];
}

// Retorna um iterador para o elemento seguinte ao indicado por x no conjunto.
// Se x aponta para o último elemento do conjunto, retorna end(s);
// Precondição: x aponta para um dos elementos do conjunto.
iterator next(iterator x){
    (SetType*)x;
    return x++;
}

// Retorna um iterador para o elemento anterior ao indicado por x no conjunto.
// Precondição: x aponta para um dos elementos do cojunto (exceto o primeiro),
// ou para end(s).
iterator prev(iterator x){
    (SetType*)x;
    return x--;
}

// Retorna a chave do elemento indicado por x.
SetType key(iterator x){
    return *((SetType*)x);
}

// Retorna um iterador para o elemento k,
// ou um iterador para end(s) caso k não pertença ao conjunto.
// OBS: Note que esta função NÃO retorna {0, 1}. Para testar se um elemento 'a'
// pertence a um conjunto 's', você deve escrever "if (find(a, &s) != end(&s))".
iterator find(SetType k, set s){
    for(iterator i = begin(s); i != end(s); i = next(i)){
        if(key(i) == k) return i;
    }
    return end(s);
}

// Insere k no conjunto.
// Caso k já pertença ao conjunto, um novo elemento NÃO é inserido no
// conjunto.
void insert(SetType k, set s){
    if(find(k,s) == end(s)){
        printf("%d insert\n",k);
        if(s->size == s->capacity){
            reserve(s->capacity*2, s);
        }
        s->v[s->size] = k;
        s->size++;
    }
}

void reserve(int m, set s){
    SetType *aux;
    aux = (SetType*)malloc(sizeof(SetType) * m);
    for(int i = 0; i < s->size; i++){
        aux[i] = s->v[i];
    }
    s->capacity = m;
    s->v = aux;
}

// Remove k do conjunto (caso lá ele esteja).
void erase(SetType k, set s){
    iterator x = find(k,s);
    if(x != end(s)){
        for(iterator i = x; i != end(s); i = next(i)){
            *(SetType*)i = *(SetType*)next(i);
        }
        s->size--;
    }
}

// Remove todos os elementos do conjunto.
void clear(set s){
    iterator i = begin(s);
    iterator aux;
    while(!empty(s)){
        aux = next(i);
        erase(key(i),s);
        i = aux;
    }
}

// Faz com que o conjunto q contenha exatamente os mesmos elementos
// do cojunto s.
void copy(set q, set s){
    clear(q);

    for(iterator x = begin(s); x != end(s); x = next(x)){
        insert(key(x),q);
    }
}

// Troca o conteúdo do conjunto q com o do conjunto s.
void swap(set q, set s){
    set aux = s;
    s = q;
    q = aux;
}

// Libera toda a memória alocada para o conjunto.
void delete_set(set s){
    free(s->v);
}