#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define DEPTH_FIRST           1
#define BREADTH_FIRST         2
#define BEST_FIRST            3

#define MAX_BRANCHING_NODES 10000

#include "defs.h"
#include "bnodelist.h"


void ReadInstructions (int argc, char *argv[], char *DataFile);

void LoadData (char *DataFile, ProblemData *pPD);

void CreateCurrentSolution (ProblemData *pPD, CurrentSolution *pCS);

void PrintSolution (CurrentSolution *pCS);

void DestroyData (ProblemData *pPD);

void DestroyCurrentSolution (CurrentSolution *pCS);

void ProcessBnode (Bnode *pta, ProblemData *pPD, CurrentSolution *pCS);

void DeriveBnode (Bnode *son, Bnode *father, int f);

boolean UsefulBnode (Bnode *temp, CurrentSolution *pCS);

Btree CreateBtree ();

void InsertBnode (Bnode *pta, Btree BT, int VisitStrategy);

Bnode *ExtractBnode (Btree BT);


int main(int argc, char  *argv[])
{
  char DataFile[RIGA];

  // inizio variabili per il branch and bound
  Btree BT;               // Albero di branching
  int VisitStrategy;
  long ExaminedNodes;     // Numero dei nodi di branching esaminati
  long GeneratedNodes;    // Numero dei nodi di branching generati
  ProblemData PD;         // Problem data
  CurrentSolution CS;     // Current solution found

  int id, f;
  Bnodepos pta, temp;     // Nodo corrente

  // fine variabili per il branch and bound


  ReadInstructions(argc,argv,DataFile);

  // Inizializzazione dei dati e allocazione delle strutture per la soluzione
  LoadData(DataFile,&PD);

  CreateCurrentSolution(&PD,&CS);

  // Creazione di un albero di branching vuoto
  BT = CreateBtree();
  VisitStrategy = DEPTH_FIRST;

  // Crea il nodo radice, che e' anche il nodo corrente
  pta = CreateBnode(1,0,1,&PD);

  // Elabora il problema corrente:
  // 1) determina bound, fissaggi, status del sottoproblema, ecc...
  // 2) determina le variabili per il futuro (eventuale) branching
  // 3) eventualmente aggiorna la soluzione
  ProcessBnode(pta,&PD,&CS);

  // Inserisce il nodo radice nella lista dei nodi aperti
  InsertBnode(pta,BT,VisitStrategy);


  id = 1;
  ExaminedNodes = 0;
  GeneratedNodes = 1;
  while ( !listavuota(BT) && (ExaminedNodes <= MAX_BRANCHING_NODES) )
  {
    // Estrae il prossimo nodo da elaborare
    pta = ExtractBnode(BT);

    // Decide se vale la pena di spezzare il problema corrente in sottoproblemi,
    // confrontando le sue informazioni locali con quelle globali (ad esempio soluzioni euristiche)
    if (UsefulBnode(pta,&CS))
    {
      // Genera i figli del nodo corrente, esplorando tutti i figli potenzialmente generabili
      // ma aggiungendo solo quelli che promettono soluzioni utili
      for (f = 1; f <= pta->branch.numfigli; f++)
      {
        // Crea un figlio identico al padre
        id++;
        temp = CreateBnode(id,pta->livello+1,f,&PD);

        // Modifica le informazioni copiate da padre a figlio, in modo da creare le info corrette per il figlio
        DeriveBnode(temp,pta,f);

        // Elabora il problema corrente
        ProcessBnode(temp,&PD,&CS);

        // Decide se vale la pena di spezzare il problema corrente in sottoproblemi,
        if (!UsefulBnode(temp,&CS))
          DestroyBnode(&temp);
        else
        {
          // Inserisce il nodo nella lista dei nodi ancora aperti
          InsertBnode(temp,BT,VisitStrategy);
          GeneratedNodes++;
        }
      }
    }

    DestroyBnode(&pta);
    ExaminedNodes++;

  }  // fine della ricerca

  if (!listavuota(BT))
    printf("Problema non risolto per eccesso di nodi!\n");
  else if (CS.status != YES_INSTANCE)
    printf("Problema privo di soluzione!\n");
  else
  {
    printf("Soluzione :\n");
    PrintSolution(&CS);
  }

  DestroyData(&PD);
  DestroyCurrentSolution(&CS);

  return EXIT_SUCCESS;
}


void ReadInstructions (int argc, char *argv[], char *DataFile)
{
  if (argc != 2)
  {
    printf("Command line format wrong!\n");
    exit(EXIT_WRONGCOMMANDLINE);
  }

  strcpy(DataFile,argv[1]);
}


void LoadData (char *DataFile, ProblemData *pPD)
{
  FILE *fDataFile;

  fDataFile = fopen(DataFile,"r");
  if (fDataFile == NULL)
  {
    printf("File %s does not exist!\n",DataFile);
    exit(EXIT_OPENFILE);
  }

  // Alloca le strutture per i dati e li carica dal file di ingresso

  fclose(fDataFile);
}


void CreateCurrentSolution (ProblemData *pPD, CurrentSolution *pCS)
{
  // Alloca e inizializza le strutture dati per rappresentare la miglior soluzione nota
  ...
}


void PrintSolution (CurrentSolution *pCS)
{
}


void DestroyData (ProblemData *pPD)
{
}


void DestroyCurrentSolution (CurrentSolution *pCS)
{
}


// Elabora il nodo:
// 1) Calcola le informazioni locali del problema (status, bound, ammissibilita', fissaggi, ecc...)
// 2) Determina le informazioni di branching (numero dei figli e come generarli)
// 3) Aggiorna le informazioni globali (miglior soluzione nota)
void ProcessBnode (Bnode *pta, ProblemData *pPD, CurrentSolution *pCS)
{
}


// Copia nel problema le informazioni del problema padre) in modo da trasformarlo
// nell'f-esimo problema figlio, sulla base delle informazioni di branching
void DeriveBnode (Bnode *son, Bnode *father, int f)
{
}


// Decide se occorra spezzare il problema in sottoproblemi o si puo' chiuderlo,
// in base allo status del problema e al confronto fra le sue informazioni locali
// e la soluzione globale.
// In problemi di ottimizzazione, di solito verifica se il problema ha un
// bound migliore della miglior soluzione euristica.
boolean UsefulBnode (Bnode *temp, CurrentSolution *pCS)
{
}


Btree CreateBtree ()
{
  return CreateBnodelist();
}


void InsertBnode (Bnode *pta, Btree BT, int VisitStrategy)
{
  if (VisitStrategy == DEPTH_FIRST)
  {
    inslista(pta,primolista(BT),BT);
  }
  else if (VisitStrategy == BREADTH_FIRST)
  {
    inslista(pta,succlista(ultimolista(BT),BT),BT);
  }
  else if (VisitStrategy == BEST_FIRST)
  {
    // Scorre la lista dei problemi aperti (ordinata per bound)
    // fino a trovare il primo problema peggiore di pta.
    // Inserisce pta prima di esso.
  }
}


Bnode *ExtractBnode (Btree BT)
{
  Bnodepos p = primolista(BT);
  return estraelista(&p,BT);
}