Lista de matrices ordenadas en Java

Estoy desconcertado de no poder encontrar una respuesta rápida a esto. Básicamente, estoy buscando una estructura de datos en Java que implemente la java.util.Listinterfaz, pero que almacene sus miembros en un orden ordenado. Sé que puede usar un normal ArrayListy usarlo Collections.sort()en él, pero tengo un escenario en el que ocasionalmente agrego y, a menudo, recupero miembros de mi lista y no quiero tener que ordenarlo cada vez que recupero un miembro en caso de que se ha agregado uno nuevo. ¿Alguien puede señalarme algo así que existe en el JDK o incluso en bibliotecas de terceros?

EDITAR : La estructura de datos deberá conservar los duplicados.

RESUMEN DE RESPUESTA : Todo esto me pareció muy interesante y aprendí mucho. Aioobe, en particular, merece una mención por su perseverancia en tratar de lograr mis requisitos anteriores (principalmente una implementación java.util.List ordenada que admite duplicados). He aceptado su respuesta como la más precisa para lo que pregunté y la más estimulante sobre las implicaciones de lo que estaba buscando, incluso si lo que pregunté no era exactamente lo que necesitaba.

El problema con lo que pedí radica en la interfaz List en sí y el concepto de métodos opcionales en una interfaz. Para citar el javadoc:

El usuario de esta interfaz tiene un control preciso sobre en qué lugar de la lista se inserta cada elemento.

Insertar en una lista ordenada no tiene un control preciso sobre el punto de inserción. Luego, debes pensar cómo manejarás algunos de los métodos. Tomemos addpor ejemplo:

public boolean add (Objeto o)

 Appends the specified element to the end of this list (optional operation).

Ahora se encuentra en la incómoda situación de 1) Romper el contrato e implementar una versión ordenada de agregar 2) Dejar que addagregue un elemento al final de la lista, rompiendo su orden ordenado 3) Salir add(como opcional) tirando an UnsupportedOperationExceptione implementando otro método que agrega elementos en un orden ordenado.

La opción 3 es probablemente la mejor, pero me resulta desagradable tener un método de adición que no puede usar y otro método sortedAdd que no está en la interfaz.

Otras soluciones relacionadas (sin ningún orden en particular):

• java.util.PriorityQueue, que probablemente esté más cerca de lo que necesitaba que de lo que pedí. Una cola no es la definición más precisa de una colección de objetos en mi caso, pero funcionalmente hace todo lo que necesito.
• net.sourceforge.nite.util.SortedList . Sin embargo, esta implementación rompe el contrato de la interfaz List al implementar la clasificación en el add(Object obj)método y, curiosamente, no tiene ningún efecto para add(int index, Object obj). El consenso general sugiere que throw new UnsupportedOperationException()podría ser una mejor opción en este escenario.
• TreeMultiSet de Guava Una implementación de conjunto que admite duplicados
• ca.odell.glazedlists.SortedList Esta clase viene con la advertencia en su javadoc:Warning: This class breaks the contract required by List

Solución minimalista

Aquí hay una solución "mínima".

class SortedArrayList<T> extends ArrayList<T> {

    @SuppressWarnings("unchecked")
    public void insertSorted(T value) {
        add(value);
        Comparable<T> cmp = (Comparable<T>) value;
        for (int i = size()-1; i > 0 && cmp.compareTo(get(i-1)) < 0; i--)
            Collections.swap(this, i, i-1);
    }
}

La inserción se ejecuta en tiempo lineal, pero eso sería lo que obtendría usando una ArrayList de todos modos (todos los elementos a la derecha del elemento insertado tendrían que ser desplazados de una forma u otra).

Insertar algo no comparable da como resultado una ClassCastException. (Este es también el enfoque adoptado por PriorityQueue: una cola de prioridad que se basa en el orden natural tampoco permite la inserción de objetos no comparables (hacerlo puede resultar en ClassCastException). )

Primordial List.add

Tenga en cuenta que anular List.add(o List.addAllpara el caso) insertar elementos de forma ordenada sería una violación directa de la especificación de la interfaz . Lo que podría hacer es anular este método para lanzar un UnsupportedOperationException.

De los documentos de List.add:

boolean add(E e)
    Agrega el elemento especificado al final de esta lista (operación opcional).

El mismo razonamiento se aplica a ambas versiones de add, ambas versiones de addAlly set. (Todas las cuales son operaciones opcionales según la interfaz de lista).

Algunas pruebas

SortedArrayList<String> test = new SortedArrayList<String>();

test.insertSorted("ddd");    System.out.println(test);
test.insertSorted("aaa");    System.out.println(test);
test.insertSorted("ccc");    System.out.println(test);
test.insertSorted("bbb");    System.out.println(test);
test.insertSorted("eee");    System.out.println(test);

