Follow US:

Practice English Speaking&Listening with: [Inheritance3, Video 6] Comparator

Normal
(0)
Difficulty: 0

You don't always want to compare objects in the same way

every time.

That's where the comparator is going to come in.

So what do I mean by that?

I'm going to start by mentioning a nice term, natural order.

It's sometimes used to refer to the ordering implied

by the compareTo method of a particular class.

So for example, in Java, if we look

at how we decide how something is less than or greater

than another, in this case a dog,

we see that it only uses the size.

So the natural ordering is simply the ordering

of dogs based on size.

So imagine we have three dogs.

Here we have Doge, who's of size 5.

We have Grigometh, size 200, and Clifford, size 9,000.

They are ordered on this slide according

to the natural order, where small is on the left

and large is on the right.

Now sometimes, maybe you actually

want to sort them in a different way.

So maybe you want to sort them alphabetically

because they're all in a class together in say a classroom,

and you want to seat them in alphabetical order

so that it seems fair.

So in this case, if you sorted your three dogs

by alphabetical order, we have Clifford, Dog, and Grigometh,

Grigometh being last because Grigometh's name starts

with a G.

So how do we do that in Java?

Well, let's think more abstractly first.

Imagine that we were doing this in a language

where we had explicit higher order functions where

we pass the comparison function as a callback.

In that case, if we wanted to print--

again, back to our print_larger method earlier.

If we wanted to do this with a different ordering,

we would simply pass a different comparison function.

So if you were passing callbacks directly,

just make a different callback.

And then the issue becomes the person using print_larger,

they just have to pick the right compare.

How do we do that with subtype polymorphism?

That's going to be your question to ponder on this blue slide.

So this print_larger function, it

takes two objects of the same type.

It calls largerThan.

Here we'd stringify whichever one is bigger.

And the question is, how can you augment this code

to support multiple orderings?

So this one already automatically supports

multiple orderings, because you could simply pass

a different compare function.

So the question is, what could you do here?

So I'll give you a couple bad ideas.

One of them is we could have instead of just compareTo,

we could have like another function

called compareTo2 and another called compareTo3

and another called CompareTo4.

And then it's just up to the person

who is using the class to look up and see what each one does.

And you can have a bunch of them or something.

You can imagine having maybe a string

argument to the compareTo method that says, which compare?

And then there's documentation someplace

that tells you what string to pick to get different fields.

You can imagine having maybe something more exotic,

where you have to pass a--

or you have like an array of something.

An array of functions.

Is that a thing you can do in Java?

No.

So-- well, I guess in Java 8 you could.

Anyway.

But all those ideas are not what Java settled on.

And the thing they settled on ultimately I find pretty clean.

So the thing that Java uses is we will pass an object, which

will be of type comparator of T. And in this case,

it's going to be--

we're going to make sure this is the type

and this is the variable name.

So we'll just ask that object to compare x's and y's.

And as long as we have a comparator that actually knows

how to handle these types, which we do here, see,

then that will give us our answer.

So let's see how we do that in Java.

I'll jump in.

We'll come back to this.

So in Java, there is something known as a comparator.

And since it's an object, the way

we're going to use it is actually

create a nested class inside of Dog

that implements a comparator.

So in this case, we'll have public class NameComparator

implements comparator dog.

So we're declaring to the world that NameComparator

is a type of object that knows how to compare dogs.

Now, here we see it says, cannot resolve symbol comparator.

And so to fix that, I'll say import Java util comparator.

So this is something that we have to do for comparator.

We do not have to for comparable.

So comparable is just a little more important in the language.

You don't have to import anything.

But with competitors, we do.

So now that we have done that, we have public class

NameComparator implements comparator.

And now we need to fill in the method that's required.

What is that method?

Well, I have it here on the slide.

This interface requires that we implement int compare T 01,

T 02.

So I'm going to say public int compare T--

what did I say?

T 01-- or o1, T o2.

I'm always saying 0.

Now in this case, we actually get a complaint,

because the issue here is that this T is supposed

to match whatever is up here.

So we need to say actually dog.

And maybe I'll call these things dog a and dog b.

Now, the rule for compare is just like compareTo.

We want to return a positive number if A is bigger,

a 0 if they're equal, and a minus type-- sorry, a negative

if a is less than b.

So to do that we can simply defer to the string method,

which has a compareTo method.

So in other words, we'll say do whatever the string

compareTo would have done--

so we'll say a dot name dot compareTo b dot name.

So basically, we're delegating all the work

to the string instead of doing some kind of loop where

we compare all the letters or whatever.

That's already done for us.

So now that we've created this NameComparator class,

I'm going to make a small observation.

If you look here, you'll note that this does not

use any of the instance variables of a dog.

You could think of this as a NameComparator

is like the great sky dog.

You don't actually need to instantiate a dog

to get a NameComparator.

And so I'm going to make this class static.

That doesn't really make that much of a difference.

But it means I cannot use any of these instance variables.

And it means it will also be easier

to use the NameComparator class.

Let's use it to make sure we see what's going on.

So if go to DogLauncher, the way we would actually

use this thing is we have to first create a comparator.

So we can say dog dot NameComparator--

we'll call this NC--

equals new dog dot NameComparator.

And that gives us an object that is capable of comparing dogs

by name.

We might then say something like if in c dot

