/* Output from p2c, the Pascal-to-C translator */
/* From input file "knapsack.pas" */


/*  Dynamic programming solution to 0/1 Knapsack Problem tailored for the 
    optimization of spare channels used during RREACT restoration protocol.
*/


#include "p2c/p2c.h"


#define KNAPSACK_G
#include "knapsack2.h"


/* initial solution used at process start */

Static ksitem empty = { 0, 0 };

Static list sets[500][2];   /* array of working solutions */
Static long targetprofit, maxprofit, count;


Local boolean path_added(current_solution, tt, workuse)
ksitem *current_solution;
pathtuple *tt;
list *workuse;
{
  boolean Result;
  long *edge, *bw;

  Result = true;

  fixed_list(workuse, (int)(sizeof(long)));

  duplicate(&current_solution->use, workuse);   /*copy use list to temp */

  edge = (long *)head_list(&tt->edges);
  while (edge != NULL) {
    bw = (long *)recall_list(workuse, *edge);
    if (bw != NULL) {
      *bw -= tt->bw;
      if (*bw < 0) {
	Result = false;
	kill_list(workuse);
	return Result;
      }
    } else 
      bw = (long *)Malloc(sizeof(int));{
      *bw = tt->bw;
      add_list(workuse, bw, workuse->count);
      /* bw = NEW; */
/* p2c: knapsack.pas, line 89:
 * Warning: Symbol 'NEW' is not of the appropriate class [222] */
    }
    edge = (long *)next_list(&tt->edges);
  }
  return Result;
}


/* adds the specified Item to each Item in the specified list,
   creating a new list of items with the sums of these additions */

Static Void addToEach(inlist, t, outlist)
list *inlist;
pathtuple *t;
list *outlist;
{
  ksitem *current, *tempitem;
  Anyptr t1ptr;
  list templist;

  init_list(outlist);   /* prepare new list structure */

  current = (ksitem *)head_list(inlist);   /* start at head_list of list */
  while (current != NULL) {   /* traverse input list... */
    if (path_added(current, t, &templist)) {
      tempitem = (ksitem *)Malloc(sizeof(ksitem));   /* create output item */

      init_list(&tempitem->tuples);
      tempitem->use = templist;
      tempitem->w = current->w + t->spares;   /* add Items */
      tempitem->p = current->p + t->bw;

      /* copy list of paths (only pointers) making up current's */
      /* solution to new solution ... */
      t1ptr = head_list(&current->tuples);
      while (t1ptr != NULL) {
	add_list(&tempitem->tuples, t1ptr, (long)tempitem->tuples.count);
	t1ptr = next_list(&current->tuples);
      }

      /* add new item to solution */
      add_list(&tempitem->tuples, (Anyptr)t, (long)tempitem->tuples.count);

      add_list(outlist, (Anyptr)tempitem, (long)outlist->count);
    }
    current = (ksitem *)next_list(inlist);   /* and continue traverse */
  }
}

/* Performs critical merge step of knapsack problem solution formation
   Nonviable solutions are also eliminated - a merged output list is created */

