Java偏序Collection<E>

Question

我正在寻找一个数据结构的Java实现，该数据结构包含定义了偏序的元素集合，并且允许以某种拓扑顺序迭代这些元素(任何可能的顺序都可以；最好是随着集合内容的变化而具有稳定的排序)。

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

所以是的，我想要的是拓扑排序，但是我想要一个集合对象，它通过每次插入/删除来维护排序顺序，类似于SortedSet如何按照排序顺序维护一个集合。

像这样的东西存在吗？在某个开源库里？

参考资料：

set

sorting

更新

在认识到需求的性能影响(以及其他各种问题，使用poset时，我无法很好地解决这些问题)之后，我最终采用了一种不同的方法来解决我的问题，在这里我不需要poset。依靠比较器来确定元素之间的顺序意味着，对于元素插入，我必须参照每个现有元素的比较器，每次插入成本为O(n)。

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

Answer 1

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

如果是这样的话，您可能会看到JGraphT：http://jgrapht.org/

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

注意，有向图不是java.util.Collections，但是可以获取顶点，这是一个java.util.Set。如果您需要数据结构本身成为一个集合，您可能可以用一个薄包装(即集合)包装一个JGraphT有向图，将顶点作为元素处理。

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