Модульное тестирование правильного создания структуры данных

Question

Как можно проверить, правильно ли построена структура данных? Я реализую вид модифицированного радикального дерева, и мне было интересно, как проверить, правильно ли выстраивается ваша структура данных.

Рассмотрим дерево из TreeNode {String, Int} узлов. Вы всегда хотите добавить новый дочерний элемент в самый глубокий узел со значением, равным 0, как в следующем примере:

Root, 0
- Child_1, 5
- Child_2, 0
   - Child_3, 1

Вопрос в том, как выполнить модульное тестирование, если древовидная структура строится так, как вы хотели? TreeNode имеет только один метод, который будет insert.

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

[Root, 0 [Child_1, 5][Child_2, 0 [Child_3, 1]]]

Зная алгоритм построения дерева, я могу создать такую ​​строку вручную, если у меня есть представление о том, какие элементы я вставляю. Мой модульный тест будет выглядеть так (на том же примере).

TreeNode root = new TreeNode("Root", 0);
root.insert(new TreeNode("Child_1", 5));
root.insert(new TreeNode("Child_2", 0));
root.insert(new TreeNode("Child_3", 1));
TreeVisitor visitor = new TreeVisitor();
String expected = "[Root, 0 [Child_1, 5][Child_2, 0 [Child_3, 1]]]";
asssertEquals(expected, visitor.visit(root));

У меня ощущение, что это не лучший подход. Для начала, как только посетитель изменится, все тесты не пройдут (просто введите изменение [ ] в ( )). Кроме того, этот подход позволяет мне тестировать довольно маленькие деревья (настолько большие, насколько я могу вычислить вручную). Как бы вы протестировали большие?

Общий вопрос, как писать тесты, проверяющие, правильно ли создается структура данных ?

Полагаю, я неправильно понял всю идею тестирования, так как я только что ознакомился с дюжиной руководств, в которых люди проверяют, работает ли .Sum (a, b), как ожидалось :-)

Answer 1

Это похоже на случай Test Driven Design в действии. Интерфейс только с методом «вставки» не тестируется, потому что он также непригоден для использования. Построение дерева, без возможности видеть или делать что-либо с деревом, которое вы построили, никуда вас не приведет.

Выясните, как вы хотите, чтобы клиенты обращались к дереву (методы доступа, интерфейс посетителя и т. Д.). Затем проверьте это через них.

Если есть внутренняя сложность, с которой вы не можете легко справиться через общедоступный интерфейс (т.е. дерево больше похоже на Java TreeMap, чем на тип дерева, который вы помещаете в TreeView), вы можете использовать:

• утверждений и инвариантов
• что-то вроде разоблаченного Метод debugVerifyTree.
• Перебор: вставьте 36542 псевдослучайных элемента, используйте инструмент покрытия, чтобы проверить, что охватывает все случаи.

Как бы то ни было, в любое время, когда вы пишете тест, обязательно задайте вопрос: «Будет ли какой-нибудь клиент этого кода заботиться о том, что этот тест не пройден?». Если нет, удалите его.

Answer 2

Обычно я делаю так, чтобы значения или имена указывали на то, что вы тестируете. Так что в случае дерева имя может указывать глубину и дочерний индекс.

TreeNode root = new MyTreeNode("0.0", 0);
root.insert(new MyTreeNode("1.0", 5));
root.insert(new MyTreeNode("1.1", 0));
root.insert(new MyTreeNode("2.0", 1));
verify(root, 0, 0);
...
public void verify(TreeNode node, int depth, int index) {
   verifyName(node, depth, index);
   int numChildren = node.getChildCount();
   depth++;
   for (int i = 0; i < numChildren; i++) {
      verify(node.getChildAt(i), depth, i);
   }
}
public void verifyName(TreeNode node, int depth, int index) {
   StringBuilder expectedName = new StringBuilder();
   expectedName.append(depth).append('.').append(index);
   assertEquals("Tree node not in expected place",
                expectedName.toString(), node.getName());
}

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

public void verify(TreeNode root) {
   Stack<TreeNode> toBeVerified = new Stack<TreeNode>();
   verifyName(root, 0, 0);
   toBeVerified.push(root);

   while(!toBeVerified.isEmpty()) {
     TreeNode node = toBeVerified.pop();
     int depth = getDepth(node.getName()) + 1;
     int numChildren = node.getChildCount();
     for (int i = 0; i < numChildren; i++) {
        verifyName(node, depth, i);
        toBeVerified.push(node);
     }
   }
}
public int getDepth(String name) {
   return Integer.parseInt(name.substring(0, name.indexOf('.')));
}

Answer 3

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