Sortierte Liste

[Peter M.]

Hallo,
ich bin gerade am Java lernen. Ich bearbeite gerade folgendes Szenario. Ich habe eine Klasse Schueler. Mit der Eigenschaft Alter, Name und der Methode getAlter(), getName().

Nun möchte ich mir eine Klasse Schule bauen. Es soll angenommen werden, dass die Namen der Schüler einmalig sind. Die Klasse Schule soll eine Liste der Schüler beinhalten, die nach dem Alter sortiert ist. Mit der Methode addSchueler(Schueler schueler) möchte ich einen neuen Schüler hinzufügen. Dabei soll er an die richtige Stelle eingefügt werden(nach alter Sortiert). Es soll aber jeden Namen nur einmal geben. Also wenn ich folgendes mache:

Schueler schueler1=new Schueler("Paul",12);
Schueler schueler2=new Schueler("Paul",12);
schule.add(schueler1);
schule.add(schueler2);

Soll der schueler2 nicht eingefügt werden.

Was nehme ich da erst mal als Container? Gibt es schon solche sortierten Listen? Wenn nein, was nehme ich da für eine Standard Klasse?

Vielen Dank

 

[cz3kit]

Das wird ein Problem, da du diese Objekte nicht direkt vergleiche kannst. Ein Container fällt damit dann ja weg. Das einzige was mir etzt einfällt ist, dass du die eine neue Klasse Schule erstellt, die dann von einem Container erbt, z.B. ArrayList oder was auch immer, und die Methode add überschreibst. Das würde dann z.B so aussehen, dass du dann du den Container itirierst und dabei von jedem Objekt den getName() aufrufst und dieses dann mit dem übergebendem Objekt vergleichst.

Vielleicht hat wer noch eine bessere Lösung, die würde mich dann auch interessieren, aber das ist erst mal das was mir einfällt.

 

[Der Müde Joe]

Alle Set lassen keine doppelten zu. Darum ein Set. Dafür musst du aber equals und hashCode entsprechend überschreiben.
Nun soll es sortiert sein -> interface SortetSet. Da gibts noch 2 Implementoren:
ConcurrentSkipListSet, TreeSet

--> TreeSet

EDIT:
Natürlich muss noch der entsprechende Comparator geschrieben werden, welche 2 Schüler vergleicht.

 

[Peter M.]

Alle Set lassen keine doppelten zu. Darum ein Set. Dafür musst du aber equals und hashCode entsprechend überschreiben.
Nun soll es sortiert sein -> interface SortetSet. Da gibts noch 2 Implementoren:
ConcurrentSkipListSet, TreeSet

--> TreeSet

EDIT:
Natürlich muss noch der entsprechende Comparator geschrieben werden, welche 2 Schüler vergleicht.

Das Klingt ja schon mal ganz gut. Kannst du mir mal kurz umreißen, wie man das alles macht? Ich bin neu in Java.

 

[Der Müde Joe]

Alle Set benutzen hashCode bzw equals um festzustellen, ob das Element gleich ist. Darum muss Schüler equals und hashCode so überschreiben, dass 2 Schüler gleich sind, wenn sie den gleichen Namen und die gleiche Alter haben (von dir definiert). Das Set erledigt dann den Rest.

Der Comparator ist einfach. Comparator implementieren mit schüler:
Comparator (Java Platform SE 6)
Vergleiche das alter und gibt:
(Returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.) zurück.

 

[Peter M.]

Also die Grundlagen verstehe ich. Nur wie ich das Ganze implementieren soll weiß ich nicht. Gibt es zu dem Problem irgend wo schon Beispiele?

Das Compare habe ich versucht zu implementieren:

public class Schueler implements Comparable {
...
    public int compareTo(Schueler schueler) {
        if ( (this.age == schueler.getAge()) && (this.name==schueler.getName()) ) {
            return 0;
        } else if ( this.age> schueler.getAge() ) {
            return 1;
        } else {
            return -1;
        }
    }
}

Da bekomme ich einen Fehler, dass ich das compareTo nciht implementiert hätte.

 

[Der Müde Joe]

War mir grad langweilig ;-)

import java.util.Comparator;
import java.util.SortedSet;
import java.util.TreeSet;


public class Student {
	
	private int age;
	
	public Student(int age) { this.age = age;}
	
	public int getAge() { return this.age;}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + age;
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Student other = (Student) obj;
		if (age != other.age)
			return false;
		return true;
	}
	
	public static void main(String... _ ) {
		SortedSet<Student> set = new TreeSet<Student>(new StudentComparator());
		set.add(new Student(5));
		set.add(new Student(1));
		set.add(new Student(3));
		set.add(new Student(2));
		set.add(new Student(2));
		set.add(new Student(2));
		set.add(new Student(2));
		set.add(new Student(10));
		
		for (Student student : set) {
			System.out.println(student.getAge());
		}
	}
	
	static class StudentComparator implements Comparator<Student> {

		@Override
		public int compare(Student o1, Student o2) {
			int age1 = o1.getAge();
			int age2 = o2.getAge();
			
			return (age1 > age2) ? 1 : (age1 == age2) ? 0 : -1;
		}
	}
}

Den name darfst du noch machen.

 

[Der Müde Joe]

Müsste so aussehen:

public class Student implements Comparable<Student> {

	private int age;
	private String name;

	public Student(int age, String name) {
		this.age = age;
		this.name = name;
	}

	public int getAge() {
		return this.age;
	}

	public String getName() {
		return this.name;
	}

	@Override
	public int compareTo(Student o) {
		return 0;
	}
}

Zum vergleich:
String vergleicht man NIE mit ==. In diesem Fall: Benutz die compare MEthode von String.

EDIT:
Du musst dir klar werden, was stärker ist: Alter oder Name ;-)

 

[CHE123]

hi,
mir auch

eine möglichkeit:

import java.util.*;

public class Schueler
{
  private final String name;
  private final int alter;

  public Schueler(String name, int alter) {
    this.name = name;
    this.alter = alter;
  }

  public int getAlter() {
    return alter;
  }

  public String getName() {
    return name;
  }

  @Override
  public String toString() {
    return name + " (" + alter + ")";
  }
}

import java.util.*;

public class Schule
{
  private final Map<String, Schueler> schueler = new HashMap<String, Schueler>();

  public void addSchueler(String name, int alter) {
    if(schueler.containsKey(name)) {
      throw new RuntimeException("schueler <" + name + "> ist bereits angelegt");
    }
    schueler.put(name, new Schueler(name, alter));
  }

  public static void main(String[] args) 
  {
    final Schule schule = new Schule();
    schule.addSchueler("Paul", 12);
    schule.addSchueler("Heinz", 13);
    schule.addSchueler("Fix", 11);
    schule.addSchueler("Foxy", 9);
    try {
      schule.addSchueler("Paul", 12);
    }
    catch(Exception x) {
      System.err.println("wie erwartet: " + x.getMessage());
    }

    final Comparator<Schueler> up = new Comparator<Schueler>() {
      @Override
      public int compare(Schueler o1, Schueler o2) {
        return o1.getAlter() > o2.getAlter() ? 1 : -1;
      }
    };
    final Comparator<Schueler> down = new Comparator<Schueler>() {
      @Override
      public int compare(Schueler o1, Schueler o2) {
        return o1.getAlter() < o2.getAlter() ? 1 : -1;
      }
    };
    
    final List<Schueler> sorted = new ArrayList<Schueler>(schule.schueler.values());
    Collections.sort(sorted, up);
    System.err.println(sorted);
    Collections.sort(sorted, down);
    System.err.println(sorted);
  }
}

liefert folgende ausgabe:

wie erwartet: schueler <Paul> ist bereits angelegt
[Foxy (9), Fix (11), Paul (12), Heinz (13)]
[Heinz (13), Paul (12), Fix (11), Foxy (9)]

g,
christian

 

[Peter M.]

@Der Müde Joe

zu deinem Code mal ein paar Fragen:

wie funktioniert das mit dem Hashcode?

Zu der equals Methode. Wieso wird da Object obj Übergeben, und nicht gleich ein Schüler? Und wieso kann man hier: if (age != other.age) ohne Methode auf other.alter zugreifen, obwohl das doch Private ist?

Dann ein SortedSet besteht aus einer Basis hier TreeSet. Wieso hast du das gewählt? Und einem Comparator. Ist das richtig?

Die Klasse Comparator ist static, weil sie für alle Schüler gelten soll, oder? Die Überprüfung, ob ein Objekt doppelt ist hast du noch nciht implementiert, oder?

 

[Der Müde Joe]

>wie funktioniert das mit dem Hashcode?

Object (Java Platform SE 6)

Zwei Objekte. Welche gleich sind (equals) haben denselben hashCode. Einfach eine Zahl. (benutzt man in Collections etc.

>Wieso wird da Object obj Übergeben, und nicht gleich ein Schüler?

Man kann auch Äpfel mit Birnen vergleichen, nur werden sie nie gleich sein. (Siehe auch link oben (Design by Contract: Object schreibts vor)).

>doch Private ist?

private ja, aber ich bin ja immer noch im Objekt drin.

>Wieso hast du das gewählt? Und einem Comparator. Ist das richtig?

Das TreeSet sortiert gleich. Aber ich habe gleich noch was gefunden, was nicht ganz passt. Alle Sets benutzen hashCode zum Objekte vergleichen, ausser das TreeSet, das benutzt compareTo bzw den Comparator. Somit ist es nicht ganz optimal.

Grund: Du möchtest nach alter und name sortieren, aber nur der name darft einmal vorkommen. Also ist peter,10 peter,11 nach TreeSet und compareTo ok, aber nach equals nicht. Darum war es der falsche Weg, den ich gewählt habe.

>Die Klasse Comparator ist static, weil sie für alle Schüler gelten soll, oder?

Nein. Es ist eine innere statische Klasse. So muss ich nicht x Files machen.

Ich habe mal 1 Lösung gemacht:
HashSet --> keine doppelten, benutzt equal bzw hashCode von Student
List --> kann man Ordnen
Comparator --> Wie soll gerodnet werden

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Student {

	private int age;
	private String name;

	public Student(int age, String name) {
		this.age = age;
		this.name = name;
	}

	public int getAge() {
		return this.age;
	}

	public String getName() {
		return this.name;
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + ((name == null) ? 0 : name.hashCode());
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj) {
			return true;
		}
		if (obj == null) {
			return false;
		}
		if (!(obj instanceof Student)) {
			return false;
		}
		Student other = (Student) obj;
		if (name == null) {
			if (other.name != null) {
				return false;
			}
		} else if (!name.equals(other.name)) {
			return false;
		}
		return true;
	}

	@Override
	public String toString() {
		return age + " " + name;
	}

	public static void main(String... _) {
		Set<Student> set = new HashSet<Student>();
		set.add(new Student(10, "peter"));
		set.add(new Student(8, "peter"));
		set.add(new Student(3, "hans"));
		set.add(new Student(5, "blub"));
		set.add(new Student(1, "xx"));
		set.add(new Student(1, "aa"));

		List<Student> view = new ArrayList<Student>(set);
		Collections.sort(view, new StudentComparator());
		for (Student student : view) {
			System.out.println(student);
		}
	}

	static class StudentComparator implements Comparator<Student> {

		@Override
		public int compare(Student o1, Student o2) {
			int age1 = o1.getAge();
			int age2 = o2.getAge();
			// compare age
			int i = (age1 > age2) ? 1 : (age1 == age2) ? 0 : -1;
			if (i != 0) {
				return i;
			}
			String name1 = o1.getName();
			String name2 = o2.getName();
			return name1.compareTo(name2);
		}
	}
}

 

[Peter M.]

Also wieso ich in dem Objekt drinne bin habe ich noch nciht verstanden. Es ist ja wie der Name schon sagt ein anderer Schüler. Auch das static habe ich noch nicht ganz verstanden.

Mit dem Namen das war ein Fehler meinerseits. Ich wollte ausdrücken, dass die Kombination Name und Alter einmalig sein soll. Der Name kann mehrmals vorkommen.

Also Paul 11, Paul 12 soll erlaubt sein, Paul 11, Paul 11 jedoch nicht.

 

[CHE123]

Hi Peter M.!

Eigentlich bist du nicht im selben Objekt sondern in der selben Klasse, d.h. du kannst in einer Instanz dieser Klasse (vulgo Object) auch auf eine andere Instanz der selben Klasse zugreifen.

Frage: bist du ganz sicher dass es nicht zwei Schüler mit dem selben Namen und Alter an einer Schule geben kann? mir scheint dein Schlüssel nicht ein-eindeutig zu sein...

g,
Christian

 

[Peter M.]

Ja na das ist auch bloß ein Fantasiebeispiel um mir die Sortierung ein wenig näher zu bringen. Es darf nur keine 2 Schüler mit gleichem Namen und Gleichem Alter geben.

 

[Der Müde Joe]

zum static:
Nested Classes (The Java™ Tutorials > Learning the Java Language > Classes and Objects)

 

[Peter M.]

Gut dass werde ich mir durchlesen. Welche Variante sollte ich denn nun nehmen, wenn es jeweils nur einen Eintrag pro Kombination Name-Alter gibt?

 

[Der Müde Joe]

>um mir die Sortierung ein wenig näher zu bringen.

Dann lass mal equals und hashCode und doppelt weg.

Interressant sind dann:
Collections (Java Platform SE 6)
--> die sort Methoden
Comparator (Java Platform SE 6)
--> welche 2 Objekte verlgeichen kann
Comparable (Java Platform SE 6)
--> welches Objekte von sich aus verlgeich bar mach (fast wie Comparator nur im am eigentliche Objekt)
(Unterschied, Es kann x Comparator geben, sort nach name, zeit, alter, grösse. Hingegen nur eine Comparable Ordunung: auch natural ordering in der API genannt)

speziell:
Collator (Java Platform SE 6)
--> für Strings

Collection-Framework:
List --> kann man Ordnern (mit Collections.sort())
Set --> kann man nicht ordnen (hat dafür andere Eigenschaften)
SortetSet --> ist immer in Ordnung (sprich beim einsetzten wird es geordnet und ist zusätzlich ein set)

und da gibts sicher noch mehr
über collection:
Trail: Collections (The Java™ Tutorials)

EDIT:
und den vielleicht noch für hashCode:
AngelikaLanger.com - Implementing the hashCode() Method - Angelika Langer Training/Consulting

 

[Peter M.]

Also ein Sorted Set hat mir bis jetzt gut gefallen. Aber wieso geht das jetzt ohne Implementierung von equals und hashCode? Ich würde das Objekt einfach Comperable machen. Aber da ist doch die Bedingung nciht drinnen, dass es das eine Paar nur einmal geben darf, oder?

 

[Der Müde Joe]

>Aber wieso geht das jetzt ohne Implementierung von equals und hashCode?

API lesen:

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. (See Comparable or Comparator for a precise definition of consistent with equals.) This is so because the Set interface is defined in terms of the equals operation, but a TreeSet instance performs all element comparisons using its compareTo (or compare) method, so two elements that are deemed equal by this method are, from the standpoint of the set, equal. The behavior of a set is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Set interface.

von:
TreeSet (Java Platform SE 6)

 

