Scjp Boot Camp: (part Iii)

SCJP Boot Camp (Part III) SQL STAR INTERNATIONAL June, 2009

-- 6.3 -Serialization 3.3 Develop code that serializes and/or de-serializes objects using the following APIs from java.io: DataInputStream, DataOutputStream, FilelnputStream, FileOutputStream, ObjectInputStream, ObjectOutputStream, and Serializable

Serialized •

Make class serializeable • implements Serializable

•

Object Graphs • Serialization is all or nothing • Serialize an object, all the objects it refers to from instance variables are also serialized. • Any object in the graph is not serializable, an exception will be thrown by JVM

•

Output • FileOutputStream/ ObjectOutputStream • FileOutputStream fos = new FileOutputStream("test.tmp"); • ObjectOutputStream oos = new ObjectOutputStream(fos);

• writeObject(); close();

•

++ static and transient fields are NOT serialized • Transient: make serialization skip the transient variable. • Static variable: Static variables are not saved. One per class, so it will be current class has (do not belong to object)

•

JVM need the class of all objects in the graph 3

++ Deserialization •

Input • FileInputStream/ ObjectInputStream • readObject(); close(); • ++ Must cast the result (Object) to the real type

• •

When deserializing, the serializable class constructor does not run non-serializable class constructor WILL run • Every constructor ABOVE the first non-serializable class constructor will run.

• •

Transient / static : Transient/ static variable get default value: 0/null Variable: the inherited variable will be reset back to original definition. • Any instance variables you INHERIT from that superclass will be reset to the values they were given during the original construction of the object.

•

Static: Serialization is not for Static

4

serialVersionID Class change will/won’t have effection •

Fail • • • • • •

•

Delete an instance variable Change the declare type of an instance variable Change a non-transient instance variable to transient Move a class up or down the inheritance hierarchy Change a class from Serializable to non-serializable Change an instance variable to static

May still ok • • • •

•

Add new instance variable Add class to the inheritance tree Remove classes from the inheritance tree Change the access level of an instance variable has no effect on the ability of deserialization to assign a value • Change an instance variable from transient to non-transient JVM compare the deserialzing object serialVersionID with the class serialVersionID •

•

Manually put a serialVersionID into the class • •

•

false: exception static final long serialVersionID = xxx; Even the class has changed, it still works

Get a serialVersionID •

-Serialver ClassName

5

Deal the non-serializable object in

object graph • •

Make xxx as Transient: transient xxx; supplement serialization process by implementing the writeObject() and readObject() methods, while embedding calls to defaultWriteObject() and defaultReadQbject() • private void writeObject(ObjectOutputStream os) { • try { • os.defaultWriteObject(); • os.writeInt(xxxx.getCollarSize());

• } catch (Exception e) { • e.printStackTrace();

• } •

}

• private void readObject(ObjectlnputStream is) { • try { • is.defaultReadObject(); • theCollar = new Collar(is.readInt());

• } catch (Exception e) { • e.printStackTrace();

• } •

}

6

Object input/output •

java.lang.Object   java.io.OutputStream   java.io.ObjectOutputStream • private void writeObject (java.io.ObjectOutputStream stream) • throws IOException;

•

java.lang.Object   java.io.InputStream   java.io.ObjectInputStream • private void readObject (java.io.ObjectInputStream stream) • throws IOException, ClassNotFoundException;

•

Interface Externalizable extends Serializable{} • If the object supports Externalizable, the writeExternal method is called. • If the object does not support Externalizable and does implement Serializable, the object is saved using 7 ObjectOutputStream.

Data input/output •

java.lang.Object   java.io.OutputStream   java.io.FilterOutputStream   java.io.DataOutputStream

•

java.lang.Object   java.io.InputStream   java.io.FilterInputStream   java.io.DataInputStream

•

FileInputStream fis = new FileInputStream("test.txt"); DataInputStream dis = new DataInputStream(fis); boolean value = dis.readBoolean();

•

public final int readInt() throws IOException

•

public final void writeInt(int v) throws IOException

• •

8

File input/output •

java.lang.Object  java.io.OutputStream java.io.FileOutputStream

•

java.lang.Object  java.io.InputStream  java.io.FileInputStream

• •

public int read() throws IOException public void write(int b) throws IOException 9

-- 6.4 -Dates, Numbers, and Currency 3.4 Use standard J2SE APIs in the java.text package to correctly format or parse dates, numbers and currency values for a specific locale; and, given a scenario, determine the appropriate methods to use if you want to use the default locale or a specific locale. Describe the purpose and use of the java.util.Locale class.

java.util •

java.util.Date • can use it to bridge between the Calendar and DateFormat class. • A Date is stored as a long, the number of milliseconds since January 1, 1970. • An instance of Date represents a mutable date and time, to a millisecond.

•

java.util.Calendar • provides a huge variety of methods that help you convert and manipulate dates and times.

•

Java.util.Locale • used in conjunction with DateFormat and NumberFormat to format dates, numbers and currency for specific locales. 11

java.text •

java.text.DateFormat • Used to format dates not only providing various styles such as "01/01/70" or "January 1, 1970," but also to format dates for numerous locales around the world.

•

Java.text.NumberFormat • used to format numbers and currencies for locales around the world.

•

++ Exam Watch: • Don’t forget import both java.util.*; and java.text.*;

12

Date Class •

java.lang.Object  java.util.Date

•

use it as a temporary bridge to format a Calendar object using the DateFormat class • Current date: Date now = new Date(); • Get its value: String s = d.toString(); • setTime() and getTime() use millisecond scale 13

Calendar Class •

java.lang.Object  java.util.Calendar

• •

Is an abstract class make date manipulation easy • Calendar cal = • ++ Calendar.getInstance(); • Calendar.getInstance(Locale);

• Manipulation • ++ roll() is different from add(): roll() the larger part of Date won’t get change. • c.add(Calendar.HOUR, -4); • c.add(Calendar.YEAR, 2); • c.add(Calendar.DAY_OF_WEEK, -2); 14

Locale Class •

java.lang.Object   java.util.Locale

• •

Is an abstract class a specific geographical, political, or cultural region • • • •

•

Locale.getDefault(); new Locale(String language); new Locale(String language, String country); String s = DateFormat .format(d1);

represents an ISO 639 Language Code • both DateFormat and NumberFormat objects can have their locales set only at the time of instantiation.

• • •

getDisplayCountry () getDisplayLanguage() getDisplayName() 15

DateFormat Class •

java.lang.Object  java.text.Format  java.text.DateFormat

•

Is an abstract class • ++ DateFormat.getInstance(); • DateFormat.getDateInstance(); • DateFormat.getDateInstance(style); • getDateInstance(DateFormat.SHORT/MEDIUM/LONG); • getDateInstance(DateFormat.FULL);

• DateFormat.getDateInstance(style, Locale); •

++ parse() must try/catch • takes a String formatted in the style of the DateFormat instance being used, and converts the String into a Date object. • throw a ParseException (checked exception) 16

NumberFormat Class •

java.lang.Object  java.text.Format  java.text.NumberFormat

•

Is an abstract class • • • •

•

NumberFormat.getInstance() / (Locale) NumberFormat.getNumberInstance() / (Locale) NumberFormat.getCurrencyInstance() / (Locale) NumberFormat.getPercentInstance() / (Locale)

++ parse(); must try/catch • Only return the integer part of String formatted as float-point numbers • setParseIntegerOnly();  true will show the float part

• •

• throw a ParseException • For the currency, should add corresponding symbol: $ getMaximumFractionDigits(); setMaximumFractionDigits();

17

Examples •

(1) • • • • •

•

Calendar c = Calendar.getInstance(); Locale loc = new Locale(...); Date d = c.getTime(); DateFormat df = DateFormat.getDateInstance (style, loc); String s = df.format(d);

(2) • • • • •

Locale loc = new Locale(...); NumberFormat nf = NumberFormat.getInstance(loc); -orNumberFormat nf = NumberFormat.getCurrencyInstance(loc); String s = nf.format(someNumber);

