#include<stdio.h>
#include<iostream.h>
#include<stdlib.h>
 
struct indexq{
	float *col;
	int head, rear, n;
};
 
float myrand(int lower, int upper)
{
 
	return (lower + rand() % (upper-lower+1));
 
}
 
 
 
int  ij_to_k(int i, int j, int n)
{ 
  return i*n+j;
}
 
float costij(float *arr, int k, int l,  int n)// function to compute cost of path from i to j
{
int s=1;
return((arr[ij_to_k(n, 2, 2)]-arr[ij_to_k(k, 2, 2)])*(s+arr[ij_to_k(l,1, 2)]-arr[ij_to_k(k, 1, 2)]));
}
 
float compf(float *sum,int i, int n)// function to compute f(i)= (W[n]-W[i])
{
	float k = (sum[ij_to_k(n, 2, 2)] - sum[ij_to_k(i, 2, 2)]);
	return(k);
}
 
float compv( int k, int l, float *P, float *F)//function to compute v=(F(k)-F(l))/(P[l]-P[k])
{
	return ( (F[ij_to_k(k, 1, 2)] - F[ij_to_k(l, 1, 2)])/(P[ij_to_k(l, 1, 2)]-P[ij_to_k(k, 1, 2)]));
 
}
 
void add(indexq &copq, int i, int n)
{
int t;
t = (copq.rear+1)%n;
if(t == copq.head)
cout<<"\nQueue Overflow\n";
else
{
copq.rear=t;
copq.col[copq.rear]=i;
}
}
 
 
int main()
{
 
 
indexq track;
float *pw, *PS;
int n, i=0, j=0;
float *F;
int upper, lower;
 
	cout<<"\n Enter number of jobs";
	cin>>track.n;
	n = track.n;
	track.head=track.rear=0;
 
	pw = new float[n*2+2];
	PS = new float[n*2+2];
	F  = new float[n*2+2];	
//	cout<<"\n Enter processing times and their corresponding weights";
	cout<<"\n Enter lower and upper value to generate random processing times";
	cin>>lower;
	cin>>upper;
 
	pw[ij_to_k(0, 1, 2)]=0; pw[ij_to_k(0, 2, 2)]=0;
 
for(i=1; i<=n ;i++)
{	pw[ij_to_k(i, 1, 2)]= myrand(lower, upper);
	pw[ij_to_k(i, 2, 2)]=1;
 
			} 	
 
	cout<<"\n\nPartial sums of processing times and weights are:\n ";
	PS[ij_to_k(0, 1, 2)]= 0; PS[ij_to_k(0, 2,2)]=0;
 
for(i=1 ; i<=n ; i++)//calculating partial sums of weights and processing times
{
 
	PS[ij_to_k(i, 1, 2)]= PS[ij_to_k(i-1, 1, 2)]+pw[ij_to_k(i, 1, 2)]; PS[ij_to_k(i, 2, 2)] = PS[ij_to_k(i-1, 2, 2)]+pw[ij_to_k(i, 2, 2)];
	cout<<"\n"<<PS[ij_to_k(i, 1, 2)]<<"\t"<<PS[ij_to_k(i, 2, 2)];
}
 
	track.col[track.head]=track.col[track.rear]=n;
	F[ij_to_k(n, 1, 2)]=0; F[ij_to_k(n, 2, 2)]=0;
 
 
	cout<<"\n Minimum values in each row and column in which it is minimum";
//code to find the shortest path 
//First while loop deletes head of the queue until it satisfies the condition: head(Q)!=tail(Q) and f(i)>=v(next(head(Q)), head(Q)) 
//Second while loop deletes the tail of the queue if it satisfies the condition: head(Q)!=tail(Q) and v(i, tail(Q)) <= v(tail(Q), previous(tail(Q))
 
for( i = n-1; i>=0; i--)
{
	int temp= track.head+1;	
	while (track.col[track.head] != track.col[track.rear] && compf(PS,  i, n) >= compv( track.col[temp], track.col[track.head], PS, F))
	track.head = (track.head + 1)%n;
 
	float j = track.col[track.head];
	F[ij_to_k(i, 1, 2)] = costij(PS, i, j, n) + F[ij_to_k(j, 1, 2)];
	F[ij_to_k(i, 2, 2)] = j;
	int temp2 = track.rear-1;
	while(track.col[track.head] != track.col[track.rear] && compv(i, track.col[track.rear], PS, F) <= compv(track.col[track.rear], track.col[temp2], PS, F))
		track.rear = (track.rear-1)%n;
	add(track, i, n);
	cout<<"\n"<<F[ij_to_k(i, 1, 2)]<<"\t"<<F[ij_to_k(i, 2, 2)];
}
	cout<<"\n The schedule is\n";
i=0;
while(i<n)
{
	cout<<"\ts";
	j=i;
	while(j<F[ij_to_k(i, 2, 2)])
	{
		cout<<"\t"<<++j;
 
	}
 
	i=j;
}
}