import java.util.*;

/**
 * Created by Lairai on 2018/1/14.
 */
public class Schedule {

    private final static String SEPERATOR = "*****************************";

    /*调度算法*/
    private final static int FCFS = 1;
    private final static int SJF = 2;

    /*内存区总大小*/
    private static int size;

    /*预先输入的所有作业，按进入时间排序*/
    private List<Job> jobList;
    int newestJobIndex = 0;


    /*作业队列, 列表*/
    private Queue<Job> waitingQueue;
    private Queue<Job> loadedQueue;
    private Job currentExecutingJob;
    private Queue<Job> scheduleOrderQueue;

    /*空闲区链表头*/
    private Node head;

    /*系统时间*/
    private Time systemTime;

    public Schedule(int size, int algorithm) {

        this.size = size;
        jobList = new ArrayList<>();


        if (algorithm == FCFS) {
            waitingQueue = new ArrayDeque<>();
            loadedQueue = new ArrayDeque<>();
        } else {
            waitingQueue = new PriorityQueue<>((x, y) -> {
                return x.getErt() - y.getErt();
            });
            loadedQueue = new PriorityQueue<>((x, y) -> {
                return x.getErt() - y.getErt();
            });
        } /*短作业优先的情况下使用小顶堆*/

        promptInput();//提示用户输入作业信息,初始化JobList

        /*系统时间初始化为第一个作业的提交时间*/
        Time startTime = jobList.get(0).getEt();
        systemTime = new Time(startTime.getHour(), startTime.getMinute());

        currentExecutingJob = null;
        scheduleOrderQueue = new ArrayDeque<>();
        head = new Node(0, size, new Node(0, size, null));
    }

    public void work() {

        while (true) {

            checkNewJob();

            /*所有作业执行完毕后结束此次调度*/
            if (newestJobIndex == jobList.size() && currentExecutingJob == null) break;

            /*如果当前没有作业在执行*/
            if (currentExecutingJob == null) {
                if (!loadedQueue.isEmpty()) {
                    currentExecutingJob = pickJobFromMemory();
                } else {
                    systemTime.increaseByMinute();
                    continue;//处理机等待一分钟
                }
            }

            executeCurrentJob();

        }
    }

    /*添加当前时刻提交的所有作业到等待列表*/
    private void checkNewJob() {
        while (true) {
            if (newestJobIndex == jobList.size()) break;

            Job job = jobList.get(newestJobIndex);

            /*如果当前时刻有新作业提交*/
            if (job.getEt().equals(systemTime)) {

                ++newestJobIndex;

                Node space = enoughSpace(job);
                /*如果能装入内存则使其装入内存*/
                if (space != null) {
                    allocateMemory(space, job.getNc());
                    loadedQueue.add(job);
                }
                /*否则装入等待队列*/
                else waitingQueue.add(job);
            } else break;
        }
    }

    /**
     * 提示用户输入作业信息
     */
    private void promptInput() {
        System.out.println("Input Job formatted as \"A(job name),8:06(entry time),42(expected runnning time),15(needed capacity in MB)\"");
        System.out.println("Input \'#\' to end input");
        Scanner scanner = new Scanner(System.in);
        String line;
        while (true) {
            line = scanner.nextLine();
            if ("#".equals(line)) break;
            else jobList.add(getJob(line));
        }
        scanner.close();
    }

    /**
     * 根据字符串构造出一个作业
     */
    private Job getJob(String s) {
        String[] parameters = s.split(",");
        if (parameters.length != 4) return null;
        String[] time = parameters[1].split(":");
        return new Job(parameters[0], Integer.parseInt(time[0]), Integer.parseInt(time[1]), Integer.parseInt(parameters[2]), Integer.parseInt(parameters[3]));
    }

    /**
     * @return 指向能容纳x的空闲区的结点
     */
    private Node enoughSpace(Job x) {
        if (x == null || head.freeSize < x.getNc()) return null;
        else {
            int len = x.getNc();
            Node p = head;
            while (p.next != null) {
                if (p.next.freeSize >= len) {
                    x.setIa(p.next.initialAddress);
                    return p;
                }
                p = p.next;
            }
            return null;
        }
    }

    /**
     * 为新进入内存的作业分配空间
     * @param p 分配区间的前驱结点
     * @param len 所分配的长度
     */
    private void allocateMemory(Node p, int len) {
        if (p.next.freeSize > len) {
            p.next.freeSize -= len;
            p.next.initialAddress += len;
        } else {
            p.next = p.next.next;
        }
        head.freeSize -= len;
    }

