/***************************************************************************
 *   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.             *
 ***************************************************************************/

#include "arvore.h"

/** Extender para dimensoes 1 3, a 2 ja esta pronta */
/** nessa versao fiz uma brincadeira atribuindo o valor interpolado {fint} nao ao filho direito,
 * mas ao filho esquerdo para ver no que da
 */

/** lembrar que agora tem folhas virtuais etc... */
void divide_pacote(int d, VNo pac[], int ex, Preditor pred,	int qual,	VNo fil[])
{
  int kk = 5;
  	
  auto void escolhe_filhos(int d, int kk, int ex, VNo pac[], Preditor pred,	int qual,	VNo fil[]);
  void escolhe_filhos(int d, int kk, int ex, VNo pac[], Preditor pred,	int qual,	VNo fil[])
  {
		//controle de natalidade!
    int i,j,k, ll, kz, ky, kx;
    if(d==1){ kz = 1; ky = 1; kx = kk; ll = 0;}
    if(d==2){ kz =  1; ky = kk; kx = kk; ll = 0;}
    if(d==3){ kz = kk; ky = kk; kx = kk; ll = kk*kk;}
		/*  SO para lembrar que, da pra tirar dessa funcao e colocar apenas o caso 3
    *  mas e preciso lembrar que as 3 consideracoes acima sao necessarias
    */
    switch(d){
      case 1:
        j=0; //for(j=0;j<ky;j++){
        for(i=0; i<kx; i++)
        { 
          int m = (i + qual)/2 + 1;
          int n = (j + qual)/2;
          int ce = ( ex == 0 ? j : n  );
          int cc = ( ex == 0 ? j : n+1);
          int cd = ( ex == 0 ? j : n+2);
          int de = ( ex == 0 ? m-1 : i);
          int dc = ( ex == 0 ? m : i  );
          int dd = ( ex == 0 ? m+1 : i);
          No *pl = pac[cc*kk + dc].p;
          double fa = pac[ce*kk + de].fv;
          double fb = pac[cc*kk + dc].fv;
          double fc = pac[cd*kk + dd].fv;
          double fint = pred(fa, fb, fc);
          No *p_fil;
          double fv_fil;
          double vfint[] ={ fint, 2.0*fb - fint}; 
          int q = ( ex == 0 ? i : j);
          if(q%2 == 0)
          { 
            int z = qual;
            p_fil = (pl == NULL ? NULL : pl->fil[z]);
            fv_fil = (p_fil == NULL ? vfint[z] : p_fil->fval);
          }
          else
          {
            int z = (qual == 0 ? 1 : 0); 
            p_fil = (pl == NULL ? NULL : pl->fil[z]);
            fv_fil = (p_fil == NULL ? vfint[z] : p_fil->fval);
          }
          fil[j*kk + i].p = p_fil;
          fil[j*kk + i].fv = fv_fil;
        }//}
        break;
      case 2:
        for(j=0; j<ky; j++)
        { 
          for(i=0; i<kx; i++)
          { 
            int m = (i + qual)/2 + 1;
            int n = (j + qual)/2;
            int ce = ( ex == 0 ? j : n  );
            int cc = ( ex == 0 ? j : n+1);
            int cd = ( ex == 0 ? j : n+2);
            int de = ( ex == 0 ? m-1 : i);
            int dc = ( ex == 0 ? m : i  );
            int dd = ( ex == 0 ? m+1 : i);
            No *pl = pac[cc*kk + dc].p;
            double fa = pac[ce*kk + de].fv;
            double fb = pac[cc*kk + dc].fv;
            double fc = pac[cd*kk + dd].fv;
            double fint = pred(fa, fb, fc);
            No *p_fil;
            double fv_fil;
            double vfint[] ={ fint, 2.0*fb - fint}; 
            int q = ( ex == 0 ? i : j);
            if(q%2 == 0)
            { 
              int z = qual;
              p_fil = (pl == NULL ? NULL : pl->fil[z]);
              fv_fil = (p_fil == NULL ? vfint[z] : p_fil->fval);
            }
            else
            {
              int z = (qual == 0 ? 1 : 0); 
              p_fil = (pl == NULL ? NULL : pl->fil[z]);
              fv_fil = (p_fil == NULL ? vfint[z] : p_fil->fval);
            }
            fil[j*kk + i].p = p_fil;
            fil[j*kk + i].fv = fv_fil;
          }
        }
        break;
      case 3:
        for(k=0;k<kz;k++)
        {
          for(j=0;j<ky;j++)
          {
            for(i=0;i<kx;i++)
            {
              int m = (i + qual)/2 + 1;
              int n = (j + qual)/2;
              int o = (k + qual)/2 + 1;
              int ce = ( ex == 0 ? j : n  );
              int cc = ( ex == 0 ? j : n+1);
              int cd = ( ex == 0 ? j : n+2);
              int de = ( ex == 0 ? m-1 : i);
              int dc = ( ex == 0 ? m : i  );
              int dd = ( ex == 0 ? m+1 : i);
              int ee = ( ex == 2 ? o-1 : k);
              int ec = ( ex == 2 ? o :   k);
              int ed = ( ex == 2 ? o+1 : k);
              No *pl = pac[ec*ll + cc*kk + dc].p;
              double fa = pac[ec*ll + ce*kk + de].fv;
              double fb = pac[ec*ll + cc*kk + dc].fv;
              double fc = pac[ec*ll + cd*kk + dd].fv;
              double fint = pred(fa, fb, fc);
              No *p_fil;
              double fv_fil;
              double vfint[] = { fint, 2.0*fb - fint}; 
							
              int q = ( ex == 0 ? i : j);
              q = ( ex == 2 ? k : q);
              if(q%2 == 0)
              { 
                int z = qual;
                p_fil = (pl == NULL ? NULL : pl->fil[z]);
                fv_fil = (p_fil == NULL ? vfint[z] : p_fil->fval);
              }
              else
              {
                int z = (qual == 0 ? 1 : 0); 
// 								z = ();//parece que nao precisa de correcao aqui
                p_fil = (pl == NULL ? NULL : pl->fil[z]);
                fv_fil = (p_fil == NULL ? vfint[z] : p_fil->fval);
              }
              fil[k*ll + j*kk + i].p = p_fil;
              fil[k*ll + j*kk + i].fv = fv_fil;
            }
          }
        }
        break;
      default:
        fprintf(stderr," divide_pacote -arvore.c- nao implementado para dimensao superior a 3");
        break;
    }
  }//fim funcao
	
  escolhe_filhos(d,  kk, ex, pac, pred,	qual,	fil);
}

