Interface Comparable für Server-Item-Interface

[innoc]

Hallo,

ich versuche ein lauffähiges Beispiel für ein Server/Item-Interface basierend auf Comparable<T> zu finden. Vom Prinzip her soll ein Client einem Server Instanzen untereinander vergleichbarer Items zum Sortieren übergeben. Da es keinen Sinn macht die Item-Referenzen direkt zu vergleichen, habe ich für die Item-Objekte ein Attribut Name vom Typ String vorgesehen. Dieses Attribut soll für die Sortierung herhalten. Um die Vorgaben umzusetzen, habe ich mir folgenden Programmcode überlegt:

import java.util.*;

interface Comparable<Object> {
  int compareTo(Object o);
}

class Item implements Comparable {
  String name;

  Item(String name) {
    this.name = name;
  }

  public int compareTo(Item item) {
    return name.compareTo(item.name);
  }
}

class Server {

  void sort(List<? extends Comparable> items) {
    Iterator<? extends Comparable> it = items.iterator();
    Item a = it.next();
    while(it.hasNext()) {
      Item b = it.next();
      if (b.compareTo(a) < 0) {
        a = b;
      }
    }
  }

}

public class Client {
  Server server;
  List<Comparable> items = new ArrayList<Comparable>();
  items.add(new Item("Lion"));
  items.add(new Item("Tiger"));
  items.add(new Item("Cat"));
  server.sort(items);
}

Beim Kompilieren bekomme ich dann eine Fehlermeldung, dass er in items.add(new Item(Stringwert)) einen Identifier erwartet. Das verstehe ich nun nicht, denn Item ist doch der Identifier oder? Ich vermute, dass der Fehler im Aufruf der compareTo-Methode in dem if-Statement der Klasse Server liegt und ich die Zuordnung der Item-Objekte an die Variablen a und b in der Klasse Server im Programm nicht berücksichtigt habe, habe aber momentan keinen Plan, wie ich das ändern kann. Hat da jemand eine Idee?

 

[jgh]

mal von anderen "Problemen" abgesehen:

[java=34]
public class Client {
Server server;
List<Comparable> items = new ArrayList<Comparable>();

public Client() {
items.add(new Item("Lion"));
items.add(new Item("Tiger"));
items.add(new Item("Cat"));
server.sort(items);
}
// oder halt in einer Methode
public void addNewItems() {
items.add(new Item("Lion"));
}

}
[/code]
dann klappt es auch mit dem adden der new Item("wasAuchImmer");

 

[Ariol]

Du rufst Methoden direkt in der Klasse auf.
Das geht nur zum Initialisieren von Attributen, aber nicht so.

Ich vermute mal, dass du eher das hier wolltest:

import java.util.*;

class Item implements Comparable<Item> {
	String name;

	Item(String name) {
		this.name = name;
	}

	public int compareTo(Item item) {
		return name.compareTo(item.name);
	}
	
	@Override
	public String toString() {
		return "ITEM(" + name + ")";
	}
}

class Server {
	<I extends Comparable<I>> void sort(List<I> items) {
		Iterator<I> it = items.iterator();
		I a = it.next();
		while (it.hasNext()) {
			I b = it.next();
			if (b.compareTo(a) < 0) {
				a = b;
			}
		}
	}
}

public class Client {
	Server server;
	List<Item> items;

	public Client() {
		this.server = new Server();
		this.items = new ArrayList<Item>();
	}

	public void doit() {
		items.add(new Item("Lion"));
		items.add(new Item("Tiger"));
		items.add(new Item("Cat"));
		server.sort(items);
		System.out.println(items);
	}

	public static void main(String[] args) {
		new Client().doit();
	}
}

Aber dein Sortieralgorithmus funktioniert so noch nicht

 

[innoc]

Danke für den Tip von jgh. Dadurch habe ich zumindest eine kompilierbare Version hinbekommen. Diese sieht jetzt wie folgt aus:

import java.util.*;

interface Comparable<Object> {
  int compareTo(Object o);
}

class Item implements Comparable<Item> {
  String name;

  Item(String name) {
    this.name = name;
  }

  public int compareTo(Item item) {
    return (name.compareTo(item.name));
  }
}

class Server {

  void sort(List<? extends Comparable> items) {
    Iterator it = items.iterator();
    Item a = (Item)it.next();
    while(it.hasNext()) {
      Item b = (Item)it.next();
      if (b.compareTo(a) < 0) {
        a = b;
      }
    }
  }

}

public class Client {
  Server server;
  List<Comparable> items = new ArrayList<Comparable>();
 
