CS2010 PS2

SchedulingDeliveries.java

import java.util.*;

// A0087884H
// Lim Jiew Meng
// Collaborators: 

class SchedulingDeliveries {

  protected ArrayMaxHeap mothersToBeQueue; // when we need to access by priority
  protected HashMap<String, MotherToBe> mothersToBe; // when we need to access by mother's name

  public SchedulingDeliveries() {
    this.mothersToBeQueue = new ArrayMaxHeap();
    this.mothersToBe = new HashMap<String, MotherToBe>();
  }

  void ArriveAtHospital(String womanName, int dilation) {
    // add mother to queue
    MotherToBe motherToBe = new MotherToBe(womanName, dilation);
    // keep track of queueIndex
    this.mothersToBeQueue.enqueue(motherToBe);
    // also put in hash map to facilitate search by name
    this.mothersToBe.put(womanName, motherToBe);

    // System.out.println("LOG: arrived " + womanName + " - Q#" + motherToBe.queueIndex);
    // System.out.println(this.mothersToBeQueue.toString());
  }

  void UpdateDilation(String womanName, int increaseDilation) {
    // search hash map for mother's name
    MotherToBe motherToBe = this.mothersToBe.get(womanName);
    // update the dilation
    motherToBe.dilation += increaseDilation;
    // update the queueIndex
    this.mothersToBeQueue.shiftUp(motherToBe.queueIndex);

    // System.out.println("LOG: update " + womanName + " - " + motherToBe.dilation + " - Q#" + motherToBe.queueIndex);
    // System.out.println(this.mothersToBeQueue.toString());
  }

  void GiveBirth(String womanName) {
    // search hash map for mother's name
    MotherToBe motherToBe = this.mothersToBe.get(womanName);
    // remove from queue
    this.mothersToBeQueue.remove(motherToBe.queueIndex);
    // remove from hash map
    this.mothersToBe.remove(womanName);

    // System.out.println("LOG: removed " + womanName + ", queue size: " + mothersToBeQueue.size() + ", hashmap size: " + mothersToBe.size());
    // System.out.println(this.mothersToBeQueue.toString());
  }

  String Query() {
    String answer = "The delivery suite is empty";
    MotherToBe motherToBe;
    if (this.mothersToBe.size() > 0) {
      motherToBe = this.mothersToBeQueue.peek();
      answer = motherToBe.name;
    }
    return answer;
  }

  void run() {
    // do not alter this method
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    while (N-- > 0) {
      int cmd = sc.nextInt();
      switch (cmd) {
        case 0: ArriveAtHospital(sc.next(), sc.nextInt()); break;
        case 1: UpdateDilation(sc.next(), sc.nextInt()); break;
        case 2: GiveBirth(sc.next()); break;
        case 3: System.out.println(Query()); break;
      }
    }
  }

  public static void main(String[] args) {
    // do not alter this method
    SchedulingDeliveries ps2 = new SchedulingDeliveries();
    ps2.run();
  }

  protected class MotherToBe implements Comparable<MotherToBe> {
    public String name;
    public int dilation;
    public int queueIndex;
    protected Date admissionTime; // to break ties in a deterministic manner if dilation is the same

    public MotherToBe(String name, int dilation) {
      this.name = name;
      this.dilation = dilation;
      this.admissionTime = Calendar.getInstance().getTime();
    }

    public int compareTo(MotherToBe mother2) {
      if (this.dilation == mother2.dilation) 
        return this.admissionTime.compareTo(mother2.admissionTime);
      return ((Integer)this.dilation).compareTo((Integer)mother2.dilation);
    }

    public String toString() {
      return this.name + ", dilation=" + this.dilation + ", queueIndex=" + this.queueIndex;
    }
  }

  protected class MotherToBeNameComparator implements Comparator<MotherToBe> {

    public int compare(MotherToBe mother1, MotherToBe mother2) {
      return mother1.name.compareTo(mother2.name);
    }

    public boolean equals(MotherToBe mother2) {
      throw new UnsupportedOperationException();
    }

  }

  // Max Heap implementation using ArrayList
  // Notes: 
  // - parent >= children
  protected class ArrayMaxHeap {

    protected ArrayList<MotherToBe> list;

    public ArrayMaxHeap() {
      this.list = new ArrayList<MotherToBe>();
    }

    public void enqueue(MotherToBe motherToBe) {
      if (this.list.size() == 0) { // don't use the 0th position
        this.list.add(null);
        this.list.add(motherToBe);
        motherToBe.queueIndex = 1;
      } else {
        this.list.add(motherToBe);
        motherToBe.queueIndex = this.list.size() - 1;
      }

      this.shiftUp(motherToBe.queueIndex);
    }

    public MotherToBe dequeue() {
      MotherToBe max = this.list.get(1);
      this.list.set(1, this.list.get(this.list.size() - 1)); 
      this.shiftDown(1);
      return max;
    }

