Sorting List of objects by object variable

asmith33

I am trying to sort a list of objects and I realize there are several post about this (I have looked at those), but I am struggling to understand the Comparator stuff.

A few questions/concerns. In my actual program, not the code listed below, I create a list of objects named corners. I don't really know the terminology, but basally I have created a list of these corners, then later in my program I gathered a subset of these corner objects into another list. I think the subset list just points to the original objects. Could someone confirm this? I'm not actually making "new" objects by making a subset list, thats my understanding.

After I make that subset list, I want to sort those objects by a variable "elevation." This has given me quite a lot of trouble.

Anyway, after several tutorials and trial and error I have constructed this simplified example and it seems to work. Code below.

import java.util.*;

List <corner> corners = new ArrayList();

void setup() {
  for (int i=0; i<5; i++) {
    float ele = random(10);
    corner c = new corner(ele, i);
    corners.add(c);
  }

  for (corner c : corners) {
    println(c.elevation, c.index);
  }
  println("----");

  Collections.sort(corners, new corner());

  for (corner c : corners) {
    println(c.elevation, c.index);
  }
}

void draw() {
}

class corner implements Comparator<corner> {
  float elevation;
  int index;

  corner () {
  }

  corner (float elevation, int index) {
    this.elevation = elevation;
    this.index = index;
  }

  int compare(corner c0, corner c1) {
    return int(c0.elevation-c1.elevation);

  }
}

My concern here is that

Collections.sort(corners, new corner());

is actually creating new objects instead of just sorting that list of objects. I did a few tests and it appears that I'm wrong, but the "new" keyword concerns me. Can someone tell me if this method has just created a set of new objects or is it just reordered the objects. Also, if it's not making new objects, why does the method require the "new" keyword?

Also, if this works, why do the other examples i've run across make this so much more complicated than the method I used above.

The tutorial that finally gave me the above code was found here : http://www.tutorialspoint.com/java/java_using_comparator.htm

GoToLoop

Never used Comparator yet, but only Comparable. And also I don't think Comparator is the proper pattern for your class. You can take a look at these old forum threads about it:
http://forum.processing.org/two/discussions/tagged/comparable

quark

When the user wants to specify the order of a collection of objects there are two ways of doing it either

the class must implement the comparable interface or the user must supply a Comparator object at sort time. In your code you have mixed them up.

By convention class names start with a capital letter so I have renamed your class as Corner for this discussion.

In the code below I have rewritten your Corner class to implement Comparable

class Corner implements Comparable<Corner> {
    float elevation;
    int index;

    Corner () {
    }

    Corner (float elevation, int index) {
        this.elevation = elevation;
        this.index = index;
    }

    // This method is required due to implementing Comparable
    public int compareTo(Corner c0) {
        return (int) Math.signum(elevation - c0.elevation);
    }
}

To sort an array list of these you use

Collections.sort(corners);

The advantage of using Comparable is that you don't need a second class, the disadvantage is that you can only sort on one criteria.

The alternative is to use a Comparator object which I show below

class SortByElevation implements Comparator<Corner>  {

    public int compare(Corner c0, Corner c1) {
         return (int) Math.signum(c0.elevation - c1.elevation);
    }

}

To sort an array list of these using a comparator object

Collections.sort(corners, new SortByElevation() );

The advantage is that you can have different comparator classes to sort the data in different ways.

When using comparator objects there is no need to implement the Comparable interface but it is OK (but unusual) to mix both techniques on the same class e.g. Corner

GoToLoop

Just some extra warnings & points: :-B

• The expression: (int) (elevation - c.elevation) breaks compareTo()'s contract when those variables can have negative range values! At least that's what I've heard about somewhere. :-SS
• If so, add signum() function too: (int) Math.signum(elevation - c.elevation).
• Or some other more approprate function like Integer.signum() for integral variables for example.
• Take notice that (int) (elevation - c.elevation) is for ascending order. For descending, swap their subtraction positions: (int) (c.elevation - elevation).
• Collections.sort(corners, new SortByElevation()); creates 1 Comparator object every time needlessly. Better instantiate 1 and store it in a "global" variable instead in order to reuse them: :-bd

// forum.processing.org/two/discussion/8973/sorting-list-of-objects-by-object-variable
// 2015/Jan/11

import java.util.Arrays;
import java.util.Comparator;

static final Comparator<Corner> SORT_BY_ELEVATION_ASCENT = new Comparator<Corner>() {
  @ Override int compare(Corner c0, Corner c1) {
    return Float.compare(c0.elevation, c1.elevation);
  }
};

static final Comparator<Corner> SORT_BY_ELEVATION_DESCENT = new Comparator<Corner>() {
  @ Override int compare(Corner c0, Corner c1) {
    return Float.compare(c1.elevation, c0.elevation);
  }
};

static final int NUM = 5, MAX = 10;
final Corner[] corners = new Corner[NUM];

