Monday, April 16, 2012

Shortest Job First Scheduling using HEAP







// 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);
    }
}