/********************************************************

   ROT-FILA
   ========

   Rotinas basicas de manipulacao de FILAS usando vetores:
   - Estruturas de dados com alocacao estatica
   - Insere no final da fila
   - Remocao do inicio da fila
   - Fila circular

   Aplicacao tipica:
   - Lista de elementos a espera de um tratamento,
     onde a ordem de chegada e importante

   Por: Fernando Osorio
   Data da ultima atualizacao: Out. 2013

*********************************************************/

/* Incluir: stdio.h */

#define FALSO      0
#define VERDADEIRO 1

#define OK         1
#define ERRO       0

typedef int Tipo_Dado;

typedef struct
        {
           Tipo_Dado *Dado;
           int       Inicio,Fim;
           int       Tamanho;
        }  Tipo_Fila;

/***

 => Rotinas de Manipulacao de FILAS - First In, First Out (FIFO)
    Alocacao sequencia

***

void inicializa_fila  (Tipo_Fila *F, int Qtde);
int  insere_fila      (Tipo_Fila *F; Tipo_Dado  Dado);
int  retira_fila      (Tipo_Fila *F; Tipo_Dado *Dado);
void lista_fila       (Tipo_Fila *F);
int  consulta_fila    (Tipo_Fila *F; int Indice; Tipo_Dado *Dado);
int  cheia_fila       (Tipo_Fila *F);
int  vazia_fila       (Tipo_Fila *F);
int  quantidade_fila  (Tipo_Fila *F);
int  acha_fila        (Tipo_Fila *F; Tipo_Dado Dado; int *Indice);

***/

void inicializa_fila (F, Qtde)
Tipo_Fila *F;
int Qtde;
{
  F->Dado=(Tipo_Dado *)calloc(Qtde,sizeof(Tipo_Dado));
  if (F->Dado == NULL) 
  {
     printf("## Erro de Alocacao ##\n");  /* Aborta programa */
     exit(0);
  }
  F->Inicio=0;
  F->Fim=0;
  F->Tamanho=Qtde;
}

int insere_fila (F,Dado)
Tipo_Fila *F;
Tipo_Dado Dado;
{
  int prox;

  prox=F->Fim+1;

  if (prox == F->Tamanho)
     prox=0;

  if (prox == F->Inicio)
     return(ERRO);
  else
  {
     F->Dado[F->Fim]=Dado;
     F->Fim=prox;
     return(OK);
  }
}

int retira_fila (F,Dado)
Tipo_Fila *F;
Tipo_Dado *Dado;
{
  if (F->Fim == F->Inicio)
     return(ERRO);
  else
  {
     *Dado= F->Dado[F->Inicio];
     (F->Inicio)++;
     if (F->Inicio >= F->Tamanho)
        F->Inicio=0;
     return(OK);
  }
}

void lista_fila (F)
Tipo_Fila *F;
{
   int cont;

   printf("\n");
   cont=F->Inicio;
   while (cont != F->Fim)
   {
      printf("Fila[%d]=%d\n",cont,F->Dado[cont]);
      cont++;
      if (cont >= F->Tamanho)
         cont=0;
   }
   printf("\n");
}

int consulta_fila (F,Indice,Dado)
Tipo_Fila *F;
int Indice;
Tipo_Dado *Dado;
{
  if (F->Fim > F->Inicio)
     if ((Indice <= F->Inicio)  || (Indice > F->Fim) ||
         (Indice >= F->Tamanho) || (Indice < 0))
        return(ERRO);
  else
     if (((Indice >  F->Fim) && (Indice <= F->Inicio)) ||
          (Indice >= F->Tamanho) || (Indice < 0))
        return(ERRO);
     else
     {
        *Dado=F->Dado[Indice];
        return(OK);
     }
}

int acha_fila (F,Dado,Indice)
Tipo_Fila *F;
Tipo_Dado Dado;
int *Indice;
{
  int cont;
  int achou;

  achou=FALSO;
  cont = F->Inicio;
  *Indice = -1;
  while (cont != F->Fim)
  {
     cont++;
     if (cont == F->Tamanho)
        cont=0;

     if (F->Dado[cont] == Dado)
     {
        achou=VERDADEIRO;
        *Indice=cont;
        break;
     }
  }

  if (achou)
     return(OK);
  else
     return(ERRO);
}

int cheia_fila (F)
Tipo_Fila *F;
{
  if ((F->Fim+1 == F->Inicio) || (F->Fim+1 > F->Tamanho))
     return(OK);
  else
     return(ERRO);
}

int vazia_fila (F)
Tipo_Fila *F;
{
  if (F->Fim == F->Inicio)
     return(OK);
  else
     return(ERRO);
}

int quantidade_fila (F)
Tipo_Fila *F;
{
  if (F->Fim > F->Inicio)
     return(F->Fim-F->Inicio);
  else
     return(F->Fim+(F->Tamanho-1)-F->Inicio);
}

/***************
  Fim rot-fil.c
****************/