void setup() {
  for (int i=0; i!=NUM; corners[i]=new Corner(random(MAX), i++));
  printArray(corners);
  println();

  Arrays.sort(corners, SORT_BY_ELEVATION_ASCENT);
  printArray(corners);
  println();

  Arrays.sort(corners, SORT_BY_ELEVATION_DESCENT);
  printArray(corners);
  exit();
}

final class Corner {
  final float elevation;
  final int index;

  Corner(float h, int idx) {
    elevation = h;
    index = idx;
  }

  @ Override String toString() {
    return "Idx: " + nf(index, 2) + "\tHeight: " + nf(elevation, 0, 4);
  }
}

P.S.: After some runs, I've spotted lotsa wrong ordering for nearby values! :O
(int) (elevation - c.elevation) can't be used for fractional types at all! [-X

quark

(int) Math.signum(elevation - c.elevation)

@GoToLoop well spotted this code will definitely not work as intended. I have modified my code above to make use of signum.

GoToLoop

And btW, same as above but implementing Comparable inside Corner. A lil' more compact: ;)

// forum.processing.org/two/discussion/8973/sorting-list-of-objects-by-object-variable
// 2015/Jan/11

static final int NUM = 5, MAX = 10;
final Corner[] corners = new Corner[NUM];

void setup() {
  for (int i=0; i!=NUM; corners[i]=new Corner(random(MAX), i++));
  printArray(corners);
  println();

  java.util.Arrays.sort(corners);
  printArray(corners);
  println();

  Corner.isDescent = true;
  java.util.Arrays.sort(corners);
  printArray(corners);
  exit();
}

static abstract class CornerStatic {
  static boolean isDescent;
}

final class Corner extends CornerStatic implements Comparable<Corner> {
  final float elevation;
  final int index;

  Corner(float h, int idx) {
    elevation = h;
    index = idx;
  }

  @ Override int compareTo(Corner c) {
    return (int) Math.signum(c.elevation - elevation) * (isDescent? 1 : -1);
  }

  @ Override String toString() {
    return "Idx: " + nf(index, 2) + "\tHeight: " + nf(elevation, 0, 4);
  }
}

quark

Can I suggest you drop the three occurrences of the final keyword in the class Corner it assumes

1) that the class will never be extended 2) that the fields will never need changing 3) that the OP understands what final means

Also why not incorporate the CornerStatic and Corner classes e.g.

static class Corner implements Comparable<Corner> {
    static boolean isDescent;
    final float elevation;
    final int index;

:)

GoToLoop

Can I suggest you drop the 3 occurrences of the final keyword in the class Corner?

I love to use final everwhere & all the time. And it's a sketch, not a distributed library:

• Wanna subclass the class later?... remove final from final class Corner.
• Wanna change values of its fields?... remove final from their declarations.

Not that hard! It's in the P5's reference page too: http://Processing.org/reference/final.html O:-)

Also why not incorporate the CornerStatic and Corner classes?

B/c Corner is an inner class. Inner classes can't declare static members by themselves.
Unless they happen to be final primitive or String datatypes w/ known-compile expression values! @-)

GoToLoop

On 2nd thought, since Corner doesn't currently deal w/ sketch's canvas and its API,
it can indeed be declared static and become a nested non-inner class! ~:>
Also removed those final keywords from it this time: :P

// forum.processing.org/two/discussion/8973/sorting-list-of-objects-by-object-variable
// 2015/Jan/11

static final int NUM = 5, MAX = 10;
final Corner[] corners = new Corner[NUM];

void setup() {
  for (int i=0; i!=NUM; corners[i]=new Corner(random(MAX), i++));
  printArray(corners);
  println();

  java.util.Arrays.sort(corners);
  printArray(corners);
  println();

  Corner.isDescent = true;
  java.util.Arrays.sort(corners);
  printArray(corners);
  exit();
}

static class Corner implements Comparable<Corner> {
  static boolean isDescent;

  float elevation;
  int index;

  Corner(float h, int idx) {
    elevation = h;
    index = idx;
  }

  @ Override int compareTo(Corner c) {
    return (int) Math.signum(c.elevation - elevation) * (isDescent? 1 : -1);
  }

  @ Override String toString() {
    return "Idx: " + nf(index, 2) + "\tHeight: " + nf(elevation, 0, 4);
  }
}

asmith33

Thank you guys, that was a lot of information and I haven't had a chance to digest it all just yet, but I will tonight. This forum is quite helpful!

asmith33

I got this all put in and it's working wonderfully. Thanks for keeping it simple, this really taught me a lot.

GoToLoop

Glad you got it alright! B-) For the sake of completeness, a bonus variant below:

@ Override int compareTo(Corner c) {
  return Float.compare(elevation, c.elevation) * (isDescent? -1 : 1);
}

Float.compare() is said to replace (int) Math.signum(<subtraction>) w/ more accuracy: :D
https://docs.oracle.com/javase/8/docs/api/java/lang/Float.html#compare-float-float-