compare d1 d3 is greater than 0, that's shorthand for--

I'll make a note here--

if d1 comes later than d3 in the alphabet,

then let's have d1 bark.

Otherwise, let's have d3 bark.

And so if we run this code, it should

be whichever of these two dogs comes later in the alphabet.

Hopefully you can see that Elise is the answer, because E comes

after B. And indeed, first this is Benjamin barking

and then lastly we have Elise here, who is barking.

So this code certainly works.

Now there's one little difference

that I'm going to do here, just to reflect the way Java code is

usually written.

We don't often do new dog NameComparator.

So instead what I'll do is I will go into the Dog class.

And I'm actually going to make this class private, which

of course will break DogLauncher.

And then I'm going to make a public method called--

it's going to return a comparator of dogs.

The name of the method is--

we'll call it get NameComparator,

something like that.

And then we'll simply return a new NameComparator.

Now, is this really any different?

No.

But it matches the kind of code that exists in existing Java

libraries.

And we might get a sense in a week or so why this is useful.

But I'm just doing this to keep in convention

with what normally people do.

So in this case, instead of doing

dog dot NameComparator in c equals

new dog dot NameComparator, we'll

do dog dot get NameComparator.

So it's a function that generates NameComparators

and returns them.

Now we look here, we actually have an issue,

which is that get NameComparator cannot be referenced from

a static context.

And what's being complained about here

is that I forgot to make this method static.

Challenge for you.

Try and figure out how to actually

get a NameComparator without putting the word "static" here

if you want.

Now last thing we need to do is that dog

dot NameComparator is a private class,

so we need to somehow get a container that

can hold dog comparators.

And it turns out you can actually do that simply

with a comparator of dog space NC.

Now again we get a complaint, cannot resolve Java assemble

comparator.

And we could do something like Java dot util dot comparator,

though that's quite a mess.

I mean, who wants to do that everywhere they

use a comparator?

So instead, I'll use an import.

We'll talk about imports in more detail in the next lecture

video.

So finally, we have code that looks more or less

like real Java code.

The Dog class has a NameComparator class

that is private.

We have a method that returns a comparator.

And then finally, to use it, we simply create a comparator,

store it in the variable, and can use it.

So all of that said, in project 1B,

you get a chance to actually play around

with this a little bit.

You're not using the official comparator interface,

but you'll build something quite similar.

So in contrast to other languages,

where you would handle this simply

by passing a different function as an argument

to a method that's supposed to do general work,

now we're passing a comparator to a function.

And that allows us to have general code.

So if we summarize how things look

in terms of the inheritance hierarchy,

we have a comparator interface that's built into Java.

We have a NameComparator, which we just built.

That's a private class that implements this comparator

interface.

So if we look at our code in Dog,

this class implements the comparator dog interface.

And we could also write a SizeComparator,

but we will not do so here.

Now notice that when it comes to inheritance,

the Dog class itself is not part of this tree.

It's not that SizeComparator is a dog.

It's not that dog is a size comparator, nothing like that.

And so ultimately, what we end up with,

just for your reference, is code that looks something

like this, where we have a NameComparator here

and we can invoke them.

And this is a little different, because I didn't have space

to do the private method.

Oops.

Sorry.

Geez.

One more time.

I didn't have room to do the private class

with public static method that returns a copy.

And it's not a big deal.

I mean, you shouldn't look at this

and think like, OK, that's a lot better than what's

on this slide.

This is just convention.

But hopefully, it makes syntactic sense to you.

So that's NameComparator.

So to summarize everything we just did on all of this video,

interfaces ultimately in Java provide us

with the ability to make callbacks.

What's a callback?

Well, sometimes when you write a function,

like the one we did today, max, we need something.

We need compareTo, something to actually do the work.

So it's kind of like if you have a friend who's, I

don't know, watching your dog--

there's a lot of dog stuff happening here--

and you give him your phone number

and say, hey, please call me if the dog needs something,

like food, and I'll tell you where it is.

And so in that case, it's considered a callback.

So some languages handle this by having explicit function

passing.

That's the way you do things.

It's a very functional style.

But in Java, we do it by wrapping the needed function

inside of an interface, either comparable or a comparator.

And that lets you call, for example, I don't know,

let's say Arrays.sort.

And in that case, when you call Arrays.sort,

it will call your compareTo method every single time

it needs to make a comparison.

So imagine a sorting algorithm, like selection sort we wrote.

It will just keep calling compareTo

every time it needs it.

And that compareTo method tells you what to do.

And so ultimately, project 1B, you'll

get a chance to play around with this a little bit.

And I think you'll like it.

Now, one thing we won't tease out in project 1B

is the difference between a comparable and a comparator.

And so the only difference is that a comparable says,

I want to compare myself to another object.

And a comparator compares two other objects.

So it's a subtle distinction.

So they're related concepts, but I'd

say they're mostly orthogonal.

So if you implement comparable, you're

comparing yourself to other objects.

And then what a comparator does for you is it

compares two other objects.

And the only reason we did that is because, well, there's

only room for one compareTo function.

And so if I want multiple ways to compare,

I have to ultimately, in Java at least,

turn to the comparator ID.

That's it, I think, for this video,

so we'll see you next time.

See you then.

The Description of [Inheritance3, Video 6] Comparator