---
tags: fall 2018 cs61b
---
# Comparators and Function Notes
[TOC]
## Comparables and Comparators
Suppose we're given an array or list of objects. We want to be able to sort the objects in the list/array based on some order (e.g. descendingOrder, ascendingOrder, etc). This is where `Comparable` and `Comparator` come in!

### What is the difference between a Comparable object and Comparator object?

**Comparable**
A `Comparable` object is able to compared with itself by some metric. It also *implements* the `Comparable` interface.

**Comparable interface:**

interface Comparable<T> {

    //compares the current object calling this method to the object in the parameter 
    int compareTo(T o);
}

`compareTo` returns an `int` value based on if `o` should be before or after the current object calling the method.

If `o` is "larger" than the current object and should be sorted behind it, then `compareTo` returns a negative number.

If `o` is "smaller" than the current object and should be sorted before it, then `compareTo` returns a positive number.

If `o` is "equal" to the current object, then `compareTo` returns 0.

**Common Usage of compareTo:**

//String implements Comparable and has a compareTo method
//allows you to compare different Strings lexographically
String longWord = "longlonglonglongword";
String shortWord = "shortword";
String equalWord = "shortword";

longword.compareTo(shortWord); //returns negative integer
shortword.compareTo(longWord); //returns positive integer
equalword.compareTo(shortWord); //returns 0

**Comparator**
A `Comparator` determines the metric for comparison.

**Comparator interface:**

class Comparator<T> {

    //Compares its two arguments of type T for order. 
    compare(T o1, T o2);
    
}

The method `compare` returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second. If `o1<o2`, then `compare` returns a negative number. If `o1>o2`, then `compare` returns a positive number. If `o1=o2`, then `compare` returns 0.

#### Common Usage

String[] arr = new String[]{"hi","whatever","fun"};

//Arrays.sort is used for arrays
Arrays.sort(arr, /* Comparator object that compares objects in arr*/);

ArrayList<String> a = new ArrayList<>();
a.add("hi")
a.add("whatever")
a.add("fun")

//Collections.sort is used for Lists
Collections.sort(a, /* Comparator object that compares objects in a*/);

Now, let's actually create a `Comparator` object.

Suppose we want to sort the Strings in the array below by their length (longest will be last). We can create a `Comparator` object that will do this for us. Note: Before making a comparator, make sure objects being compared in the `compare` method are comparable!

Note: It's common convention for `Comparator` classes to be implemented directly when we try to create an `Comparator` instance object.

String[] arr = new String[]{"hi", "whatever", "fun"};

Comparator<String> arrComp= new Comparator<String>() {
    //what is this doing? We're directly creating a StringComparator class
    // new Comparator<String> is then instantiating an instance object of this class
    @Override 
    public int compare(String o1, String o2) {
        //short complicated version
        //return (new Integer(o1.length())).compareTo(new Integer(o2.length()));
        
        //longer clearer version
        if (o1.length == o2.length) {
            return 0;
        } else if (o1.length < o2.length) {
            return -1;
        } else {
            return 1;
        }
    }
};

Arrays.sort(arr, arrComp);

//arr should now look like ['hi', 'fun', 'whatever']
System.println(a[0]); //prints hi
System.println(a[1]); //prints fun
System.println(a[2]); //prints whatever

### Strange Syntax
The most confusing part about comparators is the syntax. As shown above, we can instantly create an object `Comparator` class and instantiate it in a couple of lines. We can also create `Comparator` instance objects in a couple of other ways.

Suppose, we're still trying to create a `Comparator` object that sorts Strings based on their length.

Comparator<String> arrComp = (s1, s2) -> (new Integer(s1.length())).compareTo(new Integer(s2.length()));

The code above is using a *lambda expression* to express the `compare(String o1, String o2)` method. In this case, `s1` and `s2` are the two String objects being compared. The `->` operator divides the expression, so the left side refers to the parameters and the right side specifies the actions of the expression.

We can also use a function and a `Function` object to create a `Comparator` object.

**Comparators Using Function**
Now, let's write our function that uses a `Function` object to return a `Comparator`. If you're confused, review the Function section below!

public static Comparator<String> getStringComp(Function<String, Integer> getter){
    return (s1, s2) -> getter.apply(s1).compareTo(getter.apply(s2))
}

//We can call the function the following way:
Function<String, Integer> getter = String::length;
Comparator<String> arrComp = getStringComp(getter);

## Function Object

Since Java cannot pass functions as parameters, it will pass in a `Function` object instead. There is a Java interface called [`Function`](https://docs.oracle.com/javase/8/docs/api/java/util/function/Function.html#apply-T-) that allows you create `Function` objects.

interface Function<T,R> {
    //takes in an input of type T and returns a Type R
    R apply(T t);
}

`T` is meant to be the type of your input that your function can be applied to and **R** is the type that is outputted.

We want to write a `Function` object that takes in a String and returns its length so we can use it in our comparator!

### What does the `Apply` method do?
The `apply` method is meant to apply the specified function to an object or take in a parameter to input into the function. More specified below:

1. You can input an object that you want to call the function on (e.g. if you pass in a `User` object called `u1` and the `Function` is `User::getEmail`, then `apply(u1)` is really calling `u1.getEmail()`).

2. You can input an object that you want to pass into the function as an input (i.e. if the `Function` is referring to a method that takes in a parameter, then you can input the parameter into apply to pass it into the method).

### Instantiating a Function Object
`Function` is a special type of interface called a [functional interface](https://docs.oracle.com/javase/8/docs/api/java/lang/FunctionalInterface.html), which means instances of the interface can be created with lambda expressions, method references, or constructor references.

//First Way: Constructor Reference
Function<String, Integer> getter = new Function<String, Integer>() {
    Integer apply(String s) {
        return s.length();
    }
};

//Second Way: Method Reference
Function<String, Integer> getter = String::length;
// '::' operator divides the expression
// the left hand side refers to the class that contains the method
// the right hand side refers to the method name

//Third Way: Lambda Expression
Function<String, Integer> getter = (s) -> s.length;

### Primitive Function Specialization
If we take a look at the `Function` spec, we realize that `Function` is limited to taking in objects as parameters. What if we want to insert a primitive type such as an int?

Well, one way is to instantiate the int as an `Integer` through:

Integer i = new Integer(5);

However, we can also use other `Function` interfaces from the [java.util.function](https://docs.oracle.com/javase/8/docs/api/java/util/function/package-summary.html) package! There are three types of these objects:
* `IntFunction`, `LongFunction`, `DoubleFunction`: arguments are of specified type and return type is an object
* `ToIntFunction`, `ToLongFunction`, `ToDoubleFunction`: return type is of specified type, arguments are objects
* `DoubleToIntFunction`, `DoubleToLongFunction`, `IntToDoubleFunction`, `IntToLongFunction`, `LongToIntFunction`, `LongToDoubleFunction`: having both argument and return type defined as primitive types, as specified by their names