/**
 * CÓDIGO DESENVOLVIDO PELOS ALUNOS CÉZAR DONIZETE MENDES JUNIOR E LIBÉRIO MARTINS SILVA.
 * 
 * UFLA 2014, Desenvolvimento do 3º trabalho de AED III. 
 * 
 * Cadastro de voos com índice organizado em Árvore B e passageiros em árvore AVL
 *  
 * Este trabalho consiste em implementar um sistema para armazenar e buscar informações sobre
 * voos. O sistema seria utilizado por operadores de aeroportos para controlar voos e que
 * passageiros estão neles. A busca por passageiros em um voo em diversos momentos, bem como
 * a busca por voos são operações críticas, e portanto, devem ser realizadas com a maior eficiência.
 * 
 * @author Cézar Donizete Mendes Júnior
 * @author Libério Martins Silva 
*/
/**
 * Variável estática que define a ordem das páginas da árvore B (árvore 
 * de voos).
 */ 
#define ORDER 2
/**
 * Variável estática que define o tamanho máximo das posições das 
 * páginas da ávore B. Este valor é dado pelo dobro da ordem da árvore.
 */ 
#define MAX_INDEX ORDER*2

/**
 * Estrutura de armazenamento das informações de um passageiro. Contém 
 * um passaporte, que será a chave do registro, o nome, poltrona e 
 * código do voo do passageiro.
 */ 
struct Passager {
	char pass[11]; /* Chave. */
	char name[101];
	char chair[4];
	char code_Plane[16];
} Passager;

/**
 * Estrutura de armazenamento das informações de um voo. Contém o código
 * do mesmo, que será sua chave, o aeroporto de partida e de destino, o 
 * tempo de voo e a empresa aérea.
 */ 
struct Plane {
	char code_Plane[16]; /* chave */
	char arrival_Airport[4];
	char dest_Airport[4];
	char plane_Time[6];
	char enterprise[3];
} Plane;

/**
 * Estrutura de armazenamento dos dados de um passageiro na árvore AVL 
 * correspondente (voo na qual a mesma está alocada), juntamente com 
 * ponteiros que indicam seus nós filhos. Nesta estrutura há também uma
 * variável do tipo inteiro que armazena o fator de balanceamento de
 * cada nó.
 */ 
typedef struct Nodo {
	struct Nodo* pRight;
	struct Nodo* pLeft;
	int factor_Balance;
	struct Passager info;
} Nodo;

/**
 * Estrutura de índices de um voo na árvore B. Possui um campo que
 * armazena a posição onde o voo está dentro do arquivo de dados e
 * um vetor de caracteres que armazena a chave do voo.
 */  
struct Index {
	long RRN_Plane;
	char key_Plane[16];
}Index;

/**
 * Estrutura que contém os dados de uma página gerada na árvore B.
 * Contém um campo com o número de voos guardados dentro desta página,
 * um vetor que armazena os voos contidos nela e um outro vetor que
 * armazena o RNN das suas páginas filhas.
 */ 
struct Page {
	short num_Plane;
	struct Index planes[MAX_INDEX];
	long RRN_Son[MAX_INDEX + 1];
}Page;

/** 
 * Método de carrega a raiz da árvore de índices.
 * @param FILE *p: Arquivo onde está armazenada a árvore de índices
 * @return Long contendo o RRN da raiz da árvore de índices.
 */ 
long load_RRN_Root(FILE *p);

/**
 * Método que salva os dados de um voo no arquivo de dados.
 * @param char data[]: String contendo as informações do voo
 */ 
void save_Plane (char data[]);

/**
 * Método que separa a string de dados de voo recebida em seus
 * respectivos campos, chama o método inserir e verifica se há uma
 * promoção. Se houver, cria uma nova página para o elemtno promovido.
 * @param char data[]: String contendo as informações do voo
 */ 
void insert_Plane_Driver(char data[]);

