Rückblick – Prioritätswarteschlange

Teil des Abschnitts Objektorientierte Programmierung der Kotlin-Journey von Coddy. Lektion 41 von 57.

Aufgabe

Mittel

Erstelle eine Prioritätswarteschlange, die für jeden priorisierten Typ funktioniert. Prioritized (mit priority) und die Datenklassen Job und Ticket werden bereitgestellt.

TaskQueue<T : Prioritized> verfügt über push(item), pop() und peek(), die das Element mit der höchsten Priorität (bei gleicher Priorität das zuerst eingefügte) entfernen oder zurückgeben, oder null, sowie über size, items() (eine schreibgeschützte Momentaufnahme in der Reihenfolge des Entfernens) und drain(n), das bis zu n Elemente entfernt und sie als List<T> zurückgibt.
Die generische Funktion countUrgent(queue, min) erhält eine Warteschlange eines beliebigen priorisierten Typs und gibt zurück, wie viele ihrer Elemente mindestens diese Priorität haben.

Der bereitgestellte Code liest die Befehle job build 3, ticket 17 5 ada, pop jobs, peek tickets, drain 2 (Tickets) oder sizes, gibt jede Antwort aus und schließlich urgent: mit den dringenden Jobs und Tickets, die noch in der Warteschlange stehen.

Dein Code gehört in TaskQueue.kt, Prioritized.kt, Job.kt und Ticket.kt. Main.kt enthält den bereitgestellten Eingabe-/Ausgabecode und kann nicht bearbeitet werden.

Probier es selbst

fun main() {
    // Mitgelieferter Ein-/Ausgabecode: belasse ihn wie er ist
    val input = generateSequence(::readLine).toList()
    val jobs = TaskQueue<Job>()
    val tickets = TaskQueue<Ticket>()
    for (cmd in input) {
        val p = cmd.split(" ")
        when (p[0]) {
            "job" -> jobs.push(Job(p[1], p[2].toInt()))
            "ticket" -> tickets.push(Ticket(p[1].toInt(), p[2].toInt(), p[3]))
            "pop" -> println("popped " + (if (p[1] == "jobs") jobs.pop() else tickets.pop()))
            "peek" -> println("next " + (if (p[1] == "jobs") jobs.peek() else tickets.peek()))
            "drain" -> println("drained " + tickets.drain(p[1].toInt()).map { it.customer })
            else -> println("jobs ${jobs.size}, tickets ${tickets.size}")
        }
    }
    println("urgent: ${countUrgent(jobs, 4) + countUrgent(tickets, 4)}")
}