# Verschachtelte Treemaps, nach Value sortieren



## gnui (13. Jun 2009)

Hallo,

ich habe in meinem Programm zur Verwaltung von Personendaten folgende Struktur:
Treemap<Integer,Treemap<String,String>>.
Habe damit bisher gut mein Programm schreiben können. Die Personen werden anhand ihrer Nummer sortiert und die Nummer führt zu einer passenden Treemap in der es dann Schlüssel wie "Name", "Adresse" gibt. Kann auch Elemente löschen und Elemente anhand eines beliebigen Schlüssels (auch aus der inneren Treemap) suchen. Bei diesen Sachen und Ausgabe usw. wird immer eine temporäre Treemap erstellt welche eben den Value von der 1. bekommt und so kann ich auf alles zugreifen.
Mein Problem ist nur, dass ich gerne noch eine Sortierung nach den anderen Daten wie "Name" und "Adresse", usw. gern einbauen würde. Leider habe ich schon die Sortierung nach Value von einfachen Treemaps nicht ganz verstanden und nun habe ich ja sogar eine verschachtelte Treemap. Wäre da über eine Hilfe sehr dankbar.

vielen Danke schonmal

mfg

Gnui


----------



## Illuvatar (13. Jun 2009)

Schau dir mal das Beispielprogramm hier an:


```
import java.util.*;

public class TreeMapTest
{
  public static void main(String[] args)
  {
    SortedMap<Integer, TestEntry> map = new TreeMap<Integer, TestEntry>();
    map.put (1, new TestEntry("Eins"));
    map.put (5, new TestEntry("Fünf"));
    map.put (2, new TestEntry("Zwei"));
    map.put (4, new TestEntry("Vier"));
    map.put (3, new TestEntry("Drei"));
    System.out.println(map);
    
    Comparator<? super Integer> entryComparator = new ValueComparator(map);
    SortedMap<Integer, TestEntry> otherMap = new TreeMap<Integer, TestEntry>(entryComparator);
    otherMap.putAll(map);
    System.out.println(otherMap);
  }
}

class ValueComparator implements Comparator<Integer>
{
  private Map<Integer, TestEntry> myMap;
  public ValueComparator (Map<Integer, TestEntry> myMap)
  {
    this.myMap = myMap;
  }
  public int compare (Integer i1, Integer i2)
  {
    return myMap.get(i1).compareTo(myMap.get(i2));
  }
}

class TestEntry implements Comparable<TestEntry>
{
  private String name;
  public TestEntry (String name)
  {
    this.name = name;
  }
  public String getName()
  {
    return name;
  }
  public String toString()
  {
    return name;
  }
  public int compareTo(TestEntry other)
  {
    return name.compareTo(other.getName());
  }
}
```


----------



## Marco13 (13. Jun 2009)

Diese Verschachtelung ist ... etwas ... ungewöhnlich. Du solltest dir genau überlegen, welche Arten von Zugriffen du brauchst. Warum sind die "Personen" wieder ALS TreeMap gespeichert? Wie ist denn der Anwendungsfall?


```
Integer id = gibtDerBenutzerEinOderSo();
TreeMap person = map.get(id);

// Und hier? Sowas???
String name = person.get("name");
String datum= person.get("geburtsdatum");
```
Sowas würde man ggf. eher über eine "Person"-Klasse lösen

```
Integer id = gibtDerBenutzerEinOderSo();
Person person = map.get(id);

// Und hier sowas:
String name = person.getName();
String datum= person.getGeburtsdatum();
```

Um nach beliebigen "Dingen" Zu sortieren würde man dann evtl. einen Tree*Set* verwenden - aber beschreib' ersmal genauer, wozu die Sortierung nach anderen Kriterien dann benötigt wird, und WIE diese Sortierung und der Zugriff auf die einzelnen Elemente zusammenhängen sollen...


----------



## gnui (13. Jun 2009)

naja ich nutze das ganze folgender Maßen:

z.b. die Eingabe:

```
button_add.addActionListener(new ActionListener(){
	    	  public void actionPerformed(ActionEvent e){
	    		  if (mapp.size() < 3){
	    			TreeMap <String,String> mapp1 = new TreeMap<String,String>();
	    			mapp1.put("Name", textfield_input.getText());
	    			mapp1.put("Kurs", textfield_input2.getText());
	    			mapp1.put("Note", textfield_input3.getText());
	    			
	    		  mapp.put(Integer.valueOf(textfield_input1.getText()),mapp1);
	    		  
	    		  }
	    		  else textarea_output.setText("zu viele eingetragene Elemente");
	    		  
			  }
		  });
```

