Beim Vergleich/Sortieren mehr als zwei Objekte berücksichtigen

[Hobbes]

Hallo zusammen,

habe eine Liste mit Objekten, die ich sortieren möchte. Grundsätzlich kein großes Problem, da Java ja gute Schnittstellen bietet. Aber bei mir gibt es einzelne Fälle, in denen das Ergebnis des Vergleichs zweier Objekte (compareTo) noch von weiteren Objekten abhängt.

Hier mal ein vereinfachtes Codebeispiel

Klasse mit meinen Objekten

public class MyRecord implements Comparable<MyRecord> {
	int iValue;
	boolean bBoolean;

	public MyRecord(int iVal, boolean bBool) {
		iValue = iVal;
		bBoolean = bBool;
	}

	@Override
	public int compareTo(MyRecord other) {
		int iReturn = 0;
		if (iValue > other.iValue) {
			iReturn = 1;
		} else if (iValue < other.iValue) {
			iReturn = -1;
		} else if (bBoolean == other.bBoolean) {
			iReturn = 0;
		} else {
			// iNumber==other.iNumber
			// bBoolean!=other.bBoolean
			// => hier hängt es von mehr als diesen beiden Objekten ab
			// deshalb erst mal -1 zurückgeben
			iReturn = -1;
		}
		return iReturn;
	}

	@Override
	public String toString() {
		return "Wert: " + iValue + ", boolean: " + bBoolean;
	}
}

Klasse mit Main-Methode

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class KSKB {
	// Konstruktor
	public static void main(String[] args) {
		List<MyRecord> al = new ArrayList<MyRecord>();
		System.out.println("Beispiel 1");
		al.add(new MyRecord(5, true));
		al.add(new MyRecord(4, false));
		al.add(new MyRecord(4, true));
		al.add(new MyRecord(3, false));
		Collections.sort(al);

		System.out.println("Nach dem Sortieren....");
		for (MyRecord rec : al) {
			System.out.println(rec.toString());
		}

		System.out.println();
		System.out.println("Die gewünschte Ausgabe wäre aber");
		al.clear();
		al.add(new MyRecord(3, false));
		al.add(new MyRecord(4, true));
		al.add(new MyRecord(4, false));
		al.add(new MyRecord(5, true));
		for (MyRecord rec : al) {
			System.out.println(rec.toString());
		}

		System.out.println();
		System.out.println("Beispiel 2");
		al.clear();
		al.add(new MyRecord(5, false));
		al.add(new MyRecord(4, true));
		al.add(new MyRecord(4, false));
		al.add(new MyRecord(3, true));
		Collections.sort(al);

		System.out.println("Nach dem Sortieren....");
		for (MyRecord rec : al) {
			System.out.println(rec.toString());
		}

		System.out.println();
		System.out.println("Die gewünschte Ausgabe wäre aber");
		al.clear();
		al.add(new MyRecord(3, true));
		al.add(new MyRecord(4, false));
		al.add(new MyRecord(4, true));
		al.add(new MyRecord(5, false));
		for (MyRecord rec : al) {
			System.out.println(rec.toString());
		}
	}
}

Standardmäßig sollen die Objekte nach den int-Werten sortiert werden. In den meisten Fällen sind diese auch unterschiedlich.

Unterscheiden sich die zwei Objekte aber nur in der booleschen Variable, so soll die Reihenfolge so sein, dass sich in der sortierten Liste true und false wenn möglich abwechseln. In diesem Fall hängt es also davon ab, welchen Werte die Objekte vor bzw. nach den "gleichen" haben.

In meinem Beispiel sind es die zwei Objekte (4, true) und (4, false), die jeweils unterschiedlich sortiert werden.

Spontan fallen mir zwei Möglichkeiten ein, wie man das implementieren könnte:

1. erst Collection.sort() aufrufen, dann die dadurch vorsortierte Liste auf "gleiche" prüfen und ggf. von Hand zwei Einträge tauschen
2. auf das Standardsortieren verzichten und eine eigene Sortiermethode implementieren. Dann müsste ich dafür sorgen, dass compareTo auf diese Objekte nicht aufgerufen wird.

Beides gefällt mir nicht so richtig. Gibt es noch eine andere Möglichkeit?

 

[RySa]

Unterscheiden sich die zwei Objekte aber nur in der booleschen Variable, so soll die Reihenfolge so sein, dass sich in der sortierten Liste true und false wenn möglich abwechseln.

