// Input is from the file "input.txt" in the form (a1,t1),(a2,t2),(a3,t3) (arrival time, time to complete ie, burst time)
import java.io.*;
import java.util.*;
public class SJFHeap {
static class point {
double time;
double run;
int no;
double total;
point(int i, double a, double b) {
no = i;
time = a;
run = b;
total = 0;
}
}
static class MHeap {
private point[] Heap;
private int maxsize;
private int size;
public MHeap(int max) {
maxsize = max;
Heap = new point[maxsize];
size = 0;
}
private int leftchild(int pos) {
return 2 * pos;
}
private int rightchild(int pos) {
return 2 * pos + 1;
}
private int parent(int pos) {
return pos / 2;
}
private boolean isleaf(int pos) {
return ((pos > size / 2) && (pos <= size));
}
private void swap(int pos1, int pos2) {
point tmp;
tmp = Heap[pos1];
Heap[pos1] = Heap[pos2];
Heap[pos2] = tmp;
}
public void insert(point elem) {
size++;
Heap[size] = elem;
int current = size;
int paren = parent(current);
if (paren >= 1)
while (Heap[current].run < Heap[paren].run) {
swap(current, paren);
current = parent(current);
}
}
public void print() {
int i;
for (i = 1; i <= size; i++)
System.out.println("(" + Heap[i].time + "," + Heap[i].run + ")");
}
public point removemin() {
swap(1, size);
size--;
if (size != 0)
pushdown(1);
return Heap[size + 1];
}
private void pushdown(int position) {
int smallestchild;
while (!isleaf(position)) {
smallestchild = leftchild(position);
if ((smallestchild < size)
&& (Heap[smallestchild].run > Heap[smallestchild + 1].run))
smallestchild = smallestchild + 1;
if (Heap[position].run <= Heap[smallestchild].run)
return;
swap(position, smallestchild);
position = smallestchild;
}
}
}
public static void main(String[] args) throws IOException {
MHeap h = new MHeap(10);
FileInputStream fstream = new FileInputStream("input.txt");
DataInputStream in = new DataInputStream(fstream);
BufferedReader br = new BufferedReader(new InputStreamReader(in));
point ele;
String strLin;
strLin = in.readLine();
StringTokenizer st = new StringTokenizer(strLin, " (,)");
int mp = st.countTokens();
point[] task = new point[mp / 2];
point[] tem = new point[mp / 2];
int l = 0, num;
while (st.hasMoreTokens())
{
String x = st.nextToken();
double x1 = Double.parseDouble(x);
String y = st.nextToken();
double y1 = Double.parseDouble(y);
point pt = new point(l + 1, x1, y1);
task[l] = pt;
l++;
}
num = l;
int j = 0, i = 0, killed = 0;
double now = 0, prev = 0, diff, kill = 0;
point pt = task[0];
while (i != num)
{
now = task[i].time;
if (i == 0)
{
h.insert(task[i]);
i++;
prev = now;
}
else
{
pt = h.removemin();
diff = now - prev;
if (pt.run > diff)
{
pt.run = pt.run - diff;
h.insert(pt);
}
else
{
pt.total = prev + pt.run - pt.time;
kill = prev + pt.run;
pt.run = 0;
tem[j++] = pt;
}
h.insert(task[i]);
prev = kill > 0 ? kill : now;
i++;
}
}
h.insert(h.removemin());
while (h.size != 0)
{
pt = h.removemin();
pt.total = prev + pt.run - pt.time;
tem[j++] = pt;
prev = prev + pt.run;
}
for (i = 0; i < j; i++)
System.out.println("Process-" + tem[i].no + " processed for " + tem[i].total);
}
}
