package scheduler;
import java.io.*;
import java.lang.*;
import java.math.*;
import java.util.*;
/**
 * <p>Title: </p>
 * <p>Description: </p>
 * <p>Copyright: Copyright (c) 2003</p>
 * <p>Company: </p>
 * @author not attributable
 * @version 1.0
 */

public class scheduler {
  public static int numberOfMachines = 3;
  public static Vector[] MachineQueues = new Vector[numberOfMachines+1];
  public static Vector[] PossibleJobs = new Vector[numberOfMachines+1];
  public static planNode[] plans;
  public static Vector jobsList = new Vector();
  public static int timeStep = 1;
  public static planNode Solution;
  public static Vector currentNodes;
  public static Vector allNodes;
  public static planNode nullPlan = new planNode();
  public static boolean nosolution=true;
  public static int forwardSolutions;
  public static int backwardSolutions;
  public static int greedyforwardSolutions;
  public static int forwardCost;
  public static int backwardCost;
  public static int fgreedyCost;
  public static int bgreedyCost;
  public static int forwardTime;
  public static int backwardTime;
  public static int fgreedyTime;
  public static int bgreedyTime;

  public static int exforwardSolutions;
  public static int exbackwardSolutions;
  public static int exforwardCost;
  public static int exbackwardCost;
  public static int exforwardTotalCost;
  public static int exbackwardTotalCost;

  public scheduler() {
    nosolution = true;
  }


  public static void main(String args[]){
    int jobs=0;
    int m = 3;
    try {
      for (int j=2; j<= 7; j++) {
        for (int k = 2; k <= 5; k++) {
          jobs = k;
          FileOutputStream fostest = new FileOutputStream("J" + j + "M" + m +
                  "S" +
                  jobs + "FGminFBmin");
         Writer wtest = new BufferedWriter(new OutputStreamWriter(fostest));

          for (int l = 1; l <= 30 ; l++) {
            scheduler schedule = new scheduler();

            for (int q = 0; q <= numberOfMachines; q++) {
              MachineQueues[q] = new Vector();
            }
            randomjob myJob; //myJob to be of type randmonjob

            for (int i = 1; i <= jobs; i++) {
              //myJob = new randomjob(i); // create a Job with random jobs up to 5.
              myJob = new randomjob(i, jobs);
              myJob.display();
              wtest.write("SubJobs:" + jobs+"\n");
              for (int p = 1; p <= jobs; p++){
                subjob thisjob = (subjob) myJob.subjobs.get(p);  // get the subjob to display
                // index starts at one
                thisjob.display();
                wtest.write("Job #:" + thisjob.subjobNumber + " timeRequired: " + thisjob.timeRequired + " machine #" + thisjob.machineNumber+"\n");
              }


              schedule.loadMachineQueues(myJob);
            }

            schedule.forwardStateSpace();
            schedule.backwardStateSpace();
            schedule.ForwardStateSpaceGreedyH();
            schedule.BackwardStateSpaceGreedyH();
            //schedule.exhaustiveFackwardStateSpace();
            //schedule.exhaustiveBackwardStateSpace();


              wtest.write("JOBS: " + jobs + "\n");
              wtest.write(
                  "     \tForward     \tGreedy     \tBackward     \tGreedy" +
                  "\n");
              wtest.write("-------------------------------------------------------------------------------" +
                          "\n");
              wtest.write("Cost:\t" + (forwardCost - 1) + "\t\t" +
                          (fgreedyCost - 1) +
                          "\t\t" + (backwardCost - 1) + "\t\t" + (bgreedyCost - 1) +
                          "\n");
              wtest.write("TIME:\t" + forwardTime + "\t\t" + fgreedyTime + "\t\t" +
                          backwardTime + "\t\t" + bgreedyTime + "\t\t" + "\n");

            }
            wtest.flush();
            wtest.close();
          }


       }
      } catch (Exception e) {
        e.printStackTrace();
      }

      System.out.println("JOBS: " + jobs);
      System.out.println("     \tForward     \tGreedy     \tBackward     \tGreedy");
      System.out.println("-------------------------------------------------------------------------------");
      System.out.println("Cost:\t" + (forwardCost-1)+ "\t\t" + (fgreedyCost-1)+ "\t\t" + (backwardCost-1) + "\t\t" + (bgreedyCost-1));
      //System.out.println("#   :  " + forwardSolutions + "\t\t" + backwardSolutions+"\t\t" + greedyforwardSolutions);
      System.out.println("TIME:\t" + forwardTime + "\t\t" + fgreedyTime + "\t\t" + backwardTime + "\t\t" + bgreedyTime + "\t\t");
      //System.out.println("Cost(1st):  " + (exforwardCost-1)+ "\t\t"+ (exbackwardCost-1));
      //System.out.println("Total #sol: " + exforwardSolutions + "\t\t" + exbackwardSolutions);
      //System.out.println("Total Cost: " + exforwardTotalCost + "\t\t" + exbackwardTotalCost);
    }

    public static int numberOfJob(int n,Vector v){
    int temp = 0;
    for (int i = 0; i < v.size(); i++){
       subjob s = (subjob) v.get(i);
       if (s.subjobNumber == n) {
         temp++;
       }
     }
     return temp;
   }

  public static int numberPlanTrees(){
    int temp=1;
    int numJobs;
      for (int i = 1; i <= numberOfMachines; i++){
          numJobs = numberOfJob(1,MachineQueues[i]);
          if (numJobs > 0) {
            temp *= numJobs;
          }
      }
    return temp;

  }

