#define PROG_NAME "tmaze_ba_stats"
#define PROG_DESC "analysis of the Brasilia Airport maze"
#define PROG_VERS "1.0"

#define tmaze_ba_stats_C_COPYRIGHT \
  "Copyright © 2009 by the State University of Campinas (UNICAMP)"

/* Last edited on 2009-11-08 01:03:02 by stolfi */

#define PROG_HELP \
  "  " PROG_NAME " \\\n" \
  "    -size {NX} {NY} \\\n" \
  "    [ -topology { open | torus} } ] \\\n" \
  "    [ -seed {SEED} ] \\\n" \
  "    [ -plot {TILESIZE} ] \\\n" \
  "    [ -cells ] [ -grid ] \\\n" \
  "    [ -dump ] \\\n" \
  "    " argparser_help_info_HELP

#define PROG_INFO \
  "NAME\n" \
  "  " PROG_NAME " - " PROG_DESC "\n" \
  "\n" \
  "SYNOPSIS\n" \
  PROG_HELP "\n" \
  "\n" \
  "DESCRIPTION\n" \
  "  The program prints to standard output an" \
  " analysis of the components of a random instance" \
  " of the Brasilia Airport maze family.\n" \
  "\n" \
  "OPTIONS\n" \
  "  -size {NX} {NY}\n" \
  "    This mandatory parameter specifies the number of cell columns {NX} and" \
  " cell rows {NY} in the maze, respectively.\n" \
  "\n" \
  "  -topology { open | torus }\n" \
  "    This optional parameter specifies what happens at the edges of the" \
  " cell array.  The \"open\" option specifies that" \
  " paths cannot cross those edges, so that cells along them" \
  " have no neighbors.  The \"torus\"option specifies that" \
  " opposite edges of the maze are implicltly" \
  " connected with toroidal topology, so that" \
  " every cell has four neighbors.  The default is \"-topology open\".\n" \
  "\n" \
  "  -seed {SEED}\n" \
  "    This optional parameter specifies the (integer) seed for the random" \
  " number generator.  The default is \"-seed 0\".\n" \
  "\n" \
  "  -plot {CELLSIZE}\n" \
  "    This optional parameter requests an Encapsulated Postscript plot of the" \
  " graph, which is written to a file \"out/{NX}-{NY}-{SEED}.eps\". Each" \
  " cell will be plotted as a square with {CELLSIZE} by {CELLSIZE}" \
  " millimeters.\n" \
  "\n" \
  "  -cells\n" \
  "    This optional parameter requests that the cell backgrounds be painted.  The" \
  " default is to leave them transparent.\n" \
  "\n" \
  "  -grid\n" \
  "    This optional parameter requests that the cell outlines be stroked.  The" \
  " default is not to stroke the cell outlines.\n" \
  "\n" \
  "  -dump\n" \
  "    This optional parameter requests the dumping of the" \
  " maze's underlying graph to a file \"out/{NX}-{NY}-{SEED}.grf\".\n" \
  "\n" \
  "DOCUMENTATION OPTIONS\n" \
  argparser_help_info_HELP_INFO "\n" \
  "\n" \
  "SEE ALSO\n" \
  "  tmaze_bb_stats(1).\n" \
  "\n" \
  "AUTHOR\n" \
  "  Created 2009-01-15 by Jorge Stolfi, IC-UNICAMP.\n" \
  "\n" \
  "MODIFICATION HISTORY\n" \
  "  2009-02-04 [J.Stolfi] General renaming.\n" \
  "\n" \
  "WARRANTY\n" \
  argparser_help_info_NO_WARRANTY "\n" \
  "\n" \
  "RIGHTS\n" \
  "  " tmaze_ba_stats_C_COPYRIGHT ".\n" \
  "\n" \
  argparser_help_info_STANDARD_RIGHTS

#define _GNU_SOURCE
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>
#include <sys/stat.h>
#include <sys/types.h>

#include <bool.h>
#include <jsfile.h>
#include <argparser.h>

#include <tmaze_ba.h>
#include <tmaze_ba_graph.h>
#include <dgraph.h>

/* COMMAND-LINE OPTIONS */

typedef struct options_t
  { int nx;                /* Number of cell columns in maze. */
    int ny;                /* Number of cell rows in maze. */
    bool_t torus;          /* TRUE use toroidal topology. */
    int seed;              /* A string-valued argument. */
    double plot_cell_size; /* Size of each cell in plot (mm), or 0 if no plot. */
    bool_t plot_cells;     /* TRUE to paint the cell backgrounds. */
    bool_t plot_grid;      /* TRUE to stroke the cell outlines. */
    bool_t dump;           /* TRUE requests a dump of the graph. */
  } options_t;

options_t *parse_options(int argc, char **argv);
  /* Parses the command line arguments and packs them as an {options_t}. */

void show_options(options_t *o);
  /* Prints the options {o} to {stderr}. */

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

/* IMPLEMENTATIONS */