....huellas dactilares:

[ddd]
[aaa, ddd]
[aaa, ccc, ddd]
[aaa, bbb, ccc, ddd]
[aaa, bbb, ccc, ddd, eee]

Utilice java.util.PriorityQueue.

Eche un vistazo a SortedList

Esta clase implementa una lista ordenada. Está construido con un comparador que puede comparar dos objetos y ordenarlos en consecuencia. Cuando agrega un objeto a la lista, se inserta en el lugar correcto. Los objetos que sean iguales según el comparador, estarán en la lista en el orden en que fueron agregados a esta lista. Agregue solo objetos que el comparador pueda comparar.

Cuando la lista ya contiene objetos que son iguales según el comparador, el nuevo objeto se insertará inmediatamente después de estos otros objetos.

Puede probar TreeMultiSet de Guava .

 Multiset<Integer> ms=TreeMultiset.create(Arrays.asList(1,2,3,1,1,-1,2,4,5,100));
 System.out.println(ms);

El enfoque de Aioobe es el camino a seguir. Sin embargo, me gustaría sugerir la siguiente mejora sobre su solución.

class SortedList<T> extends ArrayList<T> {

    public void insertSorted(T value) {
        int insertPoint = insertPoint(value);
        add(insertPoint, value);
    }

    /**
     * @return The insert point for a new value. If the value is found the insert point can be any
     * of the possible positions that keeps the collection sorted (.33 or 3.3 or 33.).
     */
    private int insertPoint(T key) {
        int low = 0;
        int high = size() - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            Comparable<? super T> midVal = (Comparable<T>) get(mid);
            int cmp = midVal.compareTo(key);

            if (cmp < 0)
                low = mid + 1;
            else if (cmp > 0)
                high = mid - 1;
            else {
                return mid; // key found
            }
        }

        return low;  // key not found
    }
}

La solución de aioobe se vuelve muy lenta cuando se usan listas grandes. Usar el hecho de que la lista está ordenada nos permite encontrar el punto de inserción para nuevos valores usando la búsqueda binaria.

También usaría la composición sobre la herencia, algo así como

SortedList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable

Las listas suelen conservar el orden en el que se agregan los elementos. ¿Definitivamente necesita una lista , o sería adecuado para usted un conjunto ordenado (por ejemplo TreeSet<E>)? Básicamente, ¿necesita conservar los duplicados?

Puede que sea un poco demasiado pesado para usted, pero GlazedLists tiene una SortedList que es perfecta para usar como modelo de una tabla o JList

Puede crear una subclase de ArrayList y llamar a Collections.sort (this) después de agregar cualquier elemento; necesitaría anular dos versiones de add y dos de addAll para hacer esto.

El rendimiento no sería tan bueno como una implementación más inteligente que insertara elementos en el lugar correcto, pero funcionaría. Si la adición a la lista es poco común, el costo amortizado de todas las operaciones de la lista debería ser bajo.

Simplemente crea una nueva clase como esta:

public class SortedList<T> extends ArrayList<T> {

private final Comparator<? super T> comparator;

public SortedList() {
    super();
    this.comparator = null;
}

public SortedList(Comparator<T> comparator) {
    super();
    this.comparator = comparator;
}

@Override
public boolean add(T item) {
    int index = comparator == null ? Collections.binarySearch((List<? extends Comparable<? super T>>)this, item) :
            Collections.binarySearch(this, item, comparator);
    if (index < 0) {
        index = index * -1 - 2;
    }
    super.add(index+1, item);
    return true;
}

@Override
public void add(int index, T item) {
    throw new UnsupportedOperationException("'add' with an index is not supported in SortedArrayList");
}

@Override
public boolean addAll(Collection<? extends T> items) {
    boolean allAdded = true;
    for (T item : items) {
        allAdded = allAdded && add(item);
    }
    return allAdded;
}

@Override
public boolean addAll(int index, Collection<? extends T> items) {
    throw new UnsupportedOperationException("'addAll' with an index is not supported in SortedArrayList");
}

}

Puedes probarlo así:

    List<Integer> list = new SortedArrayList<>((Integer i1, Integer i2) -> i1.compareTo(i2));
    for (Integer i : Arrays.asList(4, 7, 3, 8, 9, 25, 20, 23, 52, 3)) {
        list.add(i);
    }
    System.out.println(list);

Creo que la elección entre SortedSets / Lists y colecciones ordenables 'normales' depende de si necesita ordenar solo con fines de presentación o en casi todos los puntos durante el tiempo de ejecución. Usar una colección ordenada puede ser mucho más costoso porque la ordenación se realiza cada vez que inserta un elemento.