/** nessa versao fiz uma brincadeira atribuindo o valor interpolado {fint} nao ao filho direito,
 * mas ao filho esquerdo para ver no que da, eh igual, desde que a formula da interpolacao seja alterada.
 */
void divide_pacote_geral(int d, VNo pac[], int ex,	Preditor pred,	int qual,	VNo fil[])
{
  int kk = 5;
	
  auto void escolhe_filhos(int d, int kk, int ex, VNo pac[], Preditor pred,	int qual,	VNo fil[]);
  void escolhe_filhos(int d, int kk, int ex, VNo pac[], Preditor pred,	int qual,	VNo fil[])
  {
		//controle de natalidade!
    int i,j,k, ll, kz, ky, kx;
    if(d==1){ kz = 1; ky = 1; kx = kk; ll = 0;}
    if(d==2){ kz =  1; ky = kk; kx = kk; ll = 0;}
    if(d==3){ kz = kk; ky = kk; kx = kk; ll = kk*kk;}
		/*  SO para lembrar que, da pra tirar dessa funcao e colocar apenas o caso 3
    *  mas e preciso lembrar que as 3 consideracoes acima sao necessarias
    */
    switch(d){
      case 1:
        j=0; //for(j=0;j<ky;j++){
        for(i=0; i<kx; i++)
        { 
          int m = (i + qual)/2 + 1;
          int n = (j + qual)/2;
          int ce = ( ex == 0 ? j : n  );
          int cc = ( ex == 0 ? j : n+1);
          int cd = ( ex == 0 ? j : n+2);
          int de = ( ex == 0 ? m-1 : i);
          int dc = ( ex == 0 ? m : i  );
          int dd = ( ex == 0 ? m+1 : i);
          No *pl = pac[cc*kk + dc].p;
          double fa = pac[ce*kk + de].fv;
          double fb = pac[cc*kk + dc].fv;
          double fc = pac[cd*kk + dd].fv;
          double fint = pred(fa, fb, fc);
          No *p_fil;
          double fv_fil;
          double vfint[] ={ fint, 2.0*fb - fint}; 
          int q = ( ex == 0 ? i : j);
          if(q%2 == 0)
          { 
            int z = qual;
            p_fil = (pl == NULL ? NULL : pl->fil[z]);
            fv_fil = (p_fil == NULL ? vfint[z] : p_fil->fval);
          }
          else
          {
            int z = (qual == 0 ? 1 : 0); 
            p_fil = (pl == NULL ? NULL : pl->fil[z]);
            fv_fil = (p_fil == NULL ? vfint[z] : p_fil->fval);
          }
          fil[j*kk + i].p = p_fil;
          fil[j*kk + i].fv = fv_fil;
        }//}
        break;
      case 2:
        for(j=0; j<ky; j++)
        { 
          for(i=0; i<kx; i++)
          { 
            int m = (i + qual)/2 + 1;
            int n = (j + qual)/2;
            int ce = ( ex == 0 ? j : n  );
            int cc = ( ex == 0 ? j : n+1);
            int cd = ( ex == 0 ? j : n+2);
            int de = ( ex == 0 ? m-1 : i);
            int dc = ( ex == 0 ? m : i  );
            int dd = ( ex == 0 ? m+1 : i);
            No *pl = pac[cc*kk + dc].p;
            double fa = pac[ce*kk + de].fv;
            double fb = pac[cc*kk + dc].fv;
            double fc = pac[cd*kk + dd].fv;
            double fint = pred(fa, fb, fc);
            No *p_fil;
            double fv_fil;
            double vfint[] ={ fint, 2.0*fb - fint}; 
            int q = ( ex == 0 ? i : j);
            if(q%2 == 0)
            { 
              int z = qual;
              p_fil = (pl == NULL ? NULL : pl->fil[z]);
              fv_fil = (p_fil == NULL ? vfint[z] : p_fil->fval);
            }
            else
            {
              int z = (qual == 0 ? 1 : 0); 
              p_fil = (pl == NULL ? NULL : pl->fil[z]);
              fv_fil = (p_fil == NULL ? vfint[z] : p_fil->fval);
            }
            fil[j*kk + i].p = p_fil;
            fil[j*kk + i].fv = fv_fil;
          }
        }
        break;
      case 3:
        for(k=0;k<kz;k++)
        {
          for(j=0;j<ky;j++)
          {
            for(i=0;i<kx;i++)
            {
              int m = (i + qual)/2 + 1;
              int n = (j + qual)/2;
              int o = (k + qual)/2 + 1;
              int ce = ( ex == 0 ? j : n  );
              int cc = ( ex == 0 ? j : n+1);
              int cd = ( ex == 0 ? j : n+2);
              int de = ( ex == 0 ? m-1 : i);
              int dc = ( ex == 0 ? m : i  );
              int dd = ( ex == 0 ? m+1 : i);
              int ee = ( ex == 2 ? o-1 : k);
              int ec = ( ex == 2 ? o :   k);
              int ed = ( ex == 2 ? o+1 : k);
              No *pl = pac[ec*ll + cc*kk + dc].p;
              double fa = pac[ec*ll + ce*kk + de].fv;
              double fb = pac[ec*ll + cc*kk + dc].fv;
              double fc = pac[ec*ll + cd*kk + dd].fv;
              double fint = pred(fa, fb, fc);
              No *p_fil;
              double fv_fil;
              double vfint[] = { fint, 2.0*fb - fint}; 
							
              int q = ( ex == 0 ? i : j);
              q = ( ex == 2 ? k : q);
              if(q%2 == 0)
              { 
                int z = qual;
                p_fil = (pl == NULL ? NULL : pl->fil[z]);
                fv_fil = (p_fil == NULL ? vfint[z] : p_fil->fval);
              }
              else
              {
                int z = (qual == 0 ? 1 : 0); 
// 								z = ();//parece que nao precisa de correcao aqui
                p_fil = (pl == NULL ? NULL : pl->fil[z]);
                fv_fil = (p_fil == NULL ? vfint[z] : p_fil->fval);
              }
              fil[k*ll + j*kk + i].p = p_fil;
              fil[k*ll + j*kk + i].fv = fv_fil;
            }
          }
        }
        break;
      default:
        fprintf(stderr," divide_pacote -arvore.c- nao implementado para dimensao superior a 3");
        break;
    }
  }//fim funcao
	
  escolhe_filhos(d,  kk, ex, pac, pred,	qual,	fil);
	
}

