如何对数据结构的内部（组织）进行单元测试？

Question

我开始着手一个小的Ruby项目，其中包含多种不同数据结构和算法的示例实现。目前只是为了让我重新熟悉一些我已经有一段时间没做的事情，但我希望它能够像Ruby Koans一样设置，为数据结构编写大量单元测试，但实现为空（完整的实现在另一个分支中）。然后它可以用作一个很好的学习工具或代码练习。

但是，我遇到了一些问题，无法想出一个好的方法来编写测试。我不能只测试公共行为，因为那并不能告诉我关于实现的信息，这在这里非常重要。例如，普通BST和红黑树的公共接口是相同的，但RB Tree具有非常特定的数据组织要求。我该如何测试呢？

- Herms

Answer 1

我不确定你在做什么，但如果你想为各种数据结构提供常见接口，然后可以以各种方式进行实现和/或专业化，我看不出你如何为任何尚不存在的具体实现编写测试。

您可以为公共接口编写测试，以确保所有实现都满足该接口指定的合同。例如，所有排序树的实现应正确排序其元素等。顺便说一句，这实际上不是单元测试，而是功能/验收测试。

对于红黑树，您可以编写一套其他（可选）测试套件，以验证插入和删除后树是否被正确地重新排序。无论如何，这可以并且应该通过公共接口进行测试。例如，以使树不平衡而未进行重新排序的方式向树添加一系列元素，然后检查树结构以确保它已被正确重新排序。

- Péter Török

---

如何公开暴露内部结构是我不确定的事情。至少不会让实际的树节点公开访问，我宁愿不这样做（尽管这对我的目的来说可能没问题）。 - Herms

@Herms 我认为，任何集合的接口如果没有访问单个元素的方法是不完整的。对于树来说，这将包括查询和遍历节点的子节点，获取到特定节点的路径等操作。 - Péter Török

我主要考虑“接口”的形式是标准的类似于Map的集合。不过也许这并不是正确的看法。 - Herms

@Herms 啊，我明白了。你说得对，地图需要一个更窄的接口。我有点从树的另一端看这个问题 :-) 你仍然可以为基于树的地图定义一个子接口，它将允许遍历地图结构。或者完全不同的Tree接口，然后让基于树的地图实现Map和Tree两个接口。 - Péter Török

嗯，这是Ruby语言，所以没有真正的接口，只有“我决定实现的方法”。但是，如果将其视为树形对象而不是使用树形结构的集合对象，则可以考虑添加更多方法，这将使测试树部分变得更容易。 - Herms

Answer 2

测试类的实际实现通常是一个不好的想法。你最好测试类中每个方法的契约。

想一想：如果公共接口相同，那么单元测试不管实现如何都应该是相同的，对吧？

Java数据结构的单元测试的一个很好的例子是Google Collections framework。它有大约35,000个测试用例。请注意，它们中没有一个测试内部实现：相反，它们验证每个方法和类的契约。

- Frederik

---

单元测试是关于测试类的实际实现，这是许多人包括我自己都非常赞成的一个好主意。（然而，在这里涉及到的测试并不符合单元测试的定义。） - Péter Török

通常我认为单元测试是测试类的预期行为，但不应该对实际实现做任何假设（因此只要外部可见的行为仍然正确，类就可以重构或选择不同的算法）。但问题在于，如果你正在谈论特定的算法，那么内部行为就是合同的一部分。 - Herms