und hier die Ausgabe:

```
button_print.addActionListener(new ActionListener(){
	    	  public void actionPerformed(ActionEvent e){
	    		  Iterator it = mapp.entrySet().iterator();
	    		  while (it.hasNext()) {
	    			  Map.Entry entry = (Map.Entry)it.next();
	    			  
	    			  TreeMap <String,String> mapp1 = new TreeMap<String,String>();
	    			  mapp1 = (TreeMap) entry.getValue();
	    			
	    			 String[] rowData = {
	    			    	    String.valueOf(entry.getKey()), mapp1.get("Name"), mapp1.get("Note"), mapp1.get("Kurs")
	    			    };
	    			 model.addRow(rowData);
	    		 }
	    	  }
		  });
```



Eigene Personenklasse wäre auch gut ja, Problem ist nur ich muss unbedingt als Zentrales Element im Programm Collections beinhaltet haben, daher meine Lösung mit Collections. 
Habe mir grad überlegt ob man nicht ne Treemap<integer, Personenklasse> machen könnte. Aber auch dann müsste ich ja erst mit getValue() die richtige Person quasi aufrufen und mit Person.name usw. dann die Elemente ansprechen und einen Vorteil im Sortieren hätte ich dann ja scheinbar nicht.


----------



## gnui (13. Jun 2009)

Hab das ganze jetzt mal doch umgeschrieben so dass ich eine eigene Studentenklasse hab.
Also Treemap<Integer,Person>.
schaut so aus:

```
package t1;

public class Person {

	public String name, note, kurs;
	
	public Person(String name, String note, String kurs){
		this.name = name;
		this.adresse = adresse;
		this.ort = ort;
	}
	
	public Person(){
		
	}
	
}
```


Allerdings hab ich nun ja immernoch als Value diese Klasse welche ich temporär dann beim ausgeben z.b. erschaffe und müsste nun nach person.name z.b. sortieren, allerdings ist person ja schon der Valuewert eines Keys.




Mhh nun hab ich auch noch ein viel größeres Problem. Er speichert das ganze nichtmehr richtig in eine Datei.
Hier meine Speicheranweisung die bisher immer geklappt hat:

```
itemSaveu.addActionListener(new ActionListener(){
	    	  public void actionPerformed(ActionEvent e){
	    		  
	    		  JFileChooser dateiAuswahl = new JFileChooser(".");
	    		  int status = dateiAuswahl.showSaveDialog();
	    		  if (status == JFileChooser.APPROVE_OPTION){
	    			  dateipfad = dateiAuswahl.getSelectedFile().getPath();
	    			  if (speichern(dateipfad)){
	    				  label_search.setText("Speichern erfolgreich.");   
	    			  }
	    		  }
			  }
		  }); 

public static boolean speichern(String pfadname){
  		try
  		{
  	      ObjectOutputStream oos = new ObjectOutputStream(
  	      		new FileOutputStream(pfadname));
  	      oos.writeObject((TreeMap<Integer,Student>) mapp);
  	      oos.close();		  
  		  return true;
  		}
  		catch(IOException e)
  		{
  		  System.out.println("Schreibfehler");
  		  return false;
  		}	  
    }
```

Er gibt immer "Schreibfehler" aus, also dnek ich liegt der Fehler in der speichern-Anweisung irgendwo, aber weiß auch nicht woran es liegen könnt
Das ging bisher immer, warum denn plötzlich nichtmehr?


----------



## Marco13 (13. Jun 2009)

Erstmal zu letzten Punkt: Mit

```
catch(IOException e)
{
    e.printStackTrace();
    System.out.println("Schreibfehler");
    return false;
}
```
gibt er den (hoffentlich hilfreichen) Stack trace aus. Es liegt wohl daran, dass bei der Person-Klasse ein
public class Person *implements Serializable* 
fehlt.

Und sonst... ist mir immeroch nicht klar, wie das mit den Zugriff aussieht. Im Moment Füllst du die Map nur, und liest sie dann wieder aus. Die Tatsache, dass das eine Map ist, wird nirgendwo verwendet. 