No *completa(int d, int niv, int prof, int indice, double xmin[], double xmax[], Funcao *f, Quadratura integra)
{ 
  if (niv == 0) { return NULL; }
  No *e = malloc(sizeof(No));
  e->deletable = FALSE;
  e->leaf = FALSE; 
  e->virtual_leaf = FALSE;
  if(niv-1 == 0)
  { e->leaf = TRUE; }

  if (f != NULL) 
  { 
    double fint =  integra( d, xmin, xmax, f);
    double cvol = 1.0;
    int i;
    for(i=0;i<d;i++)
      cvol *= fabs(xmax[i]-xmin[i]);
    e->fval = fint/cvol; 
  }
  else
  { e->fval = 0.0; }

  double xmin_fil[2], xmax_fil[2];
  int ex = prof%d;
  int qual;
  for(qual=0;qual<2;qual++)
  {
    limites_celula( d, ex, qual, xmin, xmax, xmin_fil, xmax_fil);
    e->fil[qual] = completa(d, niv - 1, prof + 1, 2*indice + qual, xmin_fil, xmax_fil, f,integra);
  }
  return e;
}

void conta_folhas(No *r, int *cont)
{
  assert((r->fil[0] == NULL) == (r->fil[1] == NULL));
  
  if(r->fil[0] == NULL)
  {
    int c = *cont;
    *cont = c + 1;
    return;
  }
  int qual;
  for(qual=0;qual<2;qual++)
    conta_folhas(r->fil[qual], cont);
  
}

void conta_nos(No *r, int *cont)
{
  assert((r->fil[0] == NULL) == (r->fil[1] == NULL));
  
  int c = *cont;
  *cont = c + 1;
  
  if(r->leaf)
  { return; }
  int qual;
  for(qual=0;qual<2;qual++)
    conta_nos(r->fil[qual], cont);
}

void copia_folhas(No *r, double vet[], int *cont)
{
  assert((r->fil[0] == NULL) == (r->fil[1] == NULL));
  if((r->fil[0] == NULL)){return;}
  if(r->leaf)
  {
    int c = *cont;
    double db = r->fval;
    vet[c] = db;
    *cont = c + 1;
    return;
  }
  int qual;
  for(qual=0;qual<2;qual++)
    copia_folhas(r->fil[qual], vet, cont);
}

void atualiza_arvore(No *r)
{
  /* Paranoia */
  assert((r->fil[0]==NULL) == (r->fil[1]==NULL));
  if(r->fil[0]==NULL)
  { return; }

  int qual;
  for (qual = 0; qual <= 1; qual++)
  { 
    atualiza_arvore(r->fil[qual]);
  }
  
  /* nao sei se ja devo atualizar o no agora ou depois que atualizar os nos virtuais */
  if(!(r->leaf))
  {
//     fprintf(stderr,"atualiza_arvore - ent\n");
    r->fval = 0.5*(r->fil[0]->fval + r->fil[1]->fval);
  }
//   return;
}

void atualiza_folhas_virtuais(int d, int prof, VNo pac[], Preditor pred)
{
  int ord = 5;
  int ctr = pow(ord,d)/2;
  assert((pac[ctr].p->fil[0]==NULL) == (pac[ctr].p->fil[1]==NULL));
  if(pac[ctr].p->fil[0]==NULL)
  { return; }
  double vp[2];
  int ex = prof % d;
  
  int qual;
  for(qual = 0; qual <= 1; qual++)
  { 
    int tam = pow(ord,d);
    VNo pac_fil[tam];
  
    /* Constrói o pacote do filho {qual}: */
    divide_pacote_geral( d, pac, ex, pred, qual, pac_fil);

    /* Calcula o valor que {pac_fil[ctr].fv} teria se esse nó fosse NULL: */
    int corr = pow(ord,ex); 
    
    double x0 = pac[ctr-corr].fv; // considera a condicao de contorno, etipulada em divide_pacote
    double x1 = pac[ctr].fv; 
    double x2 = pac[ctr+corr].fv; 
    double prv = pred( x0, x1, x2 ); // previsao do filho esquerdo
    double fprv = qual==0 ? prv : 2.0*x1 - prv;
    vp[0] = prv;
    vp[1] = 2.0*x1 - prv;
    atualiza_folhas_virtuais(d, prof+1, pac_fil, pred);
  }
  
  if(((pac[ctr].p->leaf)&&(pac[ctr].p->fil[0]!=NULL))&&(pac[ctr].p->fil[0]->virtual_leaf))
  {
//     fprintf(stderr,"atualiza_folhas_virtuais - ent\n");
    pac[ctr].p->fil[0]->fval = vp[0];
    pac[ctr].p->fil[1]->fval = vp[1];
//     return;
  }
}

