/*************************************************************************** * Copyright (C) 2008 by Douglas Castro,,, * * douglas@douglas-laptop * * * ***************************************************************************/ /* Last edited on 2008-08-15 11:06:59 by stolfi */ #ifndef ARVORE_H #define ARVORE_H #include #include #include #include #include "bool.h" #include "definicoes.h" void mostra_pacote(FILE *arq, VReg pac[], int k, double xmin[], double xmax[]); /** * Verifica se todos os nos do pacote sao nulos. Se verdadeiro retorna 1, * caso contrario retorna 0 * @param pac [in] * @param k [in] */ int pacote_trivial(VReg pac[], int k); /** * Recebe um pacote de {k}x{k} árvores e respectivos valores. * Calcula o valor da funcão representada por esse pacote no ponto {x=(x[0],x[1])}, * usando apenas os valores do pacote e ignorando as árvores. * Supõe que {x} está na célula central do pacote, definida por {xmin,xmax}. * A versão {_4} usa um spline de grau 4, a versão {_c} usa * uma função constante na célula central. * @param pac [in] pacote com medias celulares e ponteiros para nós da árvore. * @param xmin[] [in] coordenadas dos lados esq/inf da célula {pac[(k*k)/2]}. * @param xmax[] [in] coordenadas dos lados dir/sup da célula {pac[(k*k)/2]}. * @param x[] [in] coordenadas do ponto desejado. */ double interpola_ponto_4(VReg pac[], double xmin[], double xmax[], double x[]); double interpola_ponto_c(VReg pac[], double xmin[], double xmax[], double x[]); /** * Cria uma arvore completa. A media de {f} na célula é armazenada * no nó correspondente. * @param niv [in] quantidade de niveis que tera a arvore * @param profund [in] profundidade de uma certa celula * @param ind [in] indice da celula * @param xmin [in] coordenada do vertice inferior esquerdo * @param xmax [in] coordenada do vertice superior direito * @param (f) funcao arbitraria (se NULL, supõe que é identicamente nula) */ Reg *completa(int niv, int prof, int indice, double xmin[], double xmax[], Funcao *f, Quadratura integra); void altera_valor_em_arvore(Reg *p, int prof, double xmin[], double xmax[], double x[], double v); /* Soma o valor {v} ao campo {fval} da raiz da árvore {*p}, cuja profundidade é {prof}. Também ajusta os campos {fval} de outros nós dessa árvore de modo a preservar os invariantes da estrutura e os valores originais de todas as folhas, exceto a folha que contém o ponto {x[0],x[1]}. Supõe que {xmin[0],xmin[1]} é o canto inferior esquerdo da célula correspondente à raiz {*p}, e que {xmax[0],xmax[1]} é o canto superior direito. O ponto {x[0],x[1]} deve estar nesse retângulo. */ void altera_valor_em_pacote(VReg pac[], int k, int i0, int i1, double xmin[], double xmax[], double x[], double v); /* Soma o valor {v} ao campo {fv} do elemento {i0,i1} do pacote {pac} (de tamanho {k x k}). Se esse elemento tem árvore não-nula, aplica também {altera_valor_em_arvore} a essa árvore. Supõe que {xmin[0],xmin[1]} é o canto inferior esquerdo da célula correspondente ao elemento {i0,i1}, e que {xmax[0],xmax[1]} é o canto superior direito. O ponto {x[0],x[1]} deve estar nesse retângulo. */ /** * (data2sparse) * Recebe uma arvore qualquer, elimina sub-árvores supéárfluas, tomando * cuidado para náo eliminar apenas um filho de algum nó. Mantém a * raiz, mas devolve TRUE se a raiz é supérflua, FALSE caso contrário. * Uma sub-árvore á supárflua se, depois de eliminadas suas sub-árvores * próprias supárfluas, ela não 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 árvore dada é vazia, * devolve FALSE. * @param pac [in/out] gabarito, conjunto de celulas da arvore * @param xmin [in] coordenadas do vertice inferior esquerdo * @param xmax [in] coordenadas do vertice superior direito * @param profund [in] profundidade de uma celula na arvore * @param fval [in] conjunto de medias celulares, se a celula nao existe o valor e interpolado * @param (interpola_quad) funcao de interpolacao quadratica * @param fpoda [in] valor da célula central se não existisse o nó correspondente. * @param eps [in] diferenca que á considerada significativa. */ bool_t poda_arvore( VReg pac[], double xmin[], double xmax[], int profund, Interp_quad interpola_quad, double fpoda, double eps); /** criar historinha*/ Reg *cria_arvore(Funcao *f,int dim, int ind, int prof, int prof_max, double lim, double xmin, double xmax, double ymin, double ymax, Quadratura integra); /** * Recebe um pacote de {k}x{k} árvores e respectivos valores e separa o pacote * necessário para o filho esquerdo ou filho direito. A escolha é feita baseada * no parâmetro de entrada {qual}. * @param pac [in] pacote com medias celulares e ponteiros para nós da árvore. * @param xmin[] [in] coordenadas dos lados esq/inf da célula {pac[(k*k)/2]}. * @param xmax[] [in] coordenadas dos lados dir/sup da célula {pac[(k*k)/2]}. * @param ex [in] eixo perpendicular a divisao * @param (interpola_quad) [in] funcao de interpolacao quadrática das médias. * @param qual [in] pacote de filho a tomar, 0=esq/inf 1=dir/sup * @param fil[] [out] pacote filho pedido. * @param xmin_fil[] [out] coordendas esq/inf da célula central do filho. * @param xmax_fil[] [out] coordendas sup/dir da célula central do filho. */ void divide_pacote(VReg pac[], double xmin[], double xmax[], int ex, Interp_quad interpola_quad, int qual, VReg fil[], double xmin_fil[], double xmax_fil[]); /** * Recebe um pacote de {k}x{k} árvores e respectivos valores. * Calcula o valor da funcão representada por esse pacote no ponto {x=(x[0],x[1])}, * descendo até o nível {niv} ou até o pacote ser trivial, * e então supõe que o valor da função em {x} é igual à média * na célula que contém {x}. Supõe que {x} está na célula central do pacote. * @param pac [in] pacote com medias celulares e ponteiros para nós da árvore. * @param xmin[] [in] coordenadas dos lados esq/inf da célula {pac[(k*k)/2]}. * @param xmax[] [in] coordenadas dos lados dir/sup da célula {pac[(k*k)/2]}. * @param niv [in] quantidade de niveis a descer. * @param profund [in] profundidade do pacote. * @param (interpola_quad) [in] funcao de interpolacao quadrática das médias. * @param x[] [in] coordenadas do ponto desejado. */ double avalia_arvore(VReg pac[], double xmin[], double xmax[], int niv, int profund, Interp_quad interpola_quad, double x[], int debug); /** * Verifica se todos os nos do pacote sao nulos. Se verdadeiro retorna 1, * caso contrario retorna 0 * @param pac [in] * @param k [in] */ int pacote_trivial(VReg pac[], int k); #endif