/******************************************************************************
 *  Compilation:  javac BruteIndexMinPQ.java
 *  Execution:    java BruteIndexMinPQ
 *  Dependencies: none
 *
 *  Indexed PQ implementation using an array.
 *  The elements are integers between 0 and n-1.
 *
 *  Operation   Running time
 *  -------------------------
 *  Construct      n
 *  is empty       1
 *  size           1
 *  contains       1
 *  insert         1
 *  change key     1
 *  increase key   1
 *  decrease key   1
 *  delete min     n
 *  min            n
 *
 ******************************************************************************/

import java.util.NoSuchElementException;

/**
 *  The {@code BruteIndexMinPQ} class represents an indexed priority queue of generic keys.
 *  It supports the usual <em>insert</em> and <em>delete-the-minimum</em>
 *  operations, along with <em>delete</em> and <em>change-the-key</em>
 *  methods. In order to let the client refer to keys on the priority queue,
 *  an integer between {\code 0} and {@code maxN-1}
 *  is associated with each key—the client
 *  uses this integer to specify which key to delete or change.
 *  It also supports methods for peeking at the minimum key,
 *  testing if the priority queue is empty, and iterating through
 *  the keys.
 *  <p>
 *  This implementation uses an array of keys as the underlying data structure.
 *  The <em>is-empty</em>, <em>size</em>, <em>insert</em>,
 *  <em>delete</em>, <em>key-of</em>, <em>change-key</em>,
 *  <em>decrease-key</em>, and <em>increase-key</em> operations take constant time.
 *  The <em>min-key</em>, <em>min-index</em>, and <em>delete-the-minimum</em>
 *  operations take linear time.
 *  Construction takes time proportional to the specified capacity.
 *  <p>

 *  For additional documentation, see <a href="https://algs4.cs.princeton.edu/24pq">Section 2.4</a> of
 *  <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
 *
 *  @author Robert Sedgewick
 *  @author Kevin Wayne
 *
 *  @param <Key> the generic type of key on this priority queue
 */
public class BruteIndexMinPQ<Key extends Comparable<Key>> {
    private int n;           // number of elements on PQ
    private Key[] keys;      // keys[i] = key of element i

    /**
     * Initializes an empty indexed priority queue with indices between {@code 0}
     * and {@code maxN - 1}.
     *
     * @param   maxN the keys on this priority queue are index from {@code 0}
     *         {@code maxN - 1}
     * @throws IllegalArgumentException if {@code maxN < 0}
     */
    public BruteIndexMinPQ(int maxN) {
        keys = (Key[]) new Comparable[maxN];
    }

    /**
     * Returns true if this priority queue is empty.
     *
     * @return {@code true} if this priority queue is empty;
     *         {@code false} otherwise
     */
    public boolean isEmpty() {
        return n == 0;
    }

    /**
     * Returns the number of keys on this priority queue.
     *
     * @return the number of keys on this priority queue
     */
    public int size() {
        return n;
    }

    /**
     * Returns true if the argument is an index on this priority queue.
     *
     * @param  i an index
     * @return {@code true} if {@code i} is an index on this priority queue;
     *         {@code false} otherwise
     * @throws IllegalArgumentException unless {@code 0 <= i < maxN}
     */
    public boolean contains(int i) {
        return keys[i] != null;
    }

    /**
     * Associates key with index {@code i}.
     *
     * @param  i an index
     * @param  key the key to associate with index {@code i}
     * @throws IllegalArgumentException unless {@code 0 <= i < maxN}
     * @throws IllegalArgumentException if there already is an item associated
     *         with index {@code i}
     */
    public void insert(int i, Key key) {
        if (contains(i)) throw new NoSuchElementException("index is already in priority queue");
        n++;
        keys[i] = key;
    }

    /**
     * Removes a minimum key and returns its associated index.
     *
     * @return an index associated with a minimum key
     * @throws NoSuchElementException if this priority queue is empty
     */
    public int delMin() {
        int min = minIndex();
        keys[min] = null;
        n--;
        return min;
    }

   /**
     * Returns a minimum key.
     *
     * @return a minimum key
     * @throws NoSuchElementException if this priority queue is empty
     */
    public Key minKey() {
        int min = minIndex();
        return keys[min];
    }

    /**
     * Returns an index associated with a minimum key.
     *
     * @return an index associated with a minimum key
     * @throws NoSuchElementException if this priority queue is empty
     */
    public int minIndex() {
        if (n == 0) throw new NoSuchElementException("Priority queue underflow");
        int min = -1;
        for (int i = 0; i < keys.length; i++) {
            if (keys[i] == null) continue;
            else if (min == -1) min = i;
            else if (keys[i].compareTo(keys[min]) < 0) min = i;
        }
        return min;
    }
    /**
     * Change the key associated with index {@code i} to the specified value.
     *
     * @param  i the index of the key to change
     * @param  key change the key assocated with index {@code i} to this key
     * @throws IllegalArgumentException unless {@code 0 <= i maxN}
     * @throws NoSuchElementException no key is associated with index {@code i}
     */
    public void changeKey(int i, Key key) {
        if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
        keys[i] = key;
    }

    /**
     * Decrease the key associated with index {@code i} to the specified value.
     *
     * @param  i the index of the key to decrease
     * @param  key decrease the key assocated with index {@code i} to this key
     * @throws IllegalArgumentException unless {@code 0 <= i < maxN}
     * @throws IllegalArgumentException if {@code key >= keyOf(i)}
     * @throws NoSuchElementException no key is associated with index {@code i}
     */
    public void decreaseKey(int i, Key key) {
        if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
        if (keys[i].compareTo(key) <= 0)
            throw new IllegalArgumentException("Calling decreaseKey() with given argument would not strictly decrease the key");
        keys[i] = key;
    }

    /**
     * Increase the key associated with index {@code i} to the specified value.
     *
     * @param  i the index of the key to increase
     * @param  key increase the key assocated with index {@code i} to this key
     * @throws IllegalArgumentException unless {@code 0 <= i < maxN}
     * @throws IllegalArgumentException if {@code key <= keyOf(i)}
     * @throws NoSuchElementException no key is associated with index {@code i}
     */
    public void increaseKey(int i, Key key) {
        if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
        if (keys[i].compareTo(key) >= 0)
            throw new IllegalArgumentException("Calling increaseKey() with given argument would not strictly increase the key");
        keys[i] = key;
    }

}