/**
 *  Versão 3.0 - (10/06)
 *  - código limpo e mensagens na tela.
 *  - alocação dinâmica (usando malloc e calloc).
 *  - tipos genericos, definidos nos defines
 *  - calcula o tempo gasto para resolver o algoritmo e
 *     para resolver o algoritmo mais o tempo gasto com
 *     alocação dinâmica e inicializações .
 */

#include <stdio.h>
#include <stdlib.h>
#include <sys/times.h>
#include "util.h"
#include "draw.h"

// tamanhos dos vetores
#define MAX_LARG    200
#define NCOMBLIN     70
#define NL NCOMBLIN*NCOMBLIN*NCOMBLIN*NCOMBLIN

// Variáveis globais
ponto l, w;             // lados do retângulo

ponto nCombLin;         // número de combinações lineares de l's e w's

ponto *combLin;         // vetor de combinações lineares de l's e w's.

ponto *iCombLin;        // indices do vetor combLin das combinações lineares.
                        // Seja n a combinação linear. Então iCombLin[n] é o indice
                        //   do vetor combLin que está n.
                        // Ou seja, combLin[ iCombLin [ n ] ] = n

/*
qtde *nRet;             // no paper está como v*(L)
                        // números de retângulos (l, w) que entram em um dado L

flag *solucao;          // no paper está como k*(L)
                        // indica a solução adotada
                        //  -1  -> não resolvido ainda
                        //   0  -> resolvido com packing homogêneo
                        // 1..7 -> resolvido usando a subdivisão B1,..,B7, respect.

ponto **ptoDiv;         // no paper está como i_k*(L)
                        // ponto de divisão, se usado alguma subdivisão,
                        //   i.e., k*(L) = {1,..,7}
*/


int *ptoDiv;
short *solNRet;

const int ptoDiv1 = 1023;
const int ptoDiv2 = 1047552;
const int ptoDiv3 = 1072693248;

const short nRet = 127;
const short solucao = 896; 
const short descSol = 7;
const short descPtoDiv2 = 10;
const short descPtoDiv3 = 20;

// Variáveis locais
qtde resp;              // resposta do algoritmo

// protótipos das funções
void dividir( ponto *i, ponto *q, ponto *q1, ponto *q2, void (*func)( ponto*, ponto*, ponto*, ponto* ) );
void dividirL( indice L, ponto *q, ponto *lim, flag B, void (*func)( ponto*, ponto*, ponto*, ponto* ) );
void dividirR( indice L, ponto *q, flag indicador, void (*func)( ponto*, ponto*, ponto*, ponto* ) );

void Solve( indice L, ponto *q );
void L_Algorithm( ponto *q );

/*******************************************************************

  As funções abaixo (dividir, dividirL, dividirR) servem para dividir
  um L, com todas as alternativas possíveis.
  
*******************************************************************/

/**
 * divide um L, segundo uma subdivisão e normaliza essas duas novas peças
 */
void dividir( ponto *i, ponto *q, ponto *q1, ponto *q2, void (*func)( ponto*, ponto*, ponto*, ponto* ) ) {

  // deixa na posição padrão
  (*func)( i, q, q1, q2 );
  
  // normaliza os L's
  normalizar( q1 );
  normalizar( q2 );
}

/**
 *  Faz todas as divisões de um L, segundo cada subdivisão Bk
 */
void dividirL( indice L, ponto *q, ponto *lim, flag B, void (*func)( ponto*, ponto*, ponto*, ponto* ) ) {
  int i, j;
  ponto i_k[2]; // ponto de divisão
  indice L1, L2; // novos L's formados com a divisão no ponto i_k
  ponto q1[4], q2[4];
  
  // limites para cada divisão
  for( i_k[0]=lim[0], i=iCombLin[ i_k[0] ]; i_k[0]<=lim[1]; i_k[0]=combLin[++i] )
    for( i_k[1]=lim[2], j=iCombLin[ i_k[1] ]; i_k[1]<=lim[3]; i_k[1]=combLin[++j] ) {
      
      // função usada para divisão
      dividir( i_k, q, q1, q2, (*func) );
      
      if( q1[0]<0 || q2[0]<0 ) continue;
      
      L1 = q2i( q1[0], q1[1], q1[2], q1[3] ); L2 = q2i( q2[0], q2[1], q2[2], q2[3] );
      
      // verifica se a soma do limite superior dos 2 novos L's
      //   é maior que o L original (L pai)
      if( L_lim_sup(q1)+L_lim_sup(q2) > (solNRet[L] & nRet) ) {
        Solve(L1,q1); Solve(L2,q2);
        
        // verifica se a soma do número de retângulos dos 2 novos L's
        //   é maior q o L original (L pai)
        if( ((solNRet[L1]+solNRet[L2]) & nRet) > (solNRet[L] & nRet) ) {
          solNRet[L] = ((solNRet[L1]+solNRet[L2]) & nRet) | (B << descSol);               // divisão usada
          ptoDiv[L] = i_k[0] | (i_k[1] << descPtoDiv2);
        }
      }
    }
}