bool_t marca_nos(int d, VNo pac[], int niv, int prof, Preditor pred, double fpoda, double eps)
{
  int  ord=5; // posteriormente k pode se tornar argumento da funcao
  int ctr = pow(ord,d)/2;
  
  if (pac[ctr].p == NULL) 
  { /* Não há o que podar: */
    return FALSE;
  }
  
  /* fprintf(stderr, "%*sf(int) = %9.6f f(arv)= %9.6f\n", 2*profund, "", pac[ctr].fv, pac[ctr].p->fval); */
  
  /* Precisa podar as sub-árvores, depois ver se a raiz é supérflua. */

  /* Decide o eixo {ex} perpendicular ao corte: */
  int ex = prof % d;
  
  int qual;
  for (qual = 0; qual <= 1; qual++)
  { 
    int tam = pow(ord,d);
    VNo pac_fil[tam];
  
    /* Constrói o pacote do filho {qual}: */
    divide_pacote_geral( d, pac, ex, pred, qual, pac_fil);

    /* Calcula o valor que {pac_fil[ctr].fv} teria se esse nó fosse NULL: */
    int corr = pow(ord,ex);
    double x0 = pac[ctr-corr].fv; // considera a condicao de contorno, estipulada em divide_pacote
    double x1 = pac[ctr].fv; 
    double x2 = pac[ctr+corr].fv; 
    double prv = pred( x0, x1, x2 ); // previsao do filho esquerdo
    double fprv = qual==0 ? prv : 2.0*x1 - prv;
    double fpoda_fil = fprv; 
//     pac[ctr].p->deletable = marca_nos(d, pac_fil, niv, prof+1, pred, fpoda_fil, eps);
    pac[ctr].p->deletable = marca_nos(d, pac_fil, niv, prof+1, pred, fpoda_fil, eps);
  }
  /* Paranoia: */
  assert((pac[ctr].p->fil[0] == NULL) == (pac[ctr].p->fil[1] == NULL));
        
  /* Se {pac[ctr].p} tem filhos, nao e superfluo: */
  if (pac[ctr].p->fil[0] != NULL) { return FALSE; }

  /* Vale a pena manter a raiz? */
  double detalhe = fpoda - pac[ctr].fv;
  /* fprintf(stderr, "%*sdetalhe = %9.6f\n", 2*profund, "", detalhe); */
  double l = prof;
  double tol = pow(2.0,d*(l-(niv+1)))*eps;
  if ((fabs(detalhe) < tol) && (prof>3))
  { /* O nó central é supérfluo: */
    /* fprintf(stderr, "%*ssuperfluo!\n", 2*profund, ""); */
    return TRUE;
  }
  else
  { /* O nó central precisa ser mantido: */
    /* fprintf(stderr, "%*simportante!\n", 2*profund, ""); */
    return FALSE;
  }
}


