Java 部分排序集合<E>

我正在寻找一个数据结构的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

更新

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

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


答案 1

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

如果是这样,你可以看看JGraphT:http://jgrapht.org/

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

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

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


答案 2