/**
 *  Faz todas as divisões de um R, segundo cada subdivisão Bk
 */
void dividirR( indice L, ponto *q, flag indicador, void (*func)( ponto*, ponto*, ponto*, ponto* ) ) {
  int i, j, k; // indices do vetor de combinacoes lineares
  ponto i_k[3]; // ponto de divisão
  indice L1, L2; // novos L's formados com a divisão no ponto i
  ponto q1[4], q2[4];
  
  // limites para cada divisão
  for( i_k[0]=0, i=iCombLin[ i_k[0] ]; i_k[0]<=q[0]; i_k[0]=combLin[++i] )
    for( i_k[1]=0, j=iCombLin[ i_k[1] ]; i_k[1]<=q[1]; i_k[1]=combLin[++j] )
      for( i_k[2]=i_k[indicador], k=iCombLin[ i_k[2] ]; i_k[2]<=q[indicador]; i_k[2]=combLin[++k] ) {
        
        if( i_k[0]==0 && i_k[1]==0 ) continue;
        
        // função usada para divisão
        dividir( i_k, q, q1, q2, (*func) );
        
        if( q1[0]<0 || q2[0]<0 )  continue;
        
        L1 = q2i( q1[0], q1[1], q1[2], q1[3] ); L2 = q2i( q2[0], q2[1], q2[2], q2[3] );
        
        // verifica se a soma do limite superior dos 2 novos L's
        //   é maior que o R original (R pai)
        if( L_lim_sup( q1 )+L_lim_sup( q2 ) > (solNRet[L] & nRet) ) {
          Solve(L1,q1); Solve(L2,q2);
          
          // verifica se a soma do número de retângulos dos 2 novos L's
          //   é maior q o R original (R pai)
          if( ((solNRet[L1]+solNRet[L2]) & nRet) > (solNRet[L] & nRet) ) {
            solNRet[L] = ((solNRet[L1]+solNRet[L2]) & nRet) | (((indicador==0) ? B6 : B7) << descSol); // divisão usada
            ptoDiv[L] = i_k[0] | (i_k[1] << descPtoDiv2) | (i_k[2] << descPtoDiv3);
          }
        }
      }
}


/*******************************************************************

  As funções abaixo (Solve e L_Algorithm) são as principais
  do programa. O algoritmo é resolvido de forma recursiva.
  
*******************************************************************/


/**
 *  função recursiva
 */
void Solve( indice L, ponto *q ) {
  
  if( (solNRet[ L ] & nRet) == 0 ) {
    
    // L não degenerado
    if( q[0]!=q[2] ) {
      
      solNRet[ L ] = L_lim_inf( q ) | (HOMOGENEO << descSol);

      // Verifica se pode ser resolvido com packing homogeneo
      if( (solNRet[ L ] & nRet) != L_lim_sup( q ) )
      // tenta para cada subdivisão B1,..,B5
      {
        ponto lim[4];
        
        // 0 <= x' <= x  e  0 <= y' <= y
        lim[0]=0; lim[1]=q[2]; lim[2]=0; lim[3]=q[3];
        dividirL( L, q, lim, B1, posicaoPadraoB1 );
        dividirL( L, q, lim, B3, posicaoPadraoB3 );
        dividirL( L, q, lim, B5, posicaoPadraoB5 );
        
        // 0 <= x' <= x  e  y <= y' <= Y
        lim[0]=0; lim[1]=q[2]; lim[2]=q[3]; lim[3]=q[1];
        dividirL( L, q, lim, B2, posicaoPadraoB2 );
        
        // x <= x' <= X  e  0 <= y' <= y
        lim[0]=q[2]; lim[1]=q[0]; lim[2]=0; lim[3]=q[3];
        dividirL( L, q, lim, B4, posicaoPadraoB4 );
      }
    }
    
    // L degenerado (R)
    else {  // q[0]==q[2]  <=>  q[1]==q[3]
      solNRet[ L ] = R_lim_inf( q[0], q[1] ) | (HOMOGENEO << descSol);

      // Verifica se pode ser resolvido com packing homogeneo
      if( (solNRet[ L ] & nRet) != R_lim_sup( q[0], q[1] ) )
      // tenta para cada subdivisão B6, B7
      {
        dividirR( L, q, 0, posicaoPadraoB6 );
        dividirR( L, q, 1, posicaoPadraoB7 );
      }
    }
  }
}