Sollen Sie z.b wenn Du fünf objekte mit dem Wert 4 hast, aber 3 zusätzlich true haben und 2 false, soll das dann so aussehen? :
4,true
4,false
4,true
4,false
4,true

oder soll true oder false vorgezogen werden ? also z.b true Werte vor den false

 

[truesoul]

Ja.

Dafür wäre wohl PriorityQueue geeignet. Ein Beispiel wäre hier zu finden: http://www.java-forum.org/java-basics-anfaenger-themen/121259-priorityqueue-einfuegereihenfolge.html. Wenn die Sortierung evtl. schon beim Einfügen geschehen sollte .

 

[Hobbes]

@RySa

Genau so soll es aussehen. Und ob es mit true oder false anfängt, soll von dem vorherigen Eintrag abhängen.

Wobei dein Nachfrage-Beispiel für mich nur theoretischer Natur ist. Bei mir ist ausgeschlossen, dass in meiner Liste zwei Objekte sind, die sowohl den gleichen Integerwert als auch den gleichen booleschen Wert haben. Aber für die Lösung des Problems ist das vermutlich nicht relevant.

@truesoul
Danke, das muss ich mir mal in Ruhe anschauen.

 

[bERt0r]

Wobei dein Nachfrage-Beispiel für mich nur theoretischer Natur ist. Bei mir ist ausgeschlossen, dass in meiner Liste zwei Objekte sind, die sowohl den gleichen Integerwert als auch den gleichen booleschen Wert haben. Aber für die Lösung des Problems ist das vermutlich nicht relevant.

Wenn es Maximal 2 gleiche int Werte gibt, und alles was du verhindern willst so eine Ausgabe ist:
1, True
1, False
2, False
2, True
Kannst du doch einfach die compare Funktion erweitern, indem du, falls der int wert gleich ist, auch noch die boolean Werte vergleichst.

 

[Hobbes]

@bERt0r

Ich glaube nicht, dass das funktioniert. Was soll ich denn dann zurückgeben? Ob true>false oder true<false ist kann ich nur entscheiden, wenn ich noch ein drittes Referenzobjekt zur Verfügung habe. Schaue dir mal folgende zwei Beispiele an:

Möglicher Fall
1 true
2 false
2 true

Wenn ich das erste Element entferne, ein neues hinzufüge und erneut sortiere soll folgendes rauskommen:

1 false
2 true
2 false

Die letzten beiden Objekte sind also im Vergleich zu vorher in einer anderen Reihenfolge

Und wegen der PriorityQueue:

Ich verstehe das Prinzip der PriorityQueue noch nicht. Auch da brauche ich doch einen Comparator ???:L Wo genau liegt der Unterschied bzw. Vorteil für mich?

Und vor allem irritiert mich, was ich hier gelesen habe

Note: The PriorityQueue adds and removes based on Comparable; however, if you iterate of the PriorityQueue you may not get the results that you expect. The iterator does not necessarilly go through the elements in the order of their Priority. In other words, if you want to see how the elements are added and removed, do not rely on an iterator. Use the remove() method of the priorityQueue class as is shown in the example code below.

Ich muss später mehrmals über die Liste iterieren. Da kann ich remove nicht gebrauchen Oder habe ich da was vollkommen falsch verstanden? *grübel*

 

[maki]

Unterscheiden sich die zwei Objekte aber nur in der booleschen Variable, so soll die Reihenfolge so sein, dass sich in der sortierten Liste true und false wenn möglich abwechseln. In diesem Fall hängt es also davon ab, welchen Werte die Objekte vor bzw. nach den "gleichen" haben.

Hm.. denke dass du mit Comparable dann nicht wirklich glücklich wirst, denn compareTo sollte konsistent mit equals sein.

Wenn es nur um die Darstellung geht, würde ich dafür einen expliziten Comparator empfehlen und Comparable "normal" implementieren.

 

[bERt0r]

Ich habe zwar keine Ahnung für was du sowas benötigst, meiner Ansicht nach hat das aber mit Sortieren nichts mehr am Hut, du willst nur die Ausgabe in einer bestimmten Form haben.
Zur Priority queue kann ich jetzt nichts sagen, allerdings ist dir schon klar, dass du dadurch quasi bei jedem Einfügen die ganze Liste umsortierst?

