/*
 * Copyright 1997, Regents of the University of Minnesota
 *
 * selectq.c
 *
 * This file contains the driving routines for multilevel k-way refinement
 *
 * Started 7/28/97
 * George
 *
 * $Id: selectq.c 10542 2011-07-11 16:56:22Z karypis $
 */

#include <parmetislib.h>

/*************************************************************************/
/*! This stuff is hardcoded for up to four constraints 
*/
/*************************************************************************/
void Mc_DynamicSelectQueue(ctrl_t *ctrl, idx_t nqueues, idx_t ncon, idx_t subdomain1, 
         idx_t subdomain2, idx_t *currentq, real_t *flows, idx_t *from, idx_t *qnum, 
         idx_t minval, real_t avgvwgt, real_t maxdiff)
{
  idx_t i, j;
  idx_t hash, index = -1, current;
  idx_t *cand, *rank, *dont_cares;
  idx_t nperms, perm[24][5];
  real_t sign = 0.0;
  rkv_t *array;
  idx_t mype;
  gkMPI_Comm_rank(MPI_COMM_WORLD, &mype);

  WCOREPUSH;

  *qnum = -1;

  /* allocate memory */
  cand       = iwspacemalloc(ctrl, ncon);
  rank       = iwspacemalloc(ctrl, ncon);
  dont_cares = iwspacemalloc(ctrl, ncon);
  array      = rkvwspacemalloc(ctrl, ncon);

  if (*from == -1) {
    for (i=0; i<ncon; i++) {
      array[i].key = fabs(flows[i]);
      array[i].val = i;
    }

    /* GKTODO - Need to check the correct direction of the sort */
    rkvsorti(ncon, array);

    /* GKTODO - The following assert was disabled as it was failing. Need
                to check if it is a valid assert */
    /*ASSERT(array[ncon-1].key - array[0].key <= maxdiff) */

    if (flows[array[ncon-1].val] > avgvwgt*MOC_GD_GRANULARITY_FACTOR) {
      *from = subdomain1;
      sign  = 1.0;
      index = 0;
    }

    if (flows[array[ncon-1].val] < -1.0*avgvwgt*MOC_GD_GRANULARITY_FACTOR) {
      *from = subdomain2;
      sign  = -1.0;
      index = nqueues;
    }

    if (*from == -1) 
      goto DONE;
  }
  else {
    ASSERT(*from == subdomain1 || *from == subdomain2);

    if (*from == subdomain1) {
      sign  = 1.0;
      index = 0;
    }
    else {
      sign  = -1.0;
      index = nqueues;
    }
  }

  for (i=0; i<ncon; i++) {
    array[i].key = flows[i] * sign;
    array[i].val = i;
  }

  /* GKTODO Need to check the direction of those sorts */
  rkvsorti(ncon, array);

  iset(ncon, 1, dont_cares);
  for (current=0, i=0; i<ncon-1; i++) {
    if (array[i+1].key - array[i].key < maxdiff * MC_FLOW_BALANCE_THRESHOLD && dont_cares[current] < ncon-1) {
      dont_cares[current]++;
      dont_cares[i+1] = 0;
    }
    else
      current = i+1;
  }

  switch (ncon) {
    /***********************/
    case 2:
      nperms = 1;
      perm[0][0] = 0;   perm[0][1] = 1;

      break;
    /***********************/
    case 3:

      /* if the first and second flows are close */
      if (dont_cares[0] == 2 && dont_cares[1] == 0 && dont_cares[2] == 1) {
        nperms = 4;
        perm[0][0] = 0;   perm[0][1] = 1;   perm[0][2] = 2;
        perm[1][0] = 1;   perm[1][1] = 0;   perm[1][2] = 2;
        perm[2][0] = 0;   perm[2][1] = 2;   perm[2][2] = 1;
        perm[3][0] = 1;   perm[3][1] = 2;   perm[3][2] = 0;
        break;
      }

      /* if the second and third flows are close */
      if (dont_cares[0] == 1 && dont_cares[1] == 2 && dont_cares[2] == 0) {
        nperms = 4;
        perm[0][0] = 0;   perm[0][1] = 1;   perm[0][2] = 2;
        perm[1][0] = 0;   perm[1][1] = 2;   perm[1][2] = 1;
        perm[2][0] = 1;   perm[2][1] = 0;   perm[2][2] = 2;
        perm[3][0] = 2;   perm[3][1] = 0;   perm[3][2] = 1;
        break;
      }

      /* all or none of the flows are close */
      nperms = 3;
      perm[0][0] = 0;   perm[0][1] = 1;   perm[0][2] = 2;
      perm[1][0] = 1;   perm[1][1] = 0;   perm[1][2] = 2;
      perm[2][0] = 0;   perm[2][1] = 2;   perm[2][2] = 1;

      break;
    /***********************/
    case 4:

      if (dont_cares[0] == 2 && dont_cares[1] == 0 &&
          dont_cares[2] == 1 && dont_cares[3] == 1) {
        nperms = 14;
        perm[0][0] =  0;   perm[0][1] =  1;   perm[0][2] =  2;   perm[0][3] =  3;
        perm[1][0] =  1;   perm[1][1] =  0;   perm[1][2] =  2;   perm[1][3] =  3;
        perm[2][0] =  0;   perm[2][1] =  2;   perm[2][2] =  1;   perm[2][3] =  3;
        perm[3][0] =  1;   perm[3][1] =  2;   perm[3][2] =  0;   perm[3][3] =  3;
        perm[4][0] =  0;   perm[4][1] =  1;   perm[4][2] =  3;   perm[4][3] =  2;
        perm[5][0] =  1;   perm[5][1] =  0;   perm[5][2] =  3;   perm[5][3] =  2;
        
        perm[6][0] =  0;   perm[6][1] =  3;   perm[6][2] =  1;   perm[6][3] =  2;
        perm[7][0] =  1;   perm[7][1] =  3;   perm[7][2] =  0;   perm[7][3] =  2;

        perm[8][0] =  0;   perm[8][1] =  2;   perm[8][2] =  3;   perm[8][3] =  1;
        perm[9][0] =  1;   perm[9][1] =  2;   perm[9][2] =  3;   perm[9][3] =  0;

        perm[10][0] = 2;   perm[10][1] = 0;   perm[10][2] = 1;   perm[10][3] = 3;
        perm[11][0] = 2;   perm[11][1] = 1;   perm[11][2] = 0;   perm[11][3] = 3;
        
        perm[12][0] = 0;   perm[12][1] = 3;   perm[12][2] = 2;   perm[12][3] = 1;
        perm[13][0] = 1;   perm[13][1] = 3;   perm[13][2] = 2;   perm[13][3] = 0;
        break;
      }

      if (dont_cares[0] == 1 && dont_cares[1] == 1 &&
          dont_cares[2] == 2 && dont_cares[3] == 0) {
        nperms = 14;
        perm[0][0] =  0;   perm[0][1] =  1;   perm[0][2] =  2;   perm[0][3] =  3;
        perm[1][0] =  0;   perm[1][1] =  1;   perm[1][2] =  3;   perm[1][3] =  2;
        perm[2][0] =  0;   perm[2][1] =  2;   perm[2][2] =  1;   perm[2][3] =  3;
        perm[3][0] =  0;   perm[3][1] =  3;   perm[3][2] =  1;   perm[3][3] =  2;
        perm[4][0] =  1;   perm[4][1] =  0;   perm[4][2] =  2;   perm[4][3] =  3;
        perm[5][0] =  1;   perm[5][1] =  0;   perm[5][2] =  3;   perm[5][3] =  2;

        perm[6][0] =  1;   perm[6][1] =  2;   perm[6][2] =  0;   perm[6][3] =  3;
        perm[7][0] =  1;   perm[7][1] =  3;   perm[7][2] =  0;   perm[7][3] =  2;

        perm[8][0] =  2;   perm[8][1] =  0;   perm[8][2] =  1;   perm[8][3] =  3;
        perm[9][0] =  3;   perm[9][1] =  0;   perm[9][2] =  1;   perm[9][3] =  2;

        perm[10][0] = 0;   perm[10][1] = 2;   perm[10][2] = 3;   perm[10][3] = 1;
        perm[11][0] = 0;   perm[11][1] = 3;   perm[11][2] = 2;   perm[11][3] = 1;

        perm[12][0] = 2;   perm[12][1] = 1;   perm[12][2] = 0;   perm[12][3] = 3;
        perm[13][0] = 3;   perm[13][1] = 1;   perm[13][2] = 0;   perm[13][3] = 2;
        break;
      }

      if (dont_cares[0] == 2 && dont_cares[1] == 0 &&
          dont_cares[2] == 2 && dont_cares[3] == 0) {
        nperms = 14;
        perm[0][0] =  0;   perm[0][1] =  1;   perm[0][2] =  2;   perm[0][3] =  3;
        perm[1][0] =  1;   perm[1][1] =  0;   perm[1][2] =  2;   perm[1][3] =  3;
        perm[2][0] =  0;   perm[2][1] =  1;   perm[2][2] =  3;   perm[2][3] =  2;
        perm[3][0] =  1;   perm[3][1] =  0;   perm[3][2] =  3;   perm[3][3] =  2;

        perm[4][0] =  0;   perm[4][1] =  2;   perm[4][2] =  1;   perm[4][3] =  3;
        perm[5][0] =  1;   perm[5][1] =  2;   perm[5][2] =  0;   perm[5][3] =  3;
        perm[6][0] =  0;   perm[6][1] =  3;   perm[6][2] =  1;   perm[6][3] =  2;
        perm[7][0] =  1;   perm[7][1] =  3;   perm[7][2] =  0;   perm[7][3] =  2;

        perm[8][0] = 2;    perm[8][1] = 0;    perm[8][2] = 1;    perm[8][3] = 3;
        perm[9][0] = 0;    perm[9][1] = 2;    perm[9][2] = 3;    perm[9][3] = 1;
        perm[10][0] = 2;   perm[10][1] = 1;   perm[10][2] = 0;   perm[10][3] = 3;
        perm[11][0] = 0;   perm[11][1] = 3;   perm[11][2] = 2;   perm[11][3] = 1;
        perm[12][0] = 3;   perm[12][1] = 0;   perm[12][2] = 1;   perm[12][3] = 2;
        perm[13][0] = 1;   perm[13][1] = 2;   perm[13][2] = 3;   perm[13][3] = 0;
        break;
      }

      if (dont_cares[0] == 3 && dont_cares[1] == 0 &&
          dont_cares[2] == 0 && dont_cares[3] == 1) {
        nperms = 14;
        perm[0][0] =  0;   perm[0][1] =  1;   perm[0][2] =  2;   perm[0][3] =  3;
        perm[1][0] =  0;   perm[1][1] =  2;   perm[1][2] =  1;   perm[1][3] =  3;
        perm[2][0] =  1;   perm[2][1] =  0;   perm[2][2] =  2;   perm[2][3] =  3;
        perm[3][0] =  2;   perm[3][1] =  0;   perm[3][2] =  1;   perm[3][3] =  3;
        perm[4][0] =  1;   perm[4][1] =  2;   perm[4][2] =  0;   perm[4][3] =  3;
        perm[5][0] =  2;   perm[5][1] =  1;   perm[5][2] =  0;   perm[5][3] =  3;

        perm[6][0] =  0;   perm[6][1] =  1;   perm[6][2] =  3;   perm[6][3] =  2;
        perm[7][0] =  1;   perm[7][1] =  0;   perm[7][2] =  3;   perm[7][3] =  2;
        perm[8][0] =  0;   perm[8][1] =  2;   perm[8][2] =  3;   perm[8][3] =  1;
        perm[9][0] =  2;   perm[9][1] =  0;   perm[9][2] =  3;   perm[9][3] =  1;
        perm[10][0] = 1;   perm[10][1] = 2;   perm[10][2] = 3;   perm[10][3] = 0;
        perm[11][0] = 2;   perm[11][1] = 1;   perm[11][2] = 3;   perm[11][3] = 0;

        perm[12][0] = 0;   perm[12][1] = 3;   perm[12][2] = 1;   perm[12][3] = 2;
        perm[13][0] = 0;   perm[13][1] = 3;   perm[13][2] = 2;   perm[13][3] = 1;
        break;
      }

      if (dont_cares[0] == 1 && dont_cares[1] == 3 &&
          dont_cares[2] == 0 && dont_cares[3] == 0) {
        nperms = 14;
        perm[0][0] =  0;   perm[0][1] =  1;   perm[0][2] =  2;   perm[0][3] =  3;
        perm[1][0] =  0;   perm[1][1] =  2;   perm[1][2] =  1;   perm[1][3] =  3;
        perm[2][0] =  0;   perm[2][1] =  1;   perm[2][2] =  3;   perm[2][3] =  2;
        perm[3][0] =  0;   perm[3][1] =  2;   perm[3][2] =  3;   perm[3][3] =  1;
        perm[4][0] =  0;   perm[4][1] =  3;   perm[4][2] =  1;   perm[4][3] =  2;
        perm[5][0] =  0;   perm[5][1] =  3;   perm[5][2] =  2;   perm[5][3] =  1;

        perm[6][0] =  1;   perm[6][1] =  0;   perm[6][2] =  2;   perm[6][3] =  3;
        perm[7][0] =  1;   perm[7][1] =  0;   perm[7][2] =  3;   perm[7][3] =  2;
        perm[8][0] =  2;   perm[8][1] =  0;   perm[8][2] =  1;   perm[8][3] =  3;
        perm[9][0] =  2;   perm[9][1] =  0;   perm[9][2] =  3;   perm[9][3] =  1;
        perm[10][0] = 3;   perm[10][1] = 0;   perm[10][2] = 1;   perm[10][3] = 2;
        perm[11][0] = 3;   perm[11][1] = 0;   perm[11][2] = 2;   perm[11][3] = 1;

        perm[12][0] = 1;   perm[12][1] = 2;   perm[12][2] = 0;   perm[12][3] = 3;
        perm[13][0] = 2;   perm[13][1] = 1;   perm[13][2] = 0;   perm[13][3] = 3;

        break;
      }

      nperms = 14;
      perm[0][0] =  0;   perm[0][1] =  1;   perm[0][2] =  2;   perm[0][3] =  3;
      perm[1][0] =  1;   perm[1][1] =  0;   perm[1][2] =  2;   perm[1][3] =  3;
      perm[2][0] =  0;   perm[2][1] =  2;   perm[2][2] =  1;   perm[2][3] =  3;
      perm[3][0] =  0;   perm[3][1] =  1;   perm[3][2] =  3;   perm[3][3] =  2;
      perm[4][0] =  1;   perm[4][1] =  0;   perm[4][2] =  3;   perm[4][3] =  2;

      perm[5][0] =  2;   perm[5][1] =  0;   perm[5][2] =  1;   perm[5][3] =  3;
      perm[6][0] =  0;   perm[6][1] =  2;   perm[6][2] =  3;   perm[6][3] =  1;

      perm[7][0] =  1;   perm[7][1] =  2;   perm[7][2] =  0;   perm[7][3] =  3;
      perm[8][0] =  0;   perm[8][1] =  3;   perm[8][2] =  1;   perm[8][3] =  2;

      perm[9][0] =  2;   perm[9][1] =  1;   perm[9][2] =  0;   perm[9][3] =  3;
      perm[10][0] = 0;   perm[10][1] = 3;   perm[10][2] = 2;   perm[10][3] = 1;
      perm[11][0] = 2;   perm[11][1] = 0;   perm[11][2] = 3;   perm[11][3] = 1;

      perm[12][0] = 3;   perm[12][1] = 0;   perm[12][2] = 1;   perm[12][3] = 2;
      perm[13][0] = 1;   perm[13][1] = 2;   perm[13][2] = 3;   perm[13][3] = 0;
      break;
    /***********************/
    default:
      goto DONE;
  }

  for (i=0; i<nperms; i++) {
    for (j=0; j<ncon; j++)
      cand[j] = array[perm[i][j]].val;

    for (j=0; j<ncon; j++)
      rank[cand[j]] = j;

    hash = Mc_HashVRank(ncon, rank) - minval;
    if (currentq[hash+index] > 0) {
      *qnum = hash;
      goto DONE;
    }
  }

DONE:
  WCOREPOP;
}


