/* Copyright 2020 Christophe Crespelle */

/* This file is part of Coedit. */
/* Coedit 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 3 of the License, or (at your option) any later version. */
/* Coedit 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 Coedit.  If not, see <https://www.gnu.org/licenses/>. */


/**********************************************************************************
 * Name   : Coedit
 * Authors: Christophe Crespelle
 * Mail   : Christophe.Crespelle@inria.fr 
 * Purpose: Minimal cograph edition, completion and deletion of an arbitrary graph
 *********************************************************************************/


#include<stdio.h>
#include<limits.h>
#include<math.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <sys/time.h>

#include "semigraph_prelim.c"
#include "cotree_prelim.c"




/******************/
/* Default values */
/******************/




/********************/
/* Output functions */
/********************/

// print help
void usage(char *c){
  fprintf(stderr,"Usage: %s -h\n",c);
  fprintf(stderr,"Usage: %s -a\n",c);
  fprintf(stderr,"Usage: %s -d\n",c);
  fprintf(stderr,"Usage: %s -e\n",c);
//  fprintf(stderr,"Usage: %s -r number\n",c);
  fprintf(stderr,"Usage: %s -r\n",c);
  fprintf(stderr,"Usage: %s -o basename\n",c);
  fprintf(stderr,"  -h: print current help.\n");
  fprintf(stderr,"  -a: compute a minimal cograph completion of the input graph.\n");
  fprintf(stderr,"  -d: compute a minimal cograph deletion of the input graph.\n");
  fprintf(stderr,"  -e: compute a minimal cograph edition of the input graph.\n");
//  fprintf(stderr,"  -r: consider the vertices in a random order, use \"number\" different orders (and choose the best result).\n");
  fprintf(stderr,"  -r: consider the vertices in a random order.\n");
  fprintf(stderr,"  -ord filename: consider the vertices in the order given in the file named \"filename\".\n");
  fprintf(stderr,"  -pm: output modifications of the original graph (default is no).\n");
  fprintf(stderr,"  -v: verbose mode, includes a global report.\n");
  fprintf(stderr,"  -V: super verbose mode, also includes a short report for each vertex.\n");
  fprintf(stderr,"  -i filename: use file named \"filename\" as input (stdin by default).\n");
  fprintf(stderr,"  -o basename: output the results (edits and cotree) in two files named based on \"basename\" (both in stdout by default).\n");
  fprintf(stderr,"  -j basename: write report in a file named based on \"basename\" (stderr by default).\n");
  exit(-1);
}


/***************************/
/* Other utility functions */
/***************************/

int choose_node(int * list, int size) {
  if ((size==0) || (list==NULL))
	report_error("choose_node: empty list.");

  return list[rand_imp(size)];
  //debug : derandomize
  //return list[0];
}



/**************************************************************/
/**************************************************************/
/**************************************************************/
/***************************        ***************************/
/***************************  MAIN  ***************************/
/***************************        ***************************/
/**************************************************************/
/**************************************************************/
/**************************************************************/

