Содержание

Вариант 5.6. Иерархия подразделений и документов

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

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

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

Каталог — подразделение, файл — документ подразделения, text — токен содержимого документа. Перенос подразделения переносит все вложенные подразделения и документы.

Разработайте модель иерархического хранилища в оперативной памяти. В нём есть каталоги и файлы с небольшим текстовым содержимым. Необходимо создавать, искать, удалять и перемещать объекты. Работа с настоящими файлами операционной системы не требуется.

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

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

Операции

Команда Действие Ответ
MKDIR path Создать каталог по полному пути; родитель должен существовать и быть каталогом. OK; занятый путь — Error: EXISTS
PUT path text Создать файл либо заменить содержимое файла. Родитель должен существовать и быть каталогом. OK; если по пути каталог, Error: STATE
GET path Прочитать файл. VALUE text; объект отсутствует — NONE; это каталог — Error: STATE
LS path Получить непосредственных детей каталога по возрастанию их имён. ITEMS k, затем строки D name для каталогов или F name для файлов; файл — Error: STATE
RM path Удалить объект и всё его содержимое, включая вложенные каталоги. OK
MV src dst Переместить объект src по новому полному пути dst, в том числе переименовать. Родитель dst должен существовать; dst должен быть свободен. OK; занятый dst — Error: EXISTS
FIND name Найти все файлы и каталоги с точным именем name во всём хранилище, кроме корня. ITEMS k, затем полные пути лексикографически

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

Для LS/RM/MV отсутствие обязательного объекта либо родителя возвращает NOT_FOUND; для MKDIR/PUT — отсутствие родителя также NOT_FOUND. Если путь проходит через файл, а не каталог, возвращается STATE; GET для такого пути возвращает STATE, а не NONE. GET возвращает NONE только если при корректном проходе недостаёт компонента.

RM и MV корня возвращают STATE. Перемещение каталога в самого себя или своего потомка запрещено. При MV /a /a существующий dst даёт EXISTS; для свободного dst внутри src — STATE. Предварительно проверяются src и родитель dst слева направо, затем занятость dst, затем запрет перемещения внутрь себя. Корень является своим существующим родителем только для проверки PUT/MKDIR по пути /; MKDIR / даёт EXISTS, PUT / text — STATE.

LS упорядочивает файлы и каталоги вместе по ASCII-именам, без группировки по типу; сам запрошенный каталог не выводится. FIND сравнивает точное имя последнего компонента пути, а не подстроку полного пути.

Файлы и каталоги одного родителя не могут иметь одинаковые имена. FIND и LS не изменяют данные. Содержимое и потомки при MV сохраняются. Неудачное перемещение ничего не меняет.

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

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

Пусть h — число компонентов пути, s — максимальное число детей одного каталога, L — максимальная длина компоненты. Поиск по пути, MKDIR, PUT и GET — не хуже O(h·L·log(s+2)); LS допускает дополнительно O(k·L·log(k+2)) для вывода. Для MV допускается O(h·L·log(s+2) + rL), где r — число перемещаемых объектов; RM — O(h·L·log(s+2) + rL). FIND допускает полный просмотр и сортировку найденных путей. Память пропорциональна числу объектов и суммарной длине их данных; все полные пути можно формировать при выводе. Решение не должно при обычном поиске пути перебирать всё хранилище.

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

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

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

Course work for option 5.6, created by Ivan Ivanov.

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

Примеры

Пример 1. Создание, перенос и поиск

Ввод:

1
7
MKDIR /a
PUT /a/x hello
MKDIR /b
MV /a/x /b/y
LS /b
GET /b/y
FIND y

Вывод:

Course work for option 5.6, created by Ivan Ivanov.
OK
OK
OK
OK
ITEMS 1
F y
VALUE hello
ITEMS 1
/b/y

Пример 2. Рекурсивное удаление

Ввод:

1
6
MKDIR /a
MKDIR /a/b
PUT /a/b/x data
RM /a
LS /
GET /a/b/x

Вывод:

Course work for option 5.6, created by Ivan Ivanov.
OK
OK
OK
OK
ITEMS 0
NONE

Пример 3. Неудачное перемещение сохраняет объекты

Ввод:

1
6
MKDIR /a
PUT /a/x data
MV /a /a/sub
GET /a/x
RM /
LS /a

Вывод:

Course work for option 5.6, created by Ivan Ivanov.
OK
OK
Error: STATE
VALUE data
Error: STATE
ITEMS 1
F x