Si no puede optar por una colección en el JDK, puede echar un vistazo a las colecciones de Apache Commons

Dado que las implementaciones propuestas actualmente que implementan una lista ordenada rompiendo la API de colección, tienen una implementación propia de un árbol o algo similar, tenía curiosidad por saber cómo funcionaría una implementación basada en TreeMap. (Especialmente porque el TreeSet también se basa en TreeMap)

Si alguien también está interesado en eso, puede sentirse libre de investigarlo:

TreeList

Es parte de la biblioteca principal , puede agregarlo a través de la dependencia de Maven, por supuesto. (Licencia Apache)

Actualmente, la implementación parece comparar bastante bien al mismo nivel que el guava SortedMultiSet y el TreeList de la biblioteca Apache Commons.

Pero me alegraría si más que yo probara la implementación para estar seguro de que no me he perdido algo importante.

¡Atentamente!

Yo tuve el mismo problema. Así que tomé el código fuente de java.util.TreeMap y escribí IndexedTreeMap . Implementa mi propio IndexedNavigableMap :

public interface IndexedNavigableMap<K, V> extends NavigableMap<K, V> {
   K exactKey(int index);
   Entry<K, V> exactEntry(int index);
   int keyIndex(K k);
}

La implementación se basa en actualizar los pesos de los nodos en el árbol rojo-negro cuando se cambia. El peso es el número de nodos secundarios debajo de un nodo dado, más uno mismo. Por ejemplo, cuando un árbol se gira hacia la izquierda:

    private void rotateLeft(Entry<K, V> p) {
    if (p != null) {
        Entry<K, V> r = p.right;

        int delta = getWeight(r.left) - getWeight(p.right);
        p.right = r.left;
        p.updateWeight(delta);

        if (r.left != null) {
            r.left.parent = p;
        }

        r.parent = p.parent;


        if (p.parent == null) {
            root = r;
        } else if (p.parent.left == p) {
            delta = getWeight(r) - getWeight(p.parent.left);
            p.parent.left = r;
            p.parent.updateWeight(delta);
        } else {
            delta = getWeight(r) - getWeight(p.parent.right);
            p.parent.right = r;
            p.parent.updateWeight(delta);
        }

        delta = getWeight(p) - getWeight(r.left);
        r.left = p;
        r.updateWeight(delta);

        p.parent = r;
    }
  }

updateWeight simplemente actualiza los pesos hasta la raíz:

   void updateWeight(int delta) {
        weight += delta;
        Entry<K, V> p = parent;
        while (p != null) {
            p.weight += delta;
            p = p.parent;
        }
    }

Y cuando necesitamos encontrar el elemento por índice aquí está la implementación que usa pesos:

public K exactKey(int index) {
    if (index < 0 || index > size() - 1) {
        throw new ArrayIndexOutOfBoundsException();
    }
    return getExactKey(root, index);
}

private K getExactKey(Entry<K, V> e, int index) {
    if (e.left == null && index == 0) {
        return e.key;
    }
    if (e.left == null && e.right == null) {
        return e.key;
    }
    if (e.left != null && e.left.weight > index) {
        return getExactKey(e.left, index);
    }
    if (e.left != null && e.left.weight == index) {
        return e.key;
    }
    return getExactKey(e.right, index - (e.left == null ? 0 : e.left.weight) - 1);
}

También es muy útil encontrar el índice de una clave:

    public int keyIndex(K key) {
    if (key == null) {
        throw new NullPointerException();
    }
    Entry<K, V> e = getEntry(key);
    if (e == null) {
        throw new NullPointerException();
    }
    if (e == root) {
        return getWeight(e) - getWeight(e.right) - 1;//index to return
    }
    int index = 0;
    int cmp;
    index += getWeight(e.left);

    Entry<K, V> p = e.parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        while (p != null) {
            cmp = cpr.compare(key, p.key);
            if (cmp > 0) {
                index += getWeight(p.left) + 1;
            }
            p = p.parent;
        }
    } else {
        Comparable<? super K> k = (Comparable<? super K>) key;
        while (p != null) {
            if (k.compareTo(p.key) > 0) {
                index += getWeight(p.left) + 1;
            }
            p = p.parent;
        }
    }
    return index;
}

Puede encontrar el resultado de este trabajo en http://code.google.com/p/indexed-tree-map/

TreeSet / TreeMap (así como sus contrapartes indexadas del proyecto indexed-tree-map) no permiten claves duplicadas, puede usar 1 clave para una matriz de valores. Si necesita un SortedSet con duplicados, use TreeMap con valores como matrices. Yo haria eso.