//Raymond Kim 862042213
//Naid Ibarra nibar004

//---------------------------------------------------------------------------------------PrintJob.h
#ifndef __PRINTJOB_H
#define __PRINTJOB_H

using namespace std;

class PrintJob {
private:
  int priority;
  int jobNumber;
  int numPages;

public:
  PrintJob ( int, int, int);
  int getPriority ( );
  int getJobNumber ( );
  int getPages ( );
  //You can add additional functions here
};
#endif

//----------------------------------------------------------------------------------PrintJob.cpp

//Raymond Kim 862042213
//Naid Ibarra nibar004
#include "PrintJob.h"

PrintJob::PrintJob ( int setP, int setJ, int numP ):priority(setP), jobNumber(setJ), numPages(numP){}

int PrintJob::getPriority ( ){
    return priority;
}

int PrintJob::getJobNumber ( ){
    return jobNumber;
}

int PrintJob::getPages ( ){
    return numPages;
}

//------------------------------------------------------------------------------------Heap.h

//Raymond Kim 862042213
//Naid Ibarra nibar004
#ifndef __HEAP_H
#define __HEAP_H

#include "PrintJob.h"

const int MAX_HEAP_SIZE = 10;

class Heap {
private:
  PrintJob* arr[MAX_HEAP_SIZE];      // Notice this is an array of PrintJob pointers
  int numItems;  //current number of items in heap

public:
  /*Initializes an empty heap.*/
  Heap();

  /*Inserts a PrintJob to the heap without
  violating max-heap properties.*/
  void enqueue ( PrintJob* );

  /*Removes the node with highest priority from the heap.
  Follow the algorithm on priority-queue slides. */
  void dequeue ( );

  /*Returns the node with highest priority.*/
  PrintJob* highest ( );

  /*Prints the PrintJob with highest priority in the following format:
  Priority: priority, Job Number: jobNum, Number of Pages: numPages
  (Add a new line at the end.)*/
  void print ( );

  // void graphiz(const string &);
  // void visualizeTree(ofstream &outFS, int i);

private:
  /*This function is called by dequeue function
  to move the new root down the heap to the
  appropriare location.
  check:
    1) i should be valid
  Possibilities:
    1) has left child
    2) has left and right children
    3) has no children
  */
  void trickleDown(int);

  void trickeUp(int, PrintJob*);

  int getParent(int);

  int getLeft(int);

  int getRight(int);


  //You can include additional private helper functions here
};
#endif

//----------------------------------------------------------------------------------Heap.cpp

//Raymond Kim 862042213
//Naid Ibarra nibar004
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<fstream>
#include"Heap.h"
using namespace std;

Heap::Heap() : numItems(0) {}

void Heap::enqueue (PrintJob* job) {
    if (numItems == 10) {
        return;
    }
    trickeUp(numItems, job);
    ++numItems;

}

void Heap::dequeue () {
    if (numItems == 0) {
        return;
    }
    swap(arr[0], arr[numItems - 1]);
    --numItems;
    trickleDown(0);
}

PrintJob *Heap::highest () {
    if (numItems == 0) {
        return NULL;
    }
    return arr[0];
}

void Heap::print() {
    if (numItems == 0) {
        return;
    }
    cout << "Priority: " << arr[0]->getPriority()
        << ", Job Number: " << arr[0]->getJobNumber()
        << ", Number of Pages: " << arr[0]->getPages() << endl;
}

//PRIVATE--------------------------------------------------

void Heap::trickleDown(int i) {
    if (i >= numItems) {
        return;
    }
    else if (i < 0) {
        return;
    }

    if (getLeft(i) < numItems && getRight(i) < numItems) {
        if (arr[getLeft(i)]->getPriority() > arr[i]->getPriority()) {
            if (arr[getRight(i)]->getPriority() > arr[getLeft(i)]->getPriority()) {
                swap(arr[getRight(i)], arr[i]);
                trickleDown(getRight(i));
            }
            else {
                swap(arr[getLeft(i)], arr[i]);
                trickleDown(getLeft(i));
            }
        }
        else if (arr[getRight(i)]->getPriority() > arr[i]->getPriority()) {
            swap(arr[getRight(i)], arr[i]);
            trickleDown(getRight(i));
        }
    }
    else if (getLeft(i) < numItems) {
        if (arr[getLeft(i)]->getPriority() > arr[i]->getPriority()) {
            swap(arr[getLeft(i)], arr[i]);
            trickleDown(getLeft(i));
        }
    }
}

void Heap::trickeUp(int i, PrintJob* job) {
    if (i == 0) {
        arr[i] = job;
        return;
    }
    if (job->getPriority() < arr[getParent(i)]->getPriority()) {
        arr[i] = job;
        return;
    }
    else {
        arr[i] = arr[getParent(i)];
        trickeUp(getParent(i), job);
    }
}

int Heap::getParent(int i) {
    return (i - 1) / 2;
}

int Heap::getLeft(int i) {
    return (2 * i) + 1;
}

int Heap::getRight(int i) {
    return (2 * i) + 2;
}