  public static int numberBackPlanTrees(int maxSubjob){
    int temp=1;
    boolean trueNum = false;
    int numJobs;
      for (int i = 1; i <= numberOfMachines; i++){
          numJobs = numberOfJob(maxSubjob,MachineQueues[i]);
          if (numJobs > 0) {
            temp *= numJobs;
            trueNum = true;
          }
      }
      if (trueNum) {
        return temp;
      } else {
        return 0;
      }

  }

  public static void forwardStateSpace(){
    //use the forward state space algorithm to plan
    //initial state: no jobs on no machines
    // actions: start job on machine #, finish job
    // constraints: job n done before job n+1
    //              job x is done when last subjob done
    // goal test: all jobs are in done status
    // step cost: 1 per action (
    //
    //possible actions:
    //assign subjobs to machine
    //
    //make all possible plans, pick the shortest in time
    //for the beginning state:
    //for each job, if possible, start a new plan for that
    //get number of state plans:


    //set first nodes
    //int numberPlanNodes = numberPlanTrees();
    int numberPlanNodes;
    int Cost = 0;
    boolean nosolution = true;
    forwardSolutions = 0;
   //System.out.println("#of intial values:" + numberPlanNodes);
    numberPlanNodes = 1;
    plans = new planNode[numberPlanNodes+1];
    for (int j = 1; j <= numberPlanNodes; j++) {
        plans[j] = new planNode(numberOfMachines, MachineQueues);
    }
    //get the initial states
    //allNodes = new Vector();
    while (nosolution) {
      allNodes = new Vector();

      for (int j = 1; j <= numberPlanNodes; j++) {
        Cost++;
        plans[j].updateTime(1);
        //unload done jobs;
        plans[j].unload();
        if (plans[j].isDone() ){
          forwardSolutions++;
          //System.out.println("is done: ");
          //plans[j].printPlan();
          if (nosolution) {
            Solution = plans[j];
            forwardTime = plans[j].totaltime;
            nosolution = false;
            forwardCost = Cost;
          }
          break;
        }
        currentNodes = new Vector();
        mylist L = new mylist();
        Vector[] possibilities = new Vector[numberOfMachines+1];
        for (int q = 1; q <= numberOfMachines; q++){
          possibilities[q] = new Vector();
        }
        possibilities = (Vector []) getPossible(plans[j]);
        getList(numberOfMachines, possibilities, L);
        //add the new possibilities to planNodes

        //make new planNodes
        planNode p = new planNode();
        p.copy(plans[j]);
        planNode[] currentPlans = new planNode[currentNodes.size()+1];

        for (int i = 1; i <= currentNodes.size(); i++) {
          currentPlans[i] = new planNode(plans[j]);
          mylist vec = (mylist) currentNodes.get(i-1);

          for (int k = 0; k < vec.size(); k++) {

            subjob st = (subjob) vec.get(k);
            subjob s =  new subjob(st.jobNumber,st.machineNumber,st.subjobNumber,st.timeRequired,st.numSubjobs);
            currentPlans[i].add(s.machineNumber,s);
          }
        }
          for (int m=1; m < currentPlans.length; m++) {
            allNodes.add(currentPlans[m]);
          }
      } //for each plans
      //copy all allNodes into plans[];
      numberPlanNodes = allNodes.size();
      plans = new planNode[numberPlanNodes + 1];
      for (int i = 1; i <=numberPlanNodes; i++){
        plans[i] = new planNode();
        plans[i] = (planNode) allNodes.get(i-1);
      }
    }//end while(nosolution)
    //System.out.println("Forward:Solution in time " + Solution.totaltime + ":");
    //Solution.print();
  }

  public static void exhaustiveForwardStateSpace(){
     int numberPlanNodes;
     int Cost = 0;
     boolean notalldone = true;
     exforwardSolutions = 0;
    //System.out.println("#of intial values:" + numberPlanNodes);
     numberPlanNodes = 1;
     plans = new planNode[numberPlanNodes+1];
     for (int j = 1; j <= numberPlanNodes; j++) {
         plans[j] = new planNode(numberOfMachines, MachineQueues);
     }
     //get the initial states
     //allNodes = new Vector();
     while (notalldone) {
       notalldone = false;
       allNodes = new Vector();

       for (int j = 1; j <= numberPlanNodes; j++) {
         Cost++;
         plans[j].updateTime(1);
         //unload done jobs;
         plans[j].unload();
         if (plans[j].isDone() ){
           exforwardSolutions++;
           if (nosolution) {
             Solution = plans[j];
             nosolution = false;
             exforwardCost = Cost;
           }
           //break;
         } else {
           notalldone = true; //not all jobs are done.
         }
         currentNodes = new Vector();
         mylist L = new mylist();
         Vector[] possibilities = new Vector[numberOfMachines+1];
         for (int q = 1; q <= numberOfMachines; q++){
           possibilities[q] = new Vector();
         }
         possibilities = (Vector []) getPossible(plans[j]);
         getList(numberOfMachines, possibilities, L);
         //add the new possibilities to planNodes

         //make new planNodes
         planNode p = new planNode();
         p.copy(plans[j]);
         planNode[] currentPlans = new planNode[currentNodes.size()+1];

         for (int i = 1; i <= currentNodes.size(); i++) {
           currentPlans[i] = new planNode(plans[j]);
           mylist vec = (mylist) currentNodes.get(i-1);

           for (int k = 0; k < vec.size(); k++) {

             subjob st = (subjob) vec.get(k);
             subjob s =  new subjob(st.jobNumber,st.machineNumber,st.subjobNumber,st.timeRequired,st.numSubjobs);
             currentPlans[i].add(s.machineNumber,s);
           }
         }
           for (int m=1; m < currentPlans.length; m++) {
             allNodes.add(currentPlans[m]);
           }
       } //for each plans
       //copy all allNodes into plans[];
       numberPlanNodes = allNodes.size();
       plans = new planNode[numberPlanNodes + 1];
       for (int i = 1; i <=numberPlanNodes; i++){
         plans[i] = new planNode();
         plans[i] = (planNode) allNodes.get(i-1);
       }
     }//end while(nosolution)
     System.out.println("ExhaustiveForward: Solution in time " + Solution.totaltime + ":");
     exforwardTotalCost = Cost;
     //Solution.print();
   }

