#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

#define MAXOBJECTS 20000
#define MAXFNAME 80    /*Maximum length of file names*/
#define MAXMOD 20000      /*Maximum number of modules*/
#define MAXDEF 1000

/* algorithm to generate problem instances for the 2-dimensional unconstrained SLOPP with a single defect */



/* Type declarations for base modules information */

typedef struct rectangle {
   long int area;       /* rectangle area */
   int length;     /* rectangle length */
   int width;      /* rectangle width */

} base_rectangle;

/*Global declarations*/

FILE *mod_file = NULL; /* module file name */
FILE *defect_file = NULL; /* defect file name */
int no_inst;        /* number of instances created */
int no_def[MAXOBJECTS];         /* number of defects to be created per instance */
base_rectangle defects[MAXDEF];        /* holds the different defects */
int defect_x[MAXOBJECTS][MAXDEF];  /* coordinates of lower left edge of the defect */
int defect_y[MAXOBJECTS][MAXDEF];
base_rectangle items[MAXMOD];  /* array of items */
int maxitemarea;               /* minimal and maximal area of item */
int minitemarea;
double interval_lb=0.1;            /* lower and upper bound of interval for b */
double interval_ub=0.9;
int no_defects_lb;
int no_defects_ub;

long r_n;
long c = 16807;
long p = 2147483647;
long q = 127773;
long t = 2836;


/* pseudo-random number generator */

double randomnum()
{
    long h1;
    long h2;
    double h3;
    
    h2 = (long)r_n/q;             /* =r_n div q */
    h1 = r_n-h2*q;                /* =r_n mod q */
    
    r_n = c*h1 - t*h2;

    if (r_n<0)
       r_n = r_n+p;
   
    h3 = ((double)r_n)/((double)p);
        
    return h3;
}