void adapta_arvore(int d, VNo pac[], double esq[], double dir[], int prof, int niv, Preditor pred, double eps)
{
  int  ord = 5; // posteriormente k pode se tornar argumento da funcao
  int ctr = pow(ord,d)/2;
  /* tem prever todo filho e se necessario cria um no */
  if (pac[ctr].p->fil[0] == NULL) 
  { /* Não há o que podar: */
    return;
  }
  /* fprintf(stderr, "%*sf(int) = %9.6f f(arv)= %9.6f\n", 2*profund, "", pac[ctr].fv, pac[ctr].p->fval); */
  /* Precisa podar as sub-árvores, depois ver se a raiz é supérflua. */
  
  /* Decide o eixo {ex} perpendicular ao corte: */
  int ex = prof % d;
  int qual;
  double fv[2], esq_net[2], dir_net[2];
  for (qual = 0; qual <= 1; qual++)
  { 
    int tam = pow(ord,d);
    VNo pac_fil[tam];
  
    /* Constrói o pacote do filho {qual}: */
    divide_pacote_geral( d, pac, ex, pred, qual, pac_fil);

    /* Calcula o valor que {pac_fil[ctr].fv} teria se esse nó fosse NULL: */
    int corr = pow(ord,ex);
    double x0 = pac[ctr-corr].fv; // considera a condicao de contorno, estipulada em divide_pacote
    double x1 = pac[ctr].fv; 
    double x2 = pac[ctr+corr].fv; 
    double prv = pred( x0, x1, x2 ); // previsao do filho esquerdo
    fv[0] = prv; fv[1] = 2.0*x1 - prv;
    double fprv = qual==0 ? prv : 2.0*x1 - prv;
    double fpoda_fil = fprv; // passar pro filho ...
    /* prevendo os netos */
    x0 = pac_fil[ctr-corr].fv;
    x1 = pac_fil[ctr].fv;
    x2 = pac_fil[ctr+corr].fv;
    prv = pred( x0, x1, x2 );
    if(qual==0)
    { esq_net[0] = prv; esq_net[1] = 2.0*x1-prv;}
    if(qual==1)
    { dir_net[0] = prv; dir_net[1] = 2.0*x1-prv;}
    
    adapta_arvore(d, pac_fil, esq_net, dir_net, prof+1, niv, pred, eps);
  }
  /* Elimina os filhos, se sao nao-nulos mas ambos superfluos: */
  /* deste no */
  /* Paranoia: */
  assert((pac[ctr].p->fil[0] == NULL) == (pac[ctr].p->fil[1] == NULL));

  bool_t pai = pac[ctr].p->deletable;
  bool_t fesq = /*pac[ctr].p->fil[0]==NULL ? FALSE:*/ pac[ctr].p->fil[0]->deletable;
  bool_t fdir = /*pac[ctr].p->fil[1]==NULL ? FALSE:*/ pac[ctr].p->fil[1]->deletable;
//   bool_t fol = pac[ctr].p->fil[1]->leaf; // BESTEIRA PERGUNTAR ISSO, SE DELETAVEL NAO TEM FILHO
  if ((pai && (fesq && fdir))/* && fol*/&&(prof>3))
  { /* torna o pai folha */
    pac[ctr].p->leaf = TRUE;
    /* torna os dois filhos folhas virtuais: */
    pac[ctr].p->fil[0]->virtual_leaf = TRUE;
    pac[ctr].p->fil[1]->virtual_leaf = TRUE;
    /* apaga os netos, se tiver */
    free(pac[ctr].p->fil[0]->fil[0]); pac[ctr].p->fil[0]->fil[0] = NULL;
    free(pac[ctr].p->fil[0]->fil[1]); pac[ctr].p->fil[0]->fil[1] = NULL;
    free(pac[ctr].p->fil[1]->fil[0]); pac[ctr].p->fil[1]->fil[0] = NULL;
    free(pac[ctr].p->fil[1]->fil[1]); pac[ctr].p->fil[1]->fil[1] = NULL;
//       return;
  }
  else if(((prof+2)<=(niv-1))&&(pac[ctr].p->fil[0]!=NULL))
  {
    assert((pac[ctr].p->fil[0]->fil[0]==NULL)==(pac[ctr].p->fil[0]->fil[1]==NULL));
    if(((fdir==FALSE) && (pac[ctr].p->fil[0]->fil[0]==NULL) ) /*&& profund>3*/)
    {
      /* fprintf(stderr, "%*s\n", 2*profund, "0"); */
      pac[ctr].p->fil[0]->virtual_leaf = FALSE;
      pac[ctr].p->fil[0]->leaf = TRUE;
      pac[ctr].p->fil[0]->fil[0] = malloc(sizeof(No));
      pac[ctr].p->fil[0]->fil[1] = malloc(sizeof(No));
      
      for(qual=0;qual<2;qual++)
      {
        pac[ctr].p->fil[0]->fil[qual]->fval = esq[qual];
        pac[ctr].p->fil[0]->fil[qual]->leaf = FALSE;
        pac[ctr].p->fil[0]->fil[qual]->virtual_leaf = TRUE;
        pac[ctr].p->fil[0]->fil[qual]->fil[0] = NULL;
        pac[ctr].p->fil[0]->fil[qual]->fil[1] = NULL;
        
      }
    }
    assert((pac[ctr].p->fil[1]->fil[0]==NULL)==(pac[ctr].p->fil[1]->fil[1]==NULL));
    if(((fesq==FALSE) && (pac[ctr].p->fil[1]->fil[0]==NULL)) /*&& profund>3*/)
    {
      /* fprintf(stderr, "%*s\n", 2*profund, "1"); */
      pac[ctr].p->fil[1]->virtual_leaf = FALSE;
      pac[ctr].p->fil[1]->leaf = TRUE;
      pac[ctr].p->fil[1]->fil[0] = malloc(sizeof(No));
      pac[ctr].p->fil[1]->fil[1] = malloc(sizeof(No));
      for(qual=0;qual<2;qual++)
      {
        pac[ctr].p->fil[1]->fil[qual]->fval = dir[qual];
        pac[ctr].p->fil[1]->fil[qual]->leaf = FALSE;
        pac[ctr].p->fil[1]->fil[qual]->virtual_leaf = TRUE;
        pac[ctr].p->fil[1]->fil[qual]->fil[0] = NULL;
        pac[ctr].p->fil[1]->fil[qual]->fil[1] = NULL;
        
      }
    }
  }
//   /* este no precisa ter filho ? */
//   bool_t fil = pac[ctr].p->fil[0]==NULL ? FALSE :TRUE; /* tem filho? */
//   bool_t del = pac[ctr].p->deletable; /* deletavel ?*/
//   bool_t ras = ((prof+1)< niv) ? TRUE : FALSE; /* cabe mais um nivel?*/
//   if(!fil && (!del && ras))
//   {
//     pac[ctr].p->fil[0] = malloc(sizeof(No));
//     pac[ctr].p->fil[1] = malloc(sizeof(No));
//     int qual;
//     for(qual = 0;qual<2;qual++)
//     {
//       pac[ctr].p->fil[qual]->fval = fv[qual];
//       pac[ctr].p->fil[qual]->deletable = FALSE;
//       pac[ctr].p->fil[qual]->leaf = FALSE;
//       pac[ctr].p->fil[qual]->virtual_leaf = TRUE;
//       pac[ctr].p->fil[qual]->fil[0] = NULL;
//       pac[ctr].p->fil[qual]->fil[1] = NULL;
//     }
//   }
//   assert((pac[ctr].p->fil[0] == NULL) == (pac[ctr].p->fil[1] == NULL));
//   if(pac[ctr].p->fil[0] == NULL)
//   {
// //     bool_t fil = (pac[ctr].p->fil[0] != NULL ? TRUE : FALSE);    /* tem filho ? */
//     bool_t del = (pac[ctr].p->deletable == TRUE ? TRUE : FALSE); /* deletavel ? */
//     bool_t ras = ((prof < niv) ? TRUE : FALSE);                    /* e raso    ? */  
//   
//     if(/*!fil && */(!del && ras))
//     {
//       pac[ctr].p->fil[0] = malloc(sizeof(No));
//       pac[ctr].p->fil[1] = malloc(sizeof(No));
//       int qual;
//       for(qual=0;qual<2;qual++)
//       {
//         pac[ctr].p->fil[qual]->fil[0] = NULL; // diz que o neto e null
//         pac[ctr].p->fil[qual]->fil[1] = NULL; // diz que o neto e null
//         pac[ctr].p->fil[qual]->deletable = FALSE;
//         pac[ctr].p->fil[qual]->leaf = prof + 1 == niv-1 ? TRUE : FALSE;
//         pac[ctr].p->fil[qual]->virtual_leaf = prof + 1 == niv-1 ? TRUE : FALSE;
//       }
// //       return;
//     }
//   }
//   
  /* Se {pac[ctr].p} tem filho virtual, ver se precisa promover a filho real */
//   if(pac[ctr].p->fil[0]==NULL){return;}
//   bool_t virt = pac[ctr].p/*->fil[0]*/->virtual_leaf;
//   bool_t dele = pac[ctr].p/*->fil[0]*/->deletable;
//   int corr = pow(ord,ex);
//   if(virt &&(!dele))
//   {
//     bool_t ladoe = TRUE, ladod = TRUE; /* precisa criar um filho virtual? */ 
//     if((pac[ctr-corr].p==NULL)||(pac[ctr-corr].p->fil[0]==NULL))
//     { ladoe = FALSE;} /* nao precisa */
//     if((pac[ctr+corr].p==NULL)||(pac[ctr+corr].p->fil[0]==NULL))
//     { ladod = FALSE;} /* nao precisa */
// 
//     pac[ctr].p->leaf = TRUE;
//     pac[ctr].p->virtual_leaf = FALSE;
//     if((ladod || ladoe)&&(prof<(niv-1)))
//     {
//       pac[ctr].p->fil[0] = malloc(sizeof(No));
//       pac[ctr].p->fil[1] = malloc(sizeof(No));
//       int qual;
//       for(qual=0;qual<2;qual++)
//       {
//         pac[ctr].p->fil[qual]->fil[0] = NULL; // diz que o neto e null
//         pac[ctr].p->fil[qual]->fil[1] = NULL; // diz que o neto e null
//         pac[ctr].p->fil[qual]->fval = fv[qual];
//         pac[ctr].p->fil[qual]->deletable = FALSE;
//         pac[ctr].p->fil[qual]->leaf = prof + 1 == niv-1 ? TRUE : FALSE;
//         pac[ctr].p->fil[qual]->virtual_leaf = prof + 1 == niv-1 ? TRUE : FALSE;
//       }
//     }
// //     return;
//   }
  /* Se {pac[ctr].p} tem filhos, nao deletaveis: */
//   if (pac[ctr].p->fil[0]->deletable == FALSE) { return; }
  
}

