Неизменяемые структуры данных (Persistent Data Structures)
Требования
Реализуйте библиотеку со следующими структурами данных в persistent-вариантах:
- Массив (константное время доступа, переменная длинна)
- Двусвязный список
- Ассоциативный массив (на основе Hash-таблицы, либо бинарного дерева)
Требуется собственная реализация перечисленных структур. Найти соответствующие
алгоритмы также является частью задания. Язык реализации не фиксируется, но
рекомендуется Java/C#/С/C++. Для языков типа Clojure или Haskell задание
бессмысленно, т.к. такие структуры и так встроены в язык. В Ruby и т.п.
реализация будет слишком медленная и неэффективная. В базовом варианте решения
все структуры данных могут быть сделаны на основе fat-node.
Требования:
- Должен быть единый API для всех структур, желательно использовать
естественный API для выбранной платформы
Дополнительные требования
- Обеспечить произвольную вложенность данных (по аналогии с динамическими
языками), не отказываясь при этом полностью от типизации посредством
generic/template.
- Реализовать универсальный undo-redo механизм для перечисленных структур с поддержкой
каскадности (для вложенных структур)
- Реализовать более эффективное по скорости доступа представление
структур данных, чем fat-node
- Расширить экономичное использование памяти на операцию преобразования одной
структуры к другой (например, списка в массив)
- Реализовать поддержку транзакционной памяти (STM)
Рекомендации
Для успешного выполнения задания следует самостоятельно подобрать и изучить
публикации по теме Persistent Data Structures