Durch Beibehalten der TreeSet-Sortierung als Objekt ändert sich der Wert

74

Ich habe ein Objekt, das mit Comparable <> eine 'natürliche Sortierreihenfolge' definiert. Diese werden in TreeSets gespeichert.

Gibt es neben dem Entfernen und erneuten Hinzufügen des Objekts eine andere Möglichkeit, die Sortierung zu aktualisieren, wenn die Elemente, die zum Definieren der Sortierreihenfolge verwendet werden, aktualisiert werden?

Stevko
quelle
Ist das nur krankhafte Neugier oder suchen Sie nach einem bestimmten Vorteil, etwa in Bezug auf Leistung oder Code-Einfachheit?
Greim
2
Ich suchte nach einer einfachen nicht-invasiven Möglichkeit, die Sortierreihenfolge einer Sammlung beizubehalten, wenn Ereignisse die darin enthaltenen Objekte aktualisieren. Eine Änderung der Mitgliedschaft hat Nebenwirkungen auf andere Verbraucher der Sammlung. IMO, das Auslösen eines Resorts eines Elements scheint eine grundlegende Funktionalität für eine sortierte Sammlung zu sein.
Stevko
GUIs haben das gleiche Problem, und MVC ist die Lösung. Die GUI, die Ihren TreeSetAnrufen updatein regelmäßigen Abständen entspricht, oder der Controller (Beobachtermuster) wird vom Modell ausgelöst, wenn sich ein Wert ändert
Mike
Die von der Architektur ziemlich genau gefingert. Das TreeSet ist mein Modell von DOTs, die ein Websocket-JMS-Ereignis abhören, das dann die Modellaktualisierungen über die Präsentator- / Controller-Ebene weiterleitet, um Widgets anzuzeigen.
Stevko

Antworten:

16

Wie andere angemerkt haben, gibt es keinen eingebauten Weg. Sie können dieses TreeSet jedoch jederzeit mit den von Ihnen ausgewählten Konstruktoren unterklassifizieren und die erforderlichen Funktionen hinzufügen:

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;
       }
    }
}

Von da an müssen Sie aufrufen ((UpdateableTreeSet)mySet).update(anElement, aValue), um den Sortierwert und die Sortierung selbst zu aktualisieren. Dazu müssen Sie eine zusätzliche update()Methode in Ihrem Datenobjekt implementieren .

Tucuxi
quelle
5

Ich hatte ein ähnliches Problem, fand diesen Thread und die Antwort von Tucuxi (danke!), Auf deren Grundlage ich meine eigene implementiert habe UpdateableTreeSet. Meine Version bietet Mittel dazu

  • über eine solche Menge iterieren,
  • Planen Sie (verzögerte) Elementaktualisierungen / -entfernungen innerhalb der Schleife
  • ohne eine temporäre Kopie des Sets erstellen zu müssen und schließlich
  • Führen Sie alle Aktualisierungen / Entfernungen als Massenvorgang durch, nachdem die Schleife beendet wurde.

UpdateableTreeSetverbirgt einen Großteil der Komplexität vor dem Benutzer. Zusätzlich zu den verzögerten Massenaktualisierungen / -entfernungen bleibt die von tucuxi gezeigte Einzelelementaktualisierung / -entfernung in der Klasse weiterhin verfügbar.

Update 07.08.2012: Die Klasse ist in einem kleinen GitHub-Repository verfügbar, einschließlich einer einführenden README mit schematischem Beispielcode sowie Unit-Tests, die zeigen, wie (nicht) sie detaillierter verwendet werden kann.

Kriegaex
quelle
Ich mag die Idee - es würde nur bedeuten, das Array "Deferred-Update" in das UpdateableTreeSet zu platzieren und dann "Do-Deferred-Updates" aufzurufen, um zuerst alle Updates zu entfernen und sie dann erneut einzufügen.
Tucuxi
Wie mein Codebeispiel impliziert, habe ich dies getan. Es ist nicht nur eine Idee, es ist eine echte Umsetzung. Haben Sie dem Link zum Quellcode gefolgt und auch andere Dateien im Projekt ausgecheckt, um zu sehen, wie die Klasse in komplizierteren Fällen verwendet wird?
Kriegaex
Keine Notwendigkeit - die Idee ist klar genug, und obwohl Ihre Erklärung etwas zu lang ist, habe ich sie als nützlich eingestuft.
Tucuxi
Ich habe auf Ihren Kommentar reagiert, dass das Posting zu lang war, und es dramatisch verkürzt. Ich habe auch das Beispielcode-Snippet entfernt. Stattdessen gibt es jetzt einen Zeiger auf ein dediziertes Git-Repository mit dem vollständigen Code als weitere Referenz. Danke für die Rückmeldung.
Kriegaex
3

Wenn Sie wirklich ein verwenden müssen Set, dann haben Sie Pech, denke ich.

