Java部分订购的集合

Question

我正在寻找一种数据结构的Java实现，该实现包含一组元素的集合，为这些元素定义了 部分排序 ，并且允许以某种 拓扑顺序
对这些元素进行迭代（任何可能的排序都可以；最好是稳定的）随着集合内容的变化而排序）。

理想的情况下，将落实一个Collection<E>，Set<E>或SortedSet<E>接口，并支持所有的接口上的方法。在指定总排序方面，可以使用实例化集合Comparator<E>，并且如果比较的ClassCastException两个元素彼此之间没有排序，则比较器可以引发异常（？）。另外，如果插入的元素会产生有序异常（元素有序图中的循环），则会引发异常。

是的，我想要的是一种拓扑排序，但是我想要一个 集合对象，该对象 在每次插入/删除时都 保持该排序顺序
，类似于SortedSet如何按排序顺序维护集合。

是否存在这样的东西？在一些开源库中？

参考文献：

http://en.wikipedia.org/wiki/Partially_ordered_set

http://en.wikipedia.org/wiki/Topological_sorting

更新资料

在意识到需求的性能影响（以及使用波幅我无法完全解决的其他各种问题）后，我最终针对我的问题采用了一种不同的方法，即不需要波塞。依靠比较器确定元素之间的顺序意味着对于元素插入，我必须针对每个现有元素向比较器进行咨询，每次插入的成本为O（n）。

如果性能不是很重要（是），并且元素的数量限制在合理范围内（不是），我想我会采用Willie建议的方法，尽管也许是我自己的图形实现和拓扑排序实现以最小化依赖关系。

Answer 1

有向无环图是否足以满足您的需求？我知道这通常不能捕获位姿，但是您提到要排除图周期。

如果是这样，您可以看一下JGraphT：http
://jgrapht.org/

有一个用于拓扑排序的图迭代器。

请注意，有向图不是java.util.Collections，但是您可以获取顶点，它们是java.util.Set。如果你需要的数据结构本身是一个集合，你也许可以换一个JGraphT向图用薄的包装，
是 一个收集，处理顶点的元素。

这里的潜在缺点是必须显式创建边缘，这对于您的应用程序可能是可接受的，也可能是不可接受的。