====== The Comparable Interface for Sorting Objects ======

----


===== Objectives =====

  * Learn how to sort collections of objects (such as PlayList of Songs) by implementing the Comparable interface.

----

===== Comparable & Sorting =====

  * There are many sorting algorithms.
  * The simple-to-understand bubble sort is among the least efficient sorting algorithms.
  * More sophisticated algorithms will be covered in later courses.
  * Modern programming languages make it largely unnecessary for programmers to write their own sorting algorithms.
  * Java has java.util.Array.sort() and java.util.Collections.sort() that can be used to sort Arrays and ArrayLists of objects that have a natural sorting order.
    * Natural sorting order:  Numeric types (int, double), Strings

  * Problem:  Not all user-defined types have a natural sorting order
    * Solution: The Comparable and Comparator **interfaces** (We will cover the Comparable interface only.)
    * An object that implements the Comparable interface is capable of comparing itself with another object of the same class.
      * The object's class itself must implements the java.lang.Comparable interface in order to be able to compare its instances.

  * The compareTo() method of the Comparable interface:
    * java.lang.Comparable: int compareTo(Object obj1)
    * This method compares *this* object with the obj1 object. The returned int value has the following meanings:
<code>
         1. positive - this object is greater than obj1
         2. zero - this object equals to obj1
         3. negative - this object is less than obj1
</code>

==== Employee Class example ====

  * BlueJ project zip: ComparableEmployee

<code>
         // The original Employee class:
         public class Employee {
             private int empId;
             private String name;
             private int age;

             public Employee(int empId, String name, int age) {
                 // set values of fields
             }
             // getters & setters
         }
</code>

  * Next create a list of Employees.
  * Employees are added to an ArrayList without any specific order in the following class.

<code>
         import java.util.*;

         public class Util {
             
             public static ArrayList<Employee> getEmployees() {
                 
                 ArrayList<Employee> col = new ArrayList<Employee>();
                 
                 col.add(new Employee(5, "Frank", 28));
                 col.add(new Employee(1, "Jorge", 19));
                 col.add(new Employee(6, "Bill", 34));
                 col.add(new Employee(3, "Michel", 10));
                 col.add(new Employee(7, "Simpson", 8));
                 col.add(new Employee(4, "Clerk",16 ));
                 col.add(new Employee(8, "Lee", 40));
                 col.add(new Employee(2, "Mark", 30));
                 
                 return col;
             }
         }
</code>

  * Sorting in natural ordering:
  * Employee's natural ordering would be done according to the employee id.
    * For that, above Employee class must be altered to add the comparing ability as follows:

<code>
         public class Employee implements Comparable<Employee> {
             private int empId;
             private String name;
             private int age;
             
             /**
              * Compare a given Employee with this object.
              * If employee id of this object is 
              * greater than the received object,
              * then this object is greater than the other.
              */

             public int compareTo(Employee o) {
                 return this.empId - o.empId ;
             }

             // ....
         }
</code>

  * The new compareTo() method does the trick of implementing the natural ordering of the instances.
    * So if a collection of Employee objects is sorted using the Collections.sort(ArrayList) method, sorting happens according to the ordering done inside this method.

  * We'll write a class to test this natural ordering mechanism.
    * Following class uses the Collections.sort(ArrayList) method to sort the given list in natural order.

<code>
         import java.util.*;

         public class TestEmployeeSort {
             
             public static void main(String[] args) {     
                 ArrayList coll = Util.getEmployees();  // use static Util.getEmployees()
                 Collections.sort(coll); // sort method
                 printList(coll);
             }
             
             private static void printList(ArrayList<Employee> list) {
                 System.out.println("EmpId\tName\tAge");
                 for (Employee e: list) {
                     System.out.println(e.getEmpId() + "\t" + e.getName() + "\t" + e.getAge());
                 }
             }
         }
</code>

==== Song/Playlist Class example ====

  * When we last looked at the Song/PlayList example, we were unable to sort an ArrayList of Song objects because Song objects did not have a natural sorting order (were not comparable to each other).

  * By implementing the Comparable interface, we can make Songs comparable.
    * This will allow Songs to be sorted using the Java Collections.sort() method.

  * Basic example that sorts Songs by song name
    * See the comparablesong1 package in the Comparable project.

  * More advanced example in which the Songs can be sorted by other Song fields, such as artist, album and year
    * This version uses a //static Song.setSortBy()// method.
    * See the comparablesong2 package in the Comparable project.

----