   public static void ForwardStateSpaceGreedyH(){
     int numberPlanNodes;
     int Cost = 0;
     boolean notalldone = true;
     nosolution = true;
     greedyforwardSolutions = 0;
    //System.out.println("#of intial values:" + numberPlanNodes);
     numberPlanNodes = 1;
     plans = new planNode[numberPlanNodes+1];
     for (int j = 1; j <= numberPlanNodes; j++) {
         plans[j] = new planNode(numberOfMachines, MachineQueues);
     }
     //get the initial states
     //allNodes = new Vector();
     while (nosolution) {
       //notalldone = false;
       allNodes = new Vector();

       for (int j = 1; j <= numberPlanNodes; j++) {
         Cost++;
         plans[j].updateTime(1);
         //unload done jobs;
         plans[j].unload();
         if (plans[j].isDone() ){
           greedyforwardSolutions++;
           if (nosolution) {
             Solution = plans[j];
             nosolution = false;
             fgreedyCost = Cost;
             fgreedyTime = plans[j].totaltime;
             break;
           }
         }

         currentNodes = new Vector();
         mylist L = new mylist();
         Vector[] possibilities = new Vector[numberOfMachines+1];
         for (int q = 1; q <= numberOfMachines; q++){
           possibilities[q] = new Vector();
         }
         possibilities = (Vector []) getPossibleGreedy(plans[j]);
         getList(numberOfMachines, possibilities, L);
         //add the new possibilities to planNodes

         //make new planNodes
         planNode p = new planNode();
         p.copy(plans[j]);
         planNode[] currentPlans = new planNode[currentNodes.size()+1];

         for (int i = 1; i <= currentNodes.size(); i++) {
           currentPlans[i] = new planNode(plans[j]);
           mylist vec = (mylist) currentNodes.get(i-1);

           for (int k = 0; k < vec.size(); k++) {
             subjob st = (subjob) vec.get(k);
             subjob s =  new subjob(st.jobNumber,st.machineNumber,st.subjobNumber,st.timeRequired,st.numSubjobs);
             currentPlans[i].add(s.machineNumber,s);
           }
         }
           for (int m=1; m < currentPlans.length; m++) {
             allNodes.add(currentPlans[m]);
           }
       } //for each plans
       //copy all allNodes into plans[];
       numberPlanNodes = allNodes.size();
       plans = new planNode[numberPlanNodes + 1];
       for (int i = 1; i <=numberPlanNodes; i++){
         plans[i] = new planNode();
         plans[i] = (planNode) allNodes.get(i-1);
       }
     }//end while(nosolution)
     //System.out.println("Greedy Heuristic: Solution in time " + Solution.totaltime + ":");
     //forwardTotalGreedyCost = Cost;
     //Solution.print();
   }