/** 
 * Método de inserção de um novo voo.
 * @param FILE *p: Arquivo contendo a árvore de índices.
 * @param long RRN_Atual_Page: Contém a página atual onde o voo será inserido (inicialmente é a página raiz).
 * @param struct Index key_to_Insert: Chave que será inserida.
 * @param char data[]: Dados do voo que será inserido.
 * @param struct Index **promoter: Índice que será promovido (usado apenas em casos de inserção em página cheia).
 * @param long **right_Son_Page: RRN do filho à direita do índice promovido.
 * @return Um inteiro que identifica se houve promoção, não promoção ou erro.
 */ 
int insert_Plane(FILE *p, long RRN_Atual_Page, struct Index key_to_Insert, char data[], struct Index **promoter, long **right_Son_Page);

/**
 * Método que busca um determinado voo dentro da árvore de índices.
 * @param FILE *p: Arquivo de índices
 * @param long RRN_Atual_Page: Página atual (inicialmente a raiz). Chama recursivamente até achar a página onde está contida a chave do voo buscado.
 * @param char key_Plane[]: Chave do voo buscado
 * @return Um inteiro indicando se houve sucesso (1) ou erro (0) na busca.
 */ 
int search_Plane(FILE *p, long RRN_Atual_Page, char key_Plane[]);

/**
 * Método que chama o método remoção. Caso haja underflow, ele chama
 * o método agreement (junção de páginas).
 * @param char key_Plane[]: Chave do voo que será removido.
 */ 
void remove_Plane_Driver(char key_Plane[]);

/**
 * Método de remoção de um voo da árvore de índices.
 * @param FILE *p: Arquivo contendo a árvore de índices.
 * @param long RRN_Atual_Page: Contém a página atual do voo que será removido (inicialmente é a página raiz).
 * @param struct Index key_to_Insert: Chave que será removida.
 * @param int changing: Verifica se haverá troca.
 * @param struct Index *changer_Plane: Grava os dados do menor da esquerda, que será "promovido" caso haja remoção de um nó pai.
 * @param int *underflow: Verifica se haverá underflow.
 * @return Um inteiro que identifica se houve sucesso ou erro.
 */ 
int remove_Plane(FILE *p, long RRN_Atual_Page, char key_Plane[], int changing, struct Index *changer_Plane, int *underflow);

/**
 * Método que imprime os dados de um voo, armazenados no arquivo de dados.
 * @param long RRN: Posição no arquivo de dados do voo que será exibido.
 */ 
void print_Index_Plane(long RRN);

/**
 * Função que irá dividir uma página que não cabe
 * mais indices em duas páginas, criando assim uma nova.
 * E vai mandar um elemento promovido.
 * @param struct Page *atual_Page: Página atual que estava cheia passada por referência.
 * @param struct Page *new_Page: Nova página que será criada passada por referência.
 * @param struct Index promoter: Indice que será promovido no split.
 * @param long long right_Son_Page: FIlho a direita do elemento que será promovido.
 * @return
 */ 
void split(struct Page *atual_Page, struct Page *new_Page, struct Index promoter, long right_Son_Page);

/**
 * Função que será utilizada para pegar uma página raiz
 * e suas filhas e fazer uma única página a fim de evitar 
 * o underflow.
 * @param struct Index father: Indice que está na página raiz.
 * @param struct Page right_Son: Página fiha a direita.
 * @param struct Page left_Son: Página fiha a esquerda.
 * @param struct Page *newbie_Page: Página passada por referência que será a nova página após a união das 3.
 * @return
 */ 
void agreement(struct Index father, struct Page right_Son, struct Page left_Son, struct Page *newbie_Page);

/**
 * Função que irá salvar uma página da memoria
 * no disco.
 * @param FILE *p: Ponteiro do arquivo de indices.
 * @param long RRN_Page: RRN de onde a página será salva no disco.
 * @param struct Page *page: Página que terá seus valores salvados do disco.
 * @return
 */ 
void save_Page(FILE *p, long RRN_Page, struct Page *page);

