#include <stdlib.h>
#include <stdio.h>

typedef int RA;

typedef 
enum estado_entrada {livre, ocupado, removido} Estado; 

typedef struct entrada {
  Estado estado;
  RA ra;
} Entrada;

typedef struct tabela {
  int tam;  
  Entrada* v;
} Tabela;
   

void cria_tabela(Tabela *ap_tab, int tam) {
  ap_tab->v = calloc(tam, sizeof(Entrada));
  ap_tab->tam = tam;
}

void destroi_tabela(Tabela *ap_tab) {
  free(ap_tab->v);
}

/*
 *  Retorna -1 se não encontrar o RA 
 *  ou a posição do RA na tabela  
 */

int busca(Tabela* ap_tab, RA ra) {
  int h, s;

  h = ra % ap_tab->tam;
  s = h;
  do {
    switch (ap_tab->v[s].estado) {
    case livre: 
      return -1; 
    case ocupado:
      if (ap_tab->v[s].ra == ra)
	return s;  /* senão continua como no caso removido */
    case removido: 
      s = (s + 1) % ap_tab->tam; 
      break; 
    }
  } while (s != h);
  return -1;
}

/* 
 * Retorna 1 se conseguiu inserir ou se o RA já estava na tabela.
 *         0 se a tabela estiver lotada 
 */

int insere(Tabela* ap_tab, RA ra) {
  int h, s, d;

  h = ra % ap_tab->tam;
  s = h;   /* Procura o ponto de inserção */
  d = -1;  /* Marca uma posição liberada */

  do {
    switch (ap_tab->v[s].estado) {
    case livre: 
      if (d != -1) s = d;
      ap_tab->v[s].ra = ra;
      ap_tab->v[s].estado = ocupado;
      return 1;
    case ocupado:
      if (ap_tab->v[s].ra == ra) 
	return 1;
      else s = (s + 1) % ap_tab->tam;
      break;
    case removido: 
      if (d == -1) d = s;
      s = (s + 1) % ap_tab->tam;;
    }
   } while (s != h);

  if (d == -1) {
    ap_tab->v[d].ra = ra;
    ap_tab->v[d].estado = ocupado;
    return 1;
  }
  return 0;
}


/* 
 * Retorna 1 se conseguiu remover
 *         0 se não encontrou o RA
 */

int remove_tab(Tabela* ap_tab, RA ra) {
  int pos;

  pos = busca(ap_tab, ra);
  if (pos != -1) {
    ap_tab->v[pos].estado = removido;
    return 1;
  }
  return 0;
}

void imprime_tabela(Tabela tab) {
  int i;

  for (i = 0; i < tab.tam; i++) {
    switch (tab.v[i].estado) {
    case ocupado: 
      printf("[%d] Ocupado: %d\n", i, tab.v[i].ra);
      break;
    case livre: 
      printf("[%d] Livre\n", i);
      break; 
    case removido:
      printf("[%d] Removido\n", i);
      break;
    }
  }
}

int main() {
  Tabela tab;
  RA ra;
  char op;
  int pos;

  cria_tabela(&tab, 10);
  do {
    scanf("%c", &op);
    switch (op) {
    case 'b':
      scanf("%d", &ra);
      pos = busca(&tab,ra);
      if (pos == -1)
	printf ("RA não encontrada.\n");
      else
	printf ("RA na posição %d.\n", pos);
      break;
    case 'i' : 
      scanf("%d", &ra);
      insere(&tab,ra);
      break;
    case 'r' : 
      scanf("%d", &ra);
      remove_tab(&tab,ra);
      break;
    case 'm': 
      imprime_tabela(tab);
    } 
  } while (op != 's');
  return 0;
}