   public static void backwardStateSpace(){
  //use the backward state space algorithm to plan
  //initial state: all jobs finished
  // actions: unstart job on machine #, finish job
  // constraints: job n+1 undone before job n
  //              job x is undone when all jobs undone
  // goal test: all jobs are in undone status
  // step cost: 1 per action (
  //
  //possible actions:
  //assign subjobs to machine
  //
  //make all possible plans, pick the shortest in time
  //for the beginning state:
  //for each job, if possible, start a new plan for that
  //get number of state plans:

  nosolution = true;
  backwardSolutions = 0;
  int Cost = 0;
  //set first nodes
  //look for jobs with the maximum subjob numbers
  // while there are none,
  int numberPlanNodes = 0;
  int n = 6; //set n to one greater than the number of backplans
   while (numberPlanNodes < 1 ){
     numberPlanNodes = numberBackPlanTrees(n);
     n--;
   }
  //System.out.println("#of intial values:" + numberPlanNodes);

  numberPlanNodes = 1;
  plans = new planNode[numberPlanNodes+1];
  for (int j = 1; j <= numberPlanNodes; j++) {
      plans[j] = new planNode(numberOfMachines, MachineQueues);
  }
  //get the initial states
  while (nosolution) {
    allNodes = new Vector();
    for (int j = 1; j <= numberPlanNodes; j++) {
      plans[j].updateTime(1);
      Cost++;  // keep track of each step, cost one,
      //creating each element of the tree.

      //unload done jobs;
      plans[j].unload();
      if (plans[j].isDone() ){
        backwardSolutions++;
        if (nosolution) {
          nosolution = false;
          Solution = plans[j];
          backwardCost = Cost;
          backwardTime = plans[j].totaltime;
        }
        break;
      }
      currentNodes = new Vector();
      mylist L = new mylist();
      Vector[] possibilities = new Vector[numberOfMachines+1];
      for (int q = 1; q <= numberOfMachines; q++){
        possibilities[q] = new Vector();
      }
      possibilities = (Vector []) getBackPossible(plans[j]);
      getList(numberOfMachines, possibilities, L);
      //add the new possibilities to planNodes

      //make new planNodes
      planNode p = new planNode();
      p.copy(plans[j]);
      planNode[] currentPlans = new planNode[currentNodes.size()+1];

      for (int i = 1; i <= currentNodes.size(); i++) {
        currentPlans[i] = new planNode(plans[j]);
        mylist vec = (mylist) currentNodes.get(i-1);

        for (int k = 0; k < vec.size(); k++) {

          subjob st = (subjob) vec.get(k);
          subjob s =  new subjob(st.jobNumber,st.machineNumber,st.subjobNumber,st.timeRequired,st.numSubjobs);
          currentPlans[i].add(s.machineNumber,s);
        }
      }
        for (int m=1; m < currentPlans.length; m++) {
          allNodes.add(currentPlans[m]);
        }
    } //for each plans
    //copy all allNodes into plans[];
    numberPlanNodes = allNodes.size();
    plans = new planNode[numberPlanNodes + 1];
    for (int i = 1; i <=numberPlanNodes; i++){
      plans[i] = new planNode();
      plans[i] = (planNode) allNodes.get(i-1);
    }
  }//end while(nosolution)
  //System.out.println("Backward:Solution in time " + Solution.totaltime + ":");
  //Solution.printBack();
}

public static void BackwardStateSpaceGreedyH(){
 //use the backward state space algorithm to plan
 //initial state: all jobs finished
 // actions: unstart job on machine #, finish job
 // constraints: job n+1 undone before job n
 //              job x is undone when all jobs undone
 // goal test: all jobs are in undone status
 // step cost: 1 per action (
 //
 //possible actions:
 //assign subjobs to machine
 //
 //make all possible plans, pick the shortest in time
 //for the beginning state:
 //for each job, if possible, start a new plan for that
 //get number of state plans:

 nosolution = true;
 backwardSolutions = 0;
 int Cost = 0;
 //set first nodes
 //look for jobs with the maximum subjob numbers
 // while there are none,
 int numberPlanNodes = 0;
 int n = 6; //set n to one greater than the number of backplans
  while (numberPlanNodes < 1 ){
    numberPlanNodes = numberBackPlanTrees(n);
    n--;
  }
 //System.out.println("#of intial values:" + numberPlanNodes);

 numberPlanNodes = 1;
 plans = new planNode[numberPlanNodes+1];
 for (int j = 1; j <= numberPlanNodes; j++) {
     plans[j] = new planNode(numberOfMachines, MachineQueues);
 }
 //get the initial states
 while (nosolution) {
   allNodes = new Vector();
   for (int j = 1; j <= numberPlanNodes; j++) {
     plans[j].updateTime(1);
     Cost++;  // keep track of each step, cost one,
     //creating each element of the tree.

     //unload done jobs;
     plans[j].unload();
     if (plans[j].isDone() ){
       backwardSolutions++;
       if (nosolution) {
         nosolution = false;
         Solution = plans[j];
         bgreedyCost = Cost;
         bgreedyTime = plans[j].totaltime;
       }
       break;
     }
     currentNodes = new Vector();
     mylist L = new mylist();
     Vector[] possibilities = new Vector[numberOfMachines+1];
     for (int q = 1; q <= numberOfMachines; q++){
       possibilities[q] = new Vector();
     }
     possibilities = (Vector []) getBackGreedyPossible(plans[j]);
     getList(numberOfMachines, possibilities, L);
     //add the new possibilities to planNodes

     //make new planNodes
     planNode p = new planNode();
     p.copy(plans[j]);
     planNode[] currentPlans = new planNode[currentNodes.size()+1];

     for (int i = 1; i <= currentNodes.size(); i++) {
       currentPlans[i] = new planNode(plans[j]);
       mylist vec = (mylist) currentNodes.get(i-1);

       for (int k = 0; k < vec.size(); k++) {

         subjob st = (subjob) vec.get(k);
         subjob s =  new subjob(st.jobNumber,st.machineNumber,st.subjobNumber,st.timeRequired,st.numSubjobs);
         currentPlans[i].add(s.machineNumber,s);
       }
     }
       for (int m=1; m < currentPlans.length; m++) {
         allNodes.add(currentPlans[m]);
       }
   } //for each plans
   //copy all allNodes into plans[];
   numberPlanNodes = allNodes.size();
   plans = new planNode[numberPlanNodes + 1];
   for (int i = 1; i <=numberPlanNodes; i++){
     plans[i] = new planNode();
     plans[i] = (planNode) allNodes.get(i-1);
   }
 }//end while(nosolution)
 //System.out.println("Backward:Solution in time " + Solution.totaltime + ":");
 //Solution.printBack();
}

public static void exhaustiveBackwardStateSpace(){

  boolean allnotdone = true;
  nosolution = true;
  exbackwardSolutions = 0;
  int Cost = 0;
  //set first nodes
  //look for jobs with the maximum subjob numbers
  // while there are none,
  int numberPlanNodes = 0;
  int n = 6; //set n to one greater than the number of backplans
   while (numberPlanNodes < 1 ){
     numberPlanNodes = numberBackPlanTrees(n);
     n--;
   }
  //System.out.println("#of intial values:" + numberPlanNodes);

  numberPlanNodes = 1;
  plans = new planNode[numberPlanNodes+1];
  for (int j = 1; j <= numberPlanNodes; j++) {
      plans[j] = new planNode(numberOfMachines, MachineQueues);
  }
  //get the initial states
  while (allnotdone) {
    allnotdone = false;
    allNodes = new Vector();
    for (int j = 1; j <= numberPlanNodes; j++) {
      Cost++;  // keep track of each step, cost one,
      plans[j].updateTime(1);
      //creating each element of the tree.
      //unload done jobs;
      plans[j].unload();
      if (plans[j].isDone() ){
        exbackwardSolutions++;
        if (nosolution) {
          nosolution = false;
          Solution = plans[j];
          exbackwardCost = Cost;
        }
        //break;
      } else {
          allnotdone = true;
      }

      currentNodes = new Vector();
      mylist L = new mylist();
      Vector[] possibilities = new Vector[numberOfMachines+1];
      for (int q = 1; q <= numberOfMachines; q++){
        possibilities[q] = new Vector();
      }
      possibilities = (Vector []) getBackPossible(plans[j]);
      getList(numberOfMachines, possibilities, L);
      //add the new possibilities to planNodes

      //make new planNodes
      planNode p = new planNode();
      p.copy(plans[j]);
      planNode[] currentPlans = new planNode[currentNodes.size()+1];

      for (int i = 1; i <= currentNodes.size(); i++) {
        currentPlans[i] = new planNode(plans[j]);
        mylist vec = (mylist) currentNodes.get(i-1);

        for (int k = 0; k < vec.size(); k++) {

          subjob st = (subjob) vec.get(k);
          subjob s =  new subjob(st.jobNumber,st.machineNumber,st.subjobNumber,st.timeRequired,st.numSubjobs);
          currentPlans[i].add(s.machineNumber,s);
        }
      }
        for (int m=1; m < currentPlans.length; m++) {
          allNodes.add(currentPlans[m]);
        }
    } //for each plans
    //copy all allNodes into plans[];
    numberPlanNodes = allNodes.size();
    plans = new planNode[numberPlanNodes + 1];
    for (int i = 1; i <=numberPlanNodes; i++){
      plans[i] = new planNode();
      plans[i] = (planNode) allNodes.get(i-1);
    }
  }//end while(nosolution)
  exbackwardTotalCost = Cost;
  //System.out.println("Exhaustive Backward: Solution in time " + Solution.totaltime + ":");
  //Solution.printBack();
}

