/*************************************************************************/
/*                                                                       */
/*  Copyright (c) 1994 Stanford University                               */
/*                                                                       */
/*  All rights reserved.                                                 */
/*                                                                       */
/*  Permission is given to use, copy, and modify this software for any   */
/*  non-commercial purpose as long as this copyright notice is not       */
/*  removed.  All other uses, including redistribution in whole or in    */
/*  part, are forbidden without prior written permission.                */
/*                                                                       */
/*  This software is provided with absolutely no warranty and no         */
/*  support.                                                             */
/*                                                                       */
/*************************************************************************/

EXTERN_ENV

#include "matrix.h"
#include <math.h>
#include <stdlib.h>


struct Chunk {
	long first, last, assign;
	struct Chunk *next;
	} *chunks_head = NULL, *chunks_tail = NULL;

long tolerance = 20;

double domain_ops;

double *divide_lo=NULL, *divide_hi;

extern double *work_tree;
extern long *firstchild, *child;

long Divide(struct Chunk *root);
void AddInOrder(struct Chunk *t);

void Partition(SMatrix M, long parts, long *T, long *assigned_ops, long *domain, long *domains, long *proc_domains)
{
  long i, p, start, minm, maxm, ops, change;
  long which=0;
  long *depth;
  double ave, maxo=0.0, maxd;
  struct Chunk *t;

  start = 0;
  for (i=0; i<M.n; i++)
    if (T[i] == M.n) {
      t = NewChunk();
      t->first = start; t->last = i+1;
      AddInOrder(t);
      start = i+1;
    }

    NumberPartition(parts, assigned_ops, 0);

    for (;;) {
      minm = assigned_ops[MinBucket(assigned_ops, parts)];
      maxm = assigned_ops[MaxBucket(assigned_ops, parts)];

      if (maxm == 0 ||
	  (100.0*(maxm - minm)/(double) maxm < tolerance) ||
	  (1.0*parts*maxm/work_tree[M.n] < 0.05))
	break;

      t = GetChunk();

      change = Divide(t);

      if (!change)
	break;

      NumberPartition(parts, assigned_ops, 0);
    }

    NumberPartition(parts, assigned_ops, 1);

  which = 0;
  for (i=0; i<parts; i++) {
    proc_domains[i] = which;

    t = chunks_head;
    while (t) {
      if (t->assign == i) {
        domains[which++] = t->last-1;
      }
      t = t->next;
    }
  }
  proc_domains[parts] = which;

  /* free chunk list */
  while (chunks_head) {
    t = chunks_head;
    chunks_head = chunks_head->next;
    free(t);
  }

  depth = (long *) malloc(proc_domains[parts]*sizeof(long));
  for (p=0; p<parts; p++)
    for (i=proc_domains[p]; i<proc_domains[p+1]; i++)
      depth[i] = 1000000*p-BlDepth(domains[i]);

  SortByKey(proc_domains[p], domains, depth);

  free(depth);

  for (i=0; i<M.n; i++)
    domain[i] = 0;
  for (i=0; i<proc_domains[parts]; i++)
    MarkSubtreeAsDomain(domain, domains[i]);

  domain_ops = 0;
  for (i=0; i<proc_domains[parts]; i++)
    domain_ops += work_tree[domains[i]];

  maxd = 0;
  for (p=0; p<parts; p++) {
    ops = 0;
    for (i=proc_domains[p]; i<proc_domains[p+1]; i++)
      ops += work_tree[domains[i]];
    if (ops > maxd)
      maxd = ops;
  }
  ave = domain_ops/(double) parts;

  printf("Divide for %ld P, %ld domains, ", parts, proc_domains[parts]);
  printf("%.2f of work static, ", domain_ops/work_tree[M.n]);
  printf("%.2f eff, (%.2f overall)\n", ave/maxd, work_tree[M.n]/maxo/parts);
}


void MarkSubtreeAsDomain(long *domain, long root)
{
  long i, first, root_super;
  extern long *node;

  first = root;
  while (firstchild[first] != firstchild[first+1])
    first = child[firstchild[first]];

  /* all nodes not at root have domain[i] = 1 */
  for (i=first; i<=root; i++)
    domain[i] = 1;

  /* root super has domain[i] = 2 */
  root_super = root;
  if (node[root_super] < 0)
    root_super += node[root_super];
  for (i=root_super; i<root_super+node[root_super]; i++)
    domain[i] = 2;
}


void NumberPartition(long parts, long *assigned_ops, long distribute)
{
  long i, minm;
  struct Chunk *t, *old_t;

  for (i=0; i<parts; i++)
    assigned_ops[i] = 0;

  t = chunks_head;
  while (t) {
    minm = MinBucket(assigned_ops, parts);
    assigned_ops[minm] += work_tree[t->last-1];
    old_t = t;
    t = t->next;
    if (distribute) {
      old_t->assign = minm;
    }
  }
}

long Divide(struct Chunk *root)
{
  long i, first, first_in_super;
  long change = 1;
  struct Chunk *t2;

  first_in_super = root->last-1;
  while (firstchild[first_in_super]+1 ==
	 firstchild[first_in_super+1]) {
    first_in_super--;
  }

    first = root->first;
    for (i=firstchild[first_in_super];i<firstchild[first_in_super+1]; i++){
      t2 = NewChunk();
      t2->last = child[i]+1;
      t2->first = first;
      AddInOrder(t2);
      first = t2->last;
    }
    free(root);

  return(change);
}


long MaxBucket(long *assigned_ops, long parts)
{
	long i, maxm, ind;

	maxm = assigned_ops[0]; ind = 0;
	for (i=1; i<parts; i++)
		if (assigned_ops[i] > maxm) {
			ind = i; maxm = assigned_ops[i];
			}

	return(ind);
}

long MinBucket(long *assigned_ops, long parts)
{
	long i, minm, ind;

	minm = assigned_ops[0]; ind = 0;
	for (i=1; i<parts; i++)
		if (assigned_ops[i] < minm) {
			ind = i; minm = assigned_ops[i];
			}

	return(ind);
}


struct Chunk *NewChunk()
{
	struct Chunk *t;

	t = (struct Chunk *) malloc(sizeof(struct Chunk));

	return(t);
}



void AddInOrder(struct Chunk *t)
{
	struct Chunk *current;
	long work;

	work = work_tree[t->last-1];
	current = chunks_head;
	if (!current) {
		t->next = NULL;
		chunks_head = t;
		}
	else if (work >= work_tree[current->last-1]) {
		t->next = chunks_head;
		chunks_head = t;
		}
	else {
		while (current->next && work<work_tree[current->next->last-1])
			current = current->next;
		t->next = current->next;
		current->next = t;
		}
		
	if (t->next == NULL)
		chunks_tail = t;
}


struct Chunk *GetChunk()
{
	struct Chunk *t;

	t = chunks_head;
	if (t) {
	  chunks_head = t->next;
	  if (t == chunks_tail)
	    chunks_tail = NULL;
	  }

	return(t);
}