Все варианты на «Отлично» · Общие требования и формат ввода/вывода · Регламент выполнения и защиты
Уровень: Отлично.
Каталог — подразделение, файл — документ подразделения, text — токен содержимого документа. Перенос подразделения переносит все вложенные подразделения и документы.
Разработайте модель иерархического хранилища в оперативной памяти. В нём есть каталоги и файлы с небольшим текстовым содержимым. Необходимо создавать, искать, удалять и перемещать объекты. Работа с настоящими файлами операционной системы не требуется.
Выберите и обоснуйте структуры хранения и алгоритмы выполнения операций самостоятельно. Указанные далее поведение и оценки эффективности обязательны; способ реализации не предписывается. Имена команд и полей в таблице фиксированы: предметная трактовка не меняет машинный формат.
path, src, dst — абсолютные пути: / либо /name/…/name. Компоненты соответствуют общему формату токена.Error: INPUT.text — непустой токен содержимого. Сумма длин имён и содержимого текущих объектов не более 10000000./ существует с начала запуска. Других объектов первоначально нет. Общий предел числа объектов включает корень.| Команда | Действие | Ответ |
|---|---|---|
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 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
Ввод:
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
Ввод:
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