java - funciona - mantener TreeSet ordenado como el objeto cambia el valor

treeset java ejemplo

Question

Tengo un objeto que define un ''orden de clasificación natural'' usando Comparable <>. Estos se almacenan en TreeSets.

Además de eliminar y volver a agregar el objeto, ¿existe alguna otra forma de actualizar el orden cuando se actualizan los miembros que se utilizan para definir el orden de clasificación?

Answer 1

Ayuda saber si sus objetos cambiarán en pequeños incrementos o grandes. Si cada cambio es muy pequeño, haría muy bien en poner sus datos en una lista que mantenga ordenada. Para hacer esto, tienes que

1. binarySearch para encontrar el índice del elemento
2. modificar el elemento
3. mientras que el elemento es mayor que su vecino de la derecha, cambiarlo por su vecino de la derecha
4. o si eso no sucedió: mientras que el elemento es menor que su vecino de la izquierda, cambiarlo por su vecino de la izquierda.

Pero debe asegurarse de que nadie pueda cambiar el elemento sin pasar por "usted" para hacerlo.

EDIT: ¡También! Glazed Lists tiene algo de apoyo solo para esto:

http://publicobject.com/glazedlists/glazedlists-1.5.0/api/ca/odell/glazedlists/ObservableElementList.html

Answer 2

Busqué este problema cuando estaba tratando de implementar un panel de desplazamiento cinético similar a los rollos de rueda de iPhone de Apple. Los elementos en el TreeSet son esta clase:

/**
 * Data object that contains a {@code DoubleExpression} bound to an item''s
 * relative distance away from the current {@link ScrollPane#vvalueProperty()} or
 * {@link ScrollPane#hvalueProperty()}. Also contains the item index of the
 * scrollable content.
 */
private static final class ItemOffset implements Comparable<ItemOffset> {

    /**
     * Used for floor or ceiling searches into a navigable set. Used to find the
     * nearest {@code ItemOffset} to the current vValue or hValue of the scroll
     * pane using {@link NavigableSet#ceiling(Object)} or
     * {@link NavigableSet#floor(Object)}.
     */
    private static final ItemOffset ZERO = new ItemOffset(new SimpleDoubleProperty(0), -1);

    /**
     * The current offset of this item from the scroll vValue or hValue. This
     * offset is transformed into a real pixel length of the item distance from
     * the current scroll position.
     */
    private final DoubleExpression scrollOffset;

    /** The item index in the list of scrollable content. */
    private final int index;

    ItemOffset(DoubleExpression offset, int index) {
        this.scrollOffset = offset;
        this.index = index;
    }

    /** {@inheritDoc} */
    @Override
    public int compareTo(ItemOffset other) {
        double d1 = scrollOffset.get();
        double d2 = other.scrollOffset.get();

        if (d1 < d2) {
            return -1;
        }
        if (d1 > d2) {
            return 1;
        }

        // Double expression has yet to be bound
        // If we don''t compare by index we will
        // have a lot of values ejected from the
        // navigable set since they will be equal.
        return Integer.compare(index, other.index);
    }

    /** {@inheritDoc} */
    @Override
    public String toString() {
        return index + "=" + String.format("%#.4f", scrollOffset.get());
    }
}

DoubleExpression puede tardar un momento en vincularse en una tarea runLater de la plataforma JavaFX, por eso el índice se incluye en esta clase contenedora.

Dado que scrollOffset siempre cambia en función de la posición de desplazamiento del usuario en la rueda de desplazamiento, necesitamos una forma de actualizar. Por lo general, el orden es siempre el mismo, ya que el desplazamiento es relativo a la posición del índice del artículo. El índice nunca cambia, pero el desplazamiento puede ser negativo o positivo dependiendo de la distancia relativa entre los elementos de la propiedad vValue o hValue actual del ScrollPane .

Para actualizar bajo demanda solo cuando sea necesario , simplemente siga la guía de la respuesta anterior de Tucuxi.

ItemOffset first = verticalOffsets.first();
verticalOffsets.remove(first);
verticalOffsets.add(first);

donde verticalOffsets es un TreeSet<ItemOffset> . Si imprime el conjunto cada vez que se invoca este fragmento de actualización, verá que está actualizado.

Answer 3

Como otros han notado, no hay una forma integrada. Pero siempre puede subclasificar ese TreeSet, con su (s) constructor (es) de su elección, y agregar la funcionalidad requerida:

public class UpdateableTreeSet<T extends Updateable> extends TreeSet<T> {

    // definition of updateable
    interface Updateable{ void update(Object value); }

    // constructors here
    ...

    // ''update'' method; returns false if removal fails or duplicate after update
    public boolean update(T e, Object value) {
       if (remove(e)) {
           e.update(value);
           return add(e);
       } else { 
           return false;
       }
    }
}

A partir de ese momento, tendrá que llamar a ((UpdateableTreeSet)mySet).update(anElement, aValue) para actualizar el valor de clasificación y la clasificación. Esto requiere que implemente un método update() adicional en su objeto de datos.

Answer 4

No creo que exista una forma lista para hacerlo.

Puede usar un patrón de observador que notifique el conjunto de árboles cada vez que cambie un valor dentro de un elemento, luego lo elimina y lo vuelve a insertar.

De esta forma, puede mantener implícitamente la lista ordenada sin preocuparse de hacerlo a mano ... por supuesto, este enfoque deberá extender TreeSet modificando el comportamiento de inserción (estableciendo las mecánicas observadas / notificadas en el elemento recién agregado)

Answer 5

Si realmente necesitas usar un Set , entonces no tienes suerte, creo.

Sin embargo, voy a agregar un comodín: si su situación es lo suficientemente flexible como para trabajar con una List lugar de un Set , puede usar Collections.sort() para volver a ordenar la List a pedido. Esto debería ser un rendimiento, si la orden de la List no tiene que cambiar mucho.

Answer 6

Solo construido en forma es eliminar y volver a agregar.

Answer 7

Tuve un problema similar, encontré este hilo y la respuesta de tucuxi (¡gracias!) En base a la cual implementé mi propio UpdateableTreeSet . Mi versión proporciona medios para

• iterar sobre dicho conjunto,
• cronograma (diferido) de actualizaciones / eliminaciones de elementos dentro del ciclo
• sin tener que crear una copia temporal del conjunto y finalmente
• hacer todas las actualizaciones / eliminaciones como una operación masiva después de que el ciclo haya terminado.

UpdateableTreeSet oculta gran parte de la complejidad del usuario. Además de las actualizaciones / eliminaciones masivas diferidas, la actualización / eliminación de un solo elemento como se muestra en tucuxi aún permanece disponible en la clase.

Actualización 2012-08-07: la clase está disponible en un pequeño repositorio de GitHub, que incluye un README introductorio con código de ejemplo esquemático, así como pruebas unitarias que muestran cómo (no) utilizarlo con más detalle.