TreeSet - Comparator ändern -> resort?

[Shiwayari]

Hallo zusammen,

habe hier ein TreeSet mit Objekten die nach unterschiedlichen Attributen sortiert werden können. Nach welchem Attribut die Objekte sortiert werden soll zur Laufzeit verändern werden können.

Ich benutze dazu momentan einen Comparator, dessen compare(..) Methode die übergebenen Objekte unterschiedlich vergleicht.
Ein Ausschnitt vom Code:

class EntryComparator implements Comparator<Entry> {

	public enum SortType {NAME, COUNT, DATE};
	public enum Order {ASCENDING, DESCENDING};
	private SortType sortType;
	private Order order;
	
	public EntryComparator() {
		sortType = SortType.NAME;
		order = Order.ASCENDING;
	}

	public void setSortType(SortType s) {
		sortType = s;
	}

	public void setOrder(Order o) {
		order = o;
	}

	public int compare(Entry o1, Entry o2) {
		int ret = 0;
		switch (sortType) {
		case NAME:
			ret = o1.getName()compareToIgnoreCase(o2.getName());
		case COUNT:
			Integer c1 = new Integer(o1.getCount());
			Integer c2 = new Integer(o2.getCount());
			ret = c1.compareTo(c2);
			break;
		case DATE:
			ret = o1.getDate().compareTo(o2.getDate());
			break;
		default:
			break;
		}
		if (order == Order.DESCENDING) {
			ret *= -1;
		}
		return ret;
	}
}

Mein Problem ist nun, dass ein TreeSet seine Objekte nicht neusortiert, wenn irgendein Attribut im Comparator geändert wird. Und eine Methode TreeSet.resort() gibt es auch nicht.

Wie implementiere ich es nun am besten/schönsten, dass beim Ändern des "Sortierkriteriums" das TreeSet neu sortiert wird?

Ich könnte nach dem Ändern ein Element hinzufügen und wieder löschen, aber das ist nicht besonders sauber.


Das Konzept des Umsortierens ist ja nichts ungewöhnliches, da müsste es doch eine Art "Standartlösung" geben?

 

[Andi_CH]

Ist es nicht so, dass das TreeSet die Objekte beim Einfügen von Anfang an an die richtige Stelle platziert?
Es muss gar nie sortieren, weil es immer sortiert ist.

Also bliebe nichts anderes übrig als ein neues TreeSet zu generieren und die Elemente alle zu kopieren.

 

[Shiwayari]

Genau das tut es. Aber wäre es nicht zu ineffizient jedesmal ein neues Set zu erstellen, oder ist das Kopieren von Referenzen quasi "kostenfrei"? Vergleicht werden muss ja sowieso.

Muss noch dazu sagen, dass ich auch nicht unbedingt ein TreeSet nutzen muss.

Ich brauche nur eine Struktur, die eben wie das TreeSet sicherstellt, dass jedes Element nach einem festen Attribut nur einmal vorhanden ist, und die gleichzeitig immer geordnet ist. Wobei die Ordnung eben varrieren kann.

Ich könnte ja z.B. von TreeSet ableiten und irgendwie per Event dafür sorgen, dass es neu sortiert, wobei ich nicht weiß, wie das intern gehandhabt wird.

Es ist mir nur wichtig, dass es ganz unabhängig funktioniert. Das Drumherum wird etwas umfangreicher und da will ich mir keine Gedanken mehr drüber machen müssen wann ich was neusortieren muss.

 

[Andi_CH]

Setzten von Werten geht ja sicher über einen setter - der könnte auch den resort anstossen.
Wobei schon darüber nachzudenken ist, wie gross der Sortieraufwand verglichen mit dem Neuaufbau ist.

Sortieren gleich vertauschen - 3 mal lesen / schreiben
Umkopieren = allozieren des TreeSets und 1 mal lesen / schreiben wobei auch immer zwei TreeSets gehalten werden können

Hm - wo bleiben die Profis?

 

[SlaterB]

Sortieren kann man nicht pauschal Bewerten, ein TreeSet ist nunmal ein Tree, keine Liste (selbst da komisch),

wenn man das Kriterium ändert ist der ganze Tree einfach Müll, man einen unverarbeiteten Haufen an Elementen,
aus denen muss man einen neuen Baum bauen, ob im alten TreeSet-Objekt oder in einem neuen dürfte nicht so entscheidend sein, oder?
ein einzelnes neues Objekt anzulegen dauert doch keine messbare Zeit, falls das nicht gerade mit 50 fps ständig passiert,

da [c]new TreeSet(altes, neuer bzw. geänderter Comparator);[/c] oder ähnlich funktioniert, ist wohl der Bedarf an einer resort()-Methode weniger hoch,
gibt es meines Wissens nach nicht

 

[maki]

Ist es nicht so, dass das TreeSet die Objekte beim Einfügen von Anfang an an die richtige Stelle platziert?
Es muss gar nie sortieren, weil es immer sortiert ist.

Ja, richtig.

"resort" gibt es nicht beim TreeSet, weil der Aufwand darin besteht ein neues TreeSet erzeugen.

Ansonsten: Elemente eines Sets sollten allgemein gesagt immutable sein (ausser die zu ändernden Attribute ändern nix an der Reihenfolge, equals & hashcode), aus der Set Api Doku:

Note: Great care must be exercised if mutable objects are used as set elements. The behavior of a set is not specified if the value of an object is changed in a manner that affects equals comparisons while the object is an element in the set. A special case of this prohibition is that it is not permissible for a set to contain itself as an element.