18

-- 6.5 -Parsing, Tokenizing, & Formatting 3.5 Write code that uses standard J2SE APIs in the java.util and java.util.regex packages to format or parse strings or streams. For strings, write code that uses the Pattern and Matcher classes and the String. split method. Recognize and use regular expression patterns for matching (limited to: .(dot), *(star), +(plus), ?, \d, \s, \w, [],() ). The use of *, + , and ? will be limited to greedy quantifiers, and the parenthesis operator will only be used as a grouping mechanism, not for capturing content during matching. For streams, write code using the Formatter and Scanner classes and the PrintWriter. format/printf methods. Recognize and use formatting parameters (limited to: %b, %c, %d, %f, %s) in format Strings.

Basic concepts Finding stuff • use the java.util.regex.Pattern , java.util.regex.Matcher, and java.util.Scanner classes to help us find stuff. •

Tokenizing stuff • basics of using the String.split() method and the java.util.Scanner class, to tokenize your data.

•

Formatting stuff • java.util.Formatter class and to the printf() and format() methods.

20

Package java.util.regex •

Package java.util.regex • java.lang.Object  java.util.regex.Matcher

• java.lang.Object java.util.regex.Pattern •

Statement: • Pattern p = Pattern.compile ("a*b"); • Matcher m = p.matcher("aaaaab"); • boolean b = m.matches();  • boolean b = Pattern.matches("a*b", "aaaaab");

•

++ once a source’s character has been used in match, it cannot be reused.

21

Character classes (1) •

Character classes • • • • • • •

•

[abc] a, b, or c (simple class) [^abc] Any character except a, b, or c (negation) [a-zA-Z] a through z or A through Z, inclusive (range) [a-d[m-p]] a through d, or m through p: [a-dm-p] (union) [a-z&&[def]] d, e, or f (intersection) [a-z&&[^bc]] a through z, except for b and c: [ad-z] (subtraction) [a-z&&[^m-p]] a through z, and not m through p: [a-lqz](subtraction)

Predefined character classes • • • • • • •

. Any character (may or may not match line terminators) \d A digit: [0-9] \D A non-digit: [^0-9] \s A whitespace character: [ \t\n\x0B\f\r] \S A non-whitespace character: [^\s] \w A word character: [a-zA-Z_0-9] \W A non-word character: [^\w]

22

Character classes (2) • • • • • •

"+" represents "one or more" * Zero or more occurrences ? Zero or one occurrence ^ is the negation symbol "." (dot) means "any character can serve here Greedy quantifiers: • x? / x* / x+ / x(n) / x(n,) / x(n,m) • digest the whole inputted string first, then works backwards (Right to left )

•

Reluctant quantifiers: • x?? / x*? / x+? / x(n)? / x(n,)? / x(n,m)? • digest the first character and match (left to right )

•

Possessive quantifiers: • x?+ / x*+ / x++ / x(n)+ / x(n,)+ / x(n,m)+ • makes a Matcher digest the whole string and then stop 23

Pattern Class •

static Pattern compile (String regex) • Compiles the given regular expression into a pattern

•

Matcher matcher (CharSequence input) • Creates a matcher that will match the given input against this pattern

•

Must use: \\*, or \\d to get * and \d

•

++ public String[ ] split (CharSequence input, int limit) • limit parameter controls the number of times the pattern is applied • limit > 0, the pattern will be applied at most (limit - 1) times • limit < 0, the pattern will be applied as many times as

possible • limit = 0, the pattern will be applied as many times as possible, the array can have any length, and trailing empty strings will be discarded •

public String[ ] split (CharSequence input)   limit = 0

24

Matcher Class •

boolean matches() • attempts to match the entire input sequence against the pattern.

•

boolean lookingAt() • attempts to match the input sequence, starting at the beginning, against the pattern.

•

boolean Find() • scans the input sequence looking for the next sequence that matches the pattern.

•

String group() • Returns the input subsequence matched by the previous match.

•

int groupCount() • the number of capturing groups

