Как провести внутреннее тестирование (организацию) структуры данных?

Question

Я начал работать над небольшим проектом ruby, который будет иметь примеры реализаций ряда различных структур данных и алгоритмов. Сейчас я просто хочу освежить в памяти то, чем я не занимался некоторое время, но я надеюсь, что он будет настроен как Ruby Koans, с кучей модульных тестов, написанных для структур данных, но реализации пустыми (с полной реализацией в другой ветке). Затем его можно использовать как хороший инструмент обучения или код ката.

Однако у меня возникли проблемы с поиском хорошего способа написания тестов. Я не могу просто протестировать публичное поведение, так как это не обязательно скажет мне о реализации, и это здесь очень важно. Например, открытые интерфейсы обычного BST и красно-черного дерева были бы одинаковыми, но у дерева RB есть очень специфические требования к организации данных. Как мне это проверить?

Answer 1

Проверка фактической реализации класса, как правило, плохая идея. Вы намного лучше тестируете контракт для каждого метода в классе.

Подумайте об этом: если публичный интерфейс будет таким же, не будут ли модульные тесты одинаковыми, независимо от реализации?

Хорошим примером модульных тестов для структур данных (в Java) является платформа Google Collections . У этого есть приблизительно 35 000 из них. Обратите внимание, что ни один из них не проверяет внутреннюю реализацию: вместо этого они проверяют контракт для каждого метода и класса.

Answer 2

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

Вы можете написать тесты для общего интерфейса, чтобы убедиться, что все реализации выполняют контракт, указанный этим интерфейсом. Например. все реализации отсортированного дерева должны правильно упорядочивать свои элементы и т. д. В качестве примечания следует отметить, что на самом деле это будет не модульный тест, а тест функциональности / приемочного тестирования.

Для красно-черных деревьев вы можете написать набор дополнительных (необязательных) тестов, чтобы убедиться, что дерево правильно переупорядочено после вставок и удалений. Это может и, тем не менее, должно быть протестировано через открытый интерфейс. Например. добавьте серию элементов в дерево таким образом, чтобы дерево стало неуравновешенным без переупорядочения, затем проверьте структуру дерева, чтобы убедиться, что оно переупорядочено правильно.