  public static void getList(int level, Vector[] possible ,mylist L){

    if (level == 1) {
      if (possible[level].size() == 0)
      {
          mylist newlist = new mylist();
          newlist.copy(L);
          currentNodes.add(newlist);
      } else {
        for (int i =0; i < possible[level].size() ; i++){
          subjob s = (subjob) possible[level].get(i);
          L.add(s);
          mylist newlist = new mylist();
          newlist.copy(L);
          currentNodes.add(newlist);
          L.remove(s);
        }
      }
    } else {
        if ( possible[level].size() == 0 ) {
          getList(level-1,possible,L);
        }
        for (int j =0; j < possible[level].size(); j++){
          subjob st = (subjob) possible[level].get(j);
          L.add(st);
          getList(level-1,possible,L);
          L.remove(st);
        }
      }
    }

  public static Vector[] getPossible(planNode pn){

    Vector[] Possible = new Vector[numberOfMachines + 1];
    for (int j = 1; j <= numberOfMachines; j++) {
      Possible[j] = new Vector();
    }

    Vector jobs = pn.getNextJobs();
    //System.out.println("got jobs: " + jobs.size() );
    for (int i = 0; i < jobs.size(); i++) {
      subjob s = (subjob) jobs.get(i);
      Possible[s.machineNumber].add(s);
    }
    //each possible job
   //try adding the null possiblity
   //for (int i = 1; i <= numberOfMachines; i++){
   //  subjob st = new subjob();
   //  st.machineNumber = i;
   //  Possible[i].add(st);
   //}
   //try adding null
    return Possible;
  }

  public static Vector[] getPossibleGreedy(planNode pn){

     Vector[] Possible = new Vector[numberOfMachines + 1];
     for (int j = 1; j <= numberOfMachines; j++) {
       Possible[j] = new Vector();
     }

     Vector jobs = pn.getNextJobs();
     //System.out.println("got jobs: " + jobs.size() );
     for (int i = 0; i < jobs.size(); i++) {
       subjob s = (subjob) jobs.get(i);
       Possible[s.machineNumber].add(s);
     }
     //for each possible get the min
     for (int j = 1; j <= numberOfMachines; j++){
       if (Possible[j].size() > 1) {
         subjob minS = (subjob) Possible[j].get(0);
         int min = minS.timeRequired;
         for (int k=1; k < Possible[j].size(); k++){
           subjob test = (subjob) Possible[j].get(k);
           if (test.timeRequired < min) {
             minS = test;
             min = minS.timeRequired;
           }
         }
         Possible[j].clear();
         Possible[j].add(minS);
       }
     }
     //each possible job
    //try adding the null possiblity
    //for (int i = 1; i <= numberOfMachines; i++){
    //  subjob st = new subjob();
    //  st.machineNumber = i;
    //  Possible[i].add(st);
    //}
    //try adding null
     return Possible;
   }

  public static Vector[] getBackPossible(planNode pn){

    Vector[] Possible = new Vector[numberOfMachines + 1];
    for (int j = 1; j <= numberOfMachines; j++) {
      Possible[j] = new Vector();
    }

    Vector jobs = pn.getNextBackJobs();
    //System.out.println("got jobs: " + jobs.size() );
    for (int i = 0; i < jobs.size(); i++) {
      subjob s = (subjob) jobs.get(i);
      Possible[s.machineNumber].add(s);
    }
    //each possible job
    return Possible;
  }
  public static Vector[] getBackGreedyPossible(planNode pn){

      Vector[] Possible = new Vector[numberOfMachines + 1];
      for (int j = 1; j <= numberOfMachines; j++) {
        Possible[j] = new Vector();
      }

      Vector jobs = pn.getNextBackJobs();
      //System.out.println("got jobs: " + jobs.size() );
      for (int i = 0; i < jobs.size(); i++) {
        subjob s = (subjob) jobs.get(i);
        Possible[s.machineNumber].add(s);
      }
      //each possible job
      //for each possible get the min
      for (int j = 1; j <= numberOfMachines; j++){
        if (Possible[j].size() > 1) {
          subjob minS = (subjob) Possible[j].get(0);
          int min = minS.timeRequired;
          for (int k=1; k < Possible[j].size(); k++){
            subjob test = (subjob) Possible[j].get(k);
            if (test.timeRequired < min) {
              minS = test;
              min = minS.timeRequired;
            }
          }
          Possible[j].clear();
          Possible[j].add(minS);
          /*subjob maxS = (subjob) Possible[j].get(0);
          int max = maxS.timeRequired;
          for (int k=1; k < Possible[j].size(); k++){
            subjob test = (subjob) Possible[j].get(k);
            if (test.timeRequired > max) {
              maxS = test;
              max = maxS.timeRequired;
            }
          }
          Possible[j].clear();
          Possible[j].add(maxS);*/

        }
      }

      return Possible;
    }