Ich werde jedoch einen Platzhalter einwerfen. Wenn Ihre Situation flexibel genug ist, um mit einem Liststatt mit einem zu arbeiten Set, können Sie Collections.sort()das Listbei Bedarf neu sortieren . Dies sollte performant sein, wenn die ListReihenfolge nicht stark geändert werden muss.

Skaffman
quelle
1
Dies ist kein großer Vorteil - Set garantiert ein schnelles Nachschlagen, Einfügen und Entfernen, während für eine Liste zuerst Collections.binarySearch verwendet werden muss, um das Element zu finden. Es ist besser, sich an das Entfernen und Wiedereinsetzen zu halten.
Tucuxi
Mir ist das klar, weshalb ich sagte "wenn Ihre Situation flexibel genug ist". Die Leistungsanforderungen können locker genug sein, um eine Listpraktische Anwendung zu ermöglichen .
Skaffman
1
@tucuxi binäre Suche in einer Liste ist O (log n). In einem TreeSet nachschlagen? Auch O (log n).
Kevin Bourrillion
@ Kevin, aber Sie müssen die Bewegungen der Implementierung von Versionen von add (), remove () und includes () durchlaufen, die intern binäre Suchen durchführen. Im Wesentlichen implementieren Sie TreeSet mit einer sortierten Liste erneut. Deshalb habe ich geschrieben, dass das Entfernen und Wiedereinsetzen einfacher zu sein scheint. Nicht wegen der Leistung, sondern wegen der Codierungszeit.
Tucuxi
1
Mir hat diese Idee gefallen, wenn die Sammlung an Ort und Stelle sortiert werden kann, anstatt eine neue Instanz zu erstellen.
Stevko
1

Nur eingebaut ist das Entfernen und erneute Hinzufügen.

Robby Pond
quelle
1

Es ist hilfreich zu wissen, ob sich Ihre Objekte in kleinen oder großen Schritten ändern. Wenn jede Änderung sehr klein ist, tun Sie sehr gut daran, Ihre Daten in eine Liste aufzunehmen, die Sie sortiert halten. Dazu muss man

  1. binarySearch, um den Index des Elements zu finden
  2. Ändern Sie das Element
  3. Während das Element größer als sein rechter Nachbar ist, tauschen Sie es mit seinem rechten Nachbarn aus
  4. oder wenn dies nicht geschehen ist: Während das Element kleiner als sein linker Nachbar ist, tauschen Sie es mit seinem linken Nachbarn aus.

Aber Sie müssen sicherstellen, dass niemand das Element ändern kann, ohne "Sie" zu durchlaufen, um dies zu tun.

EDIT: Auch! Glazed Lists unterstützt genau dies:

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

Kevin Bourrillion
quelle
1

Ich habe dieses Problem nachgeschlagen, als ich versuchte, einen kinetischen Bildlaufbereich zu implementieren, der den Apple iPhone-Radschriftrollen ähnelt. Die Elemente in der TreeSetsind diese Klasse:

/**
 * 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());
    }
}

Es DoubleExpressionkann einen Moment dauern, bis eine runLater-Task der JavaFX-Plattform gebunden ist. Aus diesem Grund ist der Index in dieser Wrapper-Klasse enthalten.

Da sich die scrollOffsetPosition basierend auf der Scrollposition des Benutzers am Scrollrad ständig ändert, benötigen wir eine Möglichkeit zum Aktualisieren. Normalerweise ist die Reihenfolge immer dieselbe, da der Versatz relativ zur Position des Artikelindex ist. Der Index ändert sich nie, aber der Versatz kann negativ oder positiv sein, abhängig von der relativen Entfernung der Elemente von der aktuellen vValue- oder hValue-Eigenschaft der ScrollPane.

Befolgen Sie einfach die Anweisungen der obigen Antwort von Tucuxi, um bei Bedarf nur bei Bedarf zu aktualisieren .

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

Dabei ist vertikaleOffsets a TreeSet<ItemOffset>. Wenn Sie bei jedem Aufruf dieses Update-Snippets einen Ausdruck des Sets erstellen, werden Sie feststellen, dass es aktualisiert wird.

ghostNet
quelle
-1

Ich glaube nicht, dass es einen Out-of-the-Box-Weg gibt, dies zu tun.

Sie können ein Beobachtermuster verwenden, das das Baumset benachrichtigt, wenn Sie einen Wert innerhalb eines Elements ändern. Anschließend wird es entfernt und erneut eingefügt.

Auf diese Weise können Sie die Liste implizit sortieren, ohne sich darum kümmern zu müssen. Natürlich muss dieser Ansatz erweitert werden, TreeSetindem das Einfügeverhalten geändert wird (Festlegen der beobachteten / Benachrichtigungsmechanik für das gerade hinzugefügte Element).

Jack
quelle
5
Ich denke nicht, dass das funktionieren wird. Wenn sich der Wert des Elements in einer Weise ändert, die sich auf die Sortierreihenfolge auswirkt, ist es sehr wahrscheinlich, dass Sie ihn nicht im Baum finden oder entfernen können.
Michael Borgwardt