[Peter M.]

Also würde das jetzt reichen:

    @Override
    public int compareTo(Student o) {
        if ( (this.age == o.getAge()) ) {
            return 0;
        } else if ( this.age> o.getAge() ) {
            return 1;
        } else {
            return -1;
        }

    }

So wird nach Alter sortiert und es gibt keine Dubletten, also wo bei 2 Einträgen name und alter gleich sind.

 

[Der Müde Joe]

Im TreeSet würde es keine doppelten Alter geben.

-->a TreeSet instance performs all element comparisons using its compareTo (or compare) method.

dh. 2 Objekte sind für das TreeSet gleich, wenn 0 aus dem compare Methode raus kommt.
Widerspricht aber eigentlich dem equals. Denn das equals möchtest du ja als (name,age) Paar haben, sprich 2 Schüler sind gleich, wenn sie den selben Namen und das selbe Alter haben.

EDIT:
Eigentlich benutzt jedes Set equals/hashCode für den Vergleich und nicht compareTo. Ein Set hat darum keine doppelten Element. Es Fragt beim added ob schon ein Element equals ist. wenn ja dann wird es nicht hinzugefügt. Nur das TREESET eben nicht, das benutzt compareTo.

 

[Peter M.]

Stimmt. Was müsste ich denn da neben dem compareTo noch einbauen, dass es gleich Alter gibt, aber keine gleichen Alter-Namen paare?

Edit:

Das scheint zu klappen:

    @Override
    public int compareTo(Student o) {
        if ( (this.age == o.getAge() && (this.name.contains(o.getName()))) ) {
            return 0;
        } else if ( this.age> o.getAge() ) {
            return 1;
        } else {
            return -1;
        }

    }

 

[JohannisderKaeufer]

@Override
    public int compareTo(Student o) {
        if ( (this.age == o.getAge()) ) {
            return 0;
        } else if ( this.age> o.getAge() ) {
            return 1;
        } else {
            return -1;
        }
 
    }

geht auch so

@Override
    public int compareTo(Student o) {
      return  this.age - o.getAge() 
    }

Wenn man davon ausgeht, das das alter nicht negativ sein kann.

 

[Der Müde Joe]

Am besten lässt du das TreeSet mal weg.

Du überschreibst equals und hashCode. Ein Schüler ist equals wenn Name und Alter gleich.
und du nimmst ein normales Set (HashSet)

Dann hast du nie doppelte Namen,Alter Paare.

Wenn du das Set nun sortiert haben willst, pack es in ein eine List (ArrayList), und ruf Collections.sort auf.
a) entwerden mit dem entsprechenden Comparator
b) deine Schüler implementieren Comparable, was dann ihre natürliche Ordunung ist

Ich glaube das TreeSet verwirrt dich nur, da es eine Ausnahme ist.

 

[JohannisderKaeufer]

    @Override
    public int compareTo(Student o) {
        if ( this.age == o.getAge() ) {
            return this.name.compareTo(o.getName());
        } else {
            return this.age - o.Age();
        } 

    }

Damit wäre der name das zweite sortier Kriterium.

 

[Peter M.]

Am besten lässt du das TreeSet mal weg.

Du überschreibst equals und hashCode. Ein Schüler ist equals wenn Name und Alter gleich.
und du nimmst ein normales Set (HashSet)

Dann hast du nie doppelte Namen,Alter Paare.

Wenn du das Set nun sortiert haben willst, pack es in ein eine List (ArrayList), und ruf Collections.sort auf.
a) entwerden mit dem entsprechenden Comparator
b) deine Schüler implementieren Comparable, was dann ihre natürliche Ordunung ist

Ich glaube das TreeSet verwirrt dich nur, da es eine Ausnahme ist.

