/* Last edited on 2009-10-27 15:59:21 by stolfilocal */
/***************************************************************************
 *   Copyright (C) 2009 by Douglas Castro   *
 *   douglas@ime.unicamp.br   *
 *   Last edited on 2009-07-30 15:40:55 by stolfilocal
 *                                                                         *
 *   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"
#include "timestep.h"

/* 
  Um pacote eh uma matriz de {d} indices e {tm = tp^d} elementos de
  tipo {VNo}, onde {tp} eh um numero impar, que corresponde a um bloco
  de {tp^d} celulas adjacentes no mesmo nivel da malha. O pacote
  define os valores de uma funcao aproximante, em qualquer ponto
  dentro da celula central desse bloco.
  
  O valor de {tp} depende do esquema de interpolacao usado; ele eh
  {tp=4*k+1} para esquemas de interpolacao de ordem {2*k}, que usam
  {ti=2*k+1} valores. Nos {ti^d} elementos mais centrais do pacote, o
  campo {.p} eh usado, e o campo {.fv} eh irrelevante. Nos demais
  elementos da periferia, o campo {.fv} eh usado e o campo {.p} eh
  irrelevante.
  
  !!! Repensar os pacotes !!!
*/

/**
 * @brief Recebe um pacote de {tp^d} arvores e respectivos valores e separa o pacote
 * necessario para representar a funcao no filho 0 ou filho 1 da celula central.
 * A escolha e feita baseada no parametro de entrada {qual}.
 * @param d [in] dimensao do dominio
 * @param tp [in] tamanho do pacote em cada dimensao.
 * @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.
 * @param op [in] ordem da previsao. false para 3, true para 5.
 * @return
 */

//void divide_pacote_geral(int d, int tp, 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[], bool_t op);

/* !!! Funcoes que fazem combinacao linear de pacotes. !!! */

/**
 * @brief Cria uma arvore completa com medias celulares de f. Define fv[1] e fval.
 * @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);

/**
 * @brief Cria uma arvore completa com medias celulares de f, transladada em {t} unidades. Define fv[1] e fval.
 * @param d [in] dimensao do dominio
 * @param niv [in] quantidade de niveis na arvore
 * @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
 * @param t [in] unidades para transladar a funcao
 * @return
 */
No *comp_sol_ana(int d, int niv, int prof, double xmin[], double xmax[], Funcao *f, QuadraturaSA integraSA, double t);
No *comp_sol_ana_burg(int d, int niv, int prof, double xmin[], double xmax[], Funcao *f, QuadraturaSA integraSA);

/**
 * @brief 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);

/**
 * @brief 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);

/**
 * @brief 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);

/**
 * @brief Rotina para atualizar as medias das folhas de uma arvore para especial para primeiro passo de Runge-Kutta 3.
 * @param r [in/out] arvore para atualizar as medias nas folhas.
 * @return
 */
void atualiza_folhas_rk3p1( No *r);
void atualiza_folhas_v2( No *r, int t);

/**
 * @brief Rotina para atualizar as medias das folhas de uma arvore para especial para segundo passo de Runge-Kutta 3.
 * @param r [in/out] arvore para atualizar as medias nas folhas.
 * @return
 */void atualiza_folhas_rk3p2( No *r);

/**
 * @brief Rotina para atualizar as medias das folhas de uma arvore para especial para terceiro passo de Runge-Kutta 3.
 * @param r [in/out] arvore para atualizar as medias nas folhas.
 * @return
 */
void atualiza_folhas_rk3p3( No *r);

/**
 * @brief 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);

/**
 * @brief Atualiza a arvore r.
 * @param r [in/out] arvore a ser atualizada
 * @return
 */
void atualiza_arvore_rk3(No *r);

/**
 * @brief Atualiza nos internos da arvore r.
 * @param r [in/out] arvore a ser atualizada
 * @return
 */
void atualiza_nos_internos(No *r);

/**
 * @brief Atualiza as folhas, colocando em fval o valor da solucao em {n+0.5} e em fv a sol em {n}.
 * @param r [in/out] arvore a ser atualizada
 * @return
 */
void atualiza_folhas( No *r);

/**
 * @brief (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 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, bool_t op, int niv, VNo pac[], int profund, Preditor pred, double fpoda, double eps);

/**
 * @brief procura vizinhos inferiores relativos a um eixo coordenado.
 * @param d [in] dimensao do dominio
 * @param pac [in] pacote de celulas 
 * @param prof [in] profundidade da celula no centro do pacote
 * @param dir [in] procura descendentes do filho 0 ou 1.
 * @return
 */
void procura_vizinhos_inferiores(int d, VNo pac[], int prof, int dir);

/**
 * @brief procura vizinhos inferiores relativos a um eixo coordenado.
 * @param d [in] dimensao do dominio
 * @param r [in] celula a qual procuram-se os descendentes 
 * @param prof [in] profundidade de {r}
 * @param dir [in] procura descendentes do filho 0 ou 1.
 * @param xmin [in] limite inferior da celula {r}
 * @param xmin [in] limite superior da celula {r}
 * @param xf [in] limite inferior do vizinho direito de {r}
 * @param somafluxo [out] contribuicao dos fluxos que saem dos descendentes de {r} e entram no vizinho direito de {r}
 * @return
 */