  public static void loadMachineQueues(randomjob job){
    for (int i = 1; i <= job.numberSubJobs ; i++){
      subjob mySubJob = (subjob) job.subjobs.get(i);
      MachineQueues[mySubJob.machineNumber].add(mySubJob);
    }
  }
  public static void displayQueues(Vector[] Mach){
   for (int i = 1; i <= numberOfMachines ; i++){
     for (int j = 0; j < Mach[i].size() ; j++){
       subjob mySubJob = (subjob) Mach[i].get(j);
       System.out.println(" subjob #"+ mySubJob.subjobNumber +" of job #" + mySubJob.jobNumber + " on mach #" + i );
     }
     System.out.println("----------------------------------------------------------");
   }
 }


}
class planNode implements Cloneable{
  public boolean initialState;
  public Vector[] MachineQ; //what is left at this node to be loaded.
  public planNode previous;
  public Vector[] Machines; //the machine states at this node.
  public Vector Next;
  public int numberChildren;
  public int totaltime;
  public int numberOfMachines;
  public Vector Done;
  public int[] beginTimes;


//constructor for initial node of plan, set up machines
  public planNode(){
    Done = new Vector();
    initialState = true;
    numberChildren =0;
    numberOfMachines = 3;
    Machines = new Vector[4];
    MachineQ = new Vector[4];
    beginTimes = new int[4];
    for (int i = 1; i <= 3; i++){
      Machines[i] = new Vector();
      MachineQ[i] = new Vector();
      beginTimes[i]= 0 ;
    }
    totaltime = -1;
  }

  public planNode(planNode p){
    this.initialState = false;
    this.Done = new Vector();
    this.Done = (Vector) p.Done.clone();
    this.numberChildren = p.numberChildren;
    this.numberOfMachines = p.numberOfMachines;
    this.previous = p;
    this.Machines = new Vector[numberOfMachines+1];
    this.MachineQ = new Vector[numberOfMachines+1];
    this.beginTimes = new int[numberOfMachines+1];
   // this.beginTimes = (int[]) p.beginTimes.clone();
    for (int i = 1; i <= numberOfMachines; i++){
     this.MachineQ[i] = (Vector) p.MachineQ[i].clone();
     this.Machines[i] = (Vector) p.Machines[i].clone();
     this.beginTimes[i] = p.beginTimes[i];
   }
   this.totaltime = p.totaltime;
 }

  //constructor for initialstate
  public planNode(int mach, Vector[] MQs){
    Done = new Vector();
    initialState = true;
    numberChildren =0;
    numberOfMachines = mach;
    Machines = new Vector[mach+1];
    MachineQ = new Vector[mach+1];

    beginTimes = new int[mach+1];

    for (int i = 1; i <= mach; i++){
      Machines[i] = new Vector();
      MachineQ[i] = (Vector) MQs[i].clone();
      beginTimes[i]= 0;
    }
    totaltime = -1;
  }
  public planNode(int mach, planNode p){
    initialState = false;
    Done = new Vector();
    Done = (Vector) p.Done.clone() ;
    numberChildren =0;
    numberOfMachines = mach;
    previous = p;
    Machines = new Vector[mach+1];
    MachineQ = new Vector[mach+1];
    beginTimes = new int[mach+1];

    for (int i = 1; i <= mach; i++){
      MachineQ[i] = (Vector) p.MachineQ[i].clone();
      Machines[i] = (Vector) p.Machines[i].clone();
      beginTimes[i] = p.beginTimes[i];
    }
    totaltime = p.totaltime;
  }

  public planNode copy(planNode p) {
    initialState = false;
    Done = new Vector();
    Done =(Vector) p.Done.clone();
    numberChildren = p.numberChildren;
    numberOfMachines = p.numberOfMachines;
    previous =  p.previous;
    Machines = new Vector[numberOfMachines+1];
    MachineQ = new Vector[numberOfMachines+1];
    beginTimes = new int[numberOfMachines+1];
    for (int i = 1; i <= numberOfMachines; i++){
      MachineQ[i] = (Vector)p.MachineQ[i].clone() ;
      Machines[i] = (Vector)p.Machines[i].clone();
      beginTimes[i] = p.beginTimes[i];
   }
   beginTimes = (int[]) p.beginTimes.clone();
   totaltime = p.totaltime;
   return this;
  }
  public Object clone(){
    try {
      return super.clone();
    } catch (CloneNotSupportedException e) {
      throw new InternalError("but we are cloneable!");

    }
 }

  public void setNext( Vector ps){
    numberChildren = ps.size();
    Next = new Vector();
    Next = ps;
  }

  public boolean isDone(){
    for (int i = 1; i <= numberOfMachines; i++){
      if (! (MachineQ[i].isEmpty())) {
        return false; //if machine Q is empty.
      }
      if ( ! (Machines[i].isEmpty() )){
        return false;// if machines are empty.
      }
    }
    return true;
  }

