jdk8 - Java parcialmente ordenado Colección<E>

java set

Question

Estoy buscando una implementación de Java de una estructura de datos que contenga una colección de elementos para los que se define un orden parcial , y que permite iterar sobre esos elementos en algún orden topológico (cualquiera de los posibles ordenamientos es correcto, preferiblemente un estable ordenando a medida que cambia el contenido de la colección).

Lo ideal sería implementar una interfaz Collection<E> , Set<E> u SortedSet<E> y admitir todos los métodos en la interfaz. En términos de especificar el orden total, la colección podría ser instanciada con un Comparator<E> , y el comparador podría arrojar una excepción ( ClassCastException ?) Si dos elementos que se comparan no están ordenados entre sí. Como beneficio adicional, arrojaría una excepción si un elemento insertado produciría una anomalía de ordenamiento (un ciclo en el gráfico ordenado de elementos).

Así que sí, lo que quiero es un tipo topológico, pero me gustaría un objeto de colección que mantenga ese orden de clasificación con cada inserción / eliminación, de forma similar a cómo SortedSet mantiene una colección ordenada.

Existe algo como esto? En alguna biblioteca de código abierto?

Referencias

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

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

Actualizar

Terminé yendo con un enfoque diferente para mi problema donde no necesitaré un poset, después de darme cuenta de las implicaciones de rendimiento de mis requisitos (y varios otros problemas que no pude resolver del todo, usando el poset). Confiar en el comparador para determinar el orden entre los elementos significa que para la inserción del elemento, tengo que consultar el comparador contra cada elemento existente, costando O (n) por inserción.

Si el rendimiento no fuera muy importante (lo es), y si el número de elementos estuviera limitado a algo razonable (no lo es), creo que habría adoptado el enfoque sugerido por Willie, aunque tal vez con mi propia implementación gráfica y topológica ordenar la implementación para minimizar las dependencias.

Answer 1

¿Sería un gráfico acíclico dirigido suficientemente general para sus necesidades? Sé que esto no captura los correos electrónicos en general, pero mencionaste querer excluir ciclos de gráficos.

Si es así, puede consultar JGraphT: http://jgrapht.org/

Hay un iterador gráfico para géneros topológicos.

Tenga en cuenta que los gráficos dirigidos no son java.util.Collections, pero puede tomar los vértices, que son java.util.Set. Si necesita que la propia estructura de datos sea una Colección, probablemente pueda envolver un gráfico dirigido por JGraphT con un contenedor delgado que sea una Colección, tratando los vértices como elementos.

El inconveniente potencial aquí es que debe crear bordes explícitamente, lo que puede o no ser aceptable para su aplicación.