Java/Comparators

Comparators in action: Classy

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

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