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

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

Похоже, это пример тестируемого дизайна в действии.Интерфейс, содержащий только метод 'insert', не поддается проверке, поскольку он также непригоден для использования.Построение дерева без возможности увидеть построенное вами дерево или что-либо с ним сделать, никуда вас не приведет.

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

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

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

Как бы то ни было, каждый раз, когда вы пишете тест, обязательно задавайте вопрос "будет ли кого-нибудь из клиентов этого кода волновать, если этот тест завершится неудачей?".Если нет, удалите его.

Answer 2

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

Answer 3

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

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('.')));
}