    /*从装入内存的作业里调度一个可以投入运行的作业*/
    private Job pickJobFromMemory() {
        Job job = loadedQueue.poll();
        if (job != null) {
            job.setSt(new Time(systemTime.getHour(), systemTime.getMinute()));
            System.out.println("On job " + job.getName() + " gets scheduled at " + systemTime + ", partition state: " + partitionState());
            scheduleOrderQueue.add(job);
        }
        return job;
    }

    /*尽可能的从等待队列里往内存载入作业*/
    private void loadFromWaitingQueue() {
        Iterator<Job> iterator = waitingQueue.iterator();
        while (iterator.hasNext()) {
            Job job = iterator.next();
            Node space = enoughSpace(job);
            if (space != null) {
                loadedQueue.add(job);
                allocateMemory(space, job.getNc());
                iterator.remove();
            }
        }
    }

    private String partitionState() {
        Node p, q;
        p = head.next;
        StringBuffer buffer = new StringBuffer(100);
        buffer.append("Free Partition: ");
        while (p != null) {
            buffer.append(" [" + p.initialAddress + ", "
                    + (p.initialAddress + p.freeSize - 1) + "]");
            p = p.next;
        }
        return buffer.toString();
    }

    private void reclaimMemory(Job job) {
        Node front = head, back = front.next;
        int ia = job.getIa();

        Node j = new Node(ia, job.getNc(), null);

        while (front != null) {
            if (front.initialAddress <= ia && (back == null || back.initialAddress >= ia)) {
                break;
            } else {
                front = back;
                back = front.next;
            }
        }

        if (adjacent(j, back)) {
            j = merge(j, back);
        } else {
            j.next = back;
        }

        if (adjacent(front, j)) {
            front = merge(front, j);
        } else {
            front.next = j;
        }

        head.freeSize += job.getNc();
    }

    private boolean adjacent(Node front, Node back) {
        if (back == null || front == head) return false;
        return (front.initialAddress + front.freeSize == back.initialAddress);
    }

    /**
     * 合并两个相邻的空闲区
     * @return 合并后的空闲区节点
     */
    private Node merge(Node front, Node back) {
        front.freeSize += back.freeSize;
        front.next = back.next;
        return front;
    }

    private String[] getOutputInfo(Queue<Job> orderQ){
        Iterator<Job> iterator = orderQ.iterator();
        StringBuffer orderBuffer = new StringBuffer(20);
        StringBuffer timeBuffer = new StringBuffer(200);
        Job job;
        while (iterator.hasNext()) {
            job = iterator.next();
            orderBuffer.append(job.getName() + " ");
            timeBuffer.append("Job " + job.getName() + " : Starting Time: " + job.getSt() + " Finished Time: " + job.getFt() + '\n');
        }
        String[] ans =  {orderBuffer.toString(), timeBuffer.toString()};
        return ans;
    }

    private void executeCurrentJob() {

        systemTime.increaseByMinute();

        /*让当前正在执行的作业执行一分钟*/
        currentExecutingJob.executeByMinite();

        /*如果执行完毕*/
        if (currentExecutingJob.finished()) {
            currentExecutingJob.setFt(new Time(systemTime.getHour(), systemTime.getMinute()));
            currentExecutingJob.calculateTurnover();
            reclaimMemory(currentExecutingJob);//回收执行完毕的作业的空间
            currentExecutingJob = pickJobFromMemory();
            loadFromWaitingQueue();
        }
    }

    public void printScheduleInfo() {
        /*输出这批作业的调度信息*/
        String[] info = getOutputInfo(scheduleOrderQueue);
        System.out.println("Schedule Order: " + info[0]);
        System.out.println("Schedule of Each Job:\n" + info[1]);
        double mtt = 0, mwt = 0;//平均周转时间和平均带权周转时间
        for (Job job : scheduleOrderQueue) {
            mtt += job.getTt();
            mwt += job.getWt();
        }
        mtt /= newestJobIndex;
        mwt /= newestJobIndex;
        System.out.println(SEPERATOR + "\nMean Turnover Time: " + mtt + " minutes.");
        System.out.println(SEPERATOR + "\nMean Weighted Turnover Time: " + mwt + " minutes.");
    }
}