/**
 * Função que irá carregar uma página do disco
 * e colocar a mesma em uma página da memória
 * que será passada por referência.
 * @param FILE *p: Ponteiro do arquivo de indices.
 * @param long RRN_Page: RRN da página no disco.
 * @param struct Page *page: Página passada por referência que terá seus valores carregados do disco.
 * @return
 */ 
void load_Page(FILE *p, long RRN_Page, struct Page *page);

/**
 * Função que irá inicializar uma nova página com valores
 * padrões afim de evitar erros futuros.
 * @param struct Page *page: Página passada por referência que terá seus valores alterados.
 * @return
 */ 
void createNewPage(struct Page *page);

/**
 * Função que irá imprimir toda a árvore de indices 
 * obdecendo todas as especificações.
 * @param FILE *p: Ponteiro do arquivo de indices.
 * @param long RRN: RRN da página atual que será imprimida.
 * @return
 */ 
void print_Index_Tree(FILE *p, long RRN);

/**
 * Função auxiliar para conservar alguns dados que são perdidos
 * durante algumas operações no programa.
 * @param FILE *p: Ponteiro do arquivo de indices.
 * @return
 */ 
void pino(FILE *p);

/**
 * Função que desaloca toda a árvore AVL da memória.
 * @param struct Nodo* pNodo: Nodo atual que deseja ser desalocado.
 */ 
void cut_Tree (struct Nodo* pNodo);

/**
 * Função para buscar qual o maior Nodo a esquerda de um Nodo dado
 * como partida.
 * @param struct Nodo* pNodo: Nodo atual na busca.
 * @return
 */ 
struct Nodo* search_Biggest_Left(struct Nodo* pNodo);

/**
 * Função que remove um passageiro da árvore AVL através
 * de uma chave passada.
 * @param char key_Pas[]: Chave que será removida.
 * @param struct Nodo** pNodo: Nodo que será usado para a remoção.
 * @return Retorna o maior Nodo a esquerda da ávore AVL.
 */ 
int remove_Pas(char key_Pas[], struct Nodo** pNodo);

/**
 * Função que inseri um passageiro na árvore AVL a partir
 * de um determinado Nodo.
 * @param char data[]: Dados da chave a ser inserida.
 * @param struct Nodo** pNodo: Nodo que será usado para a inserção.
 * @return Retorna 1 em sucesso e 0 em erro. 
 */ 
int insert_Pas (char data[], struct Nodo** pNodo);

/**
 * Função que gira a árvoe AVL no sentido ant horário a fim de deixá-la 
 * balanceada, como é a caracteristica de uma árvore AVL.
 * @param struct Nodo** pNodo: Nodo que será usado como ponto de partida para a rotação.
 * @return Retorna 1 em sucesso e 0 em erro. 
 */ 
void balance_AntiHorario(struct Nodo** pNodo);

/**
 * Função que gira a árvoe AVL no sentido horário a fim de deixá-la 
 * balanceada, como é a caracteristica de uma árvore AVL.
 * @param struct Nodo** pNodo: Nodo que será usado como ponto de partida para a rotação.
 * @return 
 */ 
void balance_Horario(struct Nodo** pNodo);

/**
 * Função que busca um passageiro através de uma chave na árvore
 * AVL que contem todos os passageiros de um determinado voo.
 * @param char key_Pas[]: String com a chave do passageiro que será buscado.
 * @param struct Nodo* pNodo: Ponteiro de Nodo do nodo atual na busca.
 * @return
 */ 
struct Nodo* search_Pas(char key_Pas[], struct Nodo* pNodo);

/**
 * Função que salva os dados de um passageiro
 * no arquivo de passageiros.
 * @param char data[]: String com os dados do passageiro como passaporte, nome, poltrona e passaporte.
 * @return Retorna o passageiro encontrado, caso não encontrado retorna vazio.
 */
void save_Pas(char data[]);

/**
 * Função que imprime todos os dados de 
 * um voo armazenado no arquivo de voos.
 * @param long RRN: RNN(endereço) que indica em que lugar do arquivo de dados o voo está localizado.
 * @return
 */
void print_Plane(long RRN);