I wrote a linked list implementation for my java class earlier this year. This is a generic class called LList. We now have to write out the merge sort algorithm for a lab. Instead of creating a new List implementation that takes Ints, I decided to just reuse the generic list I had created before.
The problem is how do I compare two generic objects? java wont let me do something like
if(first.headNode.data > second.headNode.data)
So, my question is, is their a way to implement some sort of comparison function that will work on any type of data? I tried the following:
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);
}
Which wont even work properly. I tested with the numbers 6 and 12, the above adds 12 to the result list.
Relevant stuff:
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;
}
NOTE: entire LList class can be located here: http://rapidshare.com/files/219112739/LList.java.html MD5: BDA8217D0756CC171032FDBDE1539478
-
You should make use of the Comparable interface.
Comparable one = (Comparable)first.headNode.data; Comparable two = (Comparable)second.headNode.data; if(one.compareTo(two) < 0) { ... } else { ... }Please note: this is pretty sloppy. I'm not checking anywhere that headNode.data is actually a Comparable object. We should really throw an exception if that is the case.
-
Look into the Comparator and Comparable interfaces.
Your sort method should take Comparator or you should specify < T extends Comparable > so that the Comparable interface can be used.
public void sort(Comparable<T> comparator) { sort(SortType.MERGE, comparator); } .... private LList<T> merge(LList<T> first, LList<T> second) { ... if(comparator.compare(first.headNode.data, second.headNode.data) < 0) { ... } -
Well, as you've discovered, you've got a problem. All you know about the objects in your list are that they are instances of Object or one of its subclasses. You can't really sort Objects. You now have a few options:
One option you have is to sort across something completely meaningless, like the hashCode for the object. You can in fact implement a perfectly valid mergesort using the hashCode, but it'd be largely pointless, since the hash code doesn't actually mean anything and there's no particular reason to sort by it except to learn about sorting.
Here's a much better way to go: change the rules of your generic list. Right now, everything in your list must be some sort of anything. Why not change that so that it can be some sort of anything that implements the
Comparableinterface? That way, you don't need to know anything about the objects other than how to compare them. This is largely how Java itself solves this problem. (I recommend reading up on its Collections stuff).Just change your object from
LList<T>toLList<T extends Comparable<T>>and you're good to go!Matt R : That work perfectly. Thanks. After I got the Comparable thing in, i just made a few changes to the mergeSort (things that should or should not have been there), and now sort's properly. ThanksCaptainAwesomePants : Glad I could help! Also -- I like your laughing man icon :)Apocalisp : Just to clarify, you don't have to modify the LList class. Just expect an LList, or an LList in your sort routine. Simon Nickerson : Do you mean LList>? -
Something that worked for me in a C# framework that I made. Makes a comparer object for a typed object, and uses reflection to determine value of the property that the list is sorting on. Tweak as needed :
using System; using System.Collections.Generic; using System.ComponentModel; namespace BOCL { /// <summary> /// Provides a comparer for collections of BOCL objects so they can be compared on any property /// </summary> /// <typeparam name="T">The type of BOCL object to compare</typeparam> public class BusinessBaseComparer<T> : IComparer<T> where T : BusinessBase<T>, new() { #region Constructors /// <summary> /// Provides a default constructor for the comparer /// </summary> protected BusinessBaseComparer() { //An instance of the business base comparer must be declared with at least one argument to be of any use } /// <summary> /// Build this comparer sorting on a particular property ascending /// </summary> /// <param name="property">The property on which the sort should be applied</param> public BusinessBaseComparer(PropertyDescriptor property) { m_SortProperty = property; } /// <summary> /// Build this comparer sorting on a particular property /// </summary> /// <param name="property">The property on which the sort should be applied</param> /// <param name="direction">The direction to which the sort should be applied</param> public BusinessBaseComparer(PropertyDescriptor property, ListSortDirection direction) { m_SortProperty = property; m_SortDirection = direction; } #endregion #region SortProperty private PropertyDescriptor m_SortProperty = null; /// <summary> /// The property on which the type is to be sorted. If the property is not found, the objects are deemed equal /// </summary> protected PropertyDescriptor SortProperty { get { return m_SortProperty; } } #endregion #region SortDirection private ListSortDirection m_SortDirection = ListSortDirection.Ascending; /// <summary> /// The direction in which the type is to be sorted /// </summary> protected ListSortDirection SortDirection { get { return m_SortDirection; } } #endregion #region IComparer<T> Members /// <summary> /// Performs comparison between to BOCL objects /// </summary> /// <param name="x">The first object to compare</param> /// <param name="y">The second object to compare</param> /// <returns>The result of the comparison</returns> public int Compare(T x, T y) { if (SortProperty == null) return 0; //we didn't find the property we were supposed to sort on //set up to get the value of the objects we are comparing against IComparable xValue = null; IComparable yValue = null; try { //now get the value for the x object and value for the y object //as something we can compare against xValue = (IComparable)SortProperty.GetValue(x); yValue = (IComparable)SortProperty.GetValue(y); //if either property came back null if (xValue == null || yValue == null) return 0; //treat them as the same } catch (InvalidCastException) { return 0; //ran into a proplem trying to convert the object into something we could compare against } if (SortDirection == ListSortDirection.Ascending) return xValue.CompareTo(yValue); else return yValue.CompareTo(xValue); } #endregion } } -
Note that Comparable is also a generic type, parameterized by what type it is comparable to. The most general, type-safe way to declare your mergeSort function above is:
private <T extends Comparable<? super T>> LList<T> mergeSort(LList<T> list) { }This enforces that the type T's compareTo method can accept an argument of type T. (In theory, a type could implement Comparable, but not be comparable to itself, like
SomeClass implements Comparable<CompletelyDifferentClass>, so it is important to have the requirement on the type parameter of Comparable. In practice, however, any well-designed Comparable class should be comparable to at least itself.)We require that
<T extends Comparable<? super T>>instead of just<T extends Comparable<T>>because it is okay if a type T'scompareTomethod accepts a more general type than T, because it would still be able to accept an argument of type T. This is important because, if you have a class A, which implementsComparable<A>; and then you have a subclass B which extends A, B cannot implementComparable<B>, because B already implementsComparable<A>, inherited from A, and a class cannot implement an interface twice. So if we required<T extends Comparable<T>>above, B would not satisfy it, and we would not be able to sortLList<B>objects.Matt R : How would I write return merge(first, second); if first and second are LList? LList.java:207: merge(mattrlab2.LList ,mattrlab2.LList ) in mattrlab2.LList cannot be applied to (mattrlab2.LList ,mattrlab2.LList ) That's what I end up with, not sure what the problem is... Matt R : Ignore the above comment, I just realised that I will ALWAYS be comparing apples and apples since the mergeSort is within the LList class.Kip : Just the kind of code to make a beginner go "screw it, I'm majoring in philosophy instead". :) (not saying it's bad code, but Java's generic types syntax gets really ugly if you haven't used it a lot)
0 comments:
Post a Comment