復習 - 優先度キュー

CoddyのKotlinジャーニー「オブジェクト指向プログラミング」セクションの一部。レッスン 41/57。

チャレンジ

中級

任意の優先度付き型で動作する優先度付きキューを構築してください。Prioritized（priority付き）と、データクラスJobおよびTicketは用意されています。

TaskQueue<T : Prioritized>にはpush(item)、pop()、peek()があり、最も優先度の高いアイテム（同じ優先度の場合は先に追加されたもの）を削除または返します。該当するアイテムがなければnullを返します。また、size、items()（取り出し順の読み取り専用スナップショット）、および最大n個のアイテムを取り出してList<T>として返すdrain(n)も備えています。
ジェネリック関数countUrgent(queue, min)は、任意の優先度付き型のキューを受け取り、その優先度以上のアイテム数を返します。

用意されたコードは、job build 3、ticket 17 5 ada、pop jobs、peek tickets、drain 2（tickets）、またはsizesのコマンドを読み込み、それぞれの応答を出力します。最後に、キューに残っている緊急のジョブとチケットの数をurgent: に続けて出力します。

コードはTaskQueue.kt、Prioritized.kt、Job.kt、Ticket.ktに記述してください。Main.ktには用意された入出力コードが含まれており、編集できません。

自分で試してみよう

fun main() {
    // 提供された入出力コード: そのままにしておく
    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)}")
}