int main (int argc, char **argv) {


///////////////////////////////////////////////////////////
//////////   DECLARATIONS AND DEFAULT VALUES   ////////////
///////////////////////////////////////////////////////////


  // DEBUGGING OPTIONS
  int debug = 0;  // 0: no debug; 1: debugging mode activated
  int consistency = 0;  // 0: no consistency check; 1: consistency check activated
  int iter_debut_check=2000000000;
  //int iter_debut_check=1301849;
  //int iter_debut_check=1205702;
  //int iter_debut_check=1161377;
  //int iter_debut_check=1147295;
  //int iter_debut_check=1147255;
  

  sgraph *G=NULL;              // input semigraph
  dyncotree *dynC=NULL;

  supinfo_edit *Info=NULL;

  int * permu_new=NULL;
  int * list_insert_nodes=NULL;
  int * list_nb_filled=NULL;
  int * list_nb_emptied=NULL;
  int nb_insert_nodes;
  unsigned long nb_min_editions;
  int insert_node;
  int nb_child_tobefilled;
  int min_modif_cost;
  int nb_add_edges;
  int nb_del_edges;
  //int nb_add_compare;
  //int nb_del_compare;
  int x;
  int is_complemented;
  

  int old_0=0;                  // beginning of the children at children[old_0], old_0=0 before renumbering if the user asks
  //time_t tstart=time(NULL);     // time the programm started
  //int *nb_edges=NULL;
  int i;
  //int k;
  //int l;

  long int tot_nb_modifs=0;
  long int tot_add_edges=0;
  long int tot_del_edges=0;

  //int * permu1=NULL;
  //int * pos1=NULL;

///////////////////////////////////////////////////////////
////////////////   PARSE COMMAND LINE   ///////////////////
///////////////////////////////////////////////////////////


  // default values
  FILE* forder=NULL;
  FILE* fin=stdin;
  FILE* fout_modifs=stdout;
  FILE* fout_cotree=stdout;
  FILE* freport=stderr;
  FILE* fpermu=stderr;
//  FILE *fin_cot=NULL;
  int input_file_given=0;
  int output_file_given=0;    // 0=NO; 1=YES;
  int journal_file_given=0;
  char* fname_order="";
  char* fname_in="";
  char* bname_out="";         // basename of the output file (if requested)
  char* bname_journal="";
  int modif_method=-1;       // modif_method: 0=delete; 1=add; 2=edit
  int order_method=0;     // order_method: 0=no reordering; 1=purely random; 2= given order file
//  int nb_repet=1;         // nb_repet: number of times the modification algorithm is run with a different order of the vertices

  int output_modifs=0;
  int verbose=0;
  int ask_modif=0;       // ask_method: a method of modification has already been asked in the list of options
  int ask_order=0;       // ask_order: a method for ordering the vertices has already been asked in the list of options

  // user's values
  for (i=1; i<argc; i++){
    if ((strcmp(argv[i],"-h")==0) || (strcmp(argv[i],"--help")==0) ) {
      usage(argv[0]);     
    }
    else if ((strcmp(argv[i],"-a")==0) || (strcmp(argv[i],"--add")==0)) {
      if (ask_modif)
	     report_error("Usage error: cannot ask two methods of modification.");
      modif_method=1;
      ask_modif=1;
    }
    else if ((strcmp(argv[i],"-d")==0) || (strcmp(argv[i],"--delete")==0)) {
      if (ask_modif)
	     report_error("Usage error: cannot ask two methods of modification.");
      modif_method=0;
      ask_modif=1;
    }
    else if ((strcmp(argv[i],"-e")==0) || (strcmp(argv[i],"--edit")==0)) {
      if (ask_modif)
	     report_error("Usage error: cannot ask two methods of modification.");
      modif_method=2;
      ask_modif=1;
    }
    else if ((strcmp(argv[i],"-r")==0) || (strcmp(argv[i],"--random")==0)){
      if (ask_order)
        report_error("Usage error: cannot ask two methods for ordering vertices.");
      ask_order=1;
      order_method=1;
/*
      if (i==argc-1)
	usage(argv[0]);
      ask_order=1;
      order_method=0;
      c=(char *)malloc((strlen(argv[++i])+1)*sizeof(char));
      strcpy(c,argv[i]);
      nb_repet=atoi(c);
      if (c!=NULL) free(c);
      if (nb_repet<=0)
	report_error("Usage error: number following option --random must be positive");
*/
    }
    else if ((strcmp(argv[i],"-ord")==0) || (strcmp(argv[i],"--vertices-order")==0)){
      if (ask_order)
        report_error("Usage error: cannot ask two methods for ordering vertices.");
      ask_order=1;
      order_method=2;
      if (i==argc-1)
	     usage(argv[0]);     
      fname_order=argv[++i];      
    }
    else if ((strcmp(argv[i],"-pm")==0) || (strcmp(argv[i],"--print-modifs")==0)){
      output_modifs=1;
    }
    else if ((strcmp(argv[i],"-v")==0) || (strcmp(argv[i],"--verbose")==0)){
      verbose=1;
    }
    else if ((strcmp(argv[i],"-V")==0) || (strcmp(argv[i],"--super-verbose")==0)){
      verbose=2;
    }
    else if ((strcmp(argv[i],"-i")==0) || (strcmp(argv[i],"--input")==0)){
      if (i==argc-1)
	     usage(argv[0]);     
      input_file_given=1;
      fname_in=argv[++i];      
    }
    else if ((strcmp(argv[i],"-o")==0) || (strcmp(argv[i],"--output")==0)){
      if (i==argc-1)
	     usage(argv[0]);     
      output_file_given=1;
      bname_out=argv[++i];      
    }
    else if ((strcmp(argv[i],"-j")==0) || (strcmp(argv[i],"--journal")==0)){
      if (i==argc-1)
        usage(argv[0]);     
      journal_file_given=1;
      bname_journal=argv[++i];      
    }
    else
      usage(argv[0]);
  }
  if (ask_modif==0) {
    fprintf(stderr,"Usage error: you must ask one method of modification.\n");
    usage(argv[0]);
  }








///////////////////////////////////////////////////////////
////////////////   OPEN INPUT/OUTPUT FILES   ////////////////////
///////////////////////////////////////////////////////////


  if (order_method==2) {
    forder=NULL;
    if ( (forder=fopen(fname_order,"r"))==NULL)
      report_error("fname_order -- fopen: error");
    if (verbose>=1) fprintf(stderr,"   vertices order read from file %s\n",fname_in);
  }


  if (input_file_given==1) {
    fin=NULL;
    if ( (fin=fopen(fname_in,"r"))==NULL)
      report_error("fname_in -- fopen: error");
    if (verbose>=1) fprintf(stderr,"   input read from file %s\n",fname_in);
  }


  if (output_file_given==1) {
      
    char* fname_modifs=NULL;
    char* fname_cotree=NULL;
    if( (fname_modifs=(char *)malloc((strlen(bname_out)+20)*sizeof(char))) == NULL )
      report_error("main: malloc() error");
    strcpy(fname_modifs,bname_out);
    if( (fname_cotree=(char *)malloc((strlen(bname_out)+20)*sizeof(char))) == NULL )
      report_error("main: malloc() error");
    strcpy(fname_cotree,bname_out);
    if (modif_method==0) {strcat(fname_modifs,"_dele"); strcat(fname_cotree,"_dele");}
    else if (modif_method==1) {strcat(fname_modifs,"_comp"); strcat(fname_cotree,"_comp");}
    else if (modif_method==2) {strcat(fname_modifs,"_edit"); strcat(fname_cotree,"_edit");}
    strcat(fname_modifs,"_modifs"); strcat(fname_cotree,"_cotree");
    
    if (output_modifs==1) {
      fout_modifs=NULL;
      if ( (fout_modifs=fopen(fname_modifs,"w"))==NULL)
        report_error("fname_modifs -- fopen: error");
      if (verbose>=1) fprintf(stderr,"   outputs list of modifications in file %s\n",fname_modifs);
      free(fname_modifs);
    }

    fout_cotree=NULL;
    if ( (fout_cotree=fopen(fname_cotree,"w"))==NULL)
      report_error("fname_cotree -- fopen: error");
    if (verbose>=1) fprintf(stderr,"   outputs cotree in file %s\n",fname_cotree);
    if (fname_modifs!=NULL) free(fname_cotree);
  }

  if (journal_file_given==1) {
    freport=NULL;
    fpermu=NULL;
    char* fname_journal=NULL;
    char* fname_permu=NULL;
    if( (fname_journal=(char *)malloc((strlen(bname_journal)+20)*sizeof(char))) == NULL )
      report_error("main: malloc() error");
    if( (fname_permu=(char *)malloc((strlen(bname_journal)+20)*sizeof(char))) == NULL )
      report_error("main: malloc() error");
    strcpy(fname_journal,bname_journal);
    if (modif_method==0) strcat(fname_journal,"_dele");
    else if (modif_method==1) strcat(fname_journal,"_comp");
    else if (modif_method==2) strcat(fname_journal,"_edit");
    strcpy(fname_permu,fname_journal);
    strcat(fname_journal,"_report");
    strcat(fname_permu,"_permut");

    if ( (freport=fopen(fname_journal,"w"))==NULL)
      report_error("fname_journal -- fopen: error");
    if (verbose>=1) fprintf(stderr,"   report written in file %s\n",fname_journal);
    if ( (fpermu=fopen(fname_permu,"w"))==NULL)
      report_error("fname_permu -- fopen: error");
    if (verbose>=1) fprintf(stderr,"   permutation of vertices written in file %s\n",fname_permu);
    free(fname_journal);
    free(fname_permu);
  }



  //debug
  FILE* fbug=NULL;
  FILE* fdync=NULL;
  FILE* fcot_restart=NULL;
  FILE* fsupinfo=NULL;
  char sup_name[100];
  char bug_name[100];
  char dync_name[100];
  char cot_restart_name[100];
  



// debug
  if (debug==1) {
    strcpy(bug_name,bname_journal);
    //strcat(bug_name,dicho);
    strcat(bug_name,"_debug_log");
    if ( (fbug=fopen(bug_name,"w"))==NULL )
      report_error("debug_log -- fopen: error");
  }
  else if (consistency==1) {
    strcpy(bug_name,bname_journal);
    //strcat(bug_name,dicho);
    strcat(bug_name,"_debug_log");
    if ( (fbug=fopen(bug_name,"w"))==NULL)
      report_error("debug_log -- fopen: error");
  }

  if (consistency==1) {
    strcpy(dync_name,bname_journal);
    //strcat(dync_name,dicho);
    strcat(dync_name,"_dync_consist");
    if ( (fdync=fopen(dync_name,"w"))==NULL)
      report_error("dync_consist -- fopen: error");
      
    strcpy(cot_restart_name,bname_journal);
    //strcat(cot_restart_name,dicho);
    strcat(cot_restart_name,"_cot_restart");
    if ( (fcot_restart=fopen(cot_restart_name,"w"))==NULL)
      report_error("cot_restart -- fopen: error");
  }

  if (debug==1) {
    strcpy(sup_name,bname_journal);
    strcat(sup_name,"_supinfo");
    if ( (fsupinfo=fopen(sup_name,"w"))==NULL )
      report_error("supinfo -- fopen: error");
   
  }




///////////////////////////////////////////////////////////
/////////////////   LOAD THE GRAPH   //////////////////////
///////////////////////////////////////////////////////////

  if (verbose>=1) fprintf(stderr,"Reading the graph...\n");
  G = sgraph_from_file(fin);
  fprintf(stderr,"%d vertices, %d edges in the graph.\n",G->n,G->m);
  fflush(stderr);

   if (input_file_given==1) {
    fclose(fin);
  }

  init_permu(G);









///////////////////////////////////////////////////////////
//////////   INITIALISE THE DATA STRUCTURE   //////////////
///////////////////////////////////////////////////////////



  // for all random choices in the algorithm: 1) ordering of vertices and 2) choice of insertion node at each incremental step 
  init_random();



  // reorder the vertices of the graph, if asked
  if (order_method==1) {
    if (verbose>=1) fprintf(freport,"Randomly reordering vertices...\n");
    // generate a new random permu and assign corresponding g->pos values
    permu_new=random_perm(G->permu,G->n);


    reorder_sgraph(G,permu_new);
    if (verbose>=1) fprintf(freport," ... reordered!\n\n");
    fflush(freport);
    if (permu_new!=NULL) free(permu_new);
  }
  else if (order_method==2) {
    if (verbose>=1) fprintf(freport,"Reordering vertices according to specified vertex file ...\n");
    if( (permu_new=(int *)malloc(G->n*sizeof(int))) == NULL )
      report_error("main: malloc() error with permu_new");
    read_order_from_file(forder,G->n,permu_new);
    reorder_sgraph(G,permu_new);
    if (verbose>=1) fprintf(freport," ... reordered!\n\n");
    fflush(freport);
    fclose(forder);
    if (permu_new!=NULL) free(permu_new);
  }


  // output the order used for the vertices
  fprintf(freport,"Order used for the vertices:\n");
  if (journal_file_given==1) {
    fprintf(freport,"   -> see file *_permut.\n");
    for (i=0;i<G->n;i++) fprintf(fpermu,"%d\n",G->permu[i]);
    fflush(fpermu);
  }
  else {
    for (i=0;i<G->n;i++) fprintf(freport,"%d\n",G->permu[i]);
    fflush(freport);
  }


  if (journal_file_given==1) {
    fclose(fpermu);
  }



  //////////////////  INIT DYNCOTREE  //////////////////
  
  if (verbose>=1) fprintf(freport,"\nInitialise dyncotree with 2 leaves...\n");  
  dynC=init_dyncotree_2leaves(G);
  if (verbose>=1) fprintf(freport," ... initialised!\n");
  fflush(freport);
  
  //////////////////////////////////////////////////////







  if (verbose>=1) fprintf(freport,"\nInitialise supinfo...\n");
  Info=init_supinfo_edit(dynC);
  if (verbose>=1) fprintf(freport," ... initialised!\n");
  fflush(freport);


  // IMPORTANT NOTE: x is the position of the incoming vertex in the semigraph G, new_x is the position of the incoming vertex in the dynamic cotree, which is shifted by +dync->n



///////////////////////////////////////////////////////////
/////////////   INCREMENTAL ALGORITHM   ///////////////////
///////////////////////////////////////////////////////////


  for (x=2; x<G->n;x++) {

    is_complemented=0;

    if (verbose>=2) fprintf(freport,"\nVertex %d incoming.\n",x);
    fflush(freport);    

    



///////////////////////////////////////////////////////////
///////   ASSIGN ADDITIONAL INFO ON THE TREE   ////////////

    assign_supinfo_edit(fdync,fsupinfo,consistency,debug,fbug,dynC, G, x, iter_debut_check, Info, modif_method);



///////////////////////////////////////////////////////////
////////////   FIND ALL INSERTION NODES   /////////////////

    if( (list_insert_nodes=(int *)malloc(dynC->n*sizeof(int))) == NULL )  // size dynC->n assume that leaves cannot be insertion nodes -> to be checked
      report_error("main: malloc() error with list_insert_nodes");


    if ((modif_method==0) || (modif_method==1)) {


      if ((modif_method==0) && (Info->nb_child_nh[dynC->root]!=0)) {
        complement_cot_info(dynC,Info);
        is_complemented=1;

      }


      list_minimum_insertion_nodes (dynC, Info, list_insert_nodes, &nb_insert_nodes, &min_modif_cost);
    


    }


    if (modif_method==2) {

      if( (list_nb_filled=(int *)malloc(dynC->n*sizeof(int))) == NULL )  // size dynC->n assume that leaves cannot be insertion nodes -> to be checked
      report_error("main: malloc() error with list_insert_nodes");

      if( (list_nb_emptied=(int *)malloc(dynC->n*sizeof(int))) == NULL )  // size dynC->n assume that leaves cannot be insertion nodes -> to be checked
      report_error("main: malloc() error with list_insert_nodes");


      list_minimum_editions (debug,x,fbug, dynC, Info, list_insert_nodes, list_nb_filled, list_nb_emptied, &nb_insert_nodes, &nb_min_editions, &min_modif_cost);



    }


    // pour edit compter séparément les ajouts et les retraits
    tot_nb_modifs += (long int) min_modif_cost;


    if (modif_method==2) if (verbose>=2) fprintf(freport,"Nb of min editions: %lu\n", nb_min_editions);
    if (verbose>=2) fprintf(freport,"Nb of min insertion nodes: %d\n", nb_insert_nodes);
    if (verbose>=2) fprintf(freport,"Minimum modification cost: %d\n", min_modif_cost);
    fflush(freport);



///////////////////////////////////////////////////////////
////////////   CHOOSE AN INSERTION NODE   /////////////////



    // CHOOSE AN INSERTION NODE AND A MINIMUM EDITION SETTLED AT IT

    if ((modif_method==0) || (modif_method==1)) {
      insert_node=choose_node(list_insert_nodes, nb_insert_nodes);
      nb_child_tobefilled=Info->nb_child_nh[insert_node];



      if (output_modifs==1) {print_added_edges(fout_modifs,dynC,insert_node,Info,G,x);


      }

      if (is_complemented) {
        complement_cot_info(dynC,Info);
        nb_child_tobefilled = dynC->nb_child[insert_node]-nb_child_tobefilled;


      }


    }


    if (modif_method==2) {

      choose_min_edition(dynC, list_insert_nodes, list_nb_filled, list_nb_emptied, nb_insert_nodes, nb_min_editions, &insert_node, &nb_child_tobefilled);


      if (output_modifs==1) {print_edits(fout_modifs, dynC, insert_node, nb_child_tobefilled, Info, G,x,&nb_add_edges,&nb_del_edges,output_modifs);}
      else {compute_del_add(dynC, Info, insert_node, nb_child_tobefilled, &nb_add_edges, &nb_del_edges);}


      tot_add_edges += (long int) nb_add_edges;
      tot_del_edges += (long int) nb_del_edges;

      if (verbose>=2) fprintf(freport,"Nb of added edges: %d\n", nb_add_edges);
      if (verbose>=2) fprintf(freport,"Nb of deleted edges: %d\n", nb_del_edges);
      fflush(freport);


    }


    clear_supinfo_edit(debug,fbug,x,Info,dynC);



///////////////////////////////////////////////////////////
///////   UPDATE THE COTREE UNDER INSERTION OF X   ////////


    // UPDATE THE COTREE UNDER INSERTION OF X
    

    update_under_insert(debug,fbug,x,dynC,insert_node,nb_child_tobefilled);


    if (list_insert_nodes!=NULL) free(list_insert_nodes);
    list_insert_nodes=NULL;

    if (list_nb_filled!=NULL) free(list_nb_filled);
    list_nb_filled=NULL;

    if (list_nb_emptied!=NULL) free(list_nb_emptied);
    list_nb_emptied=NULL;

  }



///////////////////////////////////////////////////////////
/////////////////   OUTPUT RESULTS   //////////////////////
///////////////////////////////////////////////////////////

  write_dyncotree_to_file(dynC, G, fout_cotree);


  if (verbose>=1) fprintf(freport,"\nLost space:\n%ld\n",lost_space);
  if (verbose>=1) fprintf(freport,"Nb tab truncated:\n%ld\n",tab_truncated);

  if (verbose>=1) fprintf(freport,"\nTime spent copying:\n%ld\n",copy_time);
  if (verbose>=1) fprintf(freport,"Nb tab expansion:\n%ld\n",tab_expansion);

  fprintf(freport,"\nTotal number of modifications:\n%ld\n",tot_nb_modifs);
  if (modif_method==2) {
    fprintf(freport,"Total number of added edges:\n%ld\n",tot_add_edges);
    fprintf(freport,"Total number of deleted edges:\n%ld\n",tot_del_edges);
  }
  fflush(freport);



///////////////////////////////////////////////////////////
////////////////////   FREE MEMORY   //////////////////////
///////////////////////////////////////////////////////////


  free_sgraph_old_start(G,old_0);

  free_dyncot(&dynC);

  free_supinfo_edit(Info);


  if (output_file_given==1) {
    fclose(fout_modifs);
    fclose(fout_cotree);
  }

  if (journal_file_given==1) {
    fclose(freport);
  }


  if (fbug!=NULL) fclose(fbug);
  
  return 0;
}

/**************************************************************/
/**************************************************************/
/*************************            *************************/
/*************************  FIN MAIN  *************************/
/*************************            *************************/
/**************************************************************/
/**************************************************************/