  public Client() {
      items.add(new Item("Lion"));
      items.add(new Item("Tiger"));
      items.add(new Item("Cat"));
      server.sort(items);
  }  
}

Den Vorschlag von Ariol konnte ich mir noch nicht ansehen, hole ich nach.

 

[Ariol]

Der Server sollte doch eigentlich nichts von der Items-Klasse wissen, oder?
Dann darfst du dort auch nicht nach Item casten.

 

[innoc]

Danke Ariol für diesen Einwand. Den Cast habe ich eingefügt, nur um das Programm kompiliert zu bekommen. Dies steht natürlich im Gegensatz zu der Idee Item, Server und Client zu trennen und dadurch maximale Flexibilität zu erhalten. Durch <? extends Comparable> in Server ernte ich allerdings Kompiler-Beschwerden. Dein Vorschlag konnte ich mir allerdings bisher noch nicht zu Gemüte führen (wg. Job ).

 

[Ariol]

Ok,

mein Vorschlag ist noch etws spezifischer, aber da Item ja von Comparable erbt kannst du das hier verwenden:

Comparable a = it.next();

 

[innoc]

Hallo Ariol,

Dein Vorschlag ist super, das hat mir doch sehr geholfen, vielen Dank dafür. Was ich nicht verstehe ist, warum Du toString() in Item überschreibst. Was noch fehlt ist, dass der Sortieralgorithmus nicht funktioniert. Da muss ich noch etwas grübeln.
Aktuell sieht der Programmcode so aus:

import java.util.*;

interface Comparable<Object> {
  int compareTo(Object o);
}

class Item implements Comparable<Item> {
  String name;

  Item(String name) {
    this.name = name;
  }

  public int compareTo(Item item) {
    return (name.compareTo(item.name));
  }
}

class Server {

  <I extends Comparable<I>> void sort(List<I> items) {
    Iterator<I> it = items.iterator();
    I a = it.next();
    while(it.hasNext()) {
      I b = it.next();
      if (b.compareTo(a) < 0) {
        a = b;
      }
    }
  }

}

public class Client {
  Server server;
  List<Item> items;
 
  public Client() {
    this.server = new Server();
    this.items = new ArrayList<Item>();
  }

  public void doIt() {
    items.add(new Item("Lion"));
    items.add(new Item("Tiger"));
    items.add(new Item("Cat"));
    server.sort(items);
    for (Item item : items) {
      System.out.println(item.name);
    }
  }

  public static void main(String[] args) {
    new Client().doIt();
  }
  
}

Vielleicht hat ja jemand noch ein Tipp warum die Sortierung nicht klappt. Die Methode sort() ist ja an sich ok, evtl. ein pass-by-copy-Problem?

 

[Ariol]

Hallo Ariol,

Dein Vorschlag ist super, das hat mir doch sehr geholfen, vielen Dank dafür. Was ich nicht verstehe ist, warum Du toString() in Item überschreibst.
...

Wenn

toString

einer Klasse überschrieben ist, die in eine Liste gesteckt wird, kann man diese Liste direkt über

System.out.println()

ausgeben. War nur um keine eigene for-Schleife schrieben zu müssen.

...
[JAVA=20]
...
<I extends Comparable<I>> void sort(List<I> items) {
Iterator<I> it = items.iterator();
I a = it.next();
while(it.hasNext()) {
I b = it.next();
if (b.compareTo(a) < 0) {
a = b;
}
}
}

}
[/code]

Vielleicht hat ja jemand noch ein Tipp warum die Sortierung nicht klappt. Die Methode sort() ist ja an sich ok, evtl. ein pass-by-copy-Problem?

Du änderst ja nichts an der Liste. Geht es dir eigentlich darum selbst zu sortieren oder überhaupt nur darum, dass die Liste sortiert ist?

Im 2ten Fall hilft dir

Collections.sort()

.

 

[innoc]

Vorerst möchte ich nur die Liste sortieren.
Was mir beim weiteren Herumprobieren an dem Programm aufgefallen ist:
1. So wie meine Sortierfunktion aufgebaut ist, geht wohl ein Wert in der Liste verloren. Wegen a = b zeigen im letzten Durchlauf der if-Schleife die Variablen a und b auf die gleiche Referenz. Ich muss da wohl eher swappen.
Zumindest mit nachfolgendem Code bekomme ich einen Hinweis, dass es mit dem Sortieren dadurch funktioniert (die Server-Klasse habe ich zur Vereinfachung hier weggelassen):

import java.util.*;

class Item implements Comparable<Item> {
  String name;

  Item(String name) {
    this.name = name;
  }

  public int compareTo(Item item) {
    return (name.compareTo(item.name));
  }
}