void encontra_vizinhos_inferiores_esq_refinada(int d, No *r, int prof, int dir, double xmin[], double xmax[], double xf[], double *somafluxo);


/**
 * @brief procura vizinhos superiores relativos a um eixo coordenado.
 * @param d [in] dimensao do dominio
 * @param r [in] celula a qual procuram-se os descendentes 
 * @param prof [in] profundidade de {r}
 * @param dir [in] procura descendentes do filho 0 ou 1.
 * @param xmin [in] limite inferior da celula {r}
 * @param xmax [in] limite superior da celula {r}
 * @param xmm [in] limite superior do vizinho esquerdo de {r}
 * @param somafluxo [out] contribuicao dos fluxos que saem dos descendentes de {r} e entram no vizinho esquerdo de {r}
 * @return
 */
void encontra_vizinhos_superiores_dir_refinada(int d, No *r, int prof, int dir, double xmin[], double xmax[], double xmm[], double *somafluxo);

/**
 * @brief procura media de um certo descendente de {r}.
 * @param r [in] ascendente da celula a qual procuramos a media 
 * @param prof [in] profundidade de {r}
 * @param dir [in] descendente de {r} a ser investigado
 * @param xmin [in] limite inferior da celula {r}
 * @param xmax [in] limite superior da celula {r}
 * @param xMM [in] limite superior do vizinho esquerdo de {r}
 * @param media [out] media do descendente de {r} em que se esta interessado
 * @return
 */
void encontra_media_superior_refinada(int d, No *r, int prof, int dir, double xmin[], double xmax[], double xMM[], double *media);

/**
 * @brief procura media de um certo descendente de {r}.
 * @param r [in] ascendente da celula a qual procuramos a media 
 * @param prof [in] profundidade de {r}
 * @param dir [in] descendente de {r} a ser investigado
 * @param xmin [in] limite inferior da celula {r}
 * @param xmax [in] limite superior da celula {r}
 * @param xmm [in] limite infperior do vizinho direito de {r}
 * @param media [out] media do descendente de {r} em que se esta interessado
 * @return
 */
void encontra_media_inferior_refinada(int d, No *r, int prof, int dir, double xmin[], double xmax[], double xmm[], double *media);

/**
 * @brief limpa memoria.
 * @param r [in] arvore a ser apagada
 * @return
 */
void apaga_arvore(No *r);

/** 
 * @brief copia os valores dos nos da arvore {r} para a arvore {s}, criando no quando necessario
 * @param r [in] arvore matriz, a ser copiada
 * @param s [out] arvore que sera uma copia de r.
 * @return
 */
void copia_arvore(No *r,No *s);

/**
 * @brief Calcula o divergente do fluxo {f} nas folhas da arvore
 * @param d [in] dimensao do dominio
 * @param prof [in] profundidade da celula na malha
 * @param pac [in] pacote de valores para calcular o divergente de f
 * @param xmin [in] coordenada inferior da celula no centro do pacote
 * @param xmax [in] coordenada superior da celula no centro do pacote
 * @param f [in] funcao de fluxo
 * @param pred [in] operador de previsao
 * @return
 */
void calcula_divergente(int d, int prof, VNo pac[], double xmin[], double xmax[], Fluxo f, Preditor pred, bool_t op);

/**
 * @brief Com um papel semelhante a divide_pacote_geral, esta apenas escolhe os filhos das celulas, 
 *        sem interpolar para achar os valores das medias nos filhos.
 * @param d [in] dimensao do dominio
 * @param pac [in] pacote de celulas a ser examinado, daqui sai o pacote menor
 * @param ex [in] eixo de divisao da celula do centro do pacote
 * @param qual [in] escolhe o pacote a ser devolvido 
 * @param fil [out] pacote menor
 * @return
 */
void divide_pacote_menor(int d, VFl pac[], int ex, int qual, VFl fil[]);

/**
 * @brief Calcula os limites superior e inferior da celula filha.
 * @param d [in] dimensao do dominio
 * @param ex [in] eixo ortogonal ao hiperplano de corte
 * @param qual [in] diz de qual filho eh para calcular os limites
 * @param xmin [in] coordenadas do vertice inferior do pai
 * @param xmax [in] coordenadas do vertice superior do pai
 * @param xmin_fil [out] coordenadas do vertice inferior do filho {qual}
 * @param xmax_fil [out] coordenadas do vertice superior do filho {qual}
 * @return
 */
void limites_celula(int d, int ex, int qual, double xmin[], double xmax[], double xmin_fil[], double xmax_fil[]);

bool_t indica_poda_arvore(int d, bool_t op, int niv, VNo pac[], int prof, Preditor pred, double fpoda, double eps);

void threshold(int d, bool_t op, int niv, VNo pac[], int prof, Preditor pred, double fpoda, double eps);


#endif