  public int numberPossible(){
    int temp=1;
    int numJobs=0;
    for (int i = 1; i <= numberOfMachines; i++){
      //numJobs = numberOfJob(1,MachineQueues[i]);
      int n=0; // counter for getting off MachineQ
      while (n < MachineQ[i].size()) {
        subjob st = (subjob) MachineQ[i].get(n);
        if (possible(st)) {
          //if possible
          numJobs++;
        }
        n++;
      }
      if (numJobs > 0) {
        temp *= numJobs;
      }
    }
    return temp;
  }

  public void updateTime(int n){
    totaltime+=n;
  }

   public void print (){
    if (!(initialState)) {
      previous.print();
      printPlan();
    }
  }
  public void printBack (){
    if (!(initialState)) {
      printPlan();
      previous.print();
    }
  }

  public void unload(){
    for (int i=1 ; i <= numberOfMachines; i++){
      if (!(this.Machines[i].isEmpty())){
        subjob s = (subjob) Machines[i].get(0);
        if ( (totaltime - beginTimes[i]) >= s.timeRequired) {
          Machines[i].remove(0);
          Done.add(s);
        }
      }
    }
  }


  public boolean MachinesEmpty(){
    for (int i =1; i <= numberOfMachines; i++){
      if (!(this.Machines[i].isEmpty())) {
        return false;
      }
     if(!(this.MachineQ[i].isEmpty())){
       return false;
     }
   }
   return true;
 }
 public boolean foundInQueues (int jn, int sjn){
   for (int i =1; i <= numberOfMachines; i++){
     for (int j = 0; j < MachineQ[i].size() ; j++) {
       subjob s = (subjob) MachineQ[i].get(j);
       if ((s.jobNumber == jn) && (s.subjobNumber == sjn)){
         return true;
       }
     }
   }
   return false;
 }

 public boolean onMachine(int jn, int sjn){
   for (int i =1; i <= numberOfMachines; i++){
     for (int j = 0; j < Machines[i].size() ; j++) {
       subjob s = (subjob) Machines[i].get(j);
       if ((s.jobNumber == jn) && (s.subjobNumber == sjn)){
         return true;
       }
     }
   }
   return false;
 }

 public boolean isDone(subjob s) {
   for (int i = 0; i < Done.size() ; i++){
     subjob st = (subjob) Done.get(i);
     if ((st.jobNumber == s.jobNumber) && (st.subjobNumber == s.subjobNumber)) {
       return true;
     }
   }
   return false;
 }
 public boolean possible (subjob s) {
   //if all subjobs previous are complete;
   for (int i = s.subjobNumber -1 ; i > 0; i--){
     if (foundInQueues(s.jobNumber, i))  {
       return false;
     }
     if (onMachine(s.jobNumber,i)) {
       return false;
     }
     if (isDone(s)){
       return false;
     }
   }
   return true;
 }

 public boolean possibleBack (subjob s) {
   //if all subjobs previous are complete;
   for (int i = s.subjobNumber + 1; i <= s.numSubjobs; i++){
     if (foundInQueues(s.jobNumber, i))  {
       return false;
     }
     if (onMachine(s.jobNumber,i)) {
       return false;
     }
     if (isDone(s)){
       return false;
     }
   }
   return true;
 }

 public Vector getNextJobs(){
   int n = 0;
   Vector jobs = new Vector();
   //if machine is not empty and job is done, unload machine:
   for (int i = 1; i <= this.numberOfMachines; i++){
     if (!(this.Machines[i].isEmpty())) {
       subjob s = (subjob) this.Machines[i].firstElement();
       //add subjob to possible states.
       jobs.add(s);
       //the job on is not finished, only possible job for this machine.
       continue; //goto next machine, for loop
     } else {
       if ( !(this.MachineQ[i].isEmpty())){
         //decide which jobs from Q are possible.
         for (int j = 0; j < MachineQ[i].size() ; j++){
           subjob s = (subjob) MachineQ[i].get(j);
           if (possible(s)) {
             jobs.add(s);
           } else {
             //System.out.println("not possible");
           }
         }
       }
     }
   }
   return jobs;
 }
 public Vector getNextBackJobs(){
   int n = 0;
   Vector jobs = new Vector();
   //System.out.println("In getNextjobs() + " + numberOfMachines);
   //if machine is not empty and job is done, unload machine:
   for (int i = 1; i <= this.numberOfMachines; i++){
     if (!(this.Machines[i].isEmpty())) {
       subjob s = (subjob) this.Machines[i].firstElement();
       jobs.add(s);
       //the job on is not finished, only possible job for this machine.
       continue; //goto next machine, for loop
     } else {
       if ( !(this.MachineQ[i].isEmpty())){
         //decide which jobs from Q are possible.
         for (int j = 0; j < MachineQ[i].size() ; j++){
           subjob s = (subjob) MachineQ[i].get(j);
           if (possibleBack(s)) {
             jobs.add(s);
           } else {
             //System.out.println("not possible");
           }
         }
       }
     }
   }
   return jobs;
 }

 public void add(int machNumber, subjob st){

   if (!(onMachine(st.jobNumber, st.subjobNumber))) {
     beginTimes[st.machineNumber]= totaltime;
   }
   Machines[machNumber].add(0,st); //add to machine, one element only

   if (Machines[machNumber].size()>1){
     Machines[machNumber].remove(1);
   }
   remove(machNumber,st); //remove from Queue
 }

 public void remove( int mach, subjob s){
   Vector temp = new Vector();

   for (int i = 1; i <= MachineQ[mach].size(); i++){
     subjob st = (subjob) MachineQ[mach].get(i-1);
     if (!((st.jobNumber == s.jobNumber) && (st.subjobNumber == s.subjobNumber))){
       temp.add(st);
     }
   }
   MachineQ[mach] = new Vector();
   MachineQ[mach]= temp;
 }