Zum Verständnis:
1, True
2, True
3, False
3, True
4, False
5, True
5, False
6, False
7, True

So soll das aussehen? Ich würde in einer Scheife bei der Ausgabe einfach immer 3 Werte Merken und die dann Vergleichen und je nachdem ausgeben. Dann hast du zwar ein paar Ausnahmen zu regeln, sollte aber überschaubar sein.

 

[Hobbes]

allerdings ist dir schon klar, dass du dadurch quasi bei jedem Einfügen die ganze Liste umsortierst?

Ja, das ist mir klar und es ist auch so gewollt und notwendig. Wobei nur sehr selten Werte hinzugefügt werden. Es ist eher so, dass die Liste am Anfang gefüllt und sortiert wird. Danach bleibt sie in den meisten Fällen unverändert.

Zum Verständnis:
1, True
2, True
3, False
3, True
4, False
5, True
5, False
6, False
7, True

So soll das aussehen?

Ja, so soll es sein.

Ich würde in einer Scheife bei der Ausgabe einfach immer 3 Werte Merken und die dann Vergleichen und je nachdem ausgeben. Dann hast du zwar ein paar Ausnahmen zu regeln, sollte aber überschaubar sein.

Bringt mich auf eine Idee. Könnte das einmal beim Laden machen und die somit sortierte Liste in einer Datenstruktur ablegen, die als Sortierkriterium ausschließlich die Einfügereihenfolge hat. Dann sollte es eigentlich passen?!?

Sollten dann neue Elemente hinzukommen, mache ich das gleiche Prozedere erneut.

 

[RySa]

Ich habe da etwas gebastelt. Versuche vielleicht in deine Klasse MyRecord diese Methode hinzuzufügen:

    public static void sort(List<MyRecord> records){
    	for (int i = 1 ; i < records.size()-1 ; i++){
    		if((records.get(i-1).bBoolean == records.get(i).bBoolean) && (records.get(i+1).iValue == records.get(i).iValue)){
    			MyRecord temp = records.get(i);
    			records.set(i, records.get(i+1));
    			records.set(i+1, temp);
    		}
    	}
    }

Und benutze Sie nach dem Collection.sort(al). Also so etwa:

//......
        List<MyRecord> al = new ArrayList<MyRecord>();
        System.out.println("Beispiel 1");
        al.add(new MyRecord(5, true));
        al.add(new MyRecord(4, false));
        al.add(new MyRecord(4, true));
        al.add(new MyRecord(3, false));
        Collections.sort(al);
        MyRecord.sort(al);
//....

Bei mir hat das funktioniert. Hoffe es hilft dir zumindest weiter

 

[turtle]

Also, ich würde alle Objekte in einer Klasse zusammenfassen und darauf sortieren...

Dann hast Du alle Objekte zusammen und kannst sortieren, wie Du möchtest.

class ToBeSorted implements Comparable<ToBeSorted>{
private Objekt1 obj1;
private Objekt2 obj2;
private Objekt3 obj3;
@Override
public int compareTo(ToBeSorted o);
}

 

[bErt0r]

Rysa, hast du deinen code auch mit diesen Daten versucht?
1, True
2, True
3, False
3, True
4, False
5, True
5, False
6, False
7, False

Ich hab deinen Code nicht ganz durchblickt, wenn er funktioniert sind meine Bedenken ja unwichtig.
Ich hätte das so aufgezogen: die Liste Sortieren, und dann bei der Ausgabe einfach darauf achten, dass die True-False abwechselnd kommen

Vector<Record> v=new Vector<Record>();
Record prev,act,next;
prev=null
Iterator i=records.iterator()
act=i.next();
while(i.hasNext())
{
	next=i.next();
	if(act.intVal<next.intVal)			//act < next
	{
		v.add(act);
		prev=act;
	} else if(act.intVal>next.intVal)		//next < act
	{
		v.add(next);
		prev=next;
	} else if(act.intVal==next.intVal)
	{
		if(prev==null)				//Beim Ersten Durchlauf ist prev null
		{
			v.add(act);
			prev=act;
		} else
		{
			if(prev.boolVal!=act.boolVal)	//intVals gleich, bool des letzten != aktuellem
			{
				v.add(act);
				prev=act;
			}else
			{
				v.add(next);
				prev=next;
			}
		}
	}
	act=next;
}
System.out.println(v);

 

[RySa]