    public MotherToBe peek() {
      MotherToBe max = this.list.get(1);
      return max;
    }

    public void remove(int i) {
      //System.out.println("LOG: removing " + i);
      int lastIndex = this.list.size() - 1;
      this.swap(i, lastIndex);
      this.list.remove(lastIndex);
      i = this.shiftDown(i);
    } 

    public int size() {
      return this.list.size();
    }

    public void shiftUp(int i) {
      //System.out.println("LOG: in shiftUp loop " + i);
      MotherToBe currNode = this.list.get(i);
      int parentIndex = this.indexOfParent(i);
      MotherToBe parentNode = (parentIndex > 0) ? this.list.get(parentIndex) : null;

      // i > 1 ==> not root
      // and heap property (parent should be gt. child) is violated
      while (i > 1 && parentNode != null && parentNode.compareTo(currNode) < 0) {
        this.swap(i, parentIndex);

        // update parent/curr index & node
        i = parentIndex;
        currNode = this.list.get(i);
        parentIndex = this.indexOfParent(i);
        parentNode = (i > 1) ? this.list.get(parentIndex) : null;

        //System.out.println(" - " + i + ", " + parentIndex);
      }
    }

    public int shiftDown(int i) {
      // System.out.println("LOG: shiftDown on " + i);
      int maxIndex = 1, leftIndex, rightIndex;
      MotherToBe maxObj = null, leftObj, rightObj;
      int heapsize = this.list.size();

      while (i < heapsize) {
        // System.out.println(" - " + i);
        maxObj = this.list.get(i);
        leftIndex = this.indexOfLeft(i);
        rightIndex = this.indexOfRight(i);
        leftObj = (this.hasLeft(i)) ? this.list.get(leftIndex) : null;
        rightObj = (this.hasRight(i)) ? this.list.get(rightIndex) : null;

        // System.out.println("LOG: Doing shiftDown: ");
        // System.out.print(" - ");
        // System.out.println(maxObj);
        if (leftObj != null && (maxObj == null || maxObj.compareTo(leftObj) < 0)) {
          maxObj = leftObj;
          maxIndex = leftIndex;
          // System.out.println(" - max is now: (left) " + maxObj.name);
        }
        if (rightObj != null && (maxObj == null || maxObj.compareTo(rightObj) < 0)) {
          maxObj = rightObj;
          maxIndex = rightIndex;
          // System.out.println(" - max is now: (right) " + maxObj.name);
        }

        if (maxIndex != i) {
          this.swap(i, maxIndex);
          i = maxIndex;
        } else {
          break;
        }
      }

      return i;
    }

    public String toString() {
      String str = "LOG: queue below \n";
      for (MotherToBe motherToBe : this.list) {
        if (motherToBe != null)
          str += " - " + motherToBe.toString() + "\n";
      }
      return str;
    }

    protected int indexOfLeft(int i) { return 2 * i; }
    protected int indexOfRight(int i) { return (2 * i) + 1; }
    protected int indexOfParent(int i) { return (int)Math.floor((float)i/2); }
    protected boolean hasLeft(int i) { return this.indexOfLeft(i) < this.list.size(); }
    protected boolean hasRight(int i) { return this.indexOfRight(i) < this.list.size(); }
    protected void swap(int i1, int i2) {
      MotherToBe obj1 = this.list.get(i1);
      MotherToBe obj2 = this.list.get(i2);
      
      // swap queue index
      if (obj1 != null) obj1.queueIndex = i2;
      if (obj2 != null) obj2.queueIndex = i1;

      // swap objects
      this.list.set(i2, obj1);
      this.list.set(i1, obj2);

      //System.out.println("LOG: swap(): " + i1 + " with " + i2);
      // System.out.println("LOG: swap(): 1: " + obj1.name + " - Q#" + obj1.queueIndex);
      // System.out.println("LOG: swap(): 2: " + obj2.name + " - Q#" + obj2.queueIndex);
    }

  }

}

Subtask1-ans.txt

ASTRID
CINDY
ASTRID
MARIA
GRACE
The delivery suite is empty
The delivery suite is empty
The delivery suite is empty
CATHY
The delivery suite is empty
The delivery suite is empty
The delivery suite is empty
JANE
CHLOE
SOPHIA
The delivery suite is empty
The delivery suite is empty
The delivery suite is empty

Subtask1.txt

34
0 GRACE 31
0 ASTRID 55
0 MARIA 42
3
0 CINDY 77
3
2 CINDY
3
2 ASTRID
3
2 MARIA
3
2 GRACE
3
3
3
0 CATHY 80
3
2 CATHY
3
3
3
0 CHLOE 30
0 SOPHIA 30
0 JANE 31
3
2 JANE
3
2 CHLOE
3
2 SOPHIA
3
3
3