bool_t poda_arvore(int d, int niv, VNo pac[], double esq[], double dir[], int prof, Preditor pred, double fpoda, double eps)
{
  int  ord=5; // posteriormente k pode se tornar argumento da funcao
  int ctr = pow(ord,d)/2;
  
  if (pac[ctr].p == NULL) 
  { /* Não há o que podar: */
    return FALSE;
  }
  
  /* fprintf(stderr, "%*sf(int) = %9.6f f(arv)= %9.6f\n", 2*profund, "", pac[ctr].fv, pac[ctr].p->fval); */
  
  /* Precisa podar as sub-árvores, depois ver se a raiz é supérflua. */

  /* Decide o eixo {ex} perpendicular ao corte: */
  int ex = prof % d;
  
  int qual;
  bool_t filho_superfluo[2]; /* TRUE para filhos que podem ser podados. */
  for (qual = 0; qual <= 1; qual++)
  { 
    int tam = pow(ord,d);
    VNo pac_fil[tam];
  
    /* Constrói o pacote do filho {qual}: */
    divide_pacote_geral(d, pac, ex, pred, qual, pac_fil);
    
    /* Calcula o valor que {pac_fil[ctr].fv} teria se esse nó fosse NULL: */
    int corr = pow(ord,ex);
    double x0 = pac[ctr-corr].fv; // considera a condicao de contorno, estipulada em divide_pacote
    double x1 = pac[ctr].fv; 
    double x2 = pac[ctr+corr].fv; 
    double prv = pred( x0, x1, x2 ); // previsao do filho esquerdo
    double fprv = qual==0 ? prv : 2.0*x1 - prv;
    double fpoda_fil = fprv; 
    
    /* valores que estao nos 2 netos esq e nos 2 direitos */
    /* prevendo os netos */
    double esq_net[2]/*={0.0,0.0}*/, dir_net[2]/*={0.0,0.0}*/;
    /* em dimensao superior tem que mudar o eixo */
    int exo = (prof + 1)%d;
    corr = pow(ord,exo);
    VNo pac_n[tam];
    divide_pacote_geral(d, pac, ex, pred, 0, pac_n);
    x0 = pac_n[ctr-corr].fv;
    x1 = pac_n[ctr].fv;
    x2 = pac_n[ctr+corr].fv;
    prv = pred( x0, x1, x2 );
    esq_net[0] = prv; esq_net[1] = 2.0*x1-prv;
    divide_pacote_geral(d, pac, ex, pred, 1, pac_n);
    x0 = pac_n[ctr-corr].fv;
    x1 = pac_n[ctr].fv;
    x2 = pac_n[ctr+corr].fv;
    prv = pred( x0, x1, x2 );
    dir_net[0] = prv; dir_net[1] = 2.0*x1-prv;

    filho_superfluo[qual] = poda_arvore(d, niv, pac_fil, esq_net, dir_net, prof+1, pred, fpoda_fil, eps);
  }
  /* Elimina os filhos, se sao nao-nulos mas ambos superfluos: */
  if ((filho_superfluo[0] && filho_superfluo[1]) && prof>3)
  { 
    /*fprintf(stderr, "%*s\n", 2*profund, "+");*/
    /* Elimina os dois filhos: */
    free(pac[ctr].p->fil[0]); pac[ctr].p->fil[0] = NULL;
    free(pac[ctr].p->fil[1]); pac[ctr].p->fil[1] = NULL;
    /* torna o pai uma folha */
    pac[ctr].p->leaf = TRUE;
    pac[ctr].p->virtual_leaf = FALSE;
  }
  else if((prof+2)<=(niv-1))
  {
    assert((pac[ctr].p->fil[0]->fil[0]==NULL)==(pac[ctr].p->fil[0]->fil[1]==NULL));
    if(((filho_superfluo[1]==FALSE) && (pac[ctr].p->fil[0]->fil[0]==NULL) ) /*&& profund>3*/)
    {
      /* fprintf(stderr, "%*s\n", 2*profund, "0"); */
      pac[ctr].p->fil[0]->fil[0] = malloc(sizeof(No));
      pac[ctr].p->fil[0]->fil[1] = malloc(sizeof(No));
      
      for(qual=0;qual<2;qual++)
      {
        int corr = pow(ord,ex);
        pac[ctr].p->fil[0]->fil[qual]->fval = esq[qual];
        pac[ctr].p->fil[0]->fil[qual]->leaf = FALSE;
        pac[ctr].p->fil[0]->fil[qual]->virtual_leaf = TRUE;
        pac[ctr].p->fil[0]->fil[qual]->deletable = TRUE;
        pac[ctr].p->fil[0]->fil[qual]->fil[0] = NULL;
        pac[ctr].p->fil[0]->fil[qual]->fil[1] = NULL;
      }
    }
    if(((filho_superfluo[0]==FALSE) && (pac[ctr].p->fil[1]->fil[0]==NULL)) /*&& profund>3*/)
    {
      /* fprintf(stderr, "%*s\n", 2*profund, "1"); */
      pac[ctr].p->fil[1]->fil[0] = malloc(sizeof(No));
      pac[ctr].p->fil[1]->fil[1] = malloc(sizeof(No));
      for(qual=0;qual<2;qual++)
      {
        pac[ctr].p->fil[1]->fil[qual]->fval = dir[qual];
        pac[ctr].p->fil[1]->fil[qual]->leaf = FALSE;
        pac[ctr].p->fil[1]->fil[qual]->virtual_leaf = TRUE;
        pac[ctr].p->fil[1]->fil[qual]->fil[0] = NULL;
        pac[ctr].p->fil[1]->fil[qual]->fil[1] = NULL;
        
      }
    }
  }
  /* Paranoia: */
  assert((pac[ctr].p->fil[0] == NULL) == (pac[ctr].p->fil[1] == NULL));
        
  /* Se {pac[ctr].p} tem filhos, nao e superfluo: */
  if (pac[ctr].p->fil[0] != NULL) { return FALSE; }

  /* Vale a pena manter a raiz? */
  double detalhe = fpoda - pac[ctr].fv;
  /* fprintf(stderr, "%*sdetalhe = %9.6f\n", 2*profund, "", detalhe); */
  double l = prof;
  double tol = pow(2.0,d*(l-(niv+1)))*eps;
  if ((fabs(detalhe) < tol) && (prof>=4))
  { /* O nó central é supérfluo: */
    /* fprintf(stderr, "%*ssuperfluo!\n", 2*profund, ""); */
    return TRUE;
  }
  else
  { /* O nó central precisa ser mantido: */
    /* fprintf(stderr, "%*simportante!\n", 2*profund, ""); */
    return FALSE;
  }
}