int main()
{


   long seed;    /* to start random number generator */
   int no_objects;       /* holds the number of objects to be generated per instance */
   int no_items;         /* holds the number of items to be generated per instance */
   base_rectangle object;   /* holds the large object */
   float minrelsize;        /* holds the lower bound for rel. size of item types w.r.t. large object size */
   float maxrelsize;        /* holds the upper bound for rel. size of item types w.r.t. large object size */
   char filename[MAXFNAME];    /* name of the file to hold the items */
   char defectfilename[MAXFNAME];      /* name of the file to hold the defects */
   double temparea[MAXMOD];  /* temp variable to hold the randomly generated item area */
   double templength;   /* temp variable for preliminary item length */
   double tempwidth;    /* temp variable for preliminary item width */
   double b;         /* ratio of length and width of the small item */
   double bmin, bmax;   /* min and max value of z depending on area of small item */
   int i,j,k;        /* counting variables for loops */
   float out1, out2, out3, out4;   /* auxiliary variables for printout routine */
   double aux1, aux2, aux3;   /* auxiliary variables to hold intermediary results */
   int no_def_type;
   
   
   
   printf("This program generates problem instances of a two-dimensional rectangular Multiple Large Object Placement Problem with defects. \nAll dimensions of the generated item types are integer, thus the dimensions of the large object and the defects should also be entered as integer numbers. For more details see: Neidlein, V.; Scholz, A.; Wäscher, G. (2014): SLOPPGEN: A Problem Generator for the Two-Dimensional Rectangular Single Large Object Placement Problem with Defects. \n \n");

   /*specification of problem parameters to generate instances for*/


   /* number of instances */
   printf("How many instances do you want to generate? ");
   scanf("%d", &no_inst);
   if (no_inst > MAXMOD)
      {   printf("Please recompile code with larger MAXMOD value!\n");
          scanf("%d");
          exit(1);   }

   /* number of large objects */
   printf("How many large objects are to be generated per instance? ");
   scanf("%d", &no_objects);

   /* choice of large object */
   printf("Choose an integer length for the large object. ");
   scanf("%d", &object.length);
   printf("Choose an integer width for the large object. ");
   scanf("%d", &object.width);
   object.area = object.length*object.width;
   
   
   /* number of small items */
   printf("How many small items are to be generated per instance? ");
   scanf("%d", &no_items);
   	
    			
   /* choice of size of small items in relation to size of large object */
   printf("Choose a lower bound for the relative size of the item types w.r.t. the size of the large object between 0 and 1 (e.g. 0.01). ");
   scanf("%f", &minrelsize);
   if (minrelsize<=0 || minrelsize>=1)
      {  printf("Value must lie between 0 and 1!");
         scanf("%d");
         exit(1);   }

   printf("Choose an upper bound for the relative size of the item types w.r.t. the size of the large object between 0 and 1 (e.g. 0.15). ");
   scanf("%f", &maxrelsize);
   if (maxrelsize<=0 || maxrelsize>=1)
      {   printf("Value must lie between 0 and 1!");
               scanf("%d");
               exit(1);   }
      else if (maxrelsize<minrelsize)
           {   printf("The upper bound for the relative size must not be smaller than the lower bound!");
               scanf("%d");
               exit(1);   }
   
   /* computation of lower and upper bound of size of small items */
   aux1 = minrelsize*object.area;
   minitemarea = (int)aux1;
   if (aux1!=minitemarea)
      {   minitemarea=minitemarea+1;
      }
   aux2 = maxrelsize*object.area;
   maxitemarea = (int)aux2;
   

   /* choice of number of defects to be generated */
   printf("How many different types of defects per instance do you wish to generate? (NOTE: The defects might overlap, as the intention is to consider each defect as a single one and go through them one after the other!) ");
   scanf("%d", &no_def_type);
   if (no_def_type > MAXDEF)
      {   printf("Please recompile code with larger MAXDEF value!\n");
          scanf("%d");
          exit(1);   }
   
   /* choice of defect length and width */
   for (i=0;i<no_def_type;i++)
   {   printf("Enter an positive integer length and width for defect no. %d, separated by a space. ",i+1);
       scanf("%d %d", &defects[i].length, &defects[i].width);
       if (defects[i].length<=0 || defects[i].width<=0)
          {  printf("Values must be greater than 0!");
             scanf("%d");
             exit(1);   }
       if (defects[i].length > object.length || defects[i].width > object.width)
          {  printf("This defect does not fit onto the large object!");
             scanf("%d");
             exit(1);   }      
       defects[i].area = defects[i].length * defects[i].width;   
       }
   
   printf("Choose a lower bound for the number of defects per object. ");
   scanf("%d", &no_defects_lb);

   printf("Choose an upper bound for the number of defects per object. ");
   scanf("%d", &no_defects_ub);

   /* choice of file name for the item types */
   printf("Enter a name for the file to hold the items (e.g. items.txt). ");
   scanf("%s", filename);
   
   /* choice of file name for the defects */  
   if (no_def_type > 0)
      {   printf("Enter a name for the file to hold the defects (e.g. defects.txt). ");
          scanf("%s", defectfilename);  }
   
   /* initialize random generator */
   printf("Enter an integer seed (e.g. 12): ");
   scanf( "%d", &seed);

   r_n = seed;

   randomnum();
   

   /*open output file for items*/
   mod_file = fopen(filename, "w");

/* generation of items - no_inst instances of no_items items*/

/* computation of lower and upper bounds (b_min and b_max) */
   for (j=0; j<no_inst; j++) {
       for (i=0; i<no_items; i++) {
           aux1 = randomnum();     /* random number between 0 and 1 */
           aux2 = (double)(maxitemarea-minitemarea);
           temparea[i] = (aux1 * aux2) + (double)minitemarea;   /* generates temp area of item */

           aux1 = (temparea[i]*temparea[i])/((double)object.width*(double)object.width);
           aux2 = aux1 + temparea[i];
           aux3 = aux1/aux2;
           bmin = fmax(interval_lb,aux3);       /* finds lower bound for the interval for b */


           aux1 = (double)object.length*(double)object.length;
           aux2 = aux1/(aux1 + temparea[i]);
           bmax = fmin(interval_ub,aux2);        /* finds upper bound for the interval for b */


           aux1 = randomnum();
           aux2 = bmax-bmin;
           b = aux1*aux2 + bmin;         /* random value for b */

           aux3 = (b*temparea[i])/(double)(1-b);
           templength = sqrt(aux3);        /* temp value for length of item type */
           items[i].length = (int)round(templength);   /* actual value of item type */

           tempwidth = temparea[i]/templength ;    /* temp value for width of item type */
           items[i].width = (int)round(tempwidth);

           items[i].area = items[i].length * items[i].width;

           /* Check if rounded values of item area lie between chosen lower and upper bounds for the relative size of the large object */
           while (items[i].area < minitemarea || items[i].area > maxitemarea)
           {
			  aux1 = randomnum();
              if (items[i].area<minitemarea)
                 { if ((aux1 < 0.5)&&(items[i].length < object.length) && ((items[i].length+1)*items[i].width<=maxitemarea) && ((items[i].length+1)/((double)items[i].length+1+items[i].width)<=interval_ub))
                     items[i].length++;
                 else 
                      {if ((items[i].width < object.width) && ((items[i].width+1)*items[i].length<=maxitemarea) && ((items[i].length)/((double)items[i].length+items[i].width+1)>=interval_lb))
                      items[i].width++;
                      else
                          { printf(" Determination of integer length or width of the small items failed. Please check the chosen bounds for the relative size as well as the size of the large object!");
                          scanf("%d");
                          exit(1);
                          }
                      }
                 }
              if (items[i].area>maxitemarea)
                 { if ((aux1 < 0.5)&&(items[i].length > 0) && ((items[i].length-1)*items[i].width>=minitemarea) && ((items[i].length-1)/((double)items[i].length-1+items[i].width)>=interval_lb))
                     items[i].length--;
                 else 
                      {if ((items[i].width > 0) && ((items[i].width-1)*items[i].length>=maxitemarea) && ((items[i].length)/((double)items[i].length+items[i].width-1)<=interval_ub))
                      items[i].width--;
                      else
                          { printf(" Determination of integer length or width of the small items failed. Please check the chosen bounds for the relative size as well as the size of the large object!");
                          scanf("%d");
                          exit(1);
                          }
                      }
                 }
              items[i].area = items[i].length*items[i].width;          
              }
           }
       
       /* printout the instances */


      for (k = 0; k< no_items; k++) {
           out1 = (float) items[k].area;
	       out2 = (float) items[k].length;
           out3 = (float) items[k].width;
           fprintf (mod_file,"%f\t%f\t%f\n", out2, out3, out1);
           } 
       fprintf(mod_file,"\n");  
       }      


   fclose(mod_file);
   
   /* generation of defects */
   
   if (no_def_type > 0)
   {
	   defect_file = fopen(defectfilename, "w");
	   for (i = 0; i < no_inst; i++)
	   {
		   for (int ii = 0; ii < no_objects; ii++)
		   {
			   aux1 = randomnum();
			   aux2 = 1.0/(double)(no_defects_ub - no_defects_lb+1.0);

			   for (j = 1; j <= no_defects_ub - no_defects_lb + 1; j++)
			   {
				   if (aux1 <= j*aux2)
				   {
					   no_def[ii] = no_defects_lb + j - 1;
					   j = no_defects_ub - no_defects_lb + 2;
				   }
			   }
		   }

		   fprintf(defect_file, "instance: %d\n\n", i+1);
		   for (int ii = 0; ii < no_objects; ii++)
		   {   
			   for (int jj = 0; jj<no_def[ii]; jj++)
			   {
				   aux1 = randomnum();
				   j = aux1*no_def_type;
				   if (j == no_def[ii])
					   j = j - 1;
				   aux1 = randomnum();
				   aux2 = (double)object.length - (double)defects[j].length;     /* upper bound for defect_x[j] */
				   aux3 = (double)object.width - (double)defects[j].width;       /* upper bound for defect_y[j] */
				   defect_x[ii][jj] = (int)round(aux1*aux2);
				   aux1 = randomnum();
				   defect_y[ii][jj] = (int)round(aux1*aux3);

				   /* printout the defects */
				   out1 = (float)defect_x[ii][jj];
				   out2 = (float)defect_y[ii][jj];
				   out3 = out1 + (float)defects[j].length;
				   out4 = out2 + (float)defects[j].width;
				   fprintf(defect_file, "%f\t%f\t%f\t%f\n", out1, out2, out3, out4);
			   }
			   fprintf(defect_file, "\n");
		   }
		   fprintf(defect_file, "\n");
	   }
       fclose(defect_file);  
   }

printf("\n\nProgram run finished. Enter a number to quit! ");
scanf("%d",&i);

   return 0;
}