Comparaison des éléments dans une liste générique
J'ai écrit une liste liée de mise en œuvre de ma classe java plus tôt cette année. C'est une classe générique appelé LList. Nous avons maintenant pour écrire la fusion algorithme de tri pour un laboratoire. Au lieu de créer une nouvelle Liste de mise en œuvre qui prend Ints, j'ai décidé de réutiliser le générique de la liste que j'avais créé avant.
Le problème est de savoir comment dois-je comparer deux des objets génériques?
java ne me laissera pas faire quelque chose comme
if(first.headNode.data > second.headNode.data)Donc, ma question est, est-ce pour mettre en œuvre une sorte de fonction de comparaison qui fonctionne sur n'importe quel type de données? J'ai essayé le suivant:
String one, two;
one = first.headNode.data.toString();
two = second.headNode.data.toString();
if(first.headNode.data.compareTo(second.headNode.data) < 0) {
result.add(first.headNode.data);
//remove head node. remove() takes care of list size.
first.remove(1);
} else {
//If compareTo returns 0 or higher, second.headNode is lower or
//equal to first.headNode. So it's safe to update the result
//list
result.add(second.headNode.data);
second.remove(1);
}Qui wont même fonctionner correctement. J'ai testé avec les chiffres 6 et 12, ci-dessus ajoute 12 à la liste des résultats.
Pertinentes trucs:
private LList<T> mergeSort(LList<T> list) {
LList<T> first = new LList();
LList<T> second = new LList();
if (list.length() == 1) {
return list;
}
int middle = list.length() / 2;
second.headNode = list.getNodeAt(middle + 1);
second.length = list.length() - (middle);
//Set first half to full list, then remove the "second" half.
first.headNode = list.headNode;
first.length = middle;
first.getNodeAt(middle).next = null;
//Get the splitted halves.
first = mergeSort(first);
second = mergeSort(second);
return merge(first, second);
}
private LList<T> merge(LList<T> first, LList<T> second) {
LList<T> result = new LList();
while((first.length > 0) && (second.length > 0)) {
//Ok, lets force toString to compare stuff since generics are a pain.
String one, two;
one = first.headNode.data.toString();
two = second.headNode.data.toString();
if(one.compareTo(two)) < 0) {
result.add(first.headNode.data);
//remove head node. remove() takes care of list size.
first.remove(1);
} else {
//If compareTo returns 0 or higher, second.headNode is lower or
//equal to first.headNode. So it's safe to update the result
//list
result.add(second.headNode.data);
second.remove(1);
}
}
return result;
}REMARQUE: toute LList classe peut être trouvé [ici](http://rapidshare.com/files/219112739/LList.java.html
MD5: BDA8217D0756CC171032FDBDE1539478)
- Si vous voulez "tricher", regardez le source java pour quelque chose comme des Collections.sort(). Lorsque vous installez le JDK, il devrait y avoir une option pour installer la source. Puis il y aura une src.jar fichier dans votre répertoire d'installation. Un .fichier jar peut être renommé .zip et ouvert dans WinZip.
Vous devez vous connecter pour publier un commentaire.
Regarder dans le Comparateur et Comparable interfaces.
Votre méthode de tri devrait prendre Comparateur ou vous devez spécifier < T extends Comparable > de sorte que l'interface Comparable peut être utilisé.
Noter que Comparable est également un type générique, paramétré par le type est comparable. Le plus général, par type de moyen sûr pour déclarer votre mergeSort la fonction ci-dessus est:
Ceci impose que le type T de la méthode compareTo peuvent accepter un argument de type T. (En théorie, un type pourraient mettre en œuvre Comparable, mais ne pas être comparable à lui-même, comme
SomeClass implements Comparable<CompletelyDifferentClass>, de sorte qu'il est important d'avoir la condition sur le paramètre de type de Comparable. Dans la pratique, cependant, tout bien conçu Comparable classe devraient être comparables à au moins lui-même.)Nous exigeons que
<T extends Comparable<? super T>>au lieu de simplement<T extends Comparable<T>>parce que c'est pas grave si un type TcompareTométhode accepte un type plus général que de T, car il serait encore en mesure d'accepter un argument de type T. Ceci est important parce que, si vous avez une classe qui implémenteComparable<A>; et puis vous avez une sous-classe B qui s'étend A, B ne peut pas mettre en œuvreComparable<B>, parce que B implémente déjàComparable<A>, hérité de l'Un, et une classe ne peut pas mettre en œuvre une interface à deux reprises. Donc, si nous avons exigé de<T extends Comparable<T>>ci-dessus, B ne serait pas la satisfaire, et nous ne serions pas en mesure de trierLList<B>objets.Bien, comme vous l'avez découvert, vous avez un problème. Tout ce que vous savez sur les objets de votre liste sont elles qui sont les instances de l'Objet ou de l'un de ses sous-classes. Vous ne pouvez pas vraiment trier les Objets. Vous avez maintenant plusieurs options:
Une option que vous avez est de trier à travers quelque chose de complètement dénuée de sens, comme le hashCode de l'objet. Vous pouvez en effet mettre en œuvre un parfaitement valide mergesort à l'aide de la hashCode, mais ce serait en grande partie inutile, puisque le code de hachage ne signifie pas réellement quoi que ce soit et il n'y a pas de raison particulière de trier par elle, sauf pour en savoir sur le tri.
Voici une bien meilleure façon de le faire: de changer les règles de votre liste générique. Maintenant, tout est dans votre liste doit être une sorte de rien. Pourquoi ne pas changer que de sorte qu'il peut être une sorte de quelque chose qui met en œuvre la
Comparableinterface? De cette façon, vous n'avez pas besoin de tout savoir sur les objets autres que la manière de les comparer. C'est en grande partie la manière dont Java permet de résoudre ce problème. (Je vous recommande la lecture de ses Collections de trucs).Il suffit de changer votre objet à partir de
LList<T>àLList<T extends Comparable<T>>et vous êtes bon pour aller!<T extends Comparable<? super T>>Vous devriez faire usage de la Comparable interface.
Veuillez noter: c'est assez bâclée. Je ne suis pas la vérification de n'importe où que headNode.de données est en fait Comparable objet. Nous devrions vraiment lever une exception si c'est le cas.
Quelque chose qui a fonctionné pour moi en C# framework que j'ai fait. Fait de comparer un objet typé objet, et utilise la réflexion pour déterminer la valeur de la propriété que la liste est le tri. Ajuster si nécessaire :