Java/Comparators

Main article: Comparators vs Comparable

Why implement comparators

You want to implement comparators, just like you want to know how to implement a search function. Here's why - let's suppose you're receiving a stream of complex data that needs a custom sort function, and it needs to be processed rapidly.

If you extend the Comparator interface, and make it work with comparison operators, you can sort it, which means you can process it faster. Collections sort utilizes Comparator compareTo() method.

Link: https://docs.oracle.com/javase/8/docs/api/java/util/Collections.html#sort-java.util.List-

Comparators in action: Classy

A comparator was we implemented a solution to Classy, a programming puzzle from the ICPC.

This implements a custom comparator, with reverse-order (right-to-left) string comparison.

The Classy problem boils down to a custom-defined comparison rule.

public class Classy { 
	public static void main(String[] args) { 
		Scanner s = new Scanner(new BufferedReader(new InputStreamReader(System.in)));

...

The interesting bit was the Person class, which was a bare-bones wrapper around a list with a label, and a custom-defined sort function to allow People objects to be compared according to their titles.

The key is implementing Comparable<Person>, where the class that is now capable of being compared goes inside the diamonds for the Comparable interface.

Here are the fields and constructor of Person:

class Person implements Comparable<Person> {
	private String name;
	private ArrayList<String> titles;

	/** Person constructor - pass in a String array with the deets. */
	public Person(String[] deets) { 
		name = deets[0];
		// Remove : from name
		name = name.substring(0,name.length()-1);

		// initialize list of classes 
		titles = new ArrayList<String>();
		for(int i=1; i<deets.length-1; i++) { 
			titles.add(deets[i]);
		}
		// Last word will be "class", so ignore.
	}

Some utility methods:

	public String getName() { return name; }
	public ArrayList<String> getTitles() { return titles; }
	public String toString() { return getName(); } //+ ": "+getTitles().toString(); }

compareTo method

The heart of the comparable interface is the compareTo method - if we implement the compareTo method, we have a comparable object.

When we run a.compareTo(b), it should return:

• a NEGATIVE number LESS THAN ZERO if object a is LES THAN b,
• The number ZERO (0) if a and b are equal
• a POSITIVE number GREATER THAN ZERO (usually 1) if a is GREATER THAN b.

	/** Compare a person to another person. 
	 * Just compare their titles in alphabetical order. */
	public int compareTo(Person p2) { 

		Stack<String> st1 = new Stack<String>();
		Stack<String> st2 = new Stack<String>();

		// Add names to stack, left to right
		for(String title : this.getTitles()) {
			st1.push(title);
		}
		for(String title : p2.getTitles()) { 
			st2.push(title);
		}

		// Compare each name, from right-to-left.
		// If stack 1 not empty, pop item, otherwise "middle"
		// If stack 2 not empty, pop item, otherwise "middle"

		int max = Math.max(this.getTitles().size(), p2.getTitles().size());
		for(int i=0; i<max; i++) {

			// From the right
			String s1, s2;

			if(!st1.isEmpty()) {
				s1 = st1.pop();
			} else {
				s1 = "middle";
			}

			if(!st2.isEmpty()) {
				s2 = st2.pop();
			} else {
				s2 = "middle";
			}

			// Return the first non-zero value
			int res = s2.compareTo(s1);
			if( res != 0 ) {
				return res;
			}
		}

		// if we reach here, there was a tie.
		// use names as tie breaker.
		return this.getName().compareTo(p2.getName());
	}

Filling in gaps

One of the keys to the problem is identifying, from the examples, that titles should be read from right to left, with "middle" used as a filler when there are no titles specified (middle being the most "neutral" of the titles.)

This comparison test ends up being the same as the comparison test for strings ("lower" < "middle", and comparison should return <0; "middle" < "upper" and comparison should return <0; etc.)

Flags

See also:

• Template:DataStructuresFlag
• Template:AlgorithmsFlag