int main(int argc, char** argv)
  {
    options_t *o = parse_options(argc, argv);
    show_options(o);
    
    /* Create a random Brasilia Airport maze: */
    tmaze_t M = tmaze_ba_make(o->nx, o->ny, o->torus, o->seed);
    if ((M.nx <= 70) && (M.ny <= 70)) { tmaze_ba_print(stderr, &M); }
    
    dgraph_vertex_count_t nvC = M.nt;           /* Num of cell vertices. */
    dgraph_vertex_count_t nvWE = M.nxWE * M.ny; /* Num of vert joints. */
    dgraph_vertex_count_t nvSN = M.nx * M.nySN; /* Num of horz joints. */
    dgraph_vertex_count_t nvJ = nvWE + nvSN;    /* Num of joint vertices. */
    dgraph_vertex_count_t nv = nvC + nvJ;       /* Tot num of vertices. */
    fprintf(stderr, "total vertices = %d\n", nv);
    
    /* Make sure that directories exist: */
    mkdir("out", 0777);
    
    /* Plot the maze if so requested: */
    if (o->plot_cell_size > 0)
      { char *fig_name = NULL;
        char *fig_name = jsprintf("%06d-%06d-%010d", M.nx, M.ny, o->seed);
        tmaze_ba_plot_maze("out", fig_name, &M, o->plot_cells, o->plot_grid, o->plot_cell_size);
        free(fig_name);
      }
      
    /* Get its graph: */
    dgraph_t G = tmaze_ba_graph_make(&M);
    assert(G.rows == nv);
    assert(G.cols == nv);
    
    /* Dump the graph, if so requested: */
    if (o->dump) 
      { char *gfile_name = NULL;
        char *gfile_name = jsprintf("out/%06d-%06d-%010d.grf", M.nx, M.ny, o->seed);
        FILE *gfile = open_write(gfile_name, TRUE);
        dgraph_write(gfile, &G);
        fclose(gfile);
        free(gfile_name);
      }
    
    /* Get the connected components as a function of size: */
    dgraph_vertex_count_t mv;  /* Max center vertices in any component. */
    dgraph_vertex_count_t *ct; /* Count components by num of center vertices. */
    tmaze_ba_graph_count_components_by_size (&G, &M, &mv, &ct);
    
    /* Print the distribution: */
    dgraph_vertex_count_t max_size = 0;
    dgraph_vertex_count_t tot_size = 0;
    dgraph_vertex_count_t size;
    for (size = 0; size <= mv; size++)
      { if (ct[size] != 0)
          { tot_size += size*ct[size];
            max_size = size;
          }
        double exp_ct;  /* Statistically expected count. */
        if (size == 0) 
          { exp_ct = (1/16.0)*nvJ; /* Expected num of isolated joint vertices. */
          }
        else if (size == 1)
          { exp_ct = (1/64.0)*nvC; /* Expected num of 1-cell components. */
          }
        else if (size == 2)
          { exp_ct = (9/2048.0)*nvC; /* Expected num of 2-cell components. */
          }
        else if (size == 3)
          { exp_ct = (19/16384.0)*nvC; /* Expected num of 3-cell components. */
          }
        else
          { exp_ct = NAN; }
          
        if ((ct[size] != 0) || (! isnan(exp_ct)))
          { fprintf(stdout, "%9d %9d", size, ct[size]);
            if (! isnan(exp_ct)) { fprintf(stdout, " (%11.1f)", exp_ct); }
            fprintf(stdout, "\n"); 
          }
      }
    fprintf(stdout, "total cells = %d\n", tot_size);
    assert(tot_size == M.nt);
    fprintf(stdout, "max cells in component = %d\n", max_size);
    
    return 0;
  }
  
#define MIN_MAZE_SIZE (2)
#define MAX_MAZE_SIZE (65535)
  /* Maze size range in both dimensions. The minimum width and minimum
    height are defined as 2, since the graph of a 1-wide or 1-tall
    maze has parallel edges, which are not well-supported by the
    representation. */

#define MAX_SEED (1073741823L)

options_t *parse_options(int argc, char **argv)
  {
    /* Initialize argument parser: */
    argparser_t *pp = argparser_new(stderr, argc, argv);
    argparser_set_help(pp, PROG_NAME " version " PROG_VERS ", usage:\n" PROG_HELP);
    argparser_set_info(pp, PROG_INFO);
    argparser_process_help_info_options(pp);
    
    /* Allocate the command line argument record: */
    options_t *o = (options_t *)malloc(sizeof(options_t)); 
    
    /* Parse the keyword parameters: */
    
    argparser_get_keyword(pp, "-size");
    o->nx = argparser_get_next_int(pp, MIN_MAZE_SIZE, MAX_MAZE_SIZE);
    o->ny = argparser_get_next_int(pp, MIN_MAZE_SIZE, MAX_MAZE_SIZE);
    
    if (argparser_keyword_present(pp, "-topology"))
      { if (argparser_keyword_present_next(pp, "torus")) 
          { o->torus = TRUE; }
        else if (argparser_keyword_present_next(pp, "open"))
          { o->torus = FALSE; }
        else
          { argparser_error(pp, "unknown option"); }
      }
    else
      { o->torus = TRUE; }

    if (argparser_keyword_present(pp, "-seed"))
      { o->seed = argparser_get_next_int(pp, 0, MAX_SEED); }
    else
      { o->seed = 0; }

    if (argparser_keyword_present(pp, "-plot"))
      { o->plot_cell_size = argparser_get_next_double(pp, 0, 100.0); }
    else
      { o->plot_cell_size = 0; }

    o->dump = argparser_keyword_present(pp, "-dump");

    /* Parse the positional parameters: */
    
    argparser_skip_parsed(pp);
    
    /* Check for spurious arguments: */
    
    argparser_finish(pp);
    
    return o;
  }

void show_options(options_t *o)
  {
    fprintf(stderr, "-- command line arguments --------------------------------\n");
    fprintf(stderr, "maze dimensions = %d x %d\n", o->nx, o->ny);
    fprintf(stderr, "total cells = %d\n", o->nx * o->ny);
    char *topology_name[2] = { "open", "torus" };
    fprintf(stderr, "topology = %s\n", topology_name[o->torus]);
    fprintf(stderr, "seed = %d\n", o->seed);
    if (o->plot_cell_size > 0)
      { fprintf(stderr, "plot cell size = %.3f mm\n", o->plot_cell_size); }
    fprintf(stderr, "dump the graph = %c\n", "NY"[o->dump]);
    fprintf(stderr, "----------------------------------------------------------\n");
  }