Я ищу реализацию Java-структуры данных, которая содержит набор элементов, для которых определен partial ordering, и который позволяет перебирать эти элементы в некотором топологическом порядок (любой из возможных порядков в порядке, желательно стабильное упорядочение по мере изменения содержимого коллекции).
В идеале он реализует интерфейс 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) для каждой вставки.
Если производительность была не очень важна (она есть), и если количество элементов было ограничено чем-то разумным (это не так), я думаю, что я бы взял подход, предложенный Вилли, хотя, возможно, с моим собственным графиком реализации и топологической сортировки для минимизации зависимостей.