bool_t diz(VNo pac[], int ord, int d)
{
  bool_t temp = FALSE, tmp = TRUE;
  int i, ctr = pow(ord,d)/2;
  for(i=0;i<d;i++)
  {
    int corr = pow(ord,i);
//     assert((pac[ctr - corr].p->fil[0] == NULL)==(pac[ctr - corr].p->fil[1] == NULL));
//     assert((pac[ctr + corr].p->fil[0] == NULL)==(pac[ctr + corr].p->fil[1] == NULL));
    
    if(pac[ctr - corr].p == NULL || pac[ctr - corr].p->fil[0] == NULL)
    { temp = TRUE; }
    else if(pac[ctr + corr].p == NULL || pac[ctr + corr].p->fil[1] == NULL)
    { temp = TRUE; } 
    else if(pac[ctr - corr].p->leaf || pac[ctr - corr].p->fil[0]->leaf)
    { temp = TRUE; }
    else if(pac[ctr + corr].p->leaf || pac[ctr + corr].p->fil[1]->leaf)
    { temp = TRUE; }
    else
    { tmp = FALSE; }
  }
  if(temp == TRUE)
  { return temp; }
  else{ return tmp; }
}


bool_t adapta_arvore2(int d, VNo pac[], double esq[], double dir[], int prof, int niv, Preditor pred, double fpoda, double eps)
{
  int  ord=5; // posteriormente k pode se tornar argumento da funcao
  int ctr = pow(ord,d)/2;
  
  if (pac[ctr].p == NULL) 
  { /* Não há o que podar: */
    return FALSE;
  }
  
  /* fprintf(stderr, "%*sf(int) = %9.6f f(arv)= %9.6f\n", 2*profund, "", pac[ctr].fv, pac[ctr].p->fval); */
  
  /* Precisa podar as sub-árvores, depois ver se a raiz é supérflua. */

  /* Decide o eixo {ex} perpendicular ao corte: */
  int ex = prof % d;
  
  int qual;
  bool_t filho_superfluo[2]; /* TRUE para filhos que podem ser podados. */
  for (qual = 0; qual <= 1; qual++)
  { 
    int tam = pow(ord,d);
    VNo pac_fil[tam];
  
    /* Constrói o pacote do filho {qual}: */
    divide_pacote_geral(d, pac, ex, pred, qual, pac_fil);
    
    /* Calcula o valor que {pac_fil[ctr].fv} teria se esse nó fosse NULL: */
    int corr = pow(ord,ex);
    double x0 = pac[ctr-corr].fv; // considera a condicao de contorno, estipulada em divide_pacote
    double x1 = pac[ctr].fv; 
    double x2 = pac[ctr+corr].fv; 
    double prv = pred( x0, x1, x2 ); // previsao do filho esquerdo
    double fprv = qual==0 ? prv : 2.0*x1 - prv;
    double fpoda_fil = fprv; 
    
    /* valores que estao nos 2 netos esq e nos 2 direitos */
    /* prevendo os netos */
    double esq_net[2]/*={0.0,0.0}*/, dir_net[2]/*={0.0,0.0}*/;
    /* em dimensao superior tem que mudar o eixo */
    int exo = (prof + 1)%d;
    corr = pow(ord,exo);
    int i;
    for(i=0;i<2;i++)
    {
      VNo pac_n[tam];
      divide_pacote_geral(d, pac, ex, pred, i, pac_n);
      x0 = pac_n[ctr-corr].fv;
      x1 = pac_n[ctr].fv;
      x2 = pac_n[ctr+corr].fv;
      prv = pred( x0, x1, x2 );
      if(i==0){esq_net[0] = prv; esq_net[1] = 2.0*x1-prv;}
      if(i==1){dir_net[0] = prv; dir_net[1] = 2.0*x1-prv;}
    }
//     VNo pac_n[tam];
//     divide_pacote_geral(d, pac, ex, pred, 0, pac_n);
//     x0 = pac_n[ctr-corr].fv;
//     x1 = pac_n[ctr].fv;
//     x2 = pac_n[ctr+corr].fv;
//     prv = pred( x0, x1, x2 );
//     esq_net[0] = prv; esq_net[1] = 2.0*x1-prv;
//     divide_pacote_geral(d, pac, ex, pred, 1, pac_n);
//     x0 = pac_n[ctr-corr].fv;
//     x1 = pac_n[ctr].fv;
//     x2 = pac_n[ctr+corr].fv;
//     prv = pred( x0, x1, x2 );
//     dir_net[0] = prv; dir_net[1] = 2.0*x1-prv;

//     filho_superfluo[qual] = adapta_arvore2( d, pac_fil, esq_net, dir_net, prof+1, niv, pred, fpoda_fil, eps);
//     pac[ctr].p->deletable = adapta_arvore2( d, pac_fil, esq_net, dir_net, prof+1, niv, pred, fpoda_fil, eps);
  }
  /* Elimina os filhos, se sao nao-nulos mas ambos superfluos: */
  bool_t fesq = /*pac[ctr].p->fil[0]==NULL ? FALSE : pac[ctr].p->fil[0]->deletable*/filho_superfluo[0]; 
  bool_t fdir = /*pac[ctr].p->fil[1]==NULL ? FALSE : pac[ctr].p->fil[1]->deletable*/filho_superfluo[1];
  if ((fesq && fdir) && prof>3)
  { 
    /*fprintf(stderr, "%*s\n", 2*profund, "+");*/
    /* Elimina os dois filhos: */
    free(pac[ctr].p->fil[0]); pac[ctr].p->fil[0] = NULL;
    free(pac[ctr].p->fil[1]); pac[ctr].p->fil[1] = NULL;
    /* torna o pai uma folha */
    pac[ctr].p->leaf = TRUE;
    pac[ctr].p->virtual_leaf = FALSE;
  }
//   else if(((prof+2)<=(niv-1)))
//   {
//     if((pac[ctr].p->fil[0]!=NULL))
//     {
//       assert((pac[ctr].p->fil[0]->fil[0]==NULL)==(pac[ctr].p->fil[0]->fil[1]==NULL));
//       if(((filho_superfluo[1]==FALSE) && (pac[ctr].p->fil[0]->fil[0]==NULL) ) /*&& profund>3*/)
//       {
//         /* fprintf(stderr, "%*s\n", 2*profund, "0"); */
//         pac[ctr].p->fil[0]->fil[0] = malloc(sizeof(No));
//         pac[ctr].p->fil[0]->fil[1] = malloc(sizeof(No));
//       
//         for(qual=0;qual<2;qual++)
//         {
//           int corr = pow(ord,ex);
//           pac[ctr].p->fil[0]->fil[qual]->fval = esq[qual];
//           pac[ctr].p->fil[0]->fil[qual]->leaf = FALSE;
//           pac[ctr].p->fil[0]->fil[qual]->virtual_leaf = TRUE;
//           pac[ctr].p->fil[0]->fil[qual]->deletable = TRUE;
//           pac[ctr].p->fil[0]->fil[qual]->fil[0] = NULL;
//           pac[ctr].p->fil[0]->fil[qual]->fil[1] = NULL;
//         }
//       }
//     }
//     if((pac[ctr].p->fil[1]!=NULL))
//     {
//       if(((filho_superfluo[0]==FALSE) && (pac[ctr].p->fil[1]->fil[0]==NULL)) /*&& profund>3*/)
//       {
//         /* fprintf(stderr, "%*s\n", 2*profund, "1"); */
//         pac[ctr].p->fil[1]->fil[0] = malloc(sizeof(No));
//         pac[ctr].p->fil[1]->fil[1] = malloc(sizeof(No));
//         for(qual=0;qual<2;qual++)
//         {
//           pac[ctr].p->fil[1]->fil[qual]->fval = dir[qual];
//           pac[ctr].p->fil[1]->fil[qual]->leaf = FALSE;
//           pac[ctr].p->fil[1]->fil[qual]->virtual_leaf = TRUE;
//           pac[ctr].p->fil[1]->fil[qual]->fil[0] = NULL;
//           pac[ctr].p->fil[1]->fil[qual]->fil[1] = NULL;
//         }
//       }
//     }
//   }
  /* Paranoia: */
  assert((pac[ctr].p->fil[0] == NULL) == (pac[ctr].p->fil[1] == NULL));
        
  /* Se {pac[ctr].p} tem filhos, nao e superfluo: */
  if (pac[ctr].p->fil[0] != NULL) { return FALSE; }

  /* Vale a pena manter a raiz? */
  double detalhe = fpoda - pac[ctr].fv;
  /* fprintf(stderr, "%*sdetalhe = %9.6f\n", 2*profund, "", detalhe); */
  double l = prof;
  double tol = pow(2.0,d*(l-(niv+1)))*eps;
  if ((fabs(detalhe) < tol) && (prof>=4))
  { /* O nó central é supérfluo: */
    /* fprintf(stderr, "%*ssuperfluo!\n", 2*profund, ""); */
    return TRUE;
  }
  else
  { /* O nó central precisa ser mantido: */
    /* fprintf(stderr, "%*simportante!\n", 2*profund, ""); */
    return FALSE;
  }
}