#include <stdlib.h>
#include <string.h>
#include "temelia/common.h"

#ifndef _new
    #define _new malloc
#endif

typedef struct{
    void** hash;
    int* deleted_element;
    int size, cap;

    int (*compare_key)(void*, void*);
    int (*linear_hash_function)(void*);
    int (*probing_increment)(int);
} _linear_hash_t;

///PRIVATE FUNCTIONS
int _linear_hash_linear(int);
int _linear_hash_quadratic(int);
void _linear_hash_calibration(_linear_hash_t*);
int _linear_hash_keep_going(_linear_hash_t*, void*, void*, int);
void** _linear_hash_supposed_position(_linear_hash_t*, void*, int);
void* _linear_hash_find(_linear_hash_t*, void*);

///PUBLIC FUNCTIONS
void* linear_hash_new(int, int (*)(void*, void*), int (*)(void*), int);
void linear_hash_clear(_linear_hash_t*);
void linear_hash_delete(_linear_hash_t*);
int linear_hash_contains(_linear_hash_t*, void*);
int linear_hash_is_empty(_linear_hash_t*);
int linear_hash_get_size(_linear_hash_t*);
int linear_hash_get_capacity(_linear_hash_t*);
void linear_hash_insert(_linear_hash_t*, void*);
void linear_hash_erase(_linear_hash_t*, void*);
void linear_hash_iterate(_linear_hash_t*, void (*)(void*));

///PRIVATE FUNCTIONS
int _linear_hash_linear(int i){
    return 1;
}

int _linear_hash_quadratic(int i){
    return (i << 1) + 1;
}

void _linear_hash_calibration(_linear_hash_t* hash){
    int capacity, oldCapacity;

    oldCapacity = linear_hash_get_capacity(hash);
    hash -> cap = (hash -> cap << 1) + 1;
    capacity = linear_hash_get_capacity(hash);

    void** area = hash -> hash;
    hash -> hash = _new(capacity * sizeof(void*));
    linear_hash_clear(hash);

    int i;
    for (i = 0 ; i < oldCapacity ; i++)
        if (area[i] != NULL && area[i] != hash -> deleted_element)
            linear_hash_insert(hash, area[i]);

    free(area);
}

int _linear_hash_keep_going(_linear_hash_t* hash, void* node, void* key, int insertORfind){
    if (node == NULL)
        return 0;

    if (node == hash -> deleted_element)
        return insertORfind;

    return hash -> compare_key(node, key) != 0;
}

void** _linear_hash_supposed_position(_linear_hash_t* hash, void* key, int insertORfind){
    int cap = linear_hash_get_capacity(hash);
    int poz = hash -> linear_hash_function(key) % cap, i = 0;

    while (_linear_hash_keep_going(hash, hash -> hash[poz], key, insertORfind))
        poz = (poz + hash -> probing_increment(i++)) % cap;

    return (hash -> hash) + poz;
}


void* _linear_hash_find(_linear_hash_t* hash, void* key){
    if (hash -> size == 0)
        return NULL;

    void* poz = *_linear_hash_supposed_position(hash, key, 1);
    return (poz != NULL && poz != hash -> deleted_element) ? poz : NULL;
}

///PUBLIC FUNCTIONS
void* linear_hash_new(int startSize, int (*compare_key)(void*, void*), int (*linear_hash_function)(void*), int linearORquadratic_probing){
    _linear_hash_t* H = _new( sizeof(_linear_hash_t) );

    H -> hash = _new(startSize * sizeof(void*));
    H -> cap = startSize;
    linear_hash_clear(H);

    H -> compare_key = compare_key;
    H -> linear_hash_function = linear_hash_function;

    if (linearORquadratic_probing)
        H -> probing_increment = _linear_hash_quadratic;
    else
        H -> probing_increment = _linear_hash_linear;

    H -> deleted_element = _new( sizeof(int) );

    return H;
}

void linear_hash_clear(_linear_hash_t* hash){
    memset(hash -> hash, 0, linear_hash_get_capacity(hash) * sizeof(void*));
    hash -> size = 0;
}

void linear_hash_delete(_linear_hash_t* hash){
    free(hash -> hash);
    free(hash -> deleted_element);
    free(hash);
}

int linear_hash_contains(_linear_hash_t* hash, void* key){
    return _linear_hash_find(hash, key) != NULL;
}

int linear_hash_is_empty(_linear_hash_t* hash){
    return hash -> size == 0;
}

int linear_hash_get_size(_linear_hash_t* hash){
    return hash -> size;
}

int linear_hash_get_capacity(_linear_hash_t* hash){
    return hash -> cap;
}

void linear_hash_insert(_linear_hash_t* hash, void* key){
    void* poz = _linear_hash_find(hash, key);

    if (poz != NULL && poz != hash -> deleted_element)
        return;

    if ( (hash -> size << 1) >= linear_hash_get_capacity(hash) )
        _linear_hash_calibration(hash);

    hash -> size++;
    *_linear_hash_supposed_position(hash, key, 0) = key;

    if ( (hash -> size << 1) >= linear_hash_get_capacity(hash) )
        _linear_hash_calibration(hash);
}

void linear_hash_erase(_linear_hash_t* hash, void* key){
    void** poz = _linear_hash_supposed_position(hash, key, 1);

    if (*poz == NULL)
        return;

    hash -> size--;
    free(*poz);

    *poz = hash -> deleted_element;
}

void linear_hash_iterate(_linear_hash_t* hash, void (*iterate)(void*)){
    int i;
    for (i = 0 ; i < hash -> cap ; i++)
        if (hash -> hash[i] != NULL && hash -> hash[i] != hash -> deleted_element)
            iterate(hash -> hash[i]);
}

///ACTUAL CODE

int compara(void* a, void *b){
    return (*(int*)a) != (*(int*)b);
}

int hashFunction(void* a){
    return *(int*)a;
}

int* fint(int x){
    int* poz = _new(sizeof(int));
    *poz = x;

    return poz;
}

char* sth(){
    return _new(sizeof(char));
}

#include <stdio.h>

int main(){
    void* hash = linear_hash_new(1572869, compara, hashFunction, 0);
    FILE* fin = fopen("hashuri.in", "r");
    FILE* fout = fopen("hashuri.out", "w");

    int times, tip, x;

    fscanf(fin, "%d", &times);
    while (times--){
        fscanf(fin, "%d%d", &tip, &x);

        if (tip == 1)
            linear_hash_insert(hash, fint(x));
        if (tip == 2)
            linear_hash_erase(hash, &x);
        if (tip == 3)
            fprintf(fout, "%d\n", linear_hash_contains(hash, &x));
    }

    fclose(fin);
    fclose(fout);

    return 0;
}