AV-1: SortVis

скриншот / визуализатор сортировок

Введение

Представлен пример кода, визуализирующего набор алгоритмов сортировки. Некоторая его избыточность относительно решаемой задачи подразумевает возможные пути развития при создании похожих программ.

В качестве основы визуализатора взят код из BY-0.

Исходный код: codepad. Архив откомпилированный exe + freeglut.dll можно скачать по ссылке (для запуска exe должны быть установлены библиотеки Microsoft Visual C++ 2010 redistributable).

Принцип работы

Рассматривается сортировка массива чисел. На экране «число» представляется как прямоугольник определённой длины, а процесс сортировки выглядит как последовательность сравнений (зелёный цвет) и присваиваний (красный цвет), упорядочивающая столбец прямоугольников по убыванию (если смотреть сверху-вниз).

Итак, рассматриваем только те алгоритмы, которым достаточно сравнивать (оператор < ) и присваивать (оператор = ) объекты сортируемой последовательности. Чтобы «записать» последовательность вызова указанных операторов вместо чисел сортируются объекты специального класса — «зонда» Probe, который содержит как числовое значение, так и указатель на очередь событий, куда перегруженные operator< и operator= складывают соответствующие события. Такой подход позволяет визуализировать подходящий алгоритм (например, std::sort), не внося в него изменений.

Для каждого столбца создаётся свой массив и своя очередь событий, используется свой алгоритм сортировки. После применения всех сортировок очереди событий «раскручиваются» с определённой временной задержкой (нажмите «+», чтобы ускорить, «-«, чтобы замедлить), применяя к прямоугольникам на экране действия, ранее произведённые с «зондами».

Детали реализации

Прямоугольник (class Rect) является визуализацией числа, задаётся двумя углами (левый нижний с координатами (x0, y0) и правый верхний с координатами (x1, y1)) и цветом.

Массив прямоугольников (class RectArray), также «столбец», является визуализацией сортируемого массива. Имеет две функции-члена, отвечающих за визуализацию событий:

void assign ( unsigned index, float value );

соответствует присваиванию элементу массива с индексом index значения value,  прямоугольник с этим индексом изменит длину и будет помечен красным цветом;

void compare ( unsigned i1, unsigned i2 );

соответствует сравнению двух элементов массива с индексами i1 и i2, отвечающие за них прямоугольники будут помечены зелёным цветом.

Событие (struct IEvent) — абстрактный базовый класс, наследники которого должны определять метод void apply(RectArray&), вызов которого с передачей соответствующего массива прямоугольников и будет приводить к применению события и его последующей визуализации.

Очередь событий (class EventQueue) — основной структурный элемент, хранит как собственно очередь событий с временными метками их наступления (в секундах), так и указатель на соответствующий массив прямоугольников, а также его координаты на плоскости. Таким образом, очередь отвечает как за сохранение событий (функция push), за применение событий, произошедших к заданному моменту времени (функция next), так и за отрисовку связанного с ней массива прямоугольников (функция paint).

Зонд (class Probe) — сортируемый объект, генерирующий события с помощью перегруженных операторов. Событиям сравнения и присваивания нужны индексы элементов, поэтому зонд кроме собственно числового значения хранит и свой индекс. Кроме того, так как очередь событий требует «глобальную» временную метку, было решено перенести ответственность за вычисление времени наступления события на специальный класс TimeMapper, который получает объект IEvent, вычисляет время и уже сам отправляет событие в очередь. Поэтому зонд хранит указатель на объект TimeMapper, который является общим для всех элементов сортируемого массива.

Сцена (class Scene) — главный класс, соединяющий все куски визуализатора воедино. Хранит набор очередей событий и соответствующих массивов прямоугольников. Функция makeNew сбрасывает очереди, создаёт и сортирует новые массивы, заполняя очереди событиями. Функция paint отрисовывает все столбцы ( «всю сцену» ). Функция next передаёт время функциям next всех очередей, возвращает true, если хотя бы одно событие было извлечено из очередей (что используется как условие обновления буфера кадра в обработчике frameMove).

Таймер (class Timer) написан для удобного управления скоростью визуализации. Хранит «реальное» время, возвращаемое std::clock(), и «виртуальное» время визуализации в «секундах», с учётом скорости течения времени (поле factor).

UPDATE. 2013.01.23. Более новый вариант расположен здесь (в составе AV Orchid).

Реклама

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s

%d такие блоггеры, как: