Problem beim Löschen des ersten Eintrags einer TreeSet

[markus1986]

hallo comm,

da ich noch anfänger bin und jetzt an ein problem gestoßen bin, was ich bisher mit keinen mitteln lösen konnte, wende ich mich an euch.

es geht um folgendes:

ich habe eine klasse Pixel:

public class Pixel implements Comparable<Pixel> {
	private int xx, yy, regionsnummer, differenzi, farbe;
		
	public Pixel(int xKoo, int yKoo, int rnr, int diff, int colour){
		xx = xKoo;
		yy = yKoo;
		regionsnummer = rnr;
		differenzi = diff;
		farbe = colour;
	}
	
	public int getX(){
		return xx;
	}
	
	public int getY(){
		return yy;
	}
	
	public int getDifferenz(){
		return differenzi;
	}
	
	public int getFarbe(){
		return farbe;
	}
	
	public int getRegion(){
		return regionsnummer;
	}
	public static void main(String[] args){
		new Pixel(0, 0, 0, 0, 0);
	}

   public int compareTo(Pixel o) 
   { 
      int diffe = o.getDifferenz()-this.getDifferenz();
      if (diffe != 0) { 
    	  if(diffe > 0) return -1; else return 1;
      } 
      else if(diffe == 0){
    	  if (this.equals(o)) return 0; else return 1;
      }
      else {
    	  return 1;
      }
   } 
}

in der comparable implementiert ist. ich weiß nicht, ob ich die methode compareTo so richtig geschrieben habe, aber sie scheint zu funktionieren.

ich lade ein foto in mein programm und klicke dann beliebige pixel in diesem bild an.
nach jedem klick werden alle nachbarpixel (für jeden wird ein objekt Pixel erstellt) mithilfe folgender methode in einer treeset gespeichert:

public void nachbarnEinsortieren(int x, int y, int a, int farbe_elter) {
    	
    	int i, j;
    	for(i = -1; i <= 1; i++){
   	 		for(j = -1; j <= 1; j++){
   	 			if((i != 0 || j != 0) && SegImage[x+i][y+j] == -2)
   	 			{
   	 				Color pixel = bild.gibPunktfarbe(x+i, y+j);
   	 				int grau = pixel.getBlue();
   	 				int differenz = Math.abs(farbe_elter-grau);
   	 				sortierteListe.add(new Pixel(x+i, y+j, a, differenz, grau));
   	 			}
   	 		}
   	 	}
	}

die treeset wird deklariert: private TreeSet<Pixel> sortierteListe; und initialisiert: sortierteListe = new TreeSet<Pixel>();

nach einem klick auf einen button wird folgende methode aufgerufen:

	public void ListeAusgeben(){
		for(Iterator iter = sortierteListe.iterator(); iter.hasNext(); ){
			Pixel wert = (Pixel) iter.next();
			System.out.println(wert);
		}
		int i;
		for(i = 0; i < sortierteListe.size(); i++){
			Pixel wert = (Pixel) sortierteListe.first();
			System.out.println("----");
			System.out.println(wert);
			sortierteListe.remove(sortierteListe.first());
		}
	}

die erste for schleife wird wie erwartet abgearbeitet: ich erhalte also eine liste aller pixelobjekte in der treeset (alle mit versch. hashCodes). bei der zweiten for-schleife erwarte ich, dass er mir immer den ersten eintrag ausgibt, löscht und dann wieder den ersten eintrag nimmt, der natürlich der zweite aus dem vorherigen durchlauf war.
das Problem ist: er löscht den ersten eintrag nicht und ich habe keine ahnung warum!

ich habe schon sehr viel rumgetestet und mir auch ein neues beispiel geschrieben, wo ich eine treeset mit pixelobjekten (meiner pixelklasse) befüllt habe und dann genau wie hier ausgegeben habe, das klappt!

ich weiß echt nicht mehr, was ich noch testen soll .. hat jemand vielleicht eine idee?

grüße
markus

 

[markus1986]

scheinbar hat keiner von euch eine idee. ich habe jetzt noch weiter getestet. also wenn ich in der methode nachbarnEinsortieren die schleifen jeweils nur 1 durchlaufen lasse werden nur 2 punkte gespeichert. dann klappt das auch mit der ausgabe und dem löschen in der treeset!

was geht da ab??

 

[Guest]

The natural ordering for a class C is said to be consistent with equals if and only if e1.compareTo(e2) == 0 has the same boolean value as e1.equals(e2) for every e1 and e2 of class C. Note that null is not an instance of any class, and e.compareTo(null) should throw a NullPointerException even though e.equals(null) returns false.

It is strongly recommended (though not required) that natural orderings be consistent with equals. This is so because sorted sets (and sorted maps) without explicit comparators behave "strangely" when they are used with elements (or keys) whose natural ordering is inconsistent with equals. In particular, such a sorted set (or sorted map) violates the general contract for set (or map), which is defined in terms of the equals method.

For example, if one adds two keys a and b such that (!a.equals(b) && a.compareTo(b) == 0) to a sorted set that does not use an explicit comparator, the second add operation returns false (and the size of the sorted set does not increase) because a and b are equivalent from the sorted set's perspective.

 

[Guest]

Ich habe ein paar Anmerkungen zu Deiner Pixelklasse:

public class Pixel implements Comparable<Pixel> {

// Welchen Sinn hat das main an dieser Stelle?

	public static void main(String[] args){
		new Pixel(0, 0, 0, 0, 0);
	}

   public int compareTo(Pixel o) 
   { 
      int diffe = o.getDifferenz()-this.getDifferenz();

// Hier behandelst Du den Fall, dass die Differenzen verschieden sind
      if (diffe != 0) { 
    	  if(diffe > 0) return -1; else return 1;
      } 

// Falls das else-Statement ausgeführt wird, kann diffe nur 0 sein, das if ist also überflüssig!
      else if(diffe == 0){

// Du hast equals nicht überschrieben, von daher wird auf Identität überprüft. Ist es das, was Du möchtest?
    	  if (this.equals(o)) return 0; else return 1;
      }

// Dieses else kann niemals erreicht werden, da diffe nicht weder gleich 0 noch ungleich 0 sein kann
      else {
    	  return 1;
      }
   } 
}

Ich würde das compareTo so implementieren, zusammen mit equals und hashCode:

public int compareTo(Pixel p)
{
	final int diffe = differenzi - p.differenzi;
	return (diffe > 0) ? 1 : (diffe < 0) ? -1 : 0;
}

public boolean equals(Object o)
{
	if (!(o instanceof Pixel)) return false;
	Pixel p = (Pixel) o;
	return differenzi == p.differenzi; 
}

public int hashCode()
{
	return differenzi;
}

Wie bereits im dritten Post geschrieben verlangt das compareTo das Überschreiben von equals, und dieses verlangt wiederum das Überschreiben von hashCode. Sonst kannst Du die tollsten Dinge erleben, wenn Du falsch implementierte Objekte in Sets steckst.

nach einem klick auf einen button wird folgende methode aufgerufen:

public void ListeAusgeben(){
	for(Iterator iter = sortierteListe.iterator(); iter.hasNext(); ){
		Pixel wert = (Pixel) iter.next();
		System.out.println(wert);
	}
	int i;
	for(i = 0; i < sortierteListe.size(); i++){
		Pixel wert = (Pixel) sortierteListe.first();
		System.out.println("----");
		System.out.println(wert);
		sortierteListe.remove(sortierteListe.first());
	}
}

die erste for schleife wird wie erwartet abgearbeitet: ich erhalte also eine liste aller pixelobjekte in der treeset (alle mit versch. hashCodes).

Die Schleife lässt sich deutlich kompakter schreiben:

for (Pixel p : sortierteListe) System.out.println(p);

Die Schleifenbedingung Deiner zweiten Schleife ist falsch:

for(i = 0; i < sortierteListe.size(); i++)

Da Du innerhalb der Schleife die Größe der sortierten Liste durch das Löschen änderst, brichst Du zu früh ab und erwischst nicht alle Elemente. Falls die Liste am Anfang acht Elemente enthält, wirst Du so nur vier Elemente bearbeiten, danach ist die Schleife zu Ende (weil Du vier Elemente von den acht gelöscht hast ist die Liste nur noch vier Elemente gross, also sind wir fertig).

bei der zweiten for-schleife erwarte ich, dass er mir immer den ersten eintrag ausgibt, löscht und dann wieder den ersten eintrag nimmt, der natürlich der zweite aus dem vorherigen durchlauf war.
das Problem ist: er löscht den ersten eintrag nicht und ich habe keine ahnung warum!

Liegt wahrscheinlich an der falschen Implementierung von Comparable.

Es sollen also letzten Endes alle Pixel aus der Liste gelöscht werden? Warum iterierst Du dann nicht einfach ganz normale über die Liste und machst irgendwas mit Deinen Pixel, und wenn Du dann mit Deiner Schleife fertig bist, löschst Du die Liste:

for (Pixel p : sortierteListe)
{
    System.out.println("----");
    System.out.println(p);
}
sortierteListe.clear();

Müsste doch eigentlich genau das sein, was Du brauchst, oder? Gib mal Bescheid, ob es funktioniert.


Fred