Ja ich habe es eben versucht, und das funktioniert auch. Es ist "nicht klug" es bei der Ausgabe zu sortieren. Wenn, dann soll man es schon vorher intern sortieren, sonnst kann es nachher zur inkonsistenz der Daten kommen (unter Umständen). Ich schreibe einfach alles was ich dazu habe:

Die MyRecord Klasse

import java.util.List;

public class MyRecord implements Comparable<MyRecord> {
    int iValue;
    boolean bBoolean;
 
    public MyRecord(int iVal, boolean bBool) {
        iValue = iVal;
        bBoolean = bBool;
    }
    
    public static void sort(List<MyRecord> records){
    	for (int i = 1 ; i < records.size()-1 ; i++){
    		if((records.get(i-1).bBoolean == records.get(i).bBoolean) && (records.get(i+1).iValue == records.get(i).iValue)){
//In dieser If Abfrage wird geguckt, ob das Record, das vor diesem steht (also i-1) 
//den gleichen boolean-Wert hat. Und gleichzeitig ob das nächste Record den gleichen 
//Value (also die gleiche Zahl) hat wie dieser. Falls das zutrifft dann soll das Record 
//mit dem nächsten Record einfach vertauscht werden. (dazu speichere ich das jetzige
// temporär um es nachher an die nächste Stelle zu platzieren
    			MyRecord temp = records.get(i);
    			records.set(i, records.get(i+1));
    			records.set(i+1, temp);
    		}
    	}
    }
 
    @Override
    public int compareTo(MyRecord other) {
        int iReturn = 0;
        if (iValue > other.iValue) {
            iReturn = 1;
        } else if (iValue < other.iValue) {
            iReturn = -1;
        } else if (bBoolean == other.bBoolean) {
            iReturn = 0;
        } else {
            // iNumber==other.iNumber
            // bBoolean!=other.bBoolean
            // => hier hängt es von mehr als diesen beiden Objekten ab
            // deshalb erst mal -1 zurückgeben
            iReturn = -1;
        }
        return iReturn;
    }
 
    @Override
    public String toString() {
        return "Wert: " + iValue + ", boolean: " + bBoolean;
    }
}

Und die Main-Klasse zum testen:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
 
public class KSKB {

    public static void main(String[] args) {
        List<MyRecord> al = new ArrayList<MyRecord>();
        System.out.println("Beispiel 1");
        al.add(new MyRecord(2, false));
        al.add(new MyRecord(5, true));
        al.add(new MyRecord(1, true));
        al.add(new MyRecord(5, false));
        al.add(new MyRecord(6, false));
        al.add(new MyRecord(3, false));
        al.add(new MyRecord(3, true));
        al.add(new MyRecord(7, false));
        al.add(new MyRecord(4, false));

        Collections.sort(al);
        MyRecord.sort(al);
 
        System.out.println("Nach dem Sortieren....");
        for (MyRecord rec : al) {
            System.out.println(rec.toString());
        }
    }
}

Die compareTo() Methode wird hier nicht benutzt, hab die aber mit eingefügt, da Sie vom Starter dieses Topics auch angegeben wurde.

 

[Hobbes]

@RySa

Danke für die Hilfe. Werde morgen versuchen, das auf meine Klassen zu übertragen.

Sollte das gelingen, muss ich es nur noch robust machen gegen zusätzliche (unbedachte) Verwendungen von weiteren Aufrufen Collections.sort(...) Ich weiß, dass es unschön ist, aber viel mehr Möglichkeiten sehe ich aktuell leider auch nicht.

Die compareTo() Methode wird hier nicht benutzt, hab die aber mit eingefügt, da Sie vom Starter dieses Topics auch angegeben wurde.

Doch, die compareTo-Methode wird bei Collections.sort(...) genutzt.

 

[RySa]

Doch, die compareTo-Methode wird bei Collections.sort(...) genutzt.

Oh, hatte so eine Vermutung war mir aber nicht sicher, da ich noch nie das .sort() benutzt habe Man lernt aber nie aus Also anders stelle ich mir die Lösung nicht vor, da es eher bisschen ungewöhlich ist so etwas zu machen (also das mit der Abwechslung bei den booleans in aghängigkeit von int-Werten). Da wirst du wahrscheinlich nichts vorgefertigtes dafür finden Jedenfalls viel Glück, und sag noch bescheid ob du es gelöst hast