Clasificación de listas de Java: ¿hay alguna manera de mantener una lista ordenada de manera permanente como TreeMap?

En Java puedes construir una ArrayList con elementos y luego llamar:

Collections.sort(list, comparator);

¿Hay alguna forma de pasar el Comparador en el momento de la creación de la Lista como lo puede hacer con TreeMap? El objective es poder agregar un elemento a la lista y en lugar de tenerlo adjunto automáticamente al final de la lista, la lista se mantendrá ordenada en función del Comparador e insertará el nuevo elemento en el índice determinado por el Comparador. Así que, básicamente, la lista podría tener que reordenar cada nuevo elemento agregado.

¿Hay alguna forma de lograr esto de esta manera con el Comparador o por algún otro medio similar?

    Puede cambiar el comportamiento de ArrayList

     List list = new ArrayList() { public boolean add(MyType mt) { super.add(mt); Collections.sort(list, comparator); return true; } }; 

    Nota: un PriorityQueue NO es una Lista, si no le importaba qué tipo de colección era, lo más simple sería usar un TreeSet, que es como un TreeMap pero es una colección. La única ventaja que tiene PriorityQueue es permitir duplicados.

    Nota: el recurso no es muy eficiente para grandes colecciones. Usar una búsqueda binaria e insertar una entrada sería más rápido. (pero más complicado)

    EDITAR: Mucho depende de lo que necesita la “lista” para hacer. Le sugiero que escriba un Contenedor de listas para una ArrayList, LinkedList, PriorityQueue, TreeSet o una de las otras colecciones ordenadas e implemente los métodos que realmente se utilizarán. De esta forma, tiene una buena comprensión de los requisitos para la colección y puede asegurarse de que funcione correctamente para usted.

    EDITAR (2): Dado que había mucho interés en usar binarySearch en su lugar. 😉

     List list = new ArrayList() { public boolean add(MyType mt) { int index = Collections.binarySearch(this, mt); if (index < 0) index = ~index; super.add(index, mt); return true; } }; 

    Todos están sugiriendo PriorityQueue . Sin embargo, es importante tener en cuenta que si itera sobre los contenidos de una PriorityQueue , los elementos no estarán ordenados. Solo tiene la garantía de obtener el elemento “mínimo” de los métodos peek() , poll() , etc.

    Un TreeSet parece ser una mejor TreeSet . Las advertencias serían que, como Set , no puede contener elementos duplicados y no admite el acceso aleatorio con un índice.

    Comentario

    Probablemente haya una buena razón para que no exista SortedList implementación SortedList en el JDK. Personalmente, no puedo pensar en una razón para tener una clasificación automática en el JDK.

    Apesta a una optimización prematura que salió mal. Si la lista no se lee tan a menudo como se inserta, entonces perderá ciclos ordenando repetidamente sin ningún motivo. Ordenar antes de leer sería mucho más reactivo y tener un boolean algún lugar que indique que la lista necesita o no ordenarse antes de leer sería aún mejor.

    Lo único que realmente importa es el orden al atravesar la lista con un Iterator o for each ciclo, por lo que llamar a Collections.sort() antes de cualquier código que itere probablemente sea más eficaz que intentar mantener la lista ordenada todo el tiempo en cada inserción.

    Existen ambigüedades con List debido a los duplicados, ¿cómo se ordenan los duplicados de manera determinista? Hay SortedSet , y eso tiene sentido debido a la singularidad. Pero ordenar una List puede tener más complicaciones por los efectos secundarios de duplicados y otras restricciones como hacer que cada objeto sea Comparable o como muestro en mi código, teniendo que tener un Comparator que pueda hacer el trabajo en su lugar.

    Clasificando en .add()

    Si tiene una situación muy especial en la que una List clasificación automática sería útil, una cosa que podría hacer es sub-clase una implementación de List y .add() para hacer una Collections.sort(this, comparator) que usted pasar a un constructor personalizado. Utilicé LinkedList lugar de ArrayList por una razón, ArrayList es una List orden de inserción natural para comenzar. También tiene la capacidad de .add() en un índice que es bastante inútil si quiere una List constantemente ordenada, que tendría que manejarse de alguna manera que probablemente sería menos que ideal. De acuerdo con el Javadoc;

     void add(int index, Object element) 

    Inserta el elemento especificado en la posición especificada en esta lista ( operación opcional ).

    Por lo tanto, solo sería aceptable lanzar UnSupportedOperationException , o simplemente podría ignorar el index y delegar en .add(Object element); si lo documenta en un JavaDoc en el método.

    Por lo general, cuando desea realizar muchas inserciones / eliminaciones y ordenar, debe usar una LinkedList debido a las mejores características de rendimiento dado el uso de la `Lista ‘.

    Aquí hay un ejemplo rápido:

     import java.util.Collections; import java.util.Comparator; import java.util.LinkedList; public class SortedList extends LinkedList { private Comparator comparator; public SortedList(final Comparator comparator) { this.comparator = comparator; } /** * this ignores the index and delegates to .add() * so it will be sorted into the correct place immediately. */ @Override public void add(int index, Object element) { this.add(element); } @Override public boolean add(final E e) { final boolean result = super.add(e); Collections.sort(this, this.comparator); return result; } } 

    La solución más eficiente:

    Alternativamente, solo se podía ordenar al obtener el Iterator y esto estaría más orientado al rendimiento si el orden ordenado fuera realmente importante al iterar sobre la List . Esto cubriría el caso de uso del código del cliente al no tener que llamar, Collections.sort() antes de cada iteración y encapsular ese comportamiento en la clase.

     import java.util.Collections; import java.util.Comparator; import java.util.Iterator; import java.util.LinkedList; public class SortedList extends LinkedList { private Comparator comparator; public SortedList(final Comparator comparator) { this.comparator = comparator; } @Override public Iterator iterator() { Collections.sort(this, this.comparator); return super.iterator(); } } 

    Por supuesto, habría que verificar y controlar los errores para ver si el Comparator era null o no y qué hacer si ese fuera el caso, pero esto le da la idea. Aún no tienes una forma determinista de lidiar con duplicados.

    Solución de Guava:

    Si está usando guayaba y debería estarlo, puede usar

    Ordering.immutableSortedCopy() solo cuando necesita iterar y terminarlo.

    Algo como TreeSet (o TreeMultiset en caso de que necesite duplicados) con un acceso aleatorio más eficiente es posible, pero dudo que se haya implementado en Java. Hacer que cada nodo del árbol recuerde el tamaño de su subárbol izquierdo permite acceder a un elemento por índice en el tiempo O(log(size)) que no está mal.

    Para implementarlo, necesitaría reescribir una buena porción del TreeMap subyacente.

    Yo usaría un Guava TreeMultiset suponiendo que quieres una List porque puedes tener elementos duplicados. Hará todo lo que quieras. Lo único que no tendrá es acceso basado en índices, lo cual no tiene mucho sentido dado que de todos modos no está poniendo elementos en los índices que elija. La otra cosa a tener en cuenta es que en realidad no almacenará duplicados de objetos equal … solo un recuento del número total de ellos.

    commons-collections tiene TreeBag

    Inicialmente sugerí PriorityQueue , pero su orden de iteración no está definido, por lo que no sirve de nada, a menos que lo iteres obteniendo el encabezado de un clon de la cola hasta que se vacíe.

    Como lo más probable es que esté interesado en el orden de iteración, creo que puede anular el método de iterator() :

     public class OrderedIterationList extends ArrayList { @Override public Iterator iterator() { Object[] array = this.toArray(); // O(1) Arrays.sort(array); return Arrays.asList(array).iterator(); // asList - O(1) } } 

    Puede mejorar esto almacenando una instantánea de la colección ordenada, y usar modCount para verificar si la colección no se cambia.

    Dependiendo de los casos de uso, esto puede ser menos o más eficiente que la sugerencia de Peter. Por ejemplo, si agrega varios elementos e itera. (sin agregar elementos entre iteraciones), entonces esto podría ser más eficiente.

    La solución obvia es crear su propia clase que implemente la interfaz java.util.List y tome un Comparator como argumento para el constructor. Utilizaría el comparador en los lugares correctos, es decir, el método add iteraría a través de los elementos existentes e insertaría el nuevo en el lugar correcto. No permitirás llamadas a métodos como add(int index, Object obj) etc.

    De hecho, alguien debe haber creado esto ya … una búsqueda rápida en Google revela al menos un ejemplo:

    http://www.ltg.ed.ac.uk/NITE/nxt/apidoc/net/sourceforge/nite/util/SortedList.html

    La principal diferencia entre SortedSet y List es:

    • SortedSet mantiene su elemento en el orden correcto, pero no puede acceder a un elemento específico por índice.
    • La lista permite el acceso indexado y el ordenamiento arbitrario de los elementos. También permite cambiar cualquier elemento (por índice o iterador) a otro elemento, sin que la ubicación cambie.

    Parece que desea una especie de fusión de ambos: clasificación automática y acceso al índice (razonablemente rápido). Según el tamaño de los datos y la frecuencia con la lectura indexada o la adición de nuevos elementos, estas son mis ideas:

    • ArrayList envuelto, donde el método add usa un ListIterator para encontrar el lugar de inserción, luego insertando el elemento allí. Esto es O (n) para inserciones, O (1) para acceso indexado.
    • una LinkedList envolvente, donde el método add utilizó un ListIterator para encontrar el lugar de inserción, luego insertando el elemento allí. (Esto todavía es O (n) para inserciones (con factor a veces bastante menor como ArrayList, a veces incluso más), así como acceso indexado).
    • un árbol binario modificado haciendo un seguimiento de los tamaños de ambas mitades en cada nivel, lo que permite el acceso indexado. (Esto sería O (log n) para cada acceso, pero necesita alguna progtwigción adicional, ya que aún no está incluido en Java SE. O puede encontrar alguna biblioteca que pueda hacerlo.)

    En cualquier caso, las interfaces y los contratos de SortedSet y List no son realmente compatibles, por lo que querrá que la parte de la Lista sea de solo lectura (o de solo lectura y eliminación), no permita la configuración y la adición, y tenga un extra objeto (tal vez implementando la interfaz de Colección) para agregar Objetos.

    La única forma de tener cualquier estructura ordenada con menos de O (n) tiempo para agregar / indexOf / remove / get element es usando un árbol. En ese caso, las operaciones generalmente tienen O (log2n) y poligonal es como O (1).

    O (n) es solo una lista vinculada.


    Editar: insertando en la lista vinculada w / búsqueda binaria. Para las operaciones de inserción, no usar estructura binaria, y tamaños no pequeños, eso debería ser óptimo.

    @Peter: existe el algo w / O (log2n) que se compara (que es lento) para insertar y O (n) se mueve. Si necesita anular LinkedList, que así sea. Pero eso es lo mejor que puede obtener. Mantengo el algoritmo lo más limpio posible para que sea más comprensible, se puede optimizar un poco.

     package t1; import java.util.LinkedList; import java.util.List; import java.util.ListIterator; import java.util.Random; public class SortedList { private static  int binarySearch(ListIterator< ? extends Comparable> i, T key){ int low = 0; int high= i.previousIndex(); while (low < = high) { int mid = (low + high) >>> 1; Comparable< ? super T> midVal = get(i, mid); int cmp = midVal.compareTo(key); if (cmp < 0) low = mid + 1; else if (cmp > 0) high = mid - 1; else return mid; } return -(low + 1); // key not found } private static  T get(ListIterator< ? extends T> i, int index) { T obj = null; int pos = i.nextIndex(); if (pos < = index) { do { obj = i.next(); } while (pos++ < index); } else { do { obj = i.previous(); } while (--pos > index); } return obj; } private static void move(ListIterator< ?> i, int index) { int pos = i.nextIndex(); if (pos==index) return; if (pos < index) { do { i.next(); } while (++pos < index); } else { do { i.previous(); } while (--pos > index); } } @SuppressWarnings("unchecked") static  int insert(List< ? extends Comparable> list, T key){ ListIterator< ? extends Comparable> i= list.listIterator(list.size()); int idx = binarySearch(i, key); if (idx<0){ idx=~idx; } move(i, idx); ((ListIterator)i).add(key); return i.nextIndex()-1; } public static void main(String[] args) { LinkedList list = new LinkedList(); LinkedList unsorted = new LinkedList(); Random r =new Random(11); for (int i=0;i<33;i++){ Integer n = r.nextInt(17); insert(list, n); unsorted.add(n); } System.out.println(" sorted: "+list); System.out.println("unsorted: "+unsorted); } 

    Considere el mapa de árbol indexado que creé al enfrentar un problema similar, podrá acceder a los elementos por índice y obtener el índice de los elementos mientras mantiene el orden de clasificación. Los duplicados se pueden poner en matrices como valores bajo la misma clave.

    En la jerarquía JavaFX TransformationList, hay algo llamado SortedList. La lista es completamente observable, de modo que las adiciones / eliminaciones notificarán a cualquier otro oyente que vea la lista.

    El enfoque básico para hacer esto es mirar otra ObservableList para los cambios y usar Collections.binarySearch () de manera estratégica, ya que otros han sugerido ubicar el índice de la adición o eliminación en el tiempo Olog (n).

    Hay un problema que no he visto mencionado aquí y que es la capacidad de rastrear elementos agregados que tienen la misma comparación para la firma, es decir, T1.compareTo (T2) == 0. En este caso, la lista ordenada (voy a publicar la mía el código fuente a continuación) debe tener un tipo de elemento contenedor, que llamaré Elemento . Esto es similar a lo que hicieron los creadores de JavaFX con SortedList . La razón para esto se debe totalmente a las operaciones de eliminación, es imposible ubicar el elemento original si hay compareTo duplicates. Normalmente, en una implementación de NavigableSet como TreeSet, estos duplicados nunca entrarían en el conjunto. Una lista es diferente.

    Tengo una biblioteca de listas observables que pueden encadenarse eficazmente juntas (muy similar a las secuencias de Java) que propagan completamente los resultados en sentido descendente a medida que se actualiza la fuente anterior en la cadena.

    Jerarquía de clase

    Interfaz

     /** * Binds the elements of this list to the function application of each element of a * source observable list. * 

    * While a {@code IListContentBinding} is bound, any attempt to modify its contents * will result in an {@code UnsupportedOperationException}. To unbind the list, call * {@link #unbind() unbind}. * * @param The element type of the input source list that will generate change * events. * @param The element type of this output list. */ public interface IListContentBinding extends ObservableList, ObservableListValue, IContentBinding {... details not shown ....}

    Clase base abstracta para todos los tipos de enlace (Ordenar, Distinto, Mapa, Mapa plano, etc.)

     /** * Binds the elements of this list to the function application of each element of a * source observable list. * 

    * While a {@code ListContentBinding} is bound, any attempt to modify its contents * will result in an {@code UnsupportedOperationException}. To unbind the list, call * {@link #unbind() unbind}. * * @param The element type of the source list that will generate change events. * @param The element type of this binding. */ public abstract class ListContentBinding extends ObservableListWrapper implements IListContentBinding {.... details not shown ....}

    Clase de encuadernación

     /** * A {@code ListContentBinding} implementation that generates sorted elements from a * source list. The comparator can be set to another {@code Comparator} function at * any time through the {@link #comparatorProperty() comparator} property. * 

    * Unlike the Collections {@link Collections#sort(List) list sort} or Arrays * {@link Arrays#sort(Object[]) array sort}, once this binding has been added to the * order of duplicate elements cannot be guaranteed to match the original order of * the source list. That is the insertion and removal mechanism do not guarantee that * the original order of duplicates (those items where T1.compareTo(T2) == 0) is * preserved. However, any removal from the source list is guaranteed to * remove the exact object from this sorted list. This is because an int ID field * is added to the wrapped item through the {@link Element} class to ensure that * matching duplicates can be further compared. *

    * Added/Removed objects from the source list are placed inside this sorted list * through the {@link Arrays#binarySearch(Object[], Object, Comparator) array binary * search} algorithm. For any duplicate item in the sorted list, a further check on * the ID of the {@code Element} corresponding to that item is compared to the * original, and that item. Each item added to this sorted list increases the * counter, the maximum number of items that should be placed in this list should be * no greater than {@code Integer.MAX_VALUE - Integer.MIN_VALUE}, or 4,294,967,295 * total elements. Sizes greater than this value for an instance of this class * may produce unknown behavior. *

    * Removal and additions to this list binding are proportional to O(logn) * runtime, where n is the current total number of elements in this sorted * list. * * @param The element type of the source and this list binding. */ class ListContentSortBinding extends ListContentBinding implements IListContentSortBinding { /** * Each location in the source list has a random value associated it with to deal * with duplicate elements that would return T1.compareTo(T2) == 0. */ private Element[] elements = newElementArray(10); /** * The same elements from {@link #elements} but placed in their correct sorted * position according to the {@link #elementComparator element comparator}. */ protected Element[] sortedElements = newElementArray(10); /** * Create a new instance. * * @param source The source observable list. Sorted elements will be generated * from the source and set as the content of this list binding. * @param comparator The sorter. An observable that will update the comparator of * this binding when invalidated. The sorter can be set to another * {@code Comparator} function at anytime through the * {@link #comparatorProperty() comparator} property. * @param options The options of this binding. Considers {@code DependencyOption} * instances. *

    * All bindings consider {@code BeforeChangeOption} and * {@code AfterChangeOption}. */ @SafeVarargs ListContentSortBinding(ObservableList source, ObservableObjectValue> comparator, BindingOption... options) { this(source, comparator.get(), options); comparatorProperty().bind(comparator); } /** * Create a new instance. * * @param source The source observable list. Sorted elements will be generated * from the source and set as the content of this list binding. * @param comparator The sorter. The sorter can be set to another * {@code Comparator} function at anytime through the * {@link #comparatorProperty() comparator} property. * @param options The options of this binding. Considers {@code DependencyOption} * instances. *

    * All bindings consider {@code BeforeChangeOption} and * {@code AfterChangeOption}. */ @SafeVarargs ListContentSortBinding(ObservableList source, Comparator< ? super T> comparator, BindingOption... options) { super(new ArrayList<>(), options); List observables = new ArrayList<>( Arrays.asList(BindingOptionBuilder.extractDependencies(options))); setComparator(comparator); observables.add(comparatorProperty()); bind(source, observables.toArray(new Observable[observables.size()])); } @Override protected void sourceChanged(Change< ? extends T> change) { List< ? extends T> source = change.getList(); while (change.next()) { int from = change.getFrom(); if (change.wasPermutated() || change.wasUpdated()) { List< ? extends T> srcMod = source.subList(from, change.getTo()); removed(source, from, srcMod.size()); added(source, from, srcMod); } else { List< ? extends T> removed = change.getRemoved(); List< ? extends T> added = change.getAddedSubList(); if (change.wasReplaced()) { int min = Math.min(added.size(), removed.size()); replaced(source, from, added.subList(0, min)); added = added.subList(min, added.size()); removed = removed.subList(min, removed.size()); } if (removed.size() > 0) { removed(source, from, removed.size()); } if (added.size() > 0) { if (source.size() >= elements.length) { ensureSize(source.size()); } added(source, from, added); } ensureSize(source.size()); } } } /** * Replace the items in this sorted list binding resulting from a replacement * operation in the source list. For each of the items added starting at the * from index in the source list, and items was removed at the same source * position. * * @param source The source list. * @param from The index of where the replacement started in the source * (inclusive). The removed and added elements occurred starting at * the same source position. * @param added The added source elements from the change. */ @SuppressWarnings({}) private void replaced(List< ? extends T> source, int from, List< ? extends T> added) { int oldSize = size(); for (int i = 0; i < added.size(); i++) { int index = from + i; Element e = elements[index]; // Find the old element and remove it int pos = findPosition(e, index, oldSize); System.arraycopy(sortedElements, pos + 1, sortedElements, pos, oldSize - pos - 1); remove(pos); T t = added.get(i); // Create a new element and add it e = new Element(t); elements[index] = e; pos = findPosition(e, index, oldSize - 1); if (pos < 0) { pos = ~pos; } System.arraycopy(sortedElements, pos, sortedElements, pos + 1, oldSize - pos - 1); sortedElements[pos] = e; add(pos, t); } } /** * Add the elements from the source observable list to this binding. * * @param source The source list. * @param from The index of where the addition started in the source (inclusive). * @param added The added source elements from the change. */ @SuppressWarnings({}) private void added(List source, int from, List< ? extends T> added) { if (size() == 0) { int size = added.size(); Element[] temp = newElementArray(size); for (int i = 0; i < added.size(); i++) { T t = added.get(i); Element e = new Element(t); elements[i] = e; temp[i] = e; } if (elementComparator == null) { addAll(added); return; } Arrays.sort(temp, elementComparator); System.arraycopy(temp, 0, sortedElements, 0, temp.length); addAll(Arrays.stream(temp).map(e -> (T) et).collect(Collectors.toList())); return; } int size = size(); System.arraycopy(elements, from, elements, from + added.size(), size - from); for (int i = 0; i < added.size(); i++) { int index = from + i; T t = added.get(i); Element e = new Element(t); int pos = findPosition(e, index, size); if (pos < 0) { pos = ~pos; } elements[index] = e; if (pos < size) { System.arraycopy(sortedElements, pos, sortedElements, pos + 1, size - pos); } sortedElements[pos] = e; add(pos, t); size++; } } /** * Remove the elements from this binding that were removed from the source list. * Update the {@link #elements} mapping. * * @param source The source list. * @param from The index of where the removal started in the source (inclusive). * @param removedSize The total number of removed elements from the source list * for the change. */ @SuppressWarnings({}) private void removed(List source, int from, int removedSize) { if (source.size() == 0) { elements = newElementArray(10); sortedElements = newElementArray(10); elementCounter = Integer.MIN_VALUE; clear(); return; } int oldSize = size(); int size = oldSize; for (int i = 0; i < removedSize; i++) { int index = from + i; Element e = elements[index]; int pos = findPosition(e, index, size); System.arraycopy(sortedElements, pos + 1, sortedElements, pos, size - pos - 1); remove(pos); sortedElements[--size] = null; } System.arraycopy(elements, from + removedSize, elements, from, oldSize - from - removedSize); for (int i = size; i < oldSize; i++) { elements[i] = null; } } /** * Locate the position of the element in this sorted binding by performing a * binary search. A binary search locates the index of the add in Olog(n) time. * * @param e The element to insert. * @param sourceIndex The index of the source list of the modification. * @param size The size of the array to search, exclusive. * * @return The position in this binding that the element should be inserted. */ private int findPosition(Element e, int sourceIndex, int size) { if (size() == 0) { return 0; } int pos; if (elementComparator != null) { pos = Arrays.binarySearch(sortedElements, 0, size, e, elementComparator); } else { pos = sourceIndex; } return pos; } /** * Ensure that the element array is large enough to handle new elements from the * source list. Also shrinks the size of the array if it has become too large * with respect to the source list. * * @param size The minimum size of the array. */ private void ensureSize(int size) { if (size >= elements.length) { int newSize = size * 3 / 2 + 1; Element[] replacement = newElementArray(newSize); System.arraycopy(elements, 0, replacement, 0, elements.length); elements = replacement; replacement = newElementArray(newSize); System.arraycopy(sortedElements, 0, replacement, 0, sortedElements.length); sortedElements = replacement; } else if (size < elements.length / 4) { int newSize = size * 3 / 2 + 1; Element[] replacement = newElementArray(newSize); System.arraycopy(elements, 0, replacement, 0, replacement.length); elements = replacement; replacement = newElementArray(newSize); System.arraycopy(sortedElements, 0, replacement, 0, replacement.length); sortedElements = replacement; } } /** * Combines the {@link #comparatorProperty() item comparator} with a secondary * comparison if the items are equal through the compareTo operation. This * is used to quickly find the original item when 2 or more items have the same * comparison. */ private Comparator elementComparator; /** * @see #comparatorProperty() */ private ObjectProperty> comparator = new SimpleObjectProperty>(this, "comparator") { @Override protected void invalidated() { Comparator< ? super T> comp = get(); if (comp != null) { elementComparator = Comparator.nullsLast((e1, e2) -> { int c = comp.compare(e1.t, e2.t); return c == 0 ? Integer.compare(e1.id, e2.id) : c; }); } else { elementComparator = null; } } }; @Override public final ObjectProperty> comparatorProperty() { return comparator; } @Override public final Comparator< ? super T> getComparator() { return comparatorProperty().get(); } @Override public final void setComparator(Comparator< ? super T> comparator) { comparatorProperty().set(comparator); } @Override protected void onInvalidating(ObservableList source) { clear(); ensureSize(source.size()); added(source, 0, source); } /** * Counter starts at the Integer min value, and increments each time a new * element is requested. If this list becomes empty, the counter is restarted at * the min value. */ private int elementCounter = Integer.MIN_VALUE; /** * Generate a new array of {@code Element}. * * @param size The size of the array. * * @return A new array of null Elements. */ @SuppressWarnings("unchecked") private Element[] newElementArray(int size) { return new ListContentSortBinding.Element[size]; }

    Clase de Elemento Wrapper

      /** * Wrapper class to further aid in comparison of two object types <T>. Since * sorting in a list allows duplicates we must assure that when a removal occurs * from the source list feeding this binding that the removed element matches. To * do this we add an arbitrary int field inside this element class that * wraps around the original object type <T>. */ final class Element { /** Object */ private final T t; /** ID helper for T type duplicates */ private int id; Element(T t) { this.t = Objects.requireNonNull(t); this.id = elementCounter++; } @Override public String toString() { return t.toString() + " (" + id + ")"; } } } 

    PRUEBA DE VERIFICACIÓN DE JUNIT

     @Test public void testSortBinding() { ObservableList source = FXCollections.observableArrayList(); int size = 100000; for (int i = 0; i < size / 2; i++) { int index = (int) (Math.random() * size / 10); source.add(new IntWrapper(index)); } ListContentSortBinding binding = (ListContentSortBinding) CollectionBindings.createListBinding(source).sortElements(); Assert.assertEquals("Sizes not equal for sorted binding | Expected: " + source.size() + ", Actual: " + binding.size(), source.size(), binding.size()); List sourceSorted = new ArrayList<>(source); Collections.sort(sourceSorted); for (int i = 0; i < source.size(); i++) { IntWrapper expected = sourceSorted.get(i); IntWrapper actual = binding.get(i); Assert.assertEquals("Elements not equal in expected sorted lists | Expected: " + expected.value + ", Actual: " + actual.value, expected.value, actual.value); } System.out.println("Sorted Elements Equal: Complete."); // Randomly add chunks of elements at random locations in the source int addSize = size / 10000; for (int i = 0; i < size / 4; i++) { List added = new ArrayList<>(); int toAdd = (int) (Math.random() * addSize); for (int j = 0; j < toAdd; j++) { int index = (int) (Math.random() * size / 10); added.add(new IntWrapper(index)); } int atIndex = (int) (Math.random() * source.size()); source.addAll(atIndex, added); } sourceSorted = new ArrayList<>(source); Collections.sort(sourceSorted); for (int i = 0; i < source.size(); i++) { IntWrapper expected = sourceSorted.get(i); IntWrapper actual = binding.get(i); Assert.assertEquals("Elements not equal in expected sorted lists | Expected: " + expected.value + ", Actual: " + actual.value, expected.value, actual.value); } System.out.println("Sorted Elements Equal - Add Multiple Elements: Complete."); // Remove one element at a time from the source list and compare // to the elements that were removed from the sorted binding // as a result. They should all be identical index for index. List sourceRemoved = new ArrayList<>(); List bindingRemoved = new ArrayList<>(); ListChangeListener bindingListener = change -> { while (change.next()) { if (change.wasRemoved()) { bindingRemoved.addAll(change.getRemoved()); } } }; // Watch the binding for changes after the upstream source changes binding.addListener(bindingListener); for (int i = 0; i < size / 4; i++) { int index = (int) (Math.random() * source.size()); IntWrapper removed = source.remove(index); sourceRemoved.add(removed); } for (int i = 0; i < bindingRemoved.size(); i++) { IntWrapper expected = bindingRemoved.get(i); IntWrapper actual = sourceRemoved.get(i); Assert.assertEquals("Elements not equal in expected sorted lists | Expected: " + expected + ", Actual: " + actual, expected.value, actual.value); Assert.assertEquals("Element refs not equal in expected sorted lists | Expected: " + expected.value + ", Actual: " + actual.value, expected.r, actual.r, 0); } System.out.println("Sorted Remove Single Element: Complete."); // Replace random elements from the source list bindingRemoved.clear(); sourceRemoved.clear(); int removeSize = size / 10000; for (int i = 0; i < size / 1000; i++) { int replaceIndex = (int) (Math.random() * source.size()); int index = (int) (Math.random() * size / 10); IntWrapper replace = new IntWrapper(index); source.set(replaceIndex, replace); } sourceSorted = new ArrayList<>(source); Collections.sort(sourceSorted); for (int i = 0; i < source.size(); i++) { IntWrapper expected = sourceSorted.get(i); IntWrapper actual = binding.get(i); Assert.assertEquals("Elements not equal in expected sorted lists | Expected: " + expected.value + ", Actual: " + actual.value, expected.value, actual.value); } System.out.println("Sorted Elements Replace: Complete."); // Remove random chunks from the source list bindingRemoved.clear(); sourceRemoved.clear(); Set sourceRemovedSet = Collections.newSetFromMap(new IdentityHashMap<>()); // set for speed while (source.size() > 0) { int index = (int) (Math.random() * source.size()); int toRemove = (int) (Math.random() * removeSize); toRemove = Math.min(toRemove, source.size() - index); List removed = source.subList(index, index + toRemove); sourceRemovedSet.addAll(new ArrayList<>(removed)); removed.clear(); // triggers list change update to binding } Assert.assertEquals(bindingRemoved.size(), sourceRemovedSet.size()); // The binding removed will not necessarily be placed in the same order // since the change listener on the binding will make sure that the final // order of the change from the binding is in the same order as the binding // element sequence. We therefore must do a contains() to test. for (int i = 0; i < bindingRemoved.size(); i++) { IntWrapper expected = bindingRemoved.get(i); Assert.assertTrue("Binding Removed Did Not Contain Source Removed", sourceRemovedSet.contains(expected)); } System.out.println("Sorted Removed Multiple Elements: Complete."); } 

    JUNIT BENCHMARK TEST

      @Test public void sortBindingBenchmark() { ObservableList source = FXCollections.observableArrayList(); ObservableList binding = (ListContentSortBinding) CollectionBindings.createListBinding(source).sortElements(); int size = 200000; Set toAdd = new TreeSet<>(); while (toAdd.size() < size) { int index = (int) (Math.random() * size * 20); toAdd.add(new IntWrapper(index)); } // Randomize the order toAdd = new HashSet<>(toAdd); System.out.println("Sorted Binding Benchmark Setup: Complete."); long time = System.currentTimeMillis(); for (IntWrapper w : toAdd) { source.add(w); } long bindingTime = System.currentTimeMillis() - time; System.out.println("Sorted Binding Time: Complete."); source.clear(); // clear the list and re-add ObservableList sortedList = new SortedList<>(source); time = System.currentTimeMillis(); for (IntWrapper w : toAdd) { source.add(w); } long sortedListTime = System.currentTimeMillis() - time; System.out.println("JavaFX Sorted List Time: Complete."); // Make the test "fair" by adding a listener to an observable // set that populates the sorted set ObservableSet obsSet = FXCollections.observableSet(new HashSet<>()); Set sortedSet = new TreeSet<>(); obsSet.addListener((SetChangeListener) change -> { sortedSet.add(change.getElementAdded()); }); time = System.currentTimeMillis(); for (IntWrapper w : toAdd) { obsSet.add(w); } long setTime = System.currentTimeMillis() - time; System.out.println("Sorted Binding Benchmark Time: Complete"); Assert.assertEquals(sortedSet.size(), binding.size()); System.out.println("Binding: " + bindingTime + " ms, " + "JavaFX Sorted List: " + sortedListTime + " ms, " + "TreeSet: " + setTime + " ms"); } 

    Wrapper Class for Tests Only

      /** * Wrapper class for testing sort bindings. Verifies that duplicates were sorted * and removed correctly based on the object instance. */ private static class IntWrapper implements Comparable { static int counter = Integer.MIN_VALUE; final int value; final int id; IntWrapper(int value) { this.value = value; this.id = counter++; } 

    The best way to do this would be to override the add implementation of a list. I’m going to use a LinkedList to demonstrate it, as it allows for efficient insertion.

     public boolean add(Integer e) { int i = 0; for (Iterator it = this.iterator(); it.hasNext();) { int current = it.next(); if(current > e) { super.add(i, e); return true; } i++; } return super.add(e); } 

    The above code creates a sorted list of integers, that is always sorted. It can easily be modified to work with any other datatype. However here you will have to avoid using the add(index, value) function, as that would obviously break the sorting.

    Although people above suggested using Arrays.sort(), I would avoid that, as it can be a significantly less efficient approach, especially since the sort method must be called with every addition to the list.

    The contract of the ListIterator interface makes it a bit cumbersome, but this method will perform the insertion using a single scan of the list (up to the insertion point):

     private void add(Integer value) { ListIterator listIterator = list.listIterator(); Integer next = null; while (listIterator.hasNext()) { next = listIterator.next(); if (next.compareTo(value) > 0) { break; } } if (next == null || next.compareTo(value) < 0) { listIterator.add(value); } else { listIterator.set(value); listIterator.add(next); } } 

    SortedSet

    Any implementation of the SortedSet interface carries your desired behavior.

    By default, objects added are sorted in their natural order, that is, based on their implementation of the Comparable::compareTo interface method.

    Alternatively, you can pass a Comparator implementation to determine the sort.

    TreeSet

    The TreeSet is a commonly used implantation of SortedSet . You can also find others.

    Duplicates

    The major difference between a List and a SortedSet is duplicates, objects that compare as equal. A List allows duplicates whereas a SortedSet , like any Set , does not.

    Access by index

    Another difference is that a Set cannot be accessed by index. You can not locate an object by its position number within the collection.

    If you need such access after constructing your SortedSet , make a List . There are multiple ways to do this, such as passing the SortedSet to constructor of ArrayList . A mote recent way, as of Java 10, is to make an umodifiable List by passing the SortedSet to List.copyOf .

    I believe a Priority Queue will do the job.

    Caveat (from the same doc page):

    This class and its iterator implement all of the optional methods of the Collection and Iterator interfaces. The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()) .