Задача «Декартово дерево»

Задание

Произвести рефакторинг модуля, реализующего декартово дерево (treap = tree + heap = дерамида).

Исходный код

  • treap.h – интерфейс дерамиды,
  • treap.c – реализация дерамиды,
  • fatal.h – обработка ошибок,
  • testtrp.c – простой тест.

Описание

В процессе рефакторинга необходимо:

  • Переписать код на C++ (new, delete, объявление переменных не в начале блока, а там где они реально используются, и т. п.)
  • Текстовый ввод и вывод производить через std::cout и т.п
  • Избавиться от define'ов (объявление констант) и глобальных переменных.
  • Уйти от работы с указателями в пользу ссылок, где это возможно.
  • Вместо typedef int ElementType использовать шаблоны.
  • Предусмотреть возможность передачи в качестве параметра шаблона нетривиальных типов данных (потребуется передача функционального объекта, аналогичного std::less).
  • Избавиться от typedef struct TreapNode *Position создав итератор.
  • Обработку ошибок перенести на механизм исключений и std::exception.
  • Выделить класс дерамиды, глобальные функции для работы с дерамидой преобразовать в методы.
  • Выделить класс узла дерева – оформить как внутренний класс дерамиды.

В целом, получившийся класс должен приближаться к интерфейсу std::set по мере возможностей (принципиально новый функционал дописывать не нужно).

Архив с проектами для Visual Studio 2008 и Visual Studio 2013.