Transcript Problem Solving 2 Abstract Classes, Interfaces and Exception

Problem Solving 5
Using Java API for Searching and
Sorting Applications
ICS-201 Introduction to Computing II
Semester 071
Searching Algorithm: Binary Search

Java provides two binary search (02) methods:
–
Arrays.binarySearch (for an array)
–
Collections.binarySearch (for a List)
–
Note that the values in the array / list are in sorted order. If
they are not, binarySearch() method is not guaranteed
to work properly.
Searching Algorithm: Binary Search (Cont’d)
Searching Algorithm: Binary Search (Cont’d)

Using Arrays.binarySearch():
int[] numbers = {-3, 2, 8, 12, 17, 29, 44, 79};
int index = Arrays.binarySearch(numbers, 29);
System.out.println("29 is found at index " +
index);
Searching Algorithm: Binary Search (Cont’d)

Using Collections.binarySearch (for a List)
// binary search on ArrayList with the same
values:
int index = Collections.binarySearch(list, 29);
System.out.println("29 is found at index " +
index);
Sorting Algorithms: Merge Sort Algorithm

Java provides two sorting methods:
–
Arrays.sort() (for an array)
Arrays.sort(strings);
–
Collections.sort() (for a List)
Sorting Algorithms: Merge Sort Algorithm (Cont’d)
Sorting Algorithms: Merge Sort Algorithm (Cont’d)

Using Arrays.sort()
// demonstrate the Arrays.sort method
String[] strings = {"c", "b", "g", "h", "d", "f", "e", "a"};
// Printing the strings before sorting….
System.out.println(Arrays.toString(strings));
Arrays.sort(strings);
// Printing the strings after sorting….
System.out.println(Arrays.toString(strings));
–
Output:
[c, b, g, h, d, f, e, a]
[a, b, c, d, e, f, g, h]
Sorting User-Defined Types

Let’s assume we have an array of Student type
objects that we want to sort. The type Student is
class Student {
defined as follows:
private int id;
public Student(int id) {
this.id = id;
}
public int getId() {
return id;
}
// other code follows…
}
Sorting User-Defined Types (Cont’d)
public class TestSort {
public static void main(String[] args) {
Student[] students = new Student[5];
students[0] = new Student(555555);
students[1] = new Student(444444);
students[2] = new Student(333333);
students[3] = new Student(111111);
students[4] = new Student(222222);
System.out.println(Arrays.toString(students));
Arrays.sort(students); // Will this work?
System.out.println(Arrays.toString(students));
}
}
Sorting User-Defined Types (Cont’d)
The previous code compiles correctly. However, at runtime,
we get the following exception:
The method Arrays.sort() assumes that the class Student
implements the Comparable interface!  ClassCastException
Sorting User-Defined Types (Cont’d)

To fix this problem, let’s have the class Student
implements the Comparable interface as follows:
class Student implements
Comparable {
private int id;
public Student(int id) {
this.id = id;
}
public int getId() {
return id;
}
// other code follows…
// toString() method should be here
public int compareTo(Object o) {
if(o == null)
throw new NullPointerException();
else {
if(!(o instanceof Student))
throw new ClassCastException()
else {
Student st = (Student) o;
return id – st.getId();
}
}
} // End of compareTo() method
} // End of class Student
Sorting User-Defined Types

Now the code is running correctly and the output
should be:
Sorting User-Defined Types (Cont’d)

Now, let’s revisit the compareTo() method:
public int compareTo(Object o) {
if(o == null)
throw new NullPointerException();
else {
if(!(o instanceof Student))
throw new ClassCastException();
else {
Student st = (Student) o;
return id – st.getId();
}
Searching/Sorting based on id field!
}
} // End of compareTo() method
So to use Arrays.sort(), we have to restrict our comparison
key on a single key!
Sorting User-Defined Types (Cont’d)


To use different fields as keys for searching and
sorting purposes, we have to use the following
methods:
Java provides two sorting methods:
–
Arrays.sort(Object[], Comparator) (for an array)
using a specific Comparator object
–
Collections.sort(List, Comparator) (for a List)
using a specific Comparator object
Comparator Interface

The Comparator (java.util) interface defines the
following two methods:
–
int compare(Object o1, Object o2)
–
boolean equals(Object o)
Comparator Interface (Cont’d)

Example: Let’s define a Comparator class to compare two Student
objects based on the id field.
class ComparatorId implements Comparator {
public int compare(Object o1, Object o2) {
if(o1 == null | o2 == null)
throw new NullPointerException();
else {
if(!(o1 instanceof Student) | !(o2 instanceof Student))
throw new ClassCastException();
else {
Student st1 = (Student) o1;
Student st2 = (Student) o2;
return st1.getId() – st2.getId();
}
}
} } // End of ComparatorId class
Comparator Interface (Cont’d)


Important Note: The class ComparatorId implements the
Comparator interface and it overrides only one method and the
compiler does NOT complain!
Answer: ?????
Sorting Using a Comparator object

The code below illustrates the use of ComparatorId object for sorting
purposes:
import java.util.*;
public class TestSort2 {
public static void main(String[] args) {
Student[] students = new Student[5];
students[0] = new Student(555555);
students[1] = new Student(444444);
students[2] = new Student(333333);
students[3] = new Student(111111);
students[4] = new Student(222222);
System.out.println(Arrays.toString(students));
Arrays.sort(students, new ComparatorId());
System.out.println(Arrays.toString(students));
}
}
Comparator Interface (Cont’d)

Drill Exercise: Now try to define a Comparator class to compare two
Student objects based on the gpa field.
class ComparatorGpa implements Comparator {
public int compare(Object o1, Object o2) {
} // End of ComparatorGpa class