/*************************************************************************/
/*! This function sorts the nvwgts of a vertex and returns a hashed value 
*/
/*************************************************************************/
idx_t Mc_HashVwgts(ctrl_t *ctrl, idx_t ncon, real_t *nvwgt)
{
  idx_t i;
  idx_t multiplier, retval;
  idx_t *rank;
  rkv_t *array;

  WCOREPUSH;

  rank  = iwspacemalloc(ctrl, ncon);
  array = rkvwspacemalloc(ctrl, ncon);

  for (i=0; i<ncon; i++) {
    array[i].key = nvwgt[i];
    array[i].val = i;
  }

  rkvsorti(ncon, array);
  for (i=0; i<ncon; i++)
    rank[array[i].val] = i;

  multiplier = 1;

  retval = 0;
  for (i=0; i<ncon; i++) {
    multiplier *= (i+1);
    retval += rank[ncon-i-1] * multiplier;
  }

  WCOREPOP;

  return retval;
}


/*************************************************************************/
/*! This function sorts the vwgts of a vertex and returns a hashed value 
*/
/*************************************************************************/
idx_t Mc_HashVRank(idx_t ncon, idx_t *vwgt)
{
  idx_t i, multiplier, retval;

  multiplier = 1;

  retval = 0;
  for (i=0; i<ncon; i++) {
    multiplier *= (i+1);
    retval += vwgt[ncon-1-i] * multiplier;
  }

  return retval;
}