[RESOLVED] Need Help with Sorting (implementing Comparable)

[slowcoder]

I want to be able to sort an array within the function: sort_horiz. However, I'm not too familiar with implementing Comparable so I have a 2 errors that I need help with. Your suggestions are much appreciated. Here's my code:

private static int horiz_list;
private static e_list_entry[] e_list = new e_list_entry[1000];

private class e_list_entry implements Cloneable {
   int delta, xy, type, c, d;
   public e_list_entry link;
		
   public e_list_entry clone() {
      e_list_entry temp = new e_list_entry();
      temp.delta = this.delta;
      temp.xy = this.xy;
      temp.type = this.type;
      temp.c = this.c;
      temp.d = this.d;
      return temp;
   }
}

private class e_list_comp implements Comparable {  //error-The type EN.edge_list_comp must implement the inherited abstract method  Comparable.compareTo(Object)
   public e_list_entry a, b;
	   
   public int compareTo(e_list_entry a) {
      return this.compareTo(b.link);
   }
}
	
private void sort_horiz() {
   int i;
   int dx, dy;
		   
   for (i = 0; i < horiz_list; i++) {
      dx = e_list[i].c - (ia_nx >> 1);
      dy = e_list[i].xy - (ia_ny >> 1);
      e_list[i].d = dx * dx + dy * dy;
   }

   e_list_comp.sort(e_list, 0, horiz_list);  //error-the method sort() is undefined...
}

[themoffster]

The first error is because you are implementing an interface and haven't added all the procedures that interface contains.
When you implement an interface you must create a procedure for every one that lives in the interface - i.e. the Comparable interface contains the method compareTo() - you must declare a method in your class called compareTo even if you don't do anything with it.

The second error is as it says, there is no procedure called sort() - you would be as well writing

e_list_comp.doSomeMethodIJustMadeUp(e_list, 0, horiz_list);

i.e. the sort method can't be found - where is it?

[dlorde]

That code seems very confused - it seems to have a separate class (e_list_comp - supposed to be a comparator?) that implements Comparable instead of Comparator, and calls its own compareTo(..) method recursively... ouch! - you'll crash with a stack overflow.

There are two standard ways to implement a custom list or array sort. One way involves having the stored elements implement Comparable, so that they can be compared. The other way involves writing a separate Comparator that can independently compare two of the items. The second way is more flexible, as you can have different comparators that sort the items in different ways, and the comparison code doesn't clutter up the item class.

To sort a list or array where the items implement Comparable, pass it to the Collections.sort(..) or Arrays.sort(..) methods respectively. If you have written a separate Comparator, use the Collections.sort(..) or Arrays.sort(..) methods that take a Comparator as well. Alternatively, you could write your own sort method instead (but why?).

So as I explained above, you need to either have e_list_entry implement Comparable, or have a separate class (e_list_comp ?) implement Comparator.

Incidentally, that clone method is not the recommended way to clone. If you read the JavaDocs for Object.clone() you'll see how to do it. In particular, by convention, the cloned object should be obtained by calling super.clone. If you do this, you won't have to copy all those int fields.

Also, your names don't follow the Java Naming Conventions (class names start with uppercase letter, variables and methods start with a lowercase letter). These conventions are not enforced by the compiler, but should be considered mandatory if you want other people to read your code.

Out of clutter, find simplicity. From discord, find harmony. In the middle of difficulty, lies opportunity...
A. Einstein

[slowcoder]

I'm re-visiting this problem that I had, because I want to try and fix it the proper way. I've read more Java documentation, but really don't understand the warning that I receive and what I need to do to fix it. The warning in my code is at the ****warning comment, it states: "Type safety: Unchecked invocation sort(Object[], Comparator) of the generic method sort(T[], Comparator<? super T>) of type Arrays". Help to understand and rectify this warning is much appreciated.

