/**********************************************************************/
/*                                                                    */
/*            (c) Copyright, 1997 by Professor Gabriel Robins         */
/*                                                                    */
/*      Department of Computer Science, University of Virginia        */
/*          Charlottesville, VA 22903-2442  (804) 982-2207            */
/*   robins@cs.virginia.edu    http://www.cs.virginia.edu/~robins/    */
/*                                                                    */
/*   This code may be freely used for all non-commercial purposes.    */
/*   All copies/portions of this code must contain this header.       */
/*                                                                    */
/**********************************************************************/

/**********************************************************************/
/*                      Steiner4.c                                    */
/**********************************************************************/

#include "geometry.h"

/**********************************************************************/

int    num_candidates;
          
int generate_steiner4(void)
{
int   original_MST_cost, prior_MST_cost, pre_round_mst_cost;
int     s, i, j, k, heuristic_num = 4, round = 0, nsp,
        actual_number_of_points, SPs_this_round;
FILE *fd;

generate_MST2();
original_MST_cost = mst_cost;

prior_MST_cost = mst_cost;
actual_number_of_points = number_of_points;
number_of_points++;

while(YES)
{
num_candidates = 0;
for(i=0;i<actual_number_of_points;i++)
   for(j=0;j<actual_number_of_points;j++) if(i != j)
      {
      pointset[number_of_points - 1].X = pointset[i].X;
      pointset[number_of_points - 1].Y = pointset[j].Y;

      generate_MST2();      
      
      if(mst_cost < prior_MST_cost) 
         {
         SP_candidates[num_candidates].X = pointset[number_of_points - 1].X;
         SP_candidates[num_candidates].Y = pointset[number_of_points - 1].Y;
         Steiner_savings[num_candidates] = prior_MST_cost - mst_cost;
         num_candidates++;
         }
      }
      
if(num_candidates == 0) break;

qsort_candidates(0, num_candidates-1);

SPs_this_round = 0;
number_of_points--;
generate_MST2();
number_of_points++;
prior_MST_cost = mst_cost;
pre_round_mst_cost = mst_cost;

for(k=0;k<num_candidates;k++)
   {
   pointset[number_of_points - 1] = SP_candidates[k];
   generate_MST2();
     
   if((prior_MST_cost - mst_cost) >= Steiner_savings[k])
      {
      number_of_points++;
	  SPs_this_round++;
	  if(GRAPHICS) draw_point(SP_candidates[k].X,SP_candidates[k].Y, size+4);
	  nsp = number_of_points - actual_number_of_points - 1;
      prior_MST_cost = mst_cost;
      }
   }

if(SPs_this_round == 0) break;

round++;

number_of_points--;
/* delete_useless_SPs(4, actual_number_of_points); */
number_of_points++;

}   

number_of_points--;
generate_MST2(); 

if(GRAPHICS == YES) draw_edges();


steiner_cost[heuristic_num] = mst_cost;
improvement_percent[heuristic_num] = 
  (original_MST_cost - steiner_cost[heuristic_num]) * 100.0 / original_MST_cost;

num_steiner_pts[heuristic_num] = number_of_points - actual_number_of_points;
num_N_pts[heuristic_num][num_steiner_pts[heuristic_num]] ++;
ave_num_steiner_pts[heuristic_num] = ave_num_steiner_pts[heuristic_num] 
                                   + num_steiner_pts[heuristic_num];
min_num_steiner_pts[heuristic_num] = min(min_num_steiner_pts[heuristic_num],
                                         num_steiner_pts[heuristic_num]);
max_num_steiner_pts[heuristic_num] = max(max_num_steiner_pts[heuristic_num],
                                         num_steiner_pts[heuristic_num]);

min_round = min (round, min_round);
max_round = max (round, max_round);
total_round = total_round + round;

generate_MST2();

/*
fd = fopen("ST","w");
for(j=0;j<number_of_edges;j++)
   if(edges[j].flag == MARKED)
      fprintf(fd, "%d %d %d %d %d\n",
             pointset[edges[j].P1].X, pointset[edges[j].P1].Y,
             pointset[edges[j].P2].X, pointset[edges[j].P2].Y, 3);
for(j=0;j<actual_number_of_points;j++)
      fprintf(fd, "%d %d %d %d %d\n",
             pointset[j].X, pointset[j].Y,
             pointset[j].X, pointset[j].Y, 5);
for(j=actual_number_of_points;j<number_of_points;j++)
      fprintf(fd, "%d %d %d %d %d\n",
             pointset[j].X, pointset[j].Y, pointset[j].X, pointset[j].Y, 8);
fclose(fd);

draw_tree();

*/

number_of_points = actual_number_of_points;
generate_MST2();

return(improvement_percent[heuristic_num]);
}

/**********************************************************************/

void draw_tree()
{
FILE *fd;
int x1,x2,y1,y2,s;
struct point p1,p2;

fd = fopen("ST","r");

erase_window();

while(YES)
{
if(fscanf(fd,"%d %d %d %d %d", &x1, &y1, &x2, &y2, &s) < 0) break; 
if(x1 < 0) break;
p1.X = x1; p1.Y = y1;
p2.X = x2; p2.Y = y2;
draw_line(p1, p2, 1);
draw_point(x1, y1, s);
draw_point(x2, y2, s);
}
fclose(fd);
}

/**********************************************************************/

void qsort_candidates(int left, int right)
{
struct point SP;
int  t;
int    i, last, m;

if(left>= right) return;
m = (left + right) / 2;

t = Steiner_savings[left]; 
Steiner_savings[left] = Steiner_savings[m]; 
Steiner_savings[m] = t;

SP = SP_candidates[left]; 
SP_candidates[left] = SP_candidates[m]; 
SP_candidates[m] = SP;

last = left;
for(i=left+1; i <= right; i++)
  if (Steiner_savings[i] > Steiner_savings[left]) 
  		{ ++last;
  		  t = Steiner_savings[i]; 
  		  Steiner_savings[i] = Steiner_savings[last];
  		  Steiner_savings [last] = t;
  		  
          SP = SP_candidates[i]; 
          SP_candidates[i] = SP_candidates[last]; 
          SP_candidates[last] = SP;
  		  }
  		  
t = Steiner_savings[left];
Steiner_savings[left] = Steiner_savings[last];
Steiner_savings[last] = t;

SP = SP_candidates[left]; 
SP_candidates[left] = SP_candidates[last]; 
SP_candidates[last] = SP;

qsort_candidates(left, last - 1);
qsort_candidates(last + 1, right);
}

/**********************************************************************/