Du solltest genauer beschreiben, was die Anforderungen sind. Ansonsten sotochert man so im Trüben.

Bisher sieht es so aus, als könntest du einfach alle Personen in einer Liste oder ggf. einem TreeSet speichern (nochmal: Was besser ist, hängt davon ab, was du damit machen willst!). Die könntest du dann beliebig sortieren und so - aber sie würden eben ggf. keinen O(1)-Zugriff auf beliebige Elemente erlauben.


```
List<Person> personen = new ArrayList<Person>();
personen.add(new Person("Name0", note0));
personen.add(new Person("Name1", note1));
personen.add(new Person("Name2", note2));

// Sortiere Liste nach namen
Collections.sort(personen, new Comparator<Person>()
{ 
    public int compare(Person p0, Person p1)
    {
        return p0.getName().compareTo(p1.getName());
    }
});


// Sortiere Liste nach Noten
Collections.sort(personen, new Comparator<Person>()
{ 
    public int compare(Person p0, Person p1)
    {
        return p0.getNote().compareTo(p1.getNote());
    }
});
```

Kannst ggf. auch mal hier schauen http://www.java-forum.org/java-faq-beitraege/39510-arrays-und-listen-sortieren.html


----------



## gnui (14. Jun 2009)

Ah vielen vielen Dank für die Lösung des Speicherproblems. Hat wirklich nur daran gelegen und klappt nun wieder. 

Ja zu dem anderen. 
Also alles was ich möchte ist eigentlich, dass man Daten eingibt in dem Programm. Das heißt man gibt eben die Kennnummer der Person an und dann Daten die Name, Geburtstag usw. .
Das ganze wird dann in oben beschriebener Form (Treemap<Integer,Person>) gespeichert. 
Das Programm soll dann eben das hinzufügen beliebig vieler Personen erlauben, sowie das suchen nach selbigen anhand von der Nummer oder Name, Geburstag usw. und auch das löschen. Laden und Speichern ebenso.
Das alles kann das Programm bisher auch. Ist damit die Funktion der Treemap etwa nicht ausgenutzt? Also klar ich hätte die Nummer auch gleich in der Personenklasse speichern können aber dann wäre die Liste nicht sofort nach der Nummer sortiert. Außerdem muss ich eben zwangsläufig wie erwähnt Collections in meinem Programm beinhaltet haben. 
Wie könnte ich denn noch die Funktionen der Treemap mir zunutze machen? Bin auch für eventuelle weitere Programmfunktionen offen. Habe mir z.b. überlegt noch eine Funktion einzufügen bei der man Personen bearbeiten kann, man gibt die Kennnummer der Person ein und hat nun Zugriff auf die Daten der Person und kann sie ändern. Dadurch, dass man durch die Treemap mit der Nummer sofort das Element hat dürfte das doch schonmal noch ne passende Funktion sein.
Die Treemap erschien mir anfangs eben auch einfach wegen der Thematik her am passendsten, da meine Personengruppen Mitarbeiter, Studenten oder irgendwelche Personen sind die in der Verwaltung sich primär anhand ihrer zugehörigen Nummer identifizieren.

Ansonsten ist immernoch eben das mit dem Sortieren. Dein Beispiel bezieht sich ja auf eine Liste welche dafür wohl ganz gut geeignet ist was das sortieren angeht. Wäre sie das denn bei den anderen Funktionen die ich oben geschrieben habe auch oder wäre auch meine derzeitige Treemap da vertretbar und eine Sortierung eventuell umsetzbar?

Nochmals vielen Dank für die bisher erhaltene Hilfe hier


----------



## Marco13 (14. Jun 2009)

Zu dem Speichern: Beachte, dass die Daten ggf. nicht mehr gelesen werden können, wenn sich das Format der Klasse ändert. D.h. wenn du eine Person speicherst, und nachher in die Klasse noch sowas wie "private int kontostand" oder so einfügst, wirst du die vorher gespeicherten Daten nicht mehr lesen können. (Aber über das Stichwort "Persistenz" könnte man Seitenweise schreiben - und wie man bei einer Websuche sieht, wurde das auch schon getan  ). Das gleiche Problem hätte es aber vorher mit der TreeMap in ähnlicher Form gegeben.

