Java部分订购了Collection <E>

Question

我正在寻找一个数据结构的Java实现,它包含一个元素集合,其中定义了一个部分排序,并允许一个元素以某种拓扑顺序迭代这些元素(任何可能的排序都很好;最好是一个稳定的订购作为集合的内容更改).

理想情况下,它将实现一个Collection<E>,Set<E>或SortedSet<E>接口,并支持接口上的所有方法.在指定总排序方面,可以使用a来实例化集合Comparator<E>,并且ClassCastException如果被比较的两个元素没有相对于彼此排序,则比较器可以抛出异常(？).作为奖励,如果插入的元素会产生排序异常(元素的有序图中的循环),它将抛出异常.

所以是的,我想要的是一个拓扑排序,但是我想要一个集合对象,它在每次插入/删除时保持排序顺序,类似于SortedSet如何按排序顺序维护集合.

这样的事情存在吗？在一些开源库中？

参考文献:

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

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

更新

在我意识到我的要求的性能影响(以及我无法解决的各种其他问题,使用poset)之后,我最终采用了不同的方法解决了我的问题,我不需要一个poset.依靠比较器来确定元素之间的顺序意味着对于元素插入,我必须针对每个现有元素查询比较器,每次插入花费O(n).

如果性能不是很重要(确实如此),并且如果元素的数量被限制在合理的范围内(事实并非如此),我想我会采用Willie建议的方法,尽管可能使用我自己的图形实现和拓扑排序实现以最小化依赖性.

Answer 1

有向无环图是否足够通用以满足您的需求？我知道这通常不会捕获偏序集，但您提到要排除图形循环。

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

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

请注意，有向图不是 java.util.Collections，但您可以获取顶点，它是 java.util.Set。如果您需要数据结构本身是一个集合，您可能可以使用一个集合的薄包装器来包装 JGraphT 有向图，将顶点视为元素。

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