•

int start()/ end() • the start/end index of the subsequence captured

• • •

StringBuffer appendTail(StringBuffer sb) Matcher appendReplacement(StringBuffer sb, String str) String replaceAll(String replacement) 25

Scanner Class (1) •

java.lang.Object java.util.Scanner

• •

•

Scanners can be constructed using files, streams, or Strings as a source doesn't provide location information or search and replace functionality • Scanner sc = new Scanner(System.in); • int i = sc.nextInt(); • sc.close()

The default delimiter is whitespace • reset() • public Scanner useDelimiter(String pattern)

26

Scanner Class (2) • •

public boolean hasNext() public String next() • The type must match, otherwise throw java.util.InputMismatchException

•

converted to their appropriate primitive types automatically. • xxx nextXXX() • xxx nextXXX(int radix)

•

Details: • • • •

Scanner's default delimiter is whitespace next() move to next  hasnext() doesn’t move for every primitive type except char nextXxx(): nextLong()) hasNextXxx(): hasNextDouble() 27

Formatter Class (1) •

java.lang.Object  java.util.Formatter

•

java.util.Formatter class do the heavy formatting work

•

%b • If the argument arg is null, then the result is "false". If arg is a boolean or Boolean, then the result is the string returned by String.valueOf(). Otherwise, the result is "true".

•

%c • The result is a Unicode character.

•

%d • The result is formatted as a decimal integer.

•

%f • The result is formatted as a decimal number.

•

%s • If the argument arg is null, then the result is "null". If arg implements Formattable, then arg.formatTo is invoked. Otherwise, the result is obtained by invoking arg.toString(). 28

Formatter Class (2) •

%[arg_index$] [flags] [width] [.precision] conversion char • arg_index: An integer followed directly by a $, argument position. • flags • "-" Left justify this argument / " + " Include a sign (+ or -) with this argument • "0" Pad this argument with zeroes / "," Use locale-specific grouping separators (i.e., the comma in 123,456) • "(" Enclose negative numbers in parentheses

• Width: • indicates the minimum number of characters to print.

• Precision: • indicates the number of digits to print after the decimal point.

• conversion • b boolean / c char / d integer / f floating point / s string

• Mismatch conversion character and argument, you'll get a runtime exception:

29

Formatter Class- examples •

out.printf("%8d", 10.10);   wrong, • java.util.IllegalFormatConversionException • out.printf("%8d", (int)10.10);

•

out.printf("%8.3f", 10);   wrong, • java.util.IllegalFormatConversionException

•

out.printf("|%8.3f| %n", 2005.1234);   2005.123

•

out.printf("|%8.3s|", true);   tru

•

character ('c') and integral ('d') argument types CANNOT use precision • java.util.IllegalFormatPrecisionException 30

-- 7.1 -Overriding hashCode() and equals() 6.2 Distinguish between correct and incorrect overrides of corresponding hashCode and equals methods, and explain the difference between == and the equals method.

Object methods… •

Public String toString() • Returns a "text representation" of the object. • Can override to explain the class. • spill-your-guts method

•

void finalize() • Called by garbage collector when the garbage collector sees that the object cannot be referenced.

•

final void notify() • Wakes up a thread that is waiting for this object's lock.

•

final void notifyAll () • Wakes up all threads that are waiting for this object's lock.

•

final void wait() • Pauses the current thread to wait until another thread calls notify() or notifyAll() on this subject.

•

++ String and wrappers override euqals() and make good hashing keys

32

public boolean equals (Object obj) • • • •

Decides whether two objects are meaningfully equivalent. equals(null) should always return false use the equals() to know if the objects themselves (not the references) are equal Overriding equals() • ++ Must be public and take Object as the input

• public boolean equals(Object o) { • if ((o instanceof XX) // 1, instanceof test • && (((XX)o).getValue() == this. Value)) { • // 2, compare the attributes care about • return true;

• } else { return false; }

• }

33

public int hashcode() (1) • •

•

•