Static Void mergeLists(inlist1, inlist2, outlist)
list *inlist1, *inlist2, *outlist;
{
  ksitem *c1, *c2;   /* list cursors */
  ksitem *tempitem;   /* temporary pointer for items in output list */
  boolean done;
  long i;
  Anyptr t1ptr, t2ptr;
  long FORLIM;

  /* init for merge operation */
  done = false;   /* not done merge yet */
  c1 = (ksitem *)head_list(inlist1);   /* start both at head_list of list */
  c2 = (ksitem *)head_list(inlist2);

  init_list(outlist);   /* prep output list */

  /* merge both ordered lists based on increasing order data^.w values
     if weights are equal then reverse order by highest profit value
  */
  while (done != true) {   /* loop does merge sort operation */
    /* test input 1 first */
    while (c1 != NULL && c2 == NULL || c1 != NULL && c1->w < c2->w ||
	   c1 != NULL && c1->w == c2->w && c1->p >= c2->p) {
      tempitem = (ksitem *)Malloc(sizeof(ksitem));

      init_list(&tempitem->tuples);
      tempitem->use = c1->use;
      tempitem->w = c1->w;   /* add Items */
      tempitem->p = c1->p;

      /* copy list of paths (only pointers) making up current's */
      /* solution to new solution ... */
      t1ptr = head_list(&c1->tuples);
      while (t1ptr != NULL) {
	add_list(&tempitem->tuples, t1ptr, (long)tempitem->tuples.count);
	t1ptr = next_list(&c1->tuples);
      }

      add_list(outlist, (Anyptr)tempitem, (long)outlist->count);
	  /* add to output list */
      c1 = (ksitem *)next_list(inlist1);   /* bump cursor */
    }
    /* new item for output */
    /* complementary input 1 tests for input 2 */
    while (c2 != NULL && c1 == NULL || c2 != NULL && c2->w < c1->w ||
	   c2 != NULL && c2->w == c1->w && c2->p >= c1->p) {
      tempitem = (ksitem *)Malloc(sizeof(ksitem));

      init_list(&tempitem->tuples);
      tempitem->use = c2->use;
      tempitem->w = c2->w;   /* add Items */
      tempitem->p = c2->p;

      /* copy list of paths (only pointers) making up current's */
      /* solution to new solution ... */
      t2ptr = head_list(&c2->tuples);
      while (t2ptr != NULL) {
	add_list(&tempitem->tuples, t2ptr, (long)tempitem->tuples.count);
	t2ptr = next_list(&c2->tuples);
      }

      add_list(outlist, (Anyptr)tempitem, (long)outlist->count);
      c2 = (ksitem *)next_list(inlist2);
    }
    /* when BOTH cursors at end of lists, we are done */
    if (c1 == NULL && c2 == NULL)
      done = true;
  }

  /*
       { init for purge operation */
  c1 = (ksitem *)head_list(outlist);   /* set lead cursor */
  maxprofit = 0;   /* set maximum profit so far... */

  FORLIM = outlist->count;
  /* scan list looking for non-optimal items to delete or
     items which violate knapsack weight constraint
   */
  for (i = 0; i < FORLIM; i++) {
    c1 = (ksitem *)recall_list(outlist, i);
    /* good solution conditions */
    if (c1->p > maxprofit)   /* delete item */
      maxprofit = c1->p;   /* update maxp */
    else  /* non-optimal, delete item */
      remove_list(outlist, i);
  }
}


Void initialize_knapsack(tp, capacity)
long tp;
list *capacity;
{
  targetprofit = tp;
  count = 0;

  empty.p = 0;
  empty.w = 0;
  empty.use = *capacity;
  init_list(&empty.tuples);

  init_list(sets[0]);
  init_list(&sets[0][1]);
}


boolean add_to_knapsack(newpath)
pathtuple **newpath;
{
  boolean Result;
  long i;

  if (count == 0)
    add_list(sets[count], (Anyptr)(&empty), (long)sets[count][0].count);
  /* init first set as zero item */

  /* do knapsack solution processing */
  addToEach(sets[count], *newpath, &sets[count][1]);
  mergeLists(sets[count], &sets[count][1], sets[count + 1]);

  for (i = 0; i <= 1; i++)
    kill_list(&sets[count][i]);

  Result = (maxprofit >= targetprofit);

  /* bump count */
  count++;
  return Result;
}


Void determine_knapsack_solution_components(optimal)
list *optimal;
{
  ksitem *current, best;

  best.w = MAXINT;
  best.p = 0;

  current = (ksitem *)head_list(sets[count]);
  while (current != NULL) {
    if (current->p >= targetprofit && current->w <= best.w)
      best = *current;
    current = (ksitem *)next_list(sets[count]);
  }
  if (current == NULL) {
    current = (ksitem *)tail_list(sets[count]);
    best = *current;
  }
  *optimal = best.tuples;
}

/* End. */