*** Partial Ordering, dependant graph, and scheduling ***

*******************************
I. input/output specificaions:
*******************************
Language: Java and C++
Due date: C++ 12/9/2014 in class
Java 12/9/2014 in class

Input: (1) a text file contains pairs of dependencies
as taught in class
(2) a text file contains the time requirements for jobs
as taught in class

*******************************
II. Data structure:
*******************************
(1) A scheduling Table (need to be dynamically allocated) to record the schedule.

(2) An OPEN list, to store jobs that do not have any parents;
your choice of using an 1-D array, max size is the number of total jobs
or a linked list.

(3) A hash table to represent the input dependency graph.
- The size of the hash table is the total number of distinct jobs in the graph
- The hashTable is an array of pointers (C++)/reference object (Java).
- Each hashTable[i] is pointed to a linked list, serves as listHead,
initially should points to a dummy node (the hashTable contructor's job)

(4) a node class. The node in the linked list will have two fields:
- jobId (integer)
- next (node pointer/reference)

(5) processJob, an 1-D array to keep track of what job is being processing
(6) ProcessTime, an 1-D array to keep track of the time remain on the job.
(less or equal to 0 means available
(7) parentCount, an 1-D array to keep track of number of parents of each job
(0 means no parent)
(8) jobTime, an 1-D array to store the Job's time requirements.

(9) jobDone, an 1-D array to keep track what jobs remain in the graph
(1 means deleted from the graph, 0 means still in the graph)


*******************************
III. Algorithm steps for scheduling using unlimited processors and with variable job times:
*******************************(May contain bug! Let me know if you find a bug)

step 0: prepare and initialize everything
Time <-- 0

step 1: find jobs that do not have any parent
(ie., check parentCount[i] == 0)
and place them, one-by-one, onto OPEN list

step 2: 2.1: newJob <-- remove from OPEN
2.2: availProc <-- the next available processor (looking
into processjob[i] <= 0)
2.3: place newJob on the processJob[availProc],
place newJob's time on processTime[availProc]
update the scheduling table under availProc,
(with respect to TIME status and job's time requiement).
2.4: repeat 2.1 and 2.3 until OPEN is empty

step 3: print the scheduling table, TIME, all 1-D arrays with proper heading.
step 4: track the TIME (ie, decrease the processTime[i] by 1 and Time++)

step 5: job <-- find a job that is done, ie., processTIME [i] == 0 ;
5.1: delete the job from the processJob[i]
5.2: delete the job from the graph (update jobDone[job])
5.3: delete all it's outgoing arcs (decrease by 1, the paraentCount[job] of its dependents)
5.4: jobDone[job] <-- 1
5.5: repeat 5.1 to 5.4 until no more finished job

step 6: print the scheduling table, TIME, all three 1-D arrays with proper heading.

step 7: repeat step 1 to step 6 until graph is empty (looking into the 1-D array of jobs'status)

// ConsoleApplication5.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <string>
#include <fstream>
#include <sstream>
using namespace std;

struct Node{ //Data Structure (4)
int jobId;
Node* next;

Node(int i){
jobId = i;
next = NULL;
}
};

struct LinkedList{
Node* first;
Node* last;
int length;

LinkedList(){
first = new Node(-1);
last = first;
length = 0;
}
void append(int i){
Node* nn = new Node(i);
last->next = nn;
last = nn;
length++;
}
void prepend(int i){
Node* nn = new Node(i);
nn->next = first->next;
first->next = nn;
length++;
}
void discard(){
if (length > 0){
Node* current = first->next;
first->next = first->next->next;
length--;
delete current;
}
}
int retrieve(){
if (length > 0){
int result = first->next->jobId;
Node* trash = first->next;
first->next = first->next->next;
delete trash;
length--;
return result;
}
return -1;
}
bool remove(int i){
Node* walker = first;
while (walker->next != NULL){
if (walker->next->jobId == i){
Node* trash = walker->next;
walker->next = walker->next->next;
delete trash;
length--;
return true;
}
walker = walker->next;
}
return false;
}
};


bool done(int* jobs, int length){
for (int i = 0; i < length; i++){
if (jobs[i] == 0) return false;
}
return true;
}

int main(int argc, char** argv){
if (argc <= 2){
cout << "Invalid parameters\n";
system("PAUSE");
return 1;
}
ifstream f1, f2; // step 0
f2.open(argv[2]);
if (f2.fail()){
cout << "File not found!\n";
system("PAUSE");
return 1;
}
int maxJob = -1;
do{
string line;
int temp1=0, temp2=0;
getline(f2, line);
istringstream iss(line);
iss >> temp1;
iss >> temp2;
if (temp1 == 0 || temp2 == 0) continue;
if (maxJob < temp1) maxJob = temp1;
} while (!f2.eof());
f2.close();

LinkedList** hashTable = new LinkedList*[maxJob]; //Data Structure (3)


int* openList = new int[maxJob]; //Data Structure (2)/
int* processTime = new int[maxJob]; //Data Structure (6)/
int* parentCount = new int[maxJob]; //Data Structure (7)
int* jobTime = new int[maxJob]; //Data Structure (8)/
int* jobDone = new int[maxJob]; //Data Structure (9)/
int* processJob = new int[maxJob]; //Data Structure (5)/

for (int i = 0; i < maxJob; i++){
hashTable[i] = new LinkedList();
openList[i] = 0;
parentCount[i] = 0;
jobDone[i] = 0;
processJob[i] = 0;
}
f2.open(argv[2]);
if (f2.fail()){
cout << "File not found!\n";
system("PAUSE");
return 1;
}
int jobLengthSum = 0;
do{ //storing job lengths
string line;
getline(f2, line);
istringstream iss(line);
int temp1, temp2;
iss >> temp1 >> temp2;
if (temp1 == 0 || temp2 == 0) continue;
jobTime[temp1 - 1] = temp2;
jobLengthSum += temp2;
} while (!f2.eof());
f2.close();

int** schedulingTable = new int*[maxJob]; //Data Structure (1)/
for (int i = 0; i < maxJob; i++){
schedulingTable[i] = new int[jobLengthSum];
for (int j = 0; j < jobLengthSum; j++){
schedulingTable[i][j] = 0;
}
}

f1.open(argv[1]);
if (f1.fail()){
"File not found!\n";
return 1;
}
do{ //populating the dependency graph
string line;
getline(f1, line);
istringstream iss(line);
int temp1=0, temp2=0;
iss >> temp1 >> temp2;
if (temp1 == 0 || temp2 == 0) continue;
hashTable[temp1 - 1]->append(temp2);
parentCount[temp1 - 1]++;
} while (!f1.eof());

int time = 0;
while (!done(jobDone, maxJob)){
int j = 0; //step 1
for (int i = 0; i < maxJob; i++){
if (parentCount[i] == 0){
openList[j++] = i + 1;
}
}

while (openList[0] != 0){ //step 2.4
int newjob; //step 2.1
for (int i = maxJob - 1; i >= 0; i++){ //step 2.2
if (openList[i] != 0){
newjob = openList[i];
openList[i] = 0;
break;
}
}
for (int i = 0; i < maxJob; i++){ //step 2.3
if (processJob[i] > 0) continue;
else{
processJob[i] = newjob;
processTime[i] = jobTime[newjob - 1];
for (int j = time; j < processTime[i] + time; j++){
schedulingTable[i][j] = newjob;
}
break;
}
}
}

cout << "Time :" << time << endl; //step 3
cout << "Scheduling table (starting at Time = " << time << ")" << endl;
for (int i = 0; i < maxJob; i++){
for (int j = time; j < jobLengthSum; j++){
if (schedulingTable[i][j] == 0) cout << " ";
else{
cout << schedulingTable[i][j] << " ";
if (schedulingTable[i][j] < 10) cout << " ";
}
}
cout << endl;
}
cout << "Parent Count:" << endl;
for (int i = 0; i < maxJob; i++) cout << i + 1 << parentCount[i] << endl;
cout << "Process time:" << endl;
for (int i = 0; i < maxJob; i++)cout << i + 1 << processTime[i] << endl;

cout << "Job Done:" << endl;
for (int i = 0; i < maxJob; i++) cout << i + 1 << ": " << jobDone[i];

time++; // step 4
for (int i = 0; i < maxJob; i++){
if (processTime[i]>0) processTime[i]--;
}

int job;
for (int i = 0; i < maxJob; i++){ // step 5.5
if (processTime[i] == 0 && jobDone[i] == 0){
job = i + 1;
for (int j = 0; j < maxJob; j++){
if (hashTable[i]->remove(job)){ // step 5.3
parentCount[i]--;
}
}
jobDone[job - 1] = 1; //step 5.4
processJob[i] = 0; //step 5.1

}
}

cout << "Time :" << time << endl; //step 6
cout << "Scheduling table (starting at Time = " << time << ")" << endl;
for (int i = 0; i < maxJob; i++){
for (int j = time; j < jobLengthSum; j++){
if (schedulingTable[i][j] == 0) cout << " ";
else{
cout << schedulingTable[i][j] << " ";
if (schedulingTable[i][j] < 10) cout << " ";
}
}
cout << endl;
}
cout << "Parent Count:" << endl;
for (int i = 0; i < maxJob; i++) cout << i + 1 << parentCount[i] << endl;
cout << "Process time:" << endl;
for (int i = 0; i < maxJob; i++)cout << i + 1 << processTime[i] << endl;
cout << "Job Done:" << endl;
for (int i = 0; i < maxJob; i++) cout << i + 1 << ": " << jobDone[i];
}
system("PAUSE");
return 0;
}

#define PRINTS(s) fprintf(stderr, "%s", s)

PRINTS("Entering/Leaving some-identifier-of-where-I-am\n")