used to increase the performance of large collections of data. if you override equals(), you MUST override hashcode() as well. Otherwise the equals() is unuseful Hashing retrieval is a two-step process. • Find the right bucket (using hashcode()) • Search the bucket for the right element (using equals()). Returns a hashcode int value for an object, so that the object can be used in Collection classes that use hashing, including Hashtable, HashMap, and HashSet. 34

public int hashcode() (2) •

x.equals(y) == true • Require: x.hashCode() == y.hashCode()  mandatory

•

x.hashCode() == y.hashcode() • Allow: x.equals(y) == true

•

x.equals(y) == false • No hashCode() requirements

•

x.hashCode() != y.hashCode() • Require: x.equals(y) == false

•

 mandatory

Transient variables can really mess with your equals() and hashcode() implementations. • Keep variables non-transient • If they must be marked transient, don't use then to determine hashcodes or equality 35

++ == vs. equals() •

==: • for primitive: check the velue • for String: • 1.if see any new(means String s = new String("xxx"); -->check if they pointing to same object • 2.if see only ""(means String s = "xxx"; ) -->check the string content

• for Wrapper: • 1. same as String, see any new --> check if they pointing to same object • 2, if there is not, then tricky things coming: • 2.1, if it is byte, short, int and the value is <=127, -->check the value • 2.2, otherwise check the if they pointing to same object

•

equals(): • for general Object: • 1.must override it to compare the key attribute(s) of object; • 2,if collection is Hashxxx, you need override hashCode() too, otherwise equals won't effect

• for String and wrappers: • they have well overridden equals() and hashCode() 36

-- 7.2 -Collections 6.1 Given a design scenario, determine which collection classes and/or interfaces should be used to properly implement that design, including the use of the Comparable interface.

Basic concepts •

Basic operations of collection • • • • •

•

Add objects to the collection. Remove objects from the collection. Find out if an object (or group of objects) is in the collection. Retrieve an object from the collection (without removing it). Iterate through the collection, looking at each element (object) one after another.

++ Distinguish: • collection (lowercase c), which represents any of the data structures in which objects are stored and iterated over. • Collection (capital C), which is actually the java.util.Collection interface from which Set, List, and Queue extend. declarations of the methods common to most collections including add(), remove(), contains(), size(), and iterator(). • Collections (capital C and ends with s) is the java.util.Collections class that holds a pile of static utility methods for use with collections.

38

Interface & Classes •

Key interface • Collection / Set / SortedSet / List / Map / SortedMap / Queue

•

Key classes • Maps Things with a unique ID : HashMap Hashtable TreeMap LinkedHashMap • Sets Unique things : HashSet LinkedHashSet TreeSet • Lists Lists of things : ArrayList Vector LinkedList • Queues Things arranged by the order in which they are to be processed : PriorityQueue • Utilities : Collections Arrays

•

Sorted / Unsorted/ Ordered / Unordered • Ordered When a collection is ordered, it means you can iterate through the collection in a specific (not-random) order. • Sorted collection means that the order in the collection is determined according to some rule or rules, known as the sort order. 39

40

41

List Interface •

List cares about the index. • get(int index), indexOf(Object o), add(int index, Object obj)

•

ArrayList • As a growable array. • Ordered collection (by index), but not sorted.

•

Vector • A Vector is basically the same as an ArrayList, but Vector methods are synchronized for thread safety. • Vector is the only class other than ArrayList to implement RandomAccess.

•

++ LinkedList • Ordered by index position, like ArrayList, except that the elements are doubly-linked to one another. • Keep in mind that a LinkedList may iterate more slowly than an ArrayList, but it's a good choice when you need fast insertion and deletion. • As of Java 5, the LinkedList class has been enhanced to implement the java.util.Queue interface. Supports queue methods: peek(), poll(), and offer().

42

Set Interface • •

Set cares about uniqueness—it doesn't allow duplicates. HashSet • HashSet is an unsorted, unordered Set. • Use this class when you want a collection with no duplicates and you don't care about order when you iterate through it.

•

LinkedHashSet • LinkedHashSet is an ordered version of HashSet that maintains a doubly-linked List across all elements. • a LinkedHashSet lets you iterate through the elements in the order in which they were inserted.

•

TreeSet • TreeSet is one of two sorted collections (the other being TreeMap). • Uses a Red-Black tree structure (but you knew that), and guarantees that the elements will be in ascending order, according to natural order. • Optionally, you can construct a TreeSet with a constructor that lets you give the collection your own rules for what the order should be by using a Comparable or Comparator. • Implements NavigableSet 43

Map Interface •

Map cares about unique identifiers. • map a unique key (the ID) to a specific value • rely on the equals() method to determine whether two keys are the same or different.

•

HashMap • an unsorted, unordered Map. • other maps add a little more overhead.

•

Hashtable . • Hashtable is the synchronized counterpart to HashMap. • ++ HashMap lets you have null values as well as one null key, a Hashtable doesn't let you have anything that's null.

•

LinkedHashMap • Like its Set counterpart, LinkedHashSet, • the LinkedHash-Map collection maintains insertion order (or, optionally, access order).

•

TreeMap • • • •

a TreeMap is a sorted Map. Lets you define a custom sort order Implements NavigableMap ++ For Object must override equals(), hashCode()

44

Queue Interface • •

Queues are typically thought of as FIFO (first-in, first-out). PriorityQueue • This class is new with Java 5. • Since the LinkedList class has been enhanced to implement the Queue interface, basic queues can be handled with a LinkedList. • The purpose of a PriorityQueue is to create a "priorityin, priority out" queue as opposed to a typical FIFO queue. • A PriorityQueue's elements are ordered either by natural ordering (in which case the elements that are sorted first will be accessed first) or according to a Comparator. In either case, the elements' ordering represents their relative priority. 45

-- 7.3 -Using the Collections Framework 6.5 Use capabilities in the java.util package to write code to manipulate a list by sorting, performing a binary search, or converting the list to an array. Use capabilities in the java.util package to write code to manipulate an array by sorting, performing a binary search, or converting the array to a list. Use the java.util. Comparator and java.lang.Comparable interfaces to affect the sorting of lists and arrays. Furthermore, recognize the effect of the "natural ordering" of primitive wrapper classes and java.lang. String on sorting.

ArrayList Basics • • •

Can grow dynamically. Provides more powerful insertion and search mechanisms than arrays. List<String> myList = new ArrayList<String>(); • add() / size() / contains() / remove()

•

Autoboxing with Collections in Java 5 • xxInt.add(42);

47

Collections.sort() •

ArrayList doesn't give you any way to sort its contents, but the java.util.Collections does

•

Collections.sort(List o) Collections.sort(List o, Comparator)

•

• Collections.sort(ArrayList<String>); • •

Sort take only lists of Comparable objects the elements inside must all be mutually comparable. In other words, if you have an Object [] and you put Cat and Dog objects into it, you ++ won't be able to sort it. In general, objects of different types should be considered NOT mutually comparable, unless specifically stated otherwise. 48

Arrays.sort() • • • • •

Arrays.sort(arrayToSort) Arrays.sort(arrayToSort, Comparator) Special: sort primitives always sort based on natural order Arrays.sort() and Collections.sort() are static methods alter the objects they are sorting, instead of returning a different sorted object. 49

Comparable Interface • • •

•

Public interface Comparable { • Int compareTo(T o); } Used by the Collections.sort() and java.utils.Arrays.sort() • ++ Implemented frequently in the API by: String, Wrapper classes, Date, Calendar… Must implement a single method, compareTo(). • int objOne.compareTo(objTwo) • Negative • Zero • Positive

•

If objOne < objTwo If objOne == objTwo If objOne > objTwo

must modify the class whose instances you want to sort. • class DVDInfo implements Comparable { • public int compareTo(DVDInfo d) { • return title.compareTo(d.getTitle());

• } •

• } Only one sort sequence can be created • Can not compare multiple attributes

50

Comparator interface •

public interface Comparator { • int compare (T o1, T o2);

• • •

} Many sort sequences can be created Build a class separate from the class whose instances you want to sort. • import java.util.*; • class GenreSort implements Comparator<XXX> { • public int compare(XXX one, XXX two) { • return one.getGenre().compareTo(two.getGenre());

• }

• } •

Must implement a single method, compare() • int compare(objone, objTwo)

•

Mean to be implemented to sort instances of thirdparty classes.

51

Searching Arrays and Collections (1) Searches are performed using the binarySearch() method. • Successful searches return the int index of the element being searched. • ++ Unsuccessful searches return an negative number, int index that represents the insertion point. •

• The insertion point is the place in the collection/array where the clement would be inserted to keep the collection/array properly sorted. • the first available insertion point is -1. Therefore, the actual insertion point is represented as (-(insertion point) -1). For instance, if the insertion point of a search is at element 2, the actual insertion point returned will be -3. 52

Searching Arrays and Collections (2) •

The collection/array being searched must be sorted before you can search it. • If you attempt to search an array or collection that has not already been sorted, the results of the search will not be predictable.

•

++ Must be searched in same comparator of sort() • If the collection/array you want to search was sorted in natural order, it must be searched in natural order. (This is accomplished by NOT sending a Comparator as an argument to the binarysearch() method.) • Arrays.binarysearch(arrayxxx,“xxx“, COMPARTOR));

