Содержание

Вариант 5.13. Очередь сборки программных модулей

Все варианты на «Отлично» · Общие требования и формат ввода/вывода · Регламент выполнения и защиты

Уровень: Отлично.

Постановка задачи

Операция — сборка программного модуля, DEP a b означает зависимость сборки b от a. Программа моделирует порядок готовности, но не запускает компилятор.

Разработайте планировщик операций с приоритетами и зависимостями. Следующей выбирается самая приоритетная операция, все предпосылки которой выполнены. Зависимости и приоритеты могут меняться во время работы.

Выберите и обоснуйте структуры хранения и алгоритмы выполнения операций самостоятельно. Указанные далее поведение и оценки эффективности обязательны; способ реализации не предписывается. Имена команд и полей в таблице фиксированы: предметная трактовка не меняет машинный формат.

Данные и начальное состояние

Операции

Команда Действие Ответ
ADD id priority Создать PENDING-операцию без предпосылок. OK; id занят — Error: EXISTS
PRIORITY id priority Изменить приоритет PENDING-операции. OK; для DONE — Error: STATE
DEP a b Добавить предпосылку: b может завершиться только после a. Обе операции должны быть PENDING. OK; цикл или DONE-участник — Error: STATE
NEXT Получить лучшую готовую операцию без изменения её состояния. VALUE id priority; если готовых нет, NONE
DONE id Завершить готовую PENDING-операцию. OK; если не готова или уже DONE, Error: STATE
CANCEL id Удалить операцию и все её входящие/исходящие зависимости. OK
READY k Выдать первые min(k,r) готовых операций, где r — их число. ITEMS m, затем m строк id priority

Правила выполнения и ошибки

Операция готова, если она PENDING и все её существующие предшественники DONE. Из готовых выбирается наибольший приоритет, при равенстве — наименьший числовой id. Тот же порядок используется в READY. NEXT/READY не начинают и не завершают операции.

Отсутствующий обязательный id — NOT_FOUND, для DEP проверяются a и b слева направо. Зависимость операции от самой себя или любая зависимость, создающая цикл, запрещены. Повтор DEP для двух PENDING-операций успешен без дублирования. Завершённые операции сохраняются и продолжают удовлетворять уже существующим зависимостям, но новые зависимости с их участием запрещены.

CANCEL разрешён и для DONE; удалённая предпосылка больше не блокирует зависимые операции. Удалённый id разрешено использовать снова, но новая операция не получает старых зависимостей. Неудачный DEP не меняет готовность операций.

Коды ошибок в тексте обозначают точный ответ Error: CODE по общей спецификации. На каждую успешную команду, включая операцию без фактического изменения данных, выводится ответ из таблицы.

Требования к эффективности

В этих оценках n — число всех сохранённых операций, включая DONE, m — число текущих зависимостей. NEXT — O(1). ADD/PRIORITY — не хуже O(log(n+2)) ожидаемо или гарантированно. DEP допускается за O(n+m) из-за проверки допустимости зависимости. DONE/CANCEL — не хуже O((r+1)·log(n+2)), где r — число затронутых зависимостей. READY допускает O(n+k·log(n+2)) с временными данными. Память — O(n+m). NEXT и PRIORITY не должны каждый раз пересматривать все операции.

В отчёте обоснуйте эти оценки и подтвердите их экспериментами; учтите худшие случаи и стоимость вывода результатов. Полное условие по разрешённым средствам, режимам 1/6 и обработке ошибок приведено в общих требованиях.

Формат ввода и вывода

Первая строка stdin — 1, вторая — число q, затем q строк команд из таблицы. Для справки подайте только строку 6. Общая лексика, разделители и порядок проверки ошибок обязательны. Первая строка stdout для этого варианта:

Course work for option 5.13, created by Ivan Ivanov.

Вместо Ivan Ivanov укажите собственные имя и фамилию. Далее идут ответы на команды; для ITEMS k — ещё k строк записей. Все приведённые примеры являются отдельными запусками с начальным состоянием.

Примеры

Пример 1. Завершение предпосылки

Ввод:

1
7
ADD 1 5
ADD 2 9
DEP 1 2
NEXT
DONE 1
NEXT
READY 5

Вывод:

Course work for option 5.13, created by Ivan Ivanov.
OK
OK
OK
VALUE 1 5
OK
VALUE 2 9
ITEMS 1
2 9

Пример 2. Равенство приоритетов и отмена

Ввод:

1
6
ADD 2 5
ADD 1 5
NEXT
DEP 1 2
CANCEL 1
NEXT

Вывод:

Course work for option 5.13, created by Ivan Ivanov.
OK
OK
VALUE 1 5
OK
OK
VALUE 2 5

Пример 3. Цикл и неготовая операция

Ввод:

1
6
ADD 1 5
ADD 2 9
DEP 1 2
DEP 2 1
DONE 2
NEXT

Вывод:

Course work for option 5.13, created by Ivan Ivanov.
OK
OK
OK
Error: STATE
Error: STATE
VALUE 1 5