import java.util.Scanner;

public class Main {

    public static void main(String[] args) {







        int n ; //number of rows in the array / processes on the system
        int m ; //the number of columns in array / different types of resources. Resource A, B, C, and D add up to 4

        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter the number of processes present on the system: ");
        n = scanner.nextInt();
        System.out.print("Enter the number of different types of resources there are: ");
        m = scanner.nextInt();

        int[] total = new int[m]; //total resources present on the system
        System.out.print("Enter the total amount of each resource present on the system (Order matters - type the number and press enter for each resource type): ");
        for(int k = 0; k < m; k++){
            total[k] = scanner.nextInt();
        }

        int[][] allocation = new int[n][m]; //resources currently allocated to the process
        System.out.println("Enter the resources currently allocated to each process. Preserve the resource type order you entered previously: ");
        for(int k1 = 0; k1 < n; k1++){ //for each process
            System.out.println("Enter the resources allocated to process " + k1 + ":");
            for(int k2 = 0; k2 < m; k2++){
                allocation[k1][k2] = scanner.nextInt();
            }
        }

        int[][] max = new int[n][m]; //maximum resources the process needs to complete execution
        System.out.println("Enter the maximum resources each process needs. Preserve the resource type order you entered previously: ");
        for(int k1 = 0; k1 < n; k1++){ //for each process
            System.out.println("Enter the maximum resources needed by process " + k1 + ":");
            for(int k2 = 0; k2 < m; k2++){
                max[k1][k2] = scanner.nextInt();
            }
        }

        System.out.println("Calculating available resources...");
        int[] available = new int[m]; //total resources available after allocation
        int[] totalAlloc = new int[m]; //all allocated resources added up - needed to calculate available
        for(int k1 = 0; k1 < m; k1++){ //for each COLUMN
            totalAlloc[k1] = 0; //initialize to zero first
            for(int k2 = 0; k2 < n; k2++){
                totalAlloc[k1] += allocation[k2][k1];
            }
            available[k1] = total[k1] - totalAlloc[k1]; //subtract the total allocated of a resource type from the total
        }


        //Calculating need matrix
        System.out.println("Calculating need matrix...");
        int[][] need = new int[n][m]; //resources that a process still needs in order to successfully execute
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                need[i][j] = max[i][j] - allocation[i][j];
            }
        }

        System.out.println("Determining if the system is currently in a safe state...");
        if(runSafetyAlgorithm(need, available, allocation, n, m)){
            System.out.println("The system is in a safe state!");
        }
        else{
            System.out.println("The system is in an UNSAFE state!");
        }

        //handling requests
        boolean x = true;
        boolean granted;
        int input;
        while(x){
            System.out.println("Enter the process number of your request: ");
            int reqNum = scanner.nextInt();
            System.out.println("Enter the resources this process would like to request (preserve the order as previously): ");
            for(int j = 0; j < m; j++){
                input = scanner.nextInt();
                allocation[reqNum][j] += input;
                available[j] -= input;


            }
            //Re-Calculating need matrix
            System.out.println("Calculating need matrix...");
            for(int i = 0; i < n; i++){
                for(int j = 0; j < m; j++){
                    need[i][j] = max[i][j] - allocation[i][j];
                }
            }
            if(runSafetyAlgorithm(need, available, allocation, n, m)){
                System.out.println("The system is in a safe state, so the request has been granted!");

            }
            else{
                System.out.println("This request would leave the system in an unsafe state. The bank denies the request.");
            }
            System.out.println("Would you like to enter another request from this new state? (y/n): ");
            String input2 = scanner.next();
            if(input2.equals("y")){
                //do nothing, go to beginning of while loop
            }
            else{
                System.out.println("Exiting...");
                x = false; //end the while loop and exit program
            }
        }



    }

    public static boolean runSafetyAlgorithm(int[][] need, int[] available, int [][] allocation, int n, int m){

        //BEGINNING OF SAFETY ALGORITHM
        //set work[][] = available[][] or unnecessary ?
        boolean[] finish = new boolean[n]; //keeping track of whether a process has finished executing
        //all processes have not finished at first - set all to false (using i instead of j here because we are dealing with columns)
        for(int i = 0; i < n; i++){
            finish[i] = false;
        }

        //while(!isFinished(finish)){ //while there is still a process that is not finished...
        //I chose to repeat for the # of processes instead, because it is possible that a process will never finish (unsafe state in this case)
        for(int i = 0; i < n; i++){

            for(int i2 = 0; i2 < n; i2++){ //iterate through all processes (using i instead of j here because we are dealing with columns)
                //if a process has not finished yet and its needs are less than what is available
                if((finish[i2] == false) && (needLessThanAvailable(need[i2], available, m))){

                    for(int j = 0; j < m; j++){
                        available[j] += allocation[i2][j];
                    }
                    finish[i2] = true;
                }
            }


        }

        //determine if the system is in a safe state or not
        boolean SafeState;
        if(isFinished(finish)){
            SafeState = true;
        }
        else{
            SafeState = false;
        }
        return SafeState;

        //END OF SAFETY ALGORITHM
    }

    //return true if all processes have finished executing
    public static boolean isFinished(boolean[] finish){
        for (boolean b : finish) {
            if (b == false) {
                return false;
            }
        }
        return true;
    }

    //return true if the resource needs of a process are less than what is available
    public static boolean needLessThanAvailable(int[] need, int [] available, int m){
        for(int j = 0; j < m; j++){
            if(need[j] > available[j]){
                return false;
            }
        }
        return true;
    }




}