Устройство хранения данных типа лента (Tape) предназначено для последовательной записи и чтения данных. Считывающая/записывающая магнитная головка неподвижна во время чтения и записи, а лента имеет возможность двигаться в обоих направлениях. Запись и чтение информации возможны в ячейку ленты, на которой в данный момент находится магнитная головка. Перемещения ленты – затратная по времени операция – лента не предназначена для произвольного доступа.
Имеется входная лента длины N (где N – велико), содержащая элементы типа integer (2 32). Имеется выходная лента такой же длины. Необходимо записать в выходную ленту отсортированные по возрастанию элементы с входной ленты. Есть ограничение по использованию оперативной памяти – не более M байт (M может быть < N, т.е. загрузить все данные с ленты в оперативную память не получится). Для реализации алгоритма можно использовать разумное количество временных лент, т.е. лент, на которых можно хранить какую-то временную информацию, необходимую в процессе работы алгоритма. Необходимо создать проект С++, компилируемый в консольное приложение, которое реализует алгоритм сортировки данных с входной ленты на выходную. Необходимо сделать следующее:
- Определить интерфейс для работы с устройством типа лента.
- Написать класс, реализующий этот интерфейс и эмулирующий работу с лентой посредством обычного файла. Должно быть возможно сконфигурировать (без перекомпиляции – например, через внешний конфигурационный файл, который будет прочитан на старте приложения) задержки по записи/чтению элемента с ленты, перемотки ленты, и сдвига ленты на одну позицию.
- Файлы временных лент можно сохранять в директорию tmp.
- Написать класс, реализующий алгоритм сортировки данных с входной ленты на выходную.
- Консольное приложение должно принимать на вход имя входного и выходного файлов и производить сортировку.
- Желательно написать юнит-тесты
Работа с устройством типа лента эмулируется с помощью файла. Запись, чтение и доступ к элементам ленты эмулируются с
помощью вектора. Приватные методы readFromFile() и wtiteToFile() класса TapeDevice
нужны для корректной эмуляции доступа к элементам ленты с помощью вектора.
Перед запуском программы считываются данные из конфигурационного файла форматаjson,
если такого файла нет, то значения задержек устанавливаются равными нулю. Структура Config.json:
{
"readDelay": 100,
"writeDelay": 300,
"moveDelay": 500
}На вход поступает путь к файлу с входной лентой, файлу с выходной, конфигурационному файлу и объем оперативной памяти.
Пример работы программы:
Enter the path to the input tape file:C:\Users\User\Desktop\1.txt
Enter the path to the output tape file:C:\Users\User\Desktop\2.txt
Enter the path to Config file:C:\Users\User\Desktop\config.json
Enter the amount of RAM:5
Sorting started
Sorting in progress
Sorting is finished
Последовательно считываем с входной ленты по M элементов (объем оперативной памяти). Затем сортируем считанные
элементы в обратном порядке (чтобы не передвигать ленту в начало, т.к. при записи элементов лента сдвигается до конца вправо)
и записываем уже отсортированную последовательность на очередную временную ленту. Освобождаем оперативную пямять. Так повторяем до
окончания входной ленты.
Затем записываем значения на выходную ленту - каждый раз выбираем наименьший элемент с временных лент (на который указывает магнитная головка ленты). Так повторяем до тех пор, пока не будет достигнут конец всех временных лент.