Next we'll take a look at comparators which is a Java mechanism that helps us sort. The same data on different sort keys, different orders. And you're familiar with this. Your music library maybe I, at one point, you sort it by the artist's name. In this case we're looking at the b's. But in another situation, you might want to sort it by song names to look through it by song names. That's the same data using different sort keys. How do we arrange to do something is natural as this in our Java sorts? Now, we use the fourth in order to be able to implement sorts that can sort any type of data, we use Java's Comparable interface. And that concept is that there's some natural ordering of the data that you'll want to use most of the time, that's what the Comparable interface is all about. But there's a different interface called the Comparator Interface which is a way to help a sort, using some alternate order or many different orders on the same data. And the Comparator interface again just says that it's going to implement a method compare() that compares two different keys of the given type, of the generic type. Again it has to be a total order and this is very familiar for example with strings. There's many different ways that we might want to sort strings. We might want to use the natural alphabetic order or we might want to make it case insensitive or maybe there is just different languages that have different rules of the ordering. We're sorting strings but we're implementing a different ordering, various different orderings on that same data. That's what the Comparator interface is for. So the Java system sort will have a different. [cough] method to implement comparators. The idea is that you create a comparator object and then pass that as a second argument to Java's sort routine and we can do the same thing for our sorts. The idea is when a decouple, the definition of the data type from the definition of what it means to compare to items of that type. With the natural order, we had to put the definition compared to within the data type. With comparators, we can do that outside of the data type even at some later time. Strings were defined and as part of the Java system but we can define our own ordering on strings with the comparator. So in our sort implementations we can change them as shown in this example to support comparators. To support comparators in our sort implementations we'll pass an array of objects and instead of an array of comparable and then, there's a second argument passed a comparator. Then, the less method will take that comparator as an argument and this is the one that actually invokes the method compare two different keys. This is a straightforward modification to our sorts. And then exchange of course rather doing comparable has to use object. So with these straightforward changes at the comparator as argument to the sort and to less and make array to be sorted array of objects, it's easy to convert any of our implementations to support comparators. To implement a comparator you can use this code as a model. I won't go through it all in detail just to point out that this implements two different comparators as nested classes. Say, for this fictional class Student, that's got two instance variables - name and section. And the first one called by name implements a comparator for students and when you compare two students by name, it's going to use the string comparative method. If you're going to implement it compared to students by section, then it'll return just the difference of the sections which is my minus if less zero if equal then plus if greater. And this code is straight forward way to implement comparators that you can use as a model. If you need to be able to sort data on two different keys. So [cough] here is just an example of what happens if would those implemented comparators for that class student using the Java system sort, if you call array that sort with your a rray of students and you give it this by name comparator, it will put them in order alphabetical order by the name field. And if you give it to by section comparator, it will them in order by the second field very convenient for all kinds of data processing applications. And we came up with that before when we're talking about using a sort for the Graham scan. We needed to have a comparison for points that orders them by the polar angle they make, make with the given point p. That's what we needed for the Graham scan algorithm for the convex hull. Points are defined data type for geometric objects and so what we need is code that will compute the polar angle and use that as the basis for comparison. There's an easy way to do this based on CCW that is described here in this text. Most of the time all you need to do is do the CCW of the two points. You either have to check whether [cough] the, one of the points is above p and the other one is below. But otherwise, usually it's a CCW call in this code which again I won't go through in detail as an implementation of a comparator for two D points. It implements the compare method that takes two points as argument and with just a little bit of calculation is able to do the compare. So this code is the basis for applying the sort, system sort method or any sort method for the Graham scan for the convex hull that we did at the end of the last lecture. So that's the basis for the Graham scan method for the convex hull that we used at the last, at the end of the last lecture.
