Object-Oriented Programming - Lecture 7: Collections (continued) - Lê Hồng Phương

Lecture 7: Collections (continued) Lê Hồng Phương phuonglh@gmail.com Department of Mathematics, Mechanics and Informatics, Vietnam National University, Hanoi August, 2012 2 Content ● Collections ● Interfaces ● Implementations ● Algorithms ● Exercises August, 2012 3 Algorithms ● Polymorphic algorithms in the Java Collection Framework are reusable functionalities. ● All algorithms take the form of static methods. – First argument is the collection to operate ● Many algorithms operate on List instances. August, 2012 4 Algorithms ● Polymorphic algorithms in the Java Collection Framework are reusable functionalities. ● All algorithms take the form of static methods. – First argument is the collection to operate ● Many algorithms operate on List instances. August, 2012 6 Sorting ● The sort algorithm reorders a list so that its elements are in ascending order according to an ordering relationship. ● Natural ordering: – strings: alphabetic order – numbers: signed numerical order – characters: unsigned numerical order – dates: chronological order – objects: ? August, 2012 7 Sorting ● The Comparable interface specifies a natural ordering for a class. ● Objects of a class can be sorted automatically if that class implements the Comparable interface. ● Important Java platform classes implementing the Comparable interface includes – Boolean, Byte, Character, Short, Integer, Long, Float, Double, BigInteger, BigDouble. – String, Data, File, CollationKey August, 2012 8 Sorting ● If you try to sort a list whose elements do not implement Comparable, the sort method will throw a ClassCastException. ● The Comparable interface: public interface Comparable { public int compareTo(T o); } Returns a negative, zero or positive value depending on whether the receiving object is less that, equal or greater than the specified value. August, 2012 9 Sorting ● Example: Name.java, NameSort.java public class NameSort { public static void main(String[] args) { Name nameArray[] = { new Name("John", "Smith"), new Name("Karl", "Ng"), new Name("Jeff", "Smith"), new Name("Tom", "Rich") }; List names = Arrays.asList(nameArray); Collections.sort(names); System.out.println(names); } } August, 2012 10 Sorting ● If the objects that we need to sort do not implement Comparable, we may specify a Comparator to be used in the sorting. ● The Comparator interface: public interface Comparator { int compare(T o1, T o2); } August, 2012 11 Sorting ● Suppose we have an Employee class as follows: public class Employee implements Comparable { public Name name() { ... } public int number() { ... } public Date hireDate() { ... } ... } August, 2012 12 Sorting ● Naturally, we may sort a list of employees according to their name. ● What if the boss ask us to sort the list in orde of seniority? August, 2012 13 Sorting public class EmpSort { static final Comparator SENIORITY_ORDER = new Comparator() { public int compare(Employee e1, Employee e2) { int dateCmp = e2.hireDate().compareTo(e1.hireDate()); if (dateCmp != 0) return dateCmp; return (e1.number() < e2.number() ? -1 : (e1.number() == e2.number() ? 0 : 1)); } }; // Employee database static final Collection employees = ... ; public static void main(String[] args) { List e = new ArrayList(employees); Collections.sort(e, SENIORITY_ORDER); System.out.println(e); } } Why do we add this? August, 2012 14 Shuffling ● The shuffle algorithm does the opposite of what sort does. ● This algorithm reorders a list based on input from a source of randomness such that all possible permutations occur with equal likelihood. ● This algorithm is useful in implementing games of chance. August, 2012 15 Shuffling import java.util.*; public class Shuffle { public static void main(String[] args) { List list = new ArrayList(); for (String a : args) list.add(a); Collections.shuffle(list, new Random()); System.out.println(list); } } public class Shuffle { public static void main(String[] args) { List list = Arrays.asList(args); Collections.shuffle(list); System.out.println(list); } } Use a default source of randomness August, 2012 16 Routine data manipulation ● The Collections class provides 5 algorithms for doing routine data manipulation on List objects: – reverse – fill – copy – swap – addAll August, 2012 17 Searching ● The binarySearch algorithm searches for a specified element in a sorted list. ● If the element is found, its index is returned, otherwise a negative index is returned. ● Two forms of the algorithm: – Take a List and an element to search for – Take a List, an element to search for and a Comparator August, 2012 18 Composition ● Frequency algorithm – counts the number of times an element occurs in a collection ● Disjoint algorithm – determines whether two collections are disjoint August, 2012 19 Finding extreme values ● Extreme values: – Min of a collection – Max of a collection ● Two forms: – Take a Collection – Take a Collection and a Comparator ● You should check the JDK API Documentation to see the algorithms in detail. August, 2012 20 Exercises ● Exercise 1. Write a method for the Deck class (representing a deck of cards) which shuffles the deck. ● Exercise 2. Use the reverse algorithm to reverse the order of lines of a text file and write results to a file. ● Exercise 3. Design and implement a program which models a CD audio disk knowing that – Each disk contains a list of tracks (songs); – Each track has several states (artist, title, duration, kind, rating) and appropriate methods; – Ability to sort the tracks of a disk according to a specified state; – Ability to find the extreme value of duration and rating.