/**
 *  Inicialização do vetor solução e chamada da função recursiva Solve()
 */
void L_Algorithm( ponto *q ) {
  indice L;
  int i;
  int nL = nCombLin*nCombLin*nCombLin*nCombLin;
  struct tms starttime, currenttime;

  L = q2i( q[0], q[1], q[2], q[3] );

  printf("Alocando o vetor ptoDiv... ");
  ptoDiv = (ponto*) malloc( nL*sizeof( ponto ) );
  if( ptoDiv == NULL ) {
    printf("\nErro de alocacao de memoria\n");
    exit(0);
  }
  printf("OK.\n");

  printf("Alocando o vetor nRet... ");
  solNRet = (qtde*) malloc( nL*sizeof( qtde ) );
  if( solNRet == NULL ) {
    printf("\nErro de alocacao de memoria\n");
    exit(0);
  }
  printf("OK.\n");
  
  for( i=0; i<nL; i++ ) solNRet[i] = 0;

  printf("Entrando no Solve...\n\n");
  times(&starttime);
  Solve( L, q );
  times(&currenttime);

  printf("Tempo do Solve : %gs.\n", (double)( currenttime.tms_utime - starttime.tms_utime )/60 );

  resp = solNRet[L] & nRet;
  
  times(&starttime);
  Draw( L, q );
  times(&currenttime);

  printf("Tempo do Draw  : %gs.\n", (double)( currenttime.tms_utime - starttime.tms_utime )/60 );

  free( ptoDiv );
  free( solNRet );
}


/**
 *  função principal, onde contém as inicializações de algumas variáveis.
 */
int main() {
  int i, j;
  ponto q[4];
  ponto l_gde, w_gde; // dimensões do retângulo maior (palete)
  struct tms starttime, currenttime;
  
  //printf ("Digite L e W: "); scanf("%hi %hi", &l_gde, &w_gde);
  //printf ("Digite l e w: "); scanf("%hi %hi", &l, &w);
  printf ("Digite L e W: "); scanf("%d %d", &l_gde, &w_gde);
  printf ("Digite l e w: "); scanf("%d %d", &l, &w);

  printf("\nAlocando vetor iCombLin... ");
  iCombLin = (ponto*) malloc( (l_gde+2) * sizeof( ponto ) );
  if( iCombLin == NULL ) {
    printf("\nErro de alocacao de memoria\n");
    exit(0);
  }
  printf("OK.\n");

  times(&starttime);

  // ===================================
  //  Combinações lineares de l's e w's 
  // ===================================
  
  // inicializacao do vetor de indices de combinacoes lineares
  for( i=0; i<=l_gde; i++ )  iCombLin[i]=FALSE;
  
  // se j eh combinacao linear de l e w, entao marca como TRUE.
  // ordem da combinacao:
  //   0, w, 2w,.., l, l+w, l+2w,.., 2l, 2l+w, 2l+2w,..., nl+mw

  printf("Fazendo as combinações lineares... ");
  i=0;
  while( 1 ) {
    for( j=i*l; j<=l_gde; j+=w )
      iCombLin[j] = TRUE;     // é combinação
    if( i++*l>l_gde ) break;  // acabou as combinacoes lineares
  }
  printf("OK.\n");

  printf("Alocando vetor combLin... ");
  combLin = (ponto*) malloc( (l_gde+2) * sizeof( ponto ) );
  if( combLin == NULL ) {
    printf("\nErro de alocacao de memoria\n");
    exit(0);
  }
  printf("OK.\n");

  // =========================================
  //  arrumando os vetores combLin e iCombLin
  // =========================================
  printf("Arrumando o vetor de indices e de combinações lineares... ");
  nCombLin=0;
  for( i=0; i<=l_gde; i++ ) {
    
    if( iCombLin[i] ) {
      combLin[nCombLin] = i;
      iCombLin[i] = nCombLin;
      nCombLin++;
    }
    else iCombLin[i] = iCombLin[i-1];
  }
  
  // marcando o final do vetor
  iCombLin[l_gde+1] = iCombLin[l_gde]+1;
  combLin[nCombLin] = l_gde+1;
  printf("OK.\n");

  l_gde = fechaEmZ( l_gde );
  w_gde = fechaEmZ( w_gde );

  q[0] = l_gde;
  q[1] = w_gde;
  q[2] = l_gde;
  q[3] = w_gde;

  printf("Entrando no algoritmo...\n");
  L_Algorithm( q );

  times(&currenttime);
  
  printf("Tempo algoritmo: %gs.\n", (double)( currenttime.tms_utime - starttime.tms_utime )/60 );
  printf("\nNumero de retangulos: %i\n\n", resp);

  free( combLin );
  free( iCombLin );
  
  return 0;
}