Compsci 100, Fall 2009, Comparator

Name: _____________________ Netid: _________________ Name: _____________________ Netid: _________________ Name: _____________________ Netid: _________________ For this recitation you'll review java.util.Comparator, the interface that facilitates sorting using non-standard ways to compare elements being sorted.

For example, APT JohnSort, APT ClientsList, and APT Dirsort can be solved by essentially the same approach outlined in the code below

import java.util.*; public class CommonAPT { class APTComp implements Comparator<String>{ /** * return < 0 or 0 or > 0 according to a < b, a == b, a > b */ public int compare(String a, String b) { return a.compareTo(b); // default is to just sort } } public String[] sort(String[] arr){ String[] ret = arr; Arrays.sort(ret, new APTComp()); return ret; } }

For example, to complete the APT JohnSort you'd write the following:

import java.util.*; public class TheBestName { class APTComp implements Comparator<String>{ /** * return < 0 or 0 or > 0 according to a < b, a == b, a > b */ public int compare(String a, String b) { if (a.equals(b)) return 0; if ("JOHN".equals(a)) return -1; if ("JOHN".equals(b)) return 1; int asum = 0, bsum = 0; for(int k=0; k < a.length(); k++){ asum += a.charAt(k); bsum += b.charAt(k); } // complate code here by returning appropriate values } } public String[] sort(String[] arr){ String[] ret = arr; Arrays.sort(ret, new APTComp()); return ret; } }
  1. The class APTComp is called an inner class, why?
  2. By requirement with the java.util.Comparator interface, what value must be returned when parameters a and b are equal in the method compare of class APTComp?
  3. No code shown above actually calls the compare method, where is it called?
  4. What few lines will complete the compare method for the JohnSort problem.
  5. In the code above, will the parameter arr be sorted when the call returns, e.g., as shown below are the contents of list sorted? Why? String[] list = {"....", "......", "........", "xxy", "yyx}; // values CommonAPT obj = new CommonAPT; String[] next = obj.sort(list);

    General Comparator Questions

  6. What would the body of the compare method of the APTComp class be if you wanted to return a list sorted in reverse alphabetical order, so that "zoo" comes before "alpha".
  7. There's a String method compareToIgnoreCase that returns an int value less than zero, zero, or greater than zero appropriately so that "Zebra" will be greater than "apple", even though in the default lexicographical ordering of strings "Zebra" is less than "apple" because uppercase letters come earlier than lowercase letters. What's the body of the APTComp class' method compare that will cause all strings to be sorted without regard to case of the characters?
  8. Consider the code that solves the APT JohnSort that was shown above in answering the questions that follow:

    1. Why is the value of -1 returned when a is equal to "JOHN"?
    2. In the code shown the weight-value of "MARK" will actually be 77+65+82+75 = 299 instead of 13+1+18+11=43 as specified in the problem statement. This is because the Unicode/ASCII value of 'A' is 65 and each letter 'B', 'C', ..., 'Z' has a value one more than its predecessor. Explain why it's ok to write code that simply adds the values of the characters rather than subtracting 64 from each one which would result in a word's weight being calculated as specified in the problem statement.
    3. Why is the diff assigned diff = bsum-asum instead of diff = asum-bsum in the problem?
  9. For the APT Dirsort problem the body of the nested compare method has been started. You'll be asked some questions about it. class APTComp implements Comparator<String>{ public int compare(String a, String b) { String[] d1 = a.split("/"); String[] d2 = b.split("/"); int diff = d1.length - d2.length; // a and b must be the same at this point return 0; } }
    1. What's the purpose of the call to split as related to this APT?
    2. If variable diff is not zero, what should be returned and why?
    3. Describe (not with code, with words) what the code will be when diff is equal to zero.