Все варианты на «Отлично» · Общие требования и формат ввода/вывода · Регламент выполнения и защиты
Уровень: Отлично.
Рабочие пары key/value — редактируемые данные проекта, коммит — сохранённая версия, ветка — именованная линия изменений. Полная имитация настоящего Git не требуется.
Разработайте систему версий набора пар «ключ–значение». Пользователь изменяет рабочее состояние, сохраняет неизменяемые снимки, создаёт ветки, переключается между ними и сравнивает версии. Хранение большого числа почти одинаковых снимков должно экономить память.
Выберите и обоснуйте структуры хранения и алгоритмы выполнения операций самостоятельно. Указанные далее поведение и оценки эффективности обязательны; способ реализации не предписывается. Имена команд и полей в таблице фиксированы: предметная трактовка не меняет машинный формат.
key, value, cid, имена веток и идентификаторы коммитов a/b — токены общего формата.0 и единственная ветка main, указывающая на него; main является текущей.| Команда | Действие | Ответ |
|---|---|---|
PUT key value | Изменить или добавить пару в рабочем состоянии. | OK |
DEL key | Удалить пару из рабочего состояния. | OK; при отсутствии Error: NOT_FOUND |
GET key | Прочитать рабочее значение. | VALUE value; при отсутствии NONE |
COMMIT cid | Создать новый снимок рабочего состояния. Его родитель — текущий коммит; текущая ветка передвигается на cid. | OK; занятый cid — Error: EXISTS |
BRANCH name | Создать ветку на текущем коммите, не переключаясь на неё. | OK; занятое имя — Error: EXISTS |
CHECKOUT name | Сделать существующую ветку текущей и заменить рабочее состояние её снимком. Несохранённые изменения теряются. | OK; ветка отсутствует — Error: NOT_FOUND |
READ cid key | Прочитать значение из существующего снимка. | VALUE value; ключ отсутствует — NONE; коммит отсутствует — Error: NOT_FOUND |
DIFF a b | Найти различия снимков a и b, по возрастанию ключа. | ITEMS k, затем ADD key new, DEL key old либо MOD key old new; отсутствующий коммит — Error: NOT_FOUND |
MERGE name | Объединить текущую ветку с существующей веткой по описанным ниже правилам. | OK; ветка отсутствует — Error: NOT_FOUND; недопустимое объединение — Error: STATE |
Пространства имён коммитов и веток независимы. COMMIT разрешён даже без изменений. BRANCH не сохраняет несохранённые рабочие пары и не переключает ветку. CHECKOUT, в том числе текущей ветки, отбрасывает несохранённые изменения. Родителем нового коммита становится вершина текущей ветки, а не последний по времени коммит другой ветки. Предком считается и сам коммит, и любой коммит, достижимый последовательным переходом к родителю.
MERGE требует, чтобы рабочие пары точно совпадали с текущим снимком; иначе STATE. Сначала проверяется существование целевой ветки. Если текущая вершина — предок целевой, текущая ветка и рабочее состояние заменяются целевой вершиной/снимком. Если целевая вершина — предок текущей, операция успешна без изменений. Если вершины разошлись, возвращается STATE. Нового коммита MERGE не создаёт, другая ветка не изменяется. Объединение произвольных конфликтующих изменений не требуется.
В DIFF направление — от a к b. ADD означает отсутствие ключа в a и наличие в b; DEL — наоборот; MOD — наличие в обоих с разными значениями. Неизменившиеся ключи не выводятся. Изменения рабочего состояния и переключения не меняют ранее сохранённые снимки.
Коды ошибок в тексте обозначают точный ответ Error: CODE по общей спецификации. На каждую успешную команду, включая операцию без фактического изменения данных, выводится ответ из таблицы.
Пусть N — максимальное число пар в одном состоянии за сценарий; C — число сохранённых коммитов, включая 0; B — число веток, включая main; L — максимальная длина любого строкового поля. Обозначим M=L·log(C+B+2) — допустимую стоимость доступа к метаданным имён. PUT, DEL, GET — O(L·log(N+2)); READ — O(M+L·log(N+2)). COMMIT, BRANCH и CHECKOUT — O(M), без обхода всех пар. Для DIFF допустимо O(M+(na+nb+1)·L), где na и nb — числа пар в сравниваемых снимках. Для MERGE допустимо O(M+(N+1)·L+C): можно сравнивать рабочие пары и проходить историю. Эти границы относятся к худшему случаю, кроме отдельно оговорённого освобождения памяти.
Пусть U — суммарное число успешных PUT и DEL с начала сценария, включая повторную запись того же значения. При U таких изменениях суммарная память всех версий и рабочего состояния должна быть O((U+1)·L·log(N+2)+(C+B)·L), а не O(C·N·L). Способ повторного использования неизменённых данных выбирает студент. Освобождение уже недоступных данных можно учитывать амортизированно.
В отчёте обоснуйте эти оценки и подтвердите их экспериментами; учтите худшие случаи и стоимость вывода результатов. Полное условие по разрешённым средствам, режимам 1/6 и обработке ошибок приведено в общих требованиях.
Первая строка stdin — 1, вторая — число q, затем q строк команд из таблицы. Для справки подайте только строку 6. Общая лексика, разделители и порядок проверки ошибок обязательны. Первая строка stdout для этого варианта:
Course work for option 5.2, created by Ivan Ivanov.
Вместо Ivan Ivanov укажите собственные имя и фамилию. Далее идут ответы на команды; для ITEMS k — ещё k строк записей. Все приведённые примеры являются отдельными запусками с начальным состоянием.
Ввод:
1 10 PUT a x COMMIT c1 BRANCH dev PUT a y COMMIT c2 CHECKOUT dev GET a MERGE main GET a READ c1 a
Вывод:
Course work for option 5.2, created by Ivan Ivanov. OK OK OK OK OK OK VALUE x OK VALUE y VALUE x
Ввод:
1 7 PUT a x COMMIT c1 PUT a y PUT b z COMMIT c2 DIFF c1 c2 DIFF c2 c1
Вывод:
Course work for option 5.2, created by Ivan Ivanov. OK OK OK OK OK ITEMS 2 MOD a x y ADD b z ITEMS 2 MOD a y x DEL b z
Ввод:
1 9 BRANCH dev PUT a x COMMIT left CHECKOUT dev PUT a y COMMIT right MERGE main GET a READ left a
Вывод:
Course work for option 5.2, created by Ivan Ivanov. OK OK OK OK OK OK Error: STATE VALUE y VALUE x