 public void printPlan(){
   System.out.println("--------------------------------------");
   System.out.println("Time " + totaltime );
   for (int i= 1; i <= this.numberOfMachines; i++) {
     for (int j = 0 ; j < Machines[i].size(); j++){
       subjob s = (subjob) Machines[i].get(j);
       System.out.println("Job:" +s.jobNumber + " subjob:" + s.subjobNumber + " machine:" + s.machineNumber  );
       for (int k = 0; k < MachineQ[i].size() ; k++){
         subjob  st = (subjob) MachineQ[i].get(k);
         System.out.println("      machineQ:" + i +" Job:" + st.jobNumber + " subjob:" + st.subjobNumber );
       }
     }
   }
   System.out.println("--------------------------------------");
 }


}

class subjob {
 public int jobNumber;
 public int subjobNumber;
 public int numSubjobs;
 public int timeRequired;  // in minutes
 public int machineNumber; //machine which requires job

 public subjob(int job) {
   //creates empty subjob, can be used for place holding
    jobNumber = job;
    subjobNumber = 0;
    numSubjobs = 0;
    timeRequired = 0;
    machineNumber = 0;
  }

  public subjob (int j,int n, int l){
    //generate a subjob, given its number
    jobNumber = j;
    subjobNumber = n;
    numSubjobs = l;
    timeRequired = generateTime(100);
    machineNumber = generateMachNumber();
   //for testing
   //machineNumber = 3;
 }

 public subjob(){
   jobNumber = 0;
   subjobNumber = 0;
    timeRequired = 0;
    machineNumber = 0;

 }
 public subjob(int j, int m, int n, int r, int l) {
   //set a subjob given all information
   jobNumber = j;
   subjobNumber = n;
   timeRequired = r;
   machineNumber = m;
   numSubjobs = l;
  }
  public int generateTime(int max){
    //randomly generate a time of at least 10 minutes.
    double ranNum = Math.random();
    //return 10;
    int retValue = (int)(ranNum*max);
    if ((retValue < 10) && max > 50) {return (10 + retValue);}
      return (retValue);
   }

   int generateMachNumber(){
     //generate a String for the machine number
     double ranNum = Math.random();
     //if (ranNum <= (2.0/10.0)) { return 1; }
     if (ranNum <= (1.0/3.0)) { return 1; }
     if (ranNum <= (2.0/3.0)) { return 2; }
     //if (ranNum <= (8.0/10.0)) { return 2; }
     return 3;
   }
   public void display(){
     System.out.println("Job #:" + this.subjobNumber + " timeRequired: " + this.timeRequired + " machine #" + this.machineNumber);
   }
 }

 class randomjob{
   public int numberSubJobs;
   public int jobNumber;
   public Vector subjobs; //vector for subjobs of type subjob

   public randomjob(int job) {
     jobNumber = job;
     numberSubJobs = generateSubJob();
     subjobs = new Vector();
     subjob thissubjob = new subjob(job);  //create empty job to void using zero as index
     subjobs.add(0,thissubjob);         //add the empty job to the vector
     for (int i = 1; i <= numberSubJobs; i++){
       thissubjob = new subjob(job,i,numberSubJobs);      //new subjob with number, all elements generated
       // randomly in constructor
       subjobs.add(i,thissubjob);       //add to the vector the new subjob
     }
   }

   public randomjob(int job, int numSubJobs) {
     jobNumber = job;
     numberSubJobs = numSubJobs;
     subjobs = new Vector();
     subjob thissubjob = new subjob(job,0,numSubJobs);  //create empty job to void using zero as index
     subjobs.add(0,thissubjob);         //add the empty job to the vector
     for (int i = 1; i <= numberSubJobs; i++){
       thissubjob = new subjob(job,i,numberSubJobs);      //new subjob with number, all elements generated
       subjobs.add(i,thissubjob);       //add to the vector the new subjob
     }
   }


   public void display(){
     System.out.println("SubJobs:" + numberSubJobs);
     for (int i = 1; i <= numberSubJobs; i++){
       subjob thisjob = (subjob) subjobs.get(i);  // get the subjob to display
       // index starts at one
       thisjob.display();
     }
   }

   int generateSubJob(){
     // randomly generate a number to decide the number of subjobs
     double ranNum = Math.random();
     if (ranNum <= (1.0/10.0)) { return 1; }
     if (ranNum <= (2.0/10.0)) { return 1; }
     if (ranNum <= (3.0/10.0)) { return 2; }
     if (ranNum <= (4.0/10.0)) { return 2; }
     if (ranNum <= (5.0/10.0)) { return 3; }
     if (ranNum <= (6.0/10.0)) { return 3; }
     if (ranNum <= (7.0/10.0)) { return 4; }
     if (ranNum <= (8.0/10.0)) { return 4; }
     if (ranNum <= (9.0/10.0)) { return 5; }
     return 5;
   }
 }

class mylist {
  public Vector element;

  public mylist() {
   element = new Vector();
  }
  public mylist(mylist l){
    //this = new mylist();
    this.element = l.element;
  }
  public void add(subjob sj){
   element.add(sj);
  }
  public void remove (subjob sj) {
    this.element.remove(sj);
  }
  public int size() {
    return element.size();
  }
  public subjob get(int i){
    return ((subjob) element.get(i));
  }
  public void  print(){
    for (int j = 0 ; j < element.size() ; j++){
      System.out.println(" " + get(j).jobNumber + ":" + get(j).subjobNumber );
    }
  }
  public void copy (mylist l){
    for (int i =0; i < l.size() ; i++){
      element.add(l.get(i));
    }
  }
}