Wenn man bestimmte Anforderungen an Sets nicht erfüllen kann, nimmt man zB. List und prüft vor dem einfügen mit contains.

 

[Shiwayari]

Habe nochmal die genaue "Soll-Bedingung" für Sets rausgesucht:

Note that the ordering maintained by a set (whether or not an explicit comparator is provided) must be consistent with equals if it is to correctly implement the Set interface.
__
The ordering imposed by a comparator c on a set of elements S is said to be consistent with equals if and only if c.compare(e1, e2)==0 has the same boolean value as e1.equals(e2) for every e1 and e2 in S.

Wenn ich das nochmal so lese.. ist das Set eigentlich total ungeeignet dafür nach veränderlichen Attributen zu sortieren.

equals soll sich ja in meinem Fall immer auf den Namen (der unverändert bleibt) beziehen, wobei compare wahlweise andere Attribute behandelt.

Also nehme ich mir nun am besten eine ArrayList (oder Vector, falls ich noch threading brauche) und prüfe beim Hinzufügen mit contains().
Da die Attribute der Elemente veränderlich sind, muss ich dann nicht nur nach jedem Hinzufügen oder Ändern des Comparators neu sortieren, sondern immer, wenn sich ein Attribut eines Objektes verändert.
Zum Sortieren dient dann Collections.sort(list, comparator), wobei comparator dann zur Laufzeit verändert werden kann.

Wenn ich aber zur Klasser meiner Elemente hinzufüge, dass sie beim Ändern ihrer Attribute ein PropertyChangedEvent oder ähnliches an die Liste weitergeben.. dann habe ich gleich doppelt so viele Referenzen.
Denn dann enthält die Liste die Referenzen auf alle Objekte, und jedes Objekt eine Referenz auf die Liste als PropertyChangeListener. Zudem muss in die Klasse der Elemente der Aufruf des Listeners rein, der darin eigentlich nichts zu suchen hat, da er mit dem Objekt selbst keinen logischen Zusammenhang hat..

Die beste Lösung wäre also doch in der Klasse, die das User Interface implementiert sicherzustellen, dass nach jeder Attribut-verändernden Eingabe die Liste der Objekte neu sortiert wird?

Letztendlich hänge ich nun doch wieder bei einer simplen Liste und muss sie selbst verwalten =/

 

[maki]

Sieh es mal so:
Man hätte vielleicht eine Datenstruktur in Java zur Collection API hinzufügen können die "ResortOnEvereyAddList" oder gar "ResortOnAnyProprtyChangeEvent" heisst... sowas hab ich noch nicht gebraucht, aber das heisst ja nix.

Immutables sind nicht immer möglich/praktikabel(manchmal aber auch nur unbekannt), aber müssen denn deswegen wirklich auch gleich die Attribute geändert werden welche die Wertigkeit(Comparable/Comparator) und Identität(equals/hashcode) beeinflussen?

Die Anzahl der Referenzen in Bezug auf Performanceüberlegungen sollest du nicht viel Gewicht schenken, messen ist da die einzige zuverlässsige Methode, zB. mit VisualVM.
Wenn man aber die theor. Anzahl der Elemente und die Frequenz der Änderungen wüsste, könnte man vielleicht mehr sagen.

Einschränkungen betreffen übrigens nicht nur Set, HashMap hat sowas auch

 

[Shiwayari]

Also jetzt bin ich nach dem ganzen nachdenken vollkommen verwirrt :bahnhof:

Was ich am Ende brauche ist eine Art Liste mit Objekten, die mit irgendeiner Darstellung untereinander in einem Panel dargestellt werden. Per Klick auf ein Objekt lassen sich einzelne Attribute der Objekte ändern. Und per Auswahl in der MenuBar lässt sich auswählen nach welchem Attribut sortiert werden soll.

Der Name der Objekte soll einzigartig sein, die restlichen Attribute beliebig. Der Name darf sich aber trotzdem ändern, solange er dabei einzigartig bleibt.

Der Designschritt war nun festzulegen zu welchen Zeitpunkten Ordnung und Einzigartigkeit festgelegt ist. Da dachte ich mir eben, wenn es einfach immer erfüllt ist, schon zur Erstellzeit des Objektes und auch nach jedem Ändern der Attribute, dann braucht man bei der weiteren Implementierung darüber nicht mehr nachzudenken und ich könnte das UI ganz unabhängig programmieren.
Beim Anzeigen bräuchte man dann nur die Liste von vorne bis hinten durchlaufen und ausgeben.

Wenn ich im User Interface z.B. von aufsteigend auf absteigend sortieren umschalte, wäre es optimal einfach eine einzige Variable umzuschalten, die die Sortierreihenfolge angibt, und dann "anzeigen" aufzurufen.



Im Grund genommen sowas ähnliches wie eine Tabelle mit Spalten Name, etc. ; die per Klick auf die jeweilige Spalte auf- oder absteigend in genau dieser Spalte sortiert wird. Wobei die Felder der Tablette dann veränderbare TextFields oder ComboBoxes wären.


Die "Frequenz der Änderungen" beruht somit nur auf Benutzereingaben und ist sehr gering. Die Anzahl der Elemente liegt so im Bereich von 1000.


Edit:

Ich löse das nun damit, dass ich über dem UI noch einen Manager einfüge, der die Collections an Daten handhabt. Ich nehme mir Maps, die die Entry's auf eine unveränderbare ID mappen und füge Auslesemethoden hinzu, die je nach Argument ein TreeSet mit unterschiedlichen Comparators zurückgeben.