// Week 8 – Priority queue: a simple implementation with an unsorted array, and the built-in PriorityQueue
// Run: java PriorityQueueDemo.java
import java.util.ArrayList;
import java.util.PriorityQueue;

public class PriorityQueueDemo {

    record Task(String name, int priority) {
        public String toString() { return name + "(" + priority + ")"; }
    }

    // Unsorted array: insertion at the end O(1), removal searches for the smallest priority O(n).
    // (With a sorted array it is the other way round: insertion O(n), removal O(1). With a heap both are O(log n) – week 15.)
    static class SimplePQ {
        private final ArrayList<Task> items = new ArrayList<>();

        void insert(Task t) { items.add(t); }

        Task removeMin() {
            int min = 0;
            for (int i = 1; i < items.size(); i++)
                if (items.get(i).priority() < items.get(min).priority()) min = i;
            Task t = items.get(min);
            items.set(min, items.get(items.size() - 1)); // the last one into its place – O(1)
            items.remove(items.size() - 1);
            return t;
        }

        boolean isEmpty() { return items.isEmpty(); }
    }

    public static void main(String[] args) {
        Task[] tasks = { new Task("e-mail", 3), new Task("server down", 1), new Task("coffee", 5),
                new Task("prepare lecture", 2), new Task("lunch", 4) };

        SimplePQ pq = new SimplePQ();
        for (Task t : tasks) pq.insert(t);
        System.out.print("SimplePQ order:      ");
        while (!pq.isEmpty()) System.out.print(pq.removeMin() + " ");
        System.out.println();

        // Built-in: based on a heap, insert and remove O(log n)
        PriorityQueue<Task> jpq = new PriorityQueue<>((a, b) -> Integer.compare(a.priority(), b.priority()));
        for (Task t : tasks) jpq.offer(t);
        System.out.print("PriorityQueue order: ");
        while (!jpq.isEmpty()) System.out.print(jpq.poll() + " ");
        System.out.println();
    }
}