/***************************************************************************
 *   Copyright (C) 2009 by Douglas Castro   *
 *   douglas@ime.unicamp.br   *
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 *   This program is distributed in the hope that it will be useful,       *
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
 *   GNU General Public License for more details.                          *
 *                                                                         *
 *   You should have received a copy of the GNU General Public License     *
 *   along with this program; if not, write to the                         *
 *   Free Software Foundation, Inc.,                                       *
 *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
 ***************************************************************************/

#ifndef _ARVORE_H_
#define _ARVORE_H_

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include "definicoes.h"
#include "inicializa.h"

/**
 * Recebe um pacote de {k}x{k} arvores e respectivos valores e separa o pacote
 * necessario para o filho esquerdo ou filho direito. A escolha e feita baseada 
 * no parametro de entrada {qual}.
 * @param d [in] dimensao do dominio
 * @param pac [in] pacote com medias celulares e ponteiros para nos da arvore.
 * @param ex [in] eixo perpendicular a divisao
 * @param (pred) [in] funcao de interpolacao quadratica das medias.
 * @param qual [in] pacote de filho a tomar, 0=esq/inf 1=dir/sup
 * @param fil [out]  pacote filho pedido.
 * @return
 */
void divide_pacote(int d, VNo pac[], int ex, Preditor pred, int qual, VNo fil[]);

void divide_pacote_geral(int d, VNo pac[], int ex, Preditor pred,	int qual,	VNo fil[]);


/**
 * Cria uma arvore completa com medias celulares de f
 * @param d [in] dimensao do dominio
 * @param niv [in] quantidade de niveis na arvore
 * @param prof [in] profundidade atual na arvore, a profundidade da raiz eh 0
 * @param indice [in] indice da celula, o indice da raiz eh 1
 * @param xmin [in] coordenada do vertice inferior de uma celula
 * @param xmax [in] coordenada do vertice superior de uma celula
 * @param (f) [in] funcao a ser discretizada
 * @param (integra) [in] quadratura de Gauss
 * @return
 */
No *completa(int d, int niv, int prof, int indice, double xmin[], double xmax[], Funcao *f, Quadratura integra);

/**
 * Conta a quantidade de folhas na arvore, completa ou nao.
 * @param r [in] arvore
 * @param cont [out] numero de nos
 * @return
 */
void conta_folhas(No *r, int *cont);

/**
 * Conta a quantidade de nos na arvore, completa ou nao.
 * @param r [in] arvore
 * @param cont [out] numero de nos
 * @return
 */
void conta_nos(No *r, int *cont);

/**
 * Rotina para copiar as medias das folhas de uma arvore para um vetor.
 * @param r [in] arvore de onde tiraremos as medias.
 * @param vet [out] vetor com copia das medias celulares reconstruidas
 * @param *cont [in] ponteiro para a ultima posicao do vetor com medias proveniente da folhas da arvore
 * @return
 */
void copia_folhas(No *r, double vet[], int *cont);

/**
 * Atualiza a arvore r. Nas folhas virtuais repete valor das folhas e nos nohs usa restricao.
 * @param r [in/out] arvore a ser atualizada
 * @return
 */
void atualiza_arvore(No *r);

/**
 * Atualiza as folhas virtuais.
 * @param d [in] dimensao do dominio
 * @param prof [in] profundidade de um no na arvore
 * @param pac [in/out] o centro do pacote contem arvore a ser atualizada
 * @param (pred) [in] operador de previsao
 * @return
 */
void atualiza_folhas_virtuais(int d, int prof, VNo pac[], Preditor pred);

/**
 * Apos atualizacao da arvore, marca quem sao os nos deletaveis.
 * @param d [in] dimensao do dominio
 * @param pac [in] pacote de valores e ponteiros, no centro esta o no a ser testado
 * @param niv [in] numero de niveis na arvore
 * @param prof [in] profundidade na arvore
 * @param (pred) [in] operador de previsao
 * @param fpoda [in] valor interpolado para a celula filho, caso nao exista na arvore
 * @param eps [in] tolerancia
 * @return
 */
bool_t marca_nos(int d, VNo pac[], int niv, int prof, Preditor pred, double fpoda, double eps);


/**
 * Apos marca_nos, caso pai e filhos sejam deletaveis, os filhos sao transformados em folhas virtuais
 * @param d [in] dimensao do dominio
 * @param pac [in] pacote de valores e ponteiros, no centro esta o no a ser testado
 * @param esq [in] valores nos nos da esquerda antes de podar (caso seja necessario reconstruir uma virtual do lado)
 * @param dir [in] valores nos nos da direita antes de podar (idem)
 * @param prof [in] profundidade na arvore
 * @param niv [in] quantidade de niveis na arvore
 * @param (pred) [in] operador de previsao
 * @param eps [in] tolerancia
 * @return
 */
void adapta_arvore(int d, VNo pac[],double esq[], double dir[], int prof, int niv, Preditor pred, double eps);

/**
 * (data2sparse)
 * Recebe uma arvore qualquer, elimina sub-arvores superfluas, tomando 
 * cuidado para nao eliminar apenas um filho de algum no.  Mantem a
 * raiz, mas devolve TRUE se a raiz e superflua, FALSE caso contrario.
 * Uma sub-arvore e superflua se, depois de eliminadas suas sub-arvores
 * proprias superfluas, ela nao tem filhos, e a diferenca {diff} entre 
 * o valor real {fval} e o valor interpolado {fint} da raiz
 * e menor que a tolerancia {eps}.  Se a arvore dada e vazia,
 * devolve FALSE.
 * @param d [in] dimensao do dominio
 * @param niv [in] numero de niveis na arvore
 * @param pac [in/out] gabarito, conjunto de celulas da arvore
 * @param esq [in] valores nos nos da esquerda antes de podar (caso seja necessario reconstruir uma virtual do lado)
 * @param dir [in] valores nos nos da direita antes de podar (idem)
 * @param profund [in] profundidade de uma celula na arvore
 * @param (pred) funcao de interpolacao quadratica
 * @param fpoda [in] valor da celula central se nao existisse o no correspondente.
 * @param eps [in] diferenca que e considerada significativa.
 * @return
 */
bool_t poda_arvore(int d, int niv, VNo pac[], double esq[], double dir[], int profund, Preditor pred, double fpoda, double eps);

/**
 * diz se os irmaos de uma celula tem filhos ou nao.
 * @param pac [in] pacote de celulas 
 * @param ord [in] tamanho necessario para interpolacao (para quadratica, 5)
 * @param d [in] dimensao do dominio
 * @return
 */
bool_t diz(VNo pac[], int ord, int d);

bool_t adapta_arvore2(int d, VNo pac[], double esq[], double dir[], int prof, int niv, Preditor pred, double fpoda, double eps);

#endif