package DataStructures.Queues;

/**
 * This class implements a PriorityQueue.
 *
 * <p>A priority queue adds elements into positions based on their priority. So the most important
 * elements are placed at the front/on the top. In this example I give numbers that are bigger, a
 * higher priority. Queues in theory have no fixed size but when using an array implementation it
 * does.
 */
class PriorityQueue {
  /** The max size of the queue */
  private int maxSize;
  /** The array for the queue */
  private int[] queueArray;
  /** How many items are in the queue */
  private int nItems;

  /**
   * Constructor
   *
   * @param size Size of the queue
   */
  public PriorityQueue(int size) {
    maxSize = size;
    queueArray = new int[size];
    nItems = 0;
  }

  /**
   * Inserts an element in it's appropriate place
   *
   * @param value Value to be inserted
   */
  public void insert(int value) {
    if (isFull()) {
      throw new RuntimeException("Queue is full");
    } else {
      int j = nItems - 1; // index of last element
      while (j >= 0 && queueArray[j] > value) {
        queueArray[j + 1] = queueArray[j]; // Shifts every element up to make room for insertion
        j--;
      }
      queueArray[j + 1] = value; // Once the correct position is found the value is inserted
      nItems++;
    }
  }

  /**
   * Remove the element from the front of the queue
   *
   * @return The element removed
   */
  public int remove() {
    return queueArray[--nItems];
  }

  /**
   * Checks what's at the front of the queue
   *
   * @return element at the front of the queue
   */
  public int peek() {
    return queueArray[nItems - 1];
  }

  /**
   * Returns true if the queue is empty
   *
   * @return true if the queue is empty
   */
  public boolean isEmpty() {
    return (nItems == 0);
  }

  /**
   * Returns true if the queue is full
   *
   * @return true if the queue is full
   */
  public boolean isFull() {
    return (nItems == maxSize);
  }

  /**
   * Returns the number of elements in the queue
   *
   * @return number of elements in the queue
   */
  public int getSize() {
    return nItems;
  }
}

/**
 * This class implements the PriorityQueue class above.
 *
 * @author Unknown
 */
public class PriorityQueues {
  /**
   * Main method
   *
   * @param args Command Line Arguments
   */
  public static void main(String[] args) {
    PriorityQueue myQueue = new PriorityQueue(4);
    myQueue.insert(10);
    myQueue.insert(2);
    myQueue.insert(5);
    myQueue.insert(3);
    // [2, 3, 5, 10] Here higher numbers have higher priority, so they are on the top

    for (int i = 3; i >= 0; i--)
      System.out.print(
          myQueue.remove() + " "); // will print the queue in reverse order [10, 5, 3, 2]

    // As you can see, a Priority Queue can be used as a sorting algotithm
  }
}