public class BubbleSort {

    static void sort(ArrayList<Item> items) {
      int pass = 0;
      Iterator<Item> it = items.iterator();
      Item a = it.next();
      while(it.hasNext()) {
        Item b = it.next();
        if (b.compareTo(a) < 0) {
          Item temp = a;
          a = b;
          b = temp;
        }
        pass++;
        System.out.println(pass + ". Pass: Variable a: " + a.name);
        System.out.println(pass + ". Pass: Variable b: " + b.name);
      }
    }

 
  public static void main (String[] args) {
    ArrayList<Item> items = new ArrayList<Item>();
    Item lion = new Item("2:Lion");
    Item cat = new Item("1:Cat");
    Item tiger = new Item("3:Tiger");
    items.add(lion);
    items.add(tiger);
    items.add(cat);
    sort(items);
  }

}

2. Dass die Liste in der Client-Klasse nach dem Aufruf der Methode sort() sich nicht ändert, liegt meines Erachtens wohl daran, dass in dem Programm nirgends eine Umordnung der Liste angestossen wird. Dabei ist mir momentan noch unklar, ob das nur über das Befüllen einer zweiten Liste geht, oder ob es doch eine Funktion gibt, die mir meine ursprüngliche Liste neu sortiert.
3. Verstehe ich nicht, wie Server die Liste sortieren kann, ohne das Attribut name von Item zu kennen.
Es wäre super, wenn mir da jemand auf die Sprünge helfen könnte.

 

[innoc]

OK ich glaube Punkt 3 kann ich mir selbst beantworten, wohl über den Aufruf von compareTo() in Item, oder?

 

[Ariol]

1+2: Richtig, du musst swappen. Zusätzlich musst du aber auch die Werte in der Liste ändern.
3: Genau


Aktuell legst du dir lokale referenzen an, die du dann mit jeweils der anderen Referenz überschreibst.
Dabei bleibt die Liste unangetastet.

Verwende statt eines Iterators lieber

for(int i = 0; i < list.length(); i++)

...
Wenn man sich die Sourcen der Collectionsklasse ansieht, kann man entdecken, dass die zuerst aus der Liste ein Array machen, das sortieren und anschließend die Liste mit den sortierten Werten befüllen.
Je nach Aufbau der Liste ist dieser Schritt sinnvoll (z.B. LinkedList), weil der Zugriff über den Index langsamer werden kann als ein einmaliges Kopieren.

 

[innoc]

Im Prinzip ist es ja nicht so schwer die Liste mit Collections.sort() zu sortieren. Als Server/Item-Implementation sieht das wohl dann wie folgt aus:

import java.util.*;

class Item implements Comparable<Item> {
  String name;

  Item(String name) {
    this.name = name;
  }

  public int compareTo(Item item) {
    return name.compareTo(item.name);
  }
}

class Server {

  <I extends Comparable<I>> void sort(List<I> items) {
    Collections.sort(items);    
  }

}


class Client3 {
  public static void main(String[] args) {
    List<Item> items = new ArrayList<Item>();
    Server server = new Server();
    items.add(new Item("Lion"));
    items.add(new Item("Tiger"));
    items.add(new Item("Cat"));
    server.sort(items);
    for (Item item : items) {
      System.out.print(item.name + " ");
    }
  }  
}

Collections.sort() in der Server-Klasse kann man in dem obigen Beispiel auch ersetzen:

...
class Server {

  <I extends Comparable<I>> void sort(List<I> items) {
    Object[] a = items.toArray();
    Arrays.sort(a);
    ListIterator<I> i = items.listIterator();
    for (int j=0; j<a.length; j++) {
      i.next();
      i.set((I)a[j]);
    }
  }

}
...

Ursprünglich wollte ich ja die folgende allgemeine Struktur des Programms umsetzen, die wie folgt lautet:

interface Comparable {
  int compareTo(Object o);
}

class Item implements Comparable {
  
  ...

  public int compareTo(Item item) {
    ...
  }
}

class Server {

  void sort(List<? extends Comparable> items) {
    ...
    if (b.compareTo(a) < 0) {
        ...;
    }
  }

}

public class Client {
  Server server;
  List<Comparable> items;
  ...
    server.sort(items);
  ...  
}

Das setzt voraus, dass ich in

...
 if (b.compareTo(a) < 0) {
        ...;
    }
 ...

meinen eigenen Sortieralgorithmus implementiere. Das ist leider nicht so einfach, wie ich mir das am Anfang vorgestellt habe. Vielleicht hat da ja jemand noch einen Vorschlag. Andernfalls kann ich ja den einfachen Weg über die Java-Bibliothek gehen.