/*
 * Copyright (c) 2005-2017 National Technology & Engineering Solutions
 * of Sandia, LLC (NTESS).  Under the terms of Contract DE-NA0003525 with
 * NTESS, the U.S. Government retains certain rights in this software.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 *
 *     * Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *
 *     * Redistributions in binary form must reproduce the above
 *       copyright notice, this list of conditions and the following
 *       disclaimer in the documentation and/or other materials provided
 *       with the distribution.
 *
 *     * Neither the name of NTESS nor the names of its
 *       contributors may be used to endorse or promote products derived
 *       from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 */

#include "smalloc.h" // for sfree, smalloc
#include "structs.h" // for vtx_data
#include <stdio.h>   // for fprintf, printf, FILE, NULL

/* Print metrics of partition quality. */

void countup_cube(struct vtx_data **graph,      /* graph data structure */
                  int               nvtxs,      /* number of vtxs in graph */
                  int *             assignment, /* set number of each vtx (length nvtxs+1) */
                  int               ndims,      /* number of cuts at each level */
                  int               ndims_tot,  /* total number of divisions of graph */
                  int               print_lev,  /* level of output */
                  FILE *            outfile,    /* output file if not NULL */
                  int               using_ewgts /* are edge weights being used? */
)
{
  double *hopsize;            /* number of hops for each set */
  double *cutsize;            /* number of cuts for each set */
  int *   setsize;            /* number of vtxs in each set */
  int *   setseen;            /* flags for sets adjacent to a particular set */
  int *   inorder;            /* list of vtxs in each set */
  int *   startptr;           /* indices into inorder array */
  double  ncuts;              /* total number of edges connecting sets */
  double  nhops;              /* total cuts weighted by hypercube hops */
  double  ewgt;               /* edge weight */
  int     nsets;              /* number of sets after a level */
  int     vtx;                /* vertex in graph */
  int     set, set2, set3;    /* sets neighboring vtxs are assigned to */
  int     onbdy;              /* counts number of neighboring set for a vtx */
  int     bdyvtxs;            /* sum of onbdy values for a set */
  int     internal;           /* number of internal nodes in a set */
  int     min_internal;       /* smallest number of internal vertices */
  int     max_internal;       /* largest number of internal vertices */
  int     total_internal;     /* total number of internal vertices */
  int     min_size, max_size; /* smallest and largest set sizes */
  int     tot_size;           /* total of all set sizes */
  double  bdyvtx_hops;        /* bdyvtxs weighted by wire lengths */
  double  bdyvtx_hops_tot;    /* total bdyvtx_hops */
  double  bdyvtx_hops_max;    /* largest value of bdyvtx_hops among all sets */
  double  bdyvtx_hops_min;    /* smallest value of bdyvtx_hops among all sets */
  int     neighbor_sets;      /* number of neighboring sets for a set */
  double  total_bdyvtxs;      /* sum of all onbdy values in whole graph  */
  int     total_neighbors;    /* number of neighboring sets in graph */
  double  maxcuts;            /* largest cuts among all processors */
  double  mincuts;            /* smallest cuts among all processors */
  double  maxhops;            /* largest hops among all processors */
  double  minhops;            /* smallest hops among all processors */
  double  maxbdy;             /* largest bdy_vtxs among all processors */
  double  minbdy;             /* smallest bdy_vtxs among all processors */
  int     maxneighbors;       /* largest neighbor_sets among all processors */
  int     minneighbors;       /* smallest neighbor_sets among all processors */
  int     neighbor;           /* neighbor of a vertex */
  int     mask;               /* mask for active bits */
  int     bits;               /* bit pattern for counting hops */
  int     start_dims;         /* starting dimension for output loop */
  int     level;              /* recursion level of partition */
  int     print2file;         /* should I print to a file? */
  int     i, j, k, l, ll;     /* loop counters */
  int     abs();

  print2file = (outfile != NULL);
  ewgt       = 1;

  nsets   = (1 << ndims_tot);
  cutsize = smalloc(nsets * sizeof(double));
  hopsize = smalloc(nsets * sizeof(double));
  setsize = smalloc(nsets * sizeof(int));

  setseen  = smalloc(nsets * sizeof(int));
  startptr = smalloc((nsets + 1) * sizeof(int));
  inorder  = smalloc(nvtxs * sizeof(int));
  for (j = 0; j < nsets; j++) {
    setsize[j] = 0;
  }
  for (i = 1; i <= nvtxs; i++) {
    ++setsize[assignment[i]];
  }

  /* Modify setsize to become index into vertex list. */
  for (j = 1; j < nsets; j++) {
    setsize[j] += setsize[j - 1];
  }
  for (j = nsets - 1; j > 0; j--) {
    startptr[j] = setsize[j] = setsize[j - 1];
  }
  startptr[0] = setsize[0] = 0;
  startptr[nsets]          = nvtxs;
  for (i = 1; i <= nvtxs; i++) {
    set                   = assignment[i];
    inorder[setsize[set]] = i;
    setsize[set]++;
  }

  if (abs(print_lev) > 1) { /* Print data from all levels of recursion. */
    start_dims = ndims;
    level      = 0;
  }
  else { /* Only print data from final level. */
    start_dims = ndims_tot;
    level      = (ndims_tot + ndims - 1) / ndims - 1;
  }
  k = start_dims;
  while (k <= ndims_tot) {
    level++;
    nsets = (1 << k);
    for (j = 0; j < nsets; j++) {
      cutsize[j] = 0;
      hopsize[j] = 0;
      setsize[j] = 0;
    }
    mask = 0;
    for (j = 0; j < k; j++) {
      mask = (mask << 1) + 1;
    }

    for (i = 1; i <= nvtxs; i++) {
      set = assignment[i] & mask;
      setsize[set] += graph[i]->vwgt;
      for (j = 1; j < graph[i]->nedges; j++) {
        neighbor = graph[i]->edges[j];
        set2     = assignment[neighbor] & mask;
        if (set != set2) {
          if (using_ewgts) {
            ewgt = graph[i]->ewgts[j];
          }
          cutsize[set] += ewgt;
          bits = set ^ set2;
          for (l = bits; l; l >>= 1) {
            if (l & 1) {
              hopsize[set] += ewgt;
            }
          }
        }
      }
    }

    tot_size = 0;
    max_size = 0;
    for (set = 0; set < nsets; set++) {
      tot_size += setsize[set];
      if (setsize[set] > max_size) {
        max_size = setsize[set];
      }
    }

    min_size = max_size;
    for (set = 0; set < nsets; set++) {
      if (setsize[set] < min_size) {
        min_size = setsize[set];
      }
    }

    ncuts = nhops = 0;
    total_bdyvtxs = total_neighbors = 0;
    bdyvtx_hops_tot = bdyvtx_hops_max = bdyvtx_hops_min = 0;
    maxcuts = mincuts = 0;
    maxhops = minhops = 0;
    total_internal    = 0;
    min_internal      = max_size;
    max_internal      = 0;
    maxbdy = minbdy = 0;
    maxneighbors = minneighbors = 0;

    printf("\nAfter level %d  (nsets = %d):\n", level, nsets);
    if (print2file) {
      fprintf(outfile, "\nAfter level %d  (nsets = %d):\n", level, nsets);
    }
    if (print_lev < 0) {
      printf("    set    size      cuts       hops   bndy_vtxs    adj_sets\n");
      if (print2file) {
        fprintf(outfile, "    set    size      cuts       hops   bndy_vtxs    adj_sets\n");
      }
    }
    for (set = 0; set < nsets; set++) {
      internal = setsize[set];
      for (i = 0; i < nsets; i++) {
        setseen[i] = 0;
      }
      /* Compute number of set neighbors, and number of vtxs on boundary. */
      /* Loop through multiple assignments defining current set. */
      bdyvtxs     = 0;
      bdyvtx_hops = 0;
      for (l = 0; l < (1 << (ndims_tot - k)); l++) {
        set2 = (l << k) + set;
        for (i = startptr[set2]; i < startptr[set2 + 1]; i++) {
          onbdy = 0;
          vtx   = inorder[i];
          for (j = 1; j < graph[vtx]->nedges; j++) {
            neighbor = graph[vtx]->edges[j];
            set3     = assignment[neighbor] & mask;
            if (set3 != set) { /* Is vtx on boundary? */
              /* Has this neighboring set been seen already? */
              if (setseen[set3] >= 0) {
                bits = set ^ set3;
                for (ll = bits; ll; ll >>= 1) {
                  if (ll & 1) {
                    ++bdyvtx_hops;
                  }
                }
                ++onbdy;
                setseen[set3] = -setseen[set3] - 1;
              }
            }
          }
          /* Now reset all the setseen values to be positive. */
          if (onbdy != 0) {
            for (j = 1; j < graph[vtx]->nedges; j++) {
              neighbor = graph[vtx]->edges[j];
              set3     = assignment[neighbor] & mask;
              if (setseen[set3] < 0) {
                setseen[set3] = -setseen[set3];
              }
            }
            internal -= graph[vtx]->vwgt;
          }
          bdyvtxs += onbdy;
        }
      }

      total_internal += internal;
      bdyvtx_hops_tot += bdyvtx_hops;
      if (bdyvtx_hops > bdyvtx_hops_max) {
        bdyvtx_hops_max = bdyvtx_hops;
      }
      if (set == 0 || bdyvtx_hops < bdyvtx_hops_min) {
        bdyvtx_hops_min = bdyvtx_hops;
      }
      if (internal > max_internal) {
        max_internal = internal;
      }
      if (set == 0 || internal < min_internal) {
        min_internal = internal;
      }

      /* Now count up the number of neighboring sets. */
      neighbor_sets = 0;
      for (i = 0; i < nsets; i++) {
        if (setseen[i] != 0) {
          ++neighbor_sets;
        }
      }

      if (print_lev < 0) {
        printf(" %5d    %5d    %6g     %6g   %6d      %6d\n", set, setsize[set], cutsize[set],
               hopsize[set], bdyvtxs, neighbor_sets);
        if (print2file) {
          fprintf(outfile, " %5d    %5d    %6g     %6g   %6d      %6d\n", set, setsize[set],
                  cutsize[set], hopsize[set], bdyvtxs, neighbor_sets);
        }
      }
      if (cutsize[set] > maxcuts) {
        maxcuts = cutsize[set];
      }
      if (set == 0 || cutsize[set] < mincuts) {
        mincuts = cutsize[set];
      }
      if (hopsize[set] > maxhops) {
        maxhops = hopsize[set];
      }
      if (set == 0 || hopsize[set] < minhops) {
        minhops = hopsize[set];
      }
      if (bdyvtxs > maxbdy) {
        maxbdy = bdyvtxs;
      }
      if (set == 0 || bdyvtxs < minbdy) {
        minbdy = bdyvtxs;
      }
      if (neighbor_sets > maxneighbors) {
        maxneighbors = neighbor_sets;
      }
      if (set == 0 || neighbor_sets < minneighbors) {
        minneighbors = neighbor_sets;
      }
      ncuts += cutsize[set];
      nhops += hopsize[set];
      total_bdyvtxs += bdyvtxs;
      total_neighbors += neighbor_sets;
    }
    ncuts /= 2;
    nhops /= 2;

    printf("\n");
    printf("                            Total      Max/Set      Min/Set\n");
    printf("                            -----      -------      -------\n");
    printf("Set Size:             %11d  %11d  %11d\n", tot_size, max_size, min_size);
    printf("Edge Cuts:            %11g  %11g  %11g\n", ncuts, maxcuts, mincuts);
    printf("Hypercube Hops:       %11g  %11g  %11g\n", nhops, maxhops, minhops);
    printf("Boundary Vertices:    %11g  %11g  %11g\n", total_bdyvtxs, maxbdy, minbdy);
    printf("Boundary Vertex Hops: %11g  %11g  %11g\n", bdyvtx_hops_tot, bdyvtx_hops_max,
           bdyvtx_hops_min);
    printf("Adjacent Sets:        %11d  %11d  %11d\n", total_neighbors, maxneighbors, minneighbors);
    printf("Internal Vertices:    %11d  %11d  %11d\n\n", total_internal, max_internal,
           min_internal);

    if (print2file) {
      fprintf(outfile, "\n");
      fprintf(outfile, "                            Total      Max/Set      Min/Set\n");
      fprintf(outfile, "                            -----      -------      -------\n");
      fprintf(outfile, "Set Size:             %11d  %11d  %11d\n", tot_size, max_size, min_size);
      fprintf(outfile, "Edge Cuts:            %11g  %11g  %11g\n", ncuts, maxcuts, mincuts);
      fprintf(outfile, "Hypercube Hops:       %11g  %11g  %11g\n", nhops, maxhops, minhops);
      fprintf(outfile, "Boundary Vertices:    %11g  %11g  %11g\n", total_bdyvtxs, maxbdy, minbdy);
      fprintf(outfile, "Boundary Vertex Hops: %11g  %11g  %11g\n", bdyvtx_hops_tot, bdyvtx_hops_max,
              bdyvtx_hops_min);
      fprintf(outfile, "Adjacent Sets:        %11d  %11d  %11d\n", total_neighbors, maxneighbors,
              minneighbors);
      fprintf(outfile, "Internal Vertices:    %11d  %11d  %11d\n\n", total_internal, max_internal,
              min_internal);
    }

    if (k == ndims_tot) {
      k++;
    }
    else {
      k += ndims;
      if (k > ndims_tot) {
        k = ndims_tot;
      }
    }
  }

  sfree(cutsize);
  sfree(hopsize);
  sfree(setsize);
  sfree(setseen);
  sfree(startptr);
  sfree(inorder);
}