Ich weiß zwar nicht genau, wie deine Aufgabenstellung ist, aber ... wenn dort irgendwas gesagt wurde wie "Es MÜSSEN Collections" verwendet werden, dann ist TreeMap vielleicht eher ungünstig: Eine TreeMap ist KEINE Collection. Aber sie gehört zum "Collections Framework", von daher ist es nicht wirklich "falsch"...

Du solltest dir am besten mal sowas wie Trail: Collections: Table of Contents (The Java™ Tutorials) bzw. Lesson: Interfaces (The Java™ Tutorials > Collections) durchlesen. Es gibt unterschiedliche Interfaces im Collections-Framework. Die wichtigsten sind in diesem Bild zusammengefasst: 






Diese Interfaces haben unterschiedliche Eigenschaften - und sind deswegen für Unterschiedliche Dinge unterschiedlich gut geeignet. 



> Das Programm soll dann eben das hinzufügen beliebig vieler Personen erlauben, sowie das suchen nach selbigen anhand von der Nummer oder Name, Geburstag usw. und auch das löschen.
> ...
> Das alles kann das Programm bisher auch. Ist damit die Funktion der Treemap etwa nicht ausgenutzt? Also klar ich hätte die Nummer auch gleich in der Personenklasse speichern können aber dann wäre die Liste nicht sofort nach der Nummer sortiert.



Da stecken schon die wichtigsten Operationen drin. (Boah, hab gerade im Netz gesucht, aber man findet ums Verrecken keine Tabelle, wo einfach mal die Laufzeiten für die elementarsten Sachen aufgelistet sind :noe: ). Es kommt immer darauf an, was man genau machen will. 

Die Nummer könnte auch in der Personenklasse gespeichert werden. Dann könnte man die Personen auch in eine Tree*Set* einfügen, und dort wären sie auch automatisch sortiert - aber der schnelle Zugriff (zu einer gegebenen Nummer sofort die Person zu bekommen) wäre damit nicht mehr gegeben. 
(Die Nummer könnte _trotzdem_ mit in die Person-Klasse, wenn die Nummer sowas wie eine "Personalnummer" ist, die die Person eindeutig identifiziert).




> Die Treemap erschien mir anfangs eben auch einfach wegen der Thematik her am passendsten, da meine Personengruppen Mitarbeiter, Studenten oder irgendwelche Personen sind die in der Verwaltung sich primär anhand ihrer zugehörigen Nummer identifizieren.



Wenn man oft eine Nummer hat, und die dazu passende Person sucht, dann ist eine TreeMap OK (wobei dann aber eine HashMap noch besser wäre - falls das ganze nicht auch IMMER NUR nach der Nummer sortiert sein soll...). Oben hast du aber gesagt, dass immer nach unterschiedlichen Sachen gesucht wird. Dafür bietet die TreeMap aber keinen Vorteil mehr: Wenn man oft "irgendwas" hat (also entweder Name oder Nummer oder Geburtsdatum) und die passende Person sucht, dann muss man im worst case zwangsläufig immer alle Elemente (also alle values()) durchsuchen - das geht mit jeder Collection und jeder Map gleich schnell. 



> Ansonsten ist immernoch eben das mit dem Sortieren. Dein Beispiel bezieht sich ja auf eine Liste welche dafür wohl ganz gut geeignet ist was das sortieren angeht. Wäre sie das denn bei den anderen Funktionen die ich oben geschrieben habe auch oder wäre auch meine derzeitige Treemap da vertretbar und eine Sortierung eventuell umsetzbar?



Eine TreeMap ist immer nur nach dem Key sortiert. Das kann man nicht mehr ändern - außer, wenn man eine neue TreeMap mit neuen Keys anlegt. Wenn man sich "aussuchen können" soll, wonach sie sortiert sein sollen, wäre eine List ggf. besser geeignet als die TreeMap. Eine List kann man (wie im Beispiel oben) nach verschiedenen Kriterien sortieren, ohne dass man immer eine neue anlegen muss. An welcher Stelle wird das sortieren denn benötigt? Soll sortiert in eine Datei geschrieben werden? Oder eine sortierte Tabelle ausgegeben werden?


----------



## gnui (15. Jun 2009)

Also ist nun eine Liste von Personen oder ein Treeset von Personen für mich besser geeignet? Habe nun ja schon öfters die Art der Collection geeändert und frage da nun lieber nochmal genauer nach.