Also es funktioniert ja jetzt so, wie gewünscht:

    @Override
    public int compareTo(Student o) {
        if ( (this.age == o.getAge() && (this.name.contains(o.getName()))) ) {
            return 0;
        } else if ( this.age> o.getAge() ) {
            return 1;
        } else {
            return -1;
        }
 
    }

Oder habe ich da noch Fälle drinne, wo es zu Problemen kommen kann.

 

[Der Müde Joe]

>geht auch so

würd ich nicht empfehlen, wegen int überläufen (ok, wird beim Altern kaum passieren.)
(aber besser gleich gar nicht angewöhnen)

 

[Der Müde Joe]

So sollte es in etwa aussehen:

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

public class Student implements Comparable<Student> {

	private int age;
	private String name;

	public Student(int age, String name) {
		this.age = age;
		this.name = name;
	}

	public int getAge() {
		return this.age;
	}

	public String getName() {
		return this.name;
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + age;
		result = prime * result + ((name == null) ? 0 : name.hashCode());
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj) {
			return true;
		}
		if (obj == null) {
			return false;
		}
		if (!(obj instanceof Student)) {
			return false;
		}
		Student other = (Student) obj;
		if (age != other.age) {
			return false;
		}
		if (name == null) {
			if (other.name != null) {
				return false;
			}
		} else if (!name.equals(other.name)) {
			return false;
		}
		return true;
	}

	@Override
	public int compareTo(Student o) {
		int age1 = getAge();
		int age2 = o.getAge();
		int i = (age1 > age2) ? 1 : (age1 == age2) ? 0 : -1;
		if (i != 0) {
			return i;
		}
		String name1 = getName();
		String name2 = o.getName();
		return name1.compareTo(name2);
	}

	@Override
	public String toString() {
		return age + " " + name;
	}

	public static void main(String... _) {
		Set<Student> set = new HashSet<Student>();
		set.add(new Student(10, "peter"));
		set.add(new Student(8, "peter"));
		set.add(new Student(3, "hans"));
		set.add(new Student(5, "blub"));
		set.add(new Student(10, "peter"));
		set.add(new Student(10, "peter"));
		set.add(new Student(1, "xx"));
		set.add(new Student(1, "aa"));

		List<Student> view = new ArrayList<Student>(set);
		Collections.sort(view);
		for (Student student : view) {
			System.out.println(student);
		}
	}

}

Das HashSet schaut, dass es keine doppelten gibt und benutzt dafür equals bzw hashCode
Das Collections.sort sortiert nach deiner compareTo Methode.

Somit macht jeder was er soll.

 

[Peter M.]

Welchen Vorteil hat die Verwendung von hashSet etc. gegenüber compareTo only:

    @Override
    public int compareTo(Student o) {
        if ( (this.age == o.getAge() && (this.name.contains(o.getName()))) ) {
            return 0;
        } else if ( this.age> o.getAge() ) {
            return 1;
        } else {
            return -1;
        }
 
    }

 

[Der Müde Joe]

2 Objekte sind gleich, wenn hashCode/equals gleich/true sind. Das ist das Gesetzt. compareTo hat damit nicht zu tun.

Das HashSet baut auf diesem Gesetzt auf (und auch andere).

Nun (Ausnahme):
TreeSet benutzt aber compareTo dafür anstatt equals/hashCode. Sind equals/hashCode nicht gleich dem compreTo, ist der allgemeine Vertrag gebrochen (steht in der quote Box von vor ca 10 post). Dh wenn 2 Objekte equals sind muss auch im compareTo 0 rauskommen.

Da dies aber die Ausnahme ist, würd ich mich keineswegs darauf verlassen. Sobald du eine andere Collection benutzt (zB ein anderes Set), aber nur compareTo implementierst, equals/hashCode aber nicht überschreibst, kann es zu ganz komischen Effekten kommen. Darum kann man sich nur in diesem ganz speziellen fall (Ausnahme) darauf verlassen.

Es gibt eigentlich keine compareTo only Variante (oder aber sie ist sagen wir mal unsauber)