• If the collection/array you want to search was sorted using a Comparator, it must be searched using the same Comparator, which is passed as the second argument to the binarysearch() method. • Arrays.binarysearch(arrayxxx,“xxx",classOfComparator));

•

++ Remember that Comparators cannot be used when searching arrays of primitives. (The order always be natural order)

53

++ Exam Watch

Searching Arrays and Collections •

Two common mistakes • Searching an array/collection that hasn’t been sorted • Using a comparator in just the sort or search, it will leads a incorrect answer (but not compile error or exception)

•

Be careful: use Comparator to sort, must use it to do the binarySearch() 54

Converting Arrays to Lists / List to Arrays •

List and Set classes have toArray() • returns a new Object array • uses the array you send it as the destination array

•

the Arrays class has asList(). • asList() makes array and the List become joined at the hip. • ++ actually still a Array, and cannot add any thing into it • ++ Update one of them, the other gets updated automatically. 55

Key Methods in java.util.Arrays •

static List asList(T[]) • Convert an array to a List, (and bind them).

• •

static int binarySearch(Object [], key) static int binarySearch(primitive [], key) • Search a sorted array for a given value, return an index or insertion point.

•

static int binarySearch(T[], key, Comparator) • Search a Comparator-sorted array for a value.

• •

static boolean equals(Object[], Object[] ) static boolean equals(primitive[], primitive[] ) • Compare two arrays to determine if their contents are equal.

• •

public static void sort(Object[] ) public static void sort(primitive[] ) • Sort the elements of an array by natural order.

•

public static void sort(T[], Comparator) • Sort the elements of an array using a Comparator. (primitive can not)

• •

public static String toString(Object[]) public static String toString(primitive[]) • Create a String containing the contents of an array.

56

Key Methods in java.util.Collections • •

static int binarySearch(List, key) static int binarySearch(List, key, Comparator) • Search a "sorted" List for a given value, return an index or insertion point

•

++ static void reverse(List) • Reverse the order of elements in a List.

• •

++ static Comparator reverseOder() ++ static Comparator reverseOder(Comparator) • Return a Comparator that sorts the reverse of the collection's current sort sequence

• •

static void sort(List) static void sort(List, Comparator) • Sort a List either by natural order or by a Comparator 57

Using Lists • •

Don’t forget List is an interface! Used to keep things in some kind of order • LinkedList to create a first-in, first-out queue • Natural order: spaces < characters, uppercase < lowercase

•

An Iterator is an object that's associated with a specific collection. • ++ Iterator<XXX> i = xxx.iterator(); • If Iterator i = xxx.iterator(), we need cast i  (xxx) i

• boolean hasNext() • Returns true if there is at least one more element in the collection being traversed. Invoking hasNext() ++ does NOT move you to the next element of the collection

• object next() • This method returns the next object in the collection, AND ++ moves forward to the element after the element just returned 58

Key Methods in List •

boolean add(element) boolean add(index, element)

•

boolean contains (object)

•

object get(index) ++ int indexOf(object)

•

•

• Get the location of an object in a List. • •

• • •

Iterator iterator() ++ remove(index) / remove(object) int size() object[] toArray() T[] toArray(T[]) • Return an array containing the elements of the collection.

59

Using Sets Used to keep things without any duplicates • HashSets tend to be very fast by using hashcodes. • Sets do not guarantee any ordering • Must use caution when using a TreeSet •

• whenever you want a collection to be sorted, its elements must be mutually comparable 60

Key Methods in Set •

boolean add(element) • add an element to a set that already exists, add() method will return false

• • • • • •

boolean contains (object) Iterator iterator() remove(object) int size() object[] toArray() T[] toArray(T[]) • Return an array containing the elements of the collection.

61

Using Maps •

++ Class that implements Map must override the hashCode() and equals() methods • Use the hashcode() method to find the correct bucket • Use the equals() method to find the object in the bucket • legal to use a class that doesn't override equals() and hashCode() as a key in a Map; your code will compile and run, you just won't find your stuff • ++ Enums, String already overrided equals() and hashcode().

• •

The more unique hashcodes a formula creates, the faster the retrieval will be. Map m = new HashMap(); • ++ public Object put(Object key, Object value) (not add()) • public Object get(Object key) 62

Key Methods in Map •

++ put(key, value) • Add a key/value pair to a Map.

•

boolean containsKey(object key) boolean containsValue(object value) object get(key) Set keyset() ++ remove(key)

• • • •

• Can not use value •

int size() 63

++ Navigating TreeSet •

Java 6 introduce two interfaces: • java.util.NavigableSet • java.util.NavigableMap

•

J5 J6 • treeset.headSet(xxx) + last  treeset.lower(xxx) • treeset.tailSet(xxx) + first  treeset.higher(xxx)

•

New methods • • • • •

lower(e)  < e – throw runtime exp. higher(e)  > e – throw runtime exp. floor(e)  <= e – throw runtime exp. ceiling(e)  >= e – throw runtime exp. pollFirst()  retrieve and remove first entry – non runtime exp, but first() throw

• pollLast()  retrieve and remove last entry – non runtime exp, but last() throw

• descendingSet()  NavigableSet in reverse order – non runtime exp

64

++ Navigating TreeMap •

New methods: Only in NavigatingMap • • • • •

lowerKey(key)  < key – throw runtime exp. higherKey(key)  > key – throw runtime exp floorkey(key)  <= key – throw runtime exp ceilingKey(e)  >= key – throw runtime exp pollFirstEntry()  retrieve and remove first keyvalue pair – non runtime exp , but firstKey() throw,

xxxEntry() have

• pollLastEntry ()  retrieve and remove last key-value pair – non runtime exp , but lastKey() throw,

xxxEntry() have

• descendingMap()  NavigableMap in reverse order – non runtime exp 65

++ Backed Collections •

TreeSet: • headSet(e, b) • subSet(e1, b, e2, b) • tailSet(e, b)

•

<e  >= e and < e  >= e

TreeMap: • headMap(key , b) • subMap(key1 , b, key2 , b) • tailMap(key , b)

• • •

 < key  >= key1 and < key2  >= key

If there is b(boolean flag), method returns NavigableXxx, otherwise returns SortedXxx Starting point always inclusive The copy (subXxx) changed the original(Xxx) also change • The important thing is: subXxx can not add/put new entry out of the range (from original) • If add/put something out of range, throw an exception • pollFirst(), pollLast()

66

Using the PriorityQueue •

PriorityQueue orders its elements using a user-defined priority /natural order • Not FIFO • can be ordered using a Comparator

•

Methods • peek() - the highest priority element in the queue without removing • poll() - poll() returns the highest priority element, AND removes • offer() - add elements (no add()) 67