Es soll eigentlich primär im Programm in eienr Tabelle sortiert ausgegeben werden, wobei deine Sache mich auf die Idee gebracht hat, dass man es ja auch in eine Textdatei sortiert noch ausgeben könnte, aber ich denke das sehe ich vorerst mal als Zusatz.


----------



## Marco13 (15. Jun 2009)

gnui hat gesagt.:


> Also ist nun eine Liste von Personen oder ein Treeset von Personen für mich besser geeignet?



Och menno  50 Zeilen lang rede ich um diese Frage drumrum, und jetzt stellst du sie so direkt  

Die Antwort ist ganz klar: Was weiß ich?  Ich habe ja nur die Vor- und Nachteile der verschiedenen Collections aufgelistet. Welches die "beste" ist, hängt von Anwendungsfall ab: 

- Wenn du 100000 Personen hast, und willst dann zu 1000 Personennummern jeweils das passende Person-Objekt bekommen: Eine HashMap von "Integer" auf "Person". 

- Wenn du 100000 Personen hast, und willst dann zu 1000 Personennummern jeweils das passende Person-Objekt bekommen, und die Personen nach Personennummer sortiert in einer Datei ausgeben: Eine TreeMap von "Integer" auf "Person". 

- Wenn du 100000 Personen hast, und willst dann zu 1000 Personennummern ODER Namen ODER Geburtsdaten jeweils das passende Person-Objekt bekommen: Eine List, die bei jeder Suchanfrage von vorne bis hinten durchsucht wird.

- Wenn du 100000 Personen hast, und willst die Liste entweder nach Name oder nach Personennummer oder nach Geburtsdatum sortiert in einer Datei ausgeben: Eine List, die mit dem passenden Comparator sortiert wird.


Wenn es nur darum geht, das ganze in einer Tabelle (JTable) sortiert auszugeben, kann man davon ausgehen, dass es nicht um 100000 sondern vielleicht nur um 1000 Personen geht, und bei eine JTable gibt es eigene Mechanismen um sie nach verschiedenen Kriterien zu sortieren (siehe How to Use Tables (The Java™ Tutorials > Creating a GUI with JFC/Swing > Using Swing Components) ). In diesem Fall bleibt nur die Frage übrig, ob es "oft" Anfragen gibt wie "Gib mir zu einer Personennummer die passende Person".



Aber nebenbei: Man KÖNNTE auch ein Interface machen

```
interface Persons
{
    void add(Person p);
    void remove(Person p);
    Person getByNumber(int personenNummer);
    List<Person> getByName(String name);
    List<Person> getByDate(Date data);

    ... weitere benötigte Methoden...
}
```

Dieses Interface kannst du dann implementieren wie du willst. Insbesondere kannst du nachträglich leicht die Implementierung ändern. Du könntest also am Anfang sowas machen wie

```
class PersonsList implements Persons
{
    private List<Person> persons = new ArrayList<Person>();

    public Person getByNumber(int number)
    {
        for (Person p : persons)
        {
            if (p.getNumber() == number) return p;
        }
        return null;
    }
    ...
}
```
Wenn du später merkst, dass er die meiste Zeit damit beschäftigt ist, in der Liste rumzusuchen, kannst du das ändern zu

```
class PersonsMap implements Persons
{
    private Map<Integer, Person> persons = new HashMap<Integer, Persons>();

    public Person getByNumber(int number)
    {
        return persons.get(number);
    }
    ...
}
```
ohne dass sich am übrigen Code was ändert.


Aber das mit dem Interface solltest du dir TROTZDEM noch genau überlegen, im Hinblick darauf, was damit alles gemacht werden können soll.


----------



## gnui (15. Jun 2009)

Okay danke.

Hab mich jetzt für eine Liste entschieden. Und zwar eine LinkedList, wobei ich nicht wusst ob LinkedList oder ArrayList nun besser ist.  Außerdem komm ich nicht ganz mit dem Comparator klar. Hab mich zwar da nun eingelesen aber immer nur Beispiele gefunden bei denen in der Liste nur Strings oder so waren aber keine eigene Klasse mit Untereigenschaften so wie ich es bräuchte.


----------



## Marco13 (20. Jun 2009)

Zum Comparator steht hier einiges http://www.java-forum.org/java-faq-beitraege/39510-arrays-und-listen-sortieren.html


----------