And thank you dlorde for the step in the right direction. I will look more into the clone method to change how I've done it.

	private static int horiz_list;
	
	private class E_list_entry implements Cloneable {
		int delta, xy, type, c, d;
		public E_list_entry link;

		public E_list_entry clone() {
			E_list_entry temp = new E_list_entry();
			temp.delta = this.delta;
			temp.xy = this.xy;
			temp.type = this.type;
			temp.c = this.c;
			temp.d = this.d;
			return temp;
		}
	}

	private class E_list_comp implements Comparator {
	   public int compare(Object o1, Object o2) {
	      E_list_entry a = (E_list_entry)o1;
		  E_list_entry b = (E_list_entry)o2;
		  
		  if (a.d > b.d)
		     return 1;
		  else if (a.d == b.d)
			 return 0;
		  else
		     return -1;
	   }
	}

	private void sort_horiz() {
	   int i;
	   int dx, dy;
	   
	   Lm_struct lm = new Lm_struct();
	   Comparator E_list_comp = new E_list_comp();
	
	   for (i = 0; i < horiz_list; i++) {
	      dx = lm.e_list[i].c - (ia_nx >> 1);
	      dy = lm.e_list[i].xy - (ia_ny >> 1);
	      lm.e_list[i].d = dx * dx + dy * dy;
	   }

	   try {
  	      Arrays.sort(lm.e_list, E_list_comp);  //****warning
	   }
	   catch (ClassCastException ex) {
	   }
	}

	private class Lm_struct {
	   E_list_entry[] e_list;

	   Lm_struct() {
		   e_list = new E_list_entry[1000];
		   for (int i = 0; i < e_list.length; i++)
		      e_list[i] = new E_list_entry();
	   }
	}

[dlorde]

You're getting the 'Unchecked Invocation' type safety warning because you're not using the (relatively) new Java 5 language feature 'Generics'. Classes like Comparator have now been modified so that you can use generics to make them work with the exact types you want to use - i.e. no more casting to and from Object. They will still work the old way, with Object, but you get the warning because the compiler can't check that you're passing the correct types.

To use Comparator with generics you need to specify the type you want to compare, in angle brackets, after the class name - like this:

private class E_list_comp implements Comparator<E_list_entry> {

   public int compare(E_list_entry a, E_list_entry b) {

      ... // compare here, no casting needed
   }
}

The first step towards wisdom is calling things by their right names...
Chinese proverb

[slowcoder]

dlorde, thanks for your help again. Unfortunately when I changed it exactly as you said, I still receive the same warning message. Is there something else I need to do? Thanks!

[dlorde]

Unfortunately when I changed it exactly as you said, I still receive the same warning message. Is there something else I need to do? Thanks!

Something else? well I don't know. I don't get that warning when I use a generified Comparator. Without seeing the code, I can't tell what's wrong.

Programs must be written for people to read, and only incidentally for machines to execute...
H. Abelson & G Sussman

[slowcoder]

hmmm...well, the only thing that I changed to your recommendation was to this:

	private class E_list_comp implements Comparator<E_list_entry> {
	   public int compare(E_list_entry a, E_list_entry b) {
		  
		  if (a.d > b.d)
		     return 1;
		  else if (a.d == b.d)
		     return 0;
		  else
		     return -1;
	   }
	}

And still the warning message...

[dlorde]

OK... You haven't posted the relevant code, so I assume you didn't change it. The Arrays is another class that has been generified. If you've gone to the trouble of generifying your Comparator, you should pass it to Arrays.sort(..) as a generified Comparator. Your code creates a generified Comparator, but passes it to the Arrays.sort(..) method as a plain Comparator. The sort method doesn't know it's generified, so it complains:

// instead of 
Comparator E_list_comp = new E_list_comp();

// use a generified reference so the Arrays.sort(..) method knows its generified
Comparator<E_list_entry> e_list_comp = new E_list_comp();

// or why not
E_list_comp e_list_comp = new E_list_comp();

The first step towards wisdom is calling things by their right names...
Chinese proverb

[slowcoder]

Ah, makes sense! Thanks dlorde, that took care of everything