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建议的方法,尽管也许使用我自己的图实现和拓扑排序实现来最小化依赖性。