Transcript Ch. 22 Collections

Chapter 22 Java Collections
Framework
Chapter 11 Object-Oriented Design
Chapter 20 Lists, Stacks, Queues, Trees, and Heaps
Chapter 21 Generics
Chapter 22 Java Collections Framework
Chapter 19 Recursion
Chapter 23 Algorithm Efficiency and Sorting
1
Objectives










To describe the Java Collections Framework hierarchy (§22.1).
To use the Iterator interface to traverse a collection (§22.2).
To discover the Set interface, and know how and when to use
HashSet, LinkedHashSet, or TreeSet to store elements (§22.3).
To compare elements using the Comparator interface (§22.4).
To explore the List interface, and know how and when to use
ArrayList or LinkedList to store elements (§22.5).
To distinguish Vector and ArrayList, and know how to use Vector
and Stack (§22.5).
To simplify programming using JDK 1.5 generic types (§22.6).
To understand the differences between Collection and Map, and
know how and when to use HashMap and LinkedHashMap to
store values associated with keys (§22.7).
To use the static methods in the Collections class (§22.8).
To use the static methods in the Arrays classes (§22.9).
2
Java Collection Framework
hierarchy
A collection is a container object that
represents a group of objects, which are
referred to as elements.
The Java Collections Framework supports
three types of collections:
sets,
lists, and
maps.
3
Java Collection Framework
hierarchy, cont.
Set and List are subinterfaces of Collection.
SortedSet
TreeSet
Set
Collection
AbstractSet
HashSet
LinkedHashSet
Vector
Stack
AbstractCollection
List
AbstractList
ArrayList
AbstractSequentialList
Interfaces
Abstract Classes
LinkedList
Concrete Classes
4
Java Collection Framework
hierarchy, cont.
An instance of Map represents a group of objects, each of
which is associated with a key.
-- Use a key to get the object from a map, and
-- Must use a key to put the object into the map.
SortedMap
Map
TreeMap
AbstractMap
Interfaces
Abstract Classes
HashMap
LinkedHashMap
Concrete Classes
5
The Collection Interface
«interface»
java.util.Collection<E>
The Collection interface is the root interface for
manipulating a collection of objects.
+add(o: E): boolean
Adds a new element o to this collection.
+addAll(c: Collection<? extends E): boolean
Adds all the elements in the collection c to this collection.
+clear(): void
Removes all the elements from this collection.
+contains(o: Object): boolean
Returns true if this collection contains the element o.
+containsAll(c: Collection<?>):boolean
Returns true if this collection contains all the elements in c.
+equals(o: Object): boolean
Returns true if this collection is equal to another collection o.
+hashCode(): int
Returns the hash code for this collection.
+isEmpty(): boolean
Returns true if this collection contains no elements.
+iterator(): Iterator
Returns an iterator for the elements in this collection.
+remove(o: Object): boolean
Removes the element o from this collection.
+removeAll(c: Collection<?>): boolean
Removes all the elements in c from this collection.
+retainAll(c: Collection<?>): boolean
Retains the elements that are both in c and in this collection.
+size(): int
Returns the number of elements in this collection.
+toArray(): Object[]
Returns an array of Object for the elements in this collection.
«interface»
java.util.Iterator<E>
+hasNext(): boolean
Returns true if this iterator has more elements to traverse.
+next(): E
Returns the next element from this iterator.
+remove(): void
Removes the last element obtained using the next method.
6
The Set Interface
Set interface extends the Collection interface.
-- Set does not introduce new methods or constants
-- A Set instance must not contains duplicate
elements.
--Any concrete classes that implement Set must ensure
that no duplicate elements can be added to the set.
--
No two elements e1 and e2 can be in the set such that
e1.equals(e2) is true.
7
The Set Interface Hierarchy
«interface»
java.util.Set<E>
«interface»
java.util.AbstractSet<E>
java.util.SortedSet<E>
java.util.HashSet<E>
+HashSet()
+HashSet(c: Collection<? extends E>)
java.util.LinkedHashSet<E>
+LinkedHashSet()
+LinkedHashSet(c: Collection<?
extends E>)
+first(): E
Returns the first in this set.
+last(): E
Returns the last in this set.
+headSet(toElement: E): SortedSet<E>
headSet/tailSet returns a
portion of the set less
than toElement/greater
than fromElement.
+tailSet(fromElement: E): SortedSet<E>
java.util.TreeSet<E>
+TreeSet()
+TreeSet(c: Collection<? extends E>)
+TreeSet(c: Comparator<? super E>)
Creates a tree set with the
specified comparator.
8
The AbstractSet Class
AbstractSet class is a convenience class
- extends AbstractCollection and implements Set.
- Implements the equals() and hashCode() methods
- Hash code of a set == the sum of the hash code of
all the elements in the set.
- size() and iterator () methods are not implemented
- Hence AbstractSet is an abstract class.
9
The HashSet Class
HashSet class
- Concrete class that implements Set
-Set and Hash
- Use: to store duplicate-free elements
- For efficiency, objects added to a hash set
need to implement the hashCode method in a
manner that properly disperses the hash code.
10
Example: Using HashSet and Iterator
//creates a hash set filled with strings
– // Create a hash set
–Set set = new HashSet();
–// Text in String
– String text = "Have a good day. Have a good
class. " + "Have a good visit. Have fun!“;
–// Extract words from text
– StringTokenizer st = new StringTokenizer(text,
" .!?");
– while (st.hasMoreTokens())
–
set.add(st.nextToken());
–
11
See BJ_HashSet_Iterator: TestHashSet
// First way to display set
System.out.println(set);
/*Second way to display set: iterator to
traverse the elements in the set */
// Obtain an iterator for the hash set
Iterator iterator = set.iterator();
// Display the elements in the hash set
while (iterator.hasNext()) {
System.out.print(iterator.next() + " ");
}
12
Third way to display set
/** Display the elements in the hash set*/
for (Object element: set)
 System.out.print(element.toString() + " ");
System.out.println("\n");
13
// Initial string
String text = "Have a good day. Have a good class. "
+ "Have a good visit. Have fun!";
// Set action: drop duplicates
[Have, a, good, day, class, visit, fun]
// Program prints: See the hash effect
First way:
[a, class, visit, good, fun, day, Have]
Second way:
a class visit good fun day Have
Third way:
a class visit good fun day Have
14
JDK 1.5
Feature
TIP from Third way
You can simplify the code in iterator (second
way) using a JDK 1.5 enhanced for loop without
using an iterator, as follows:
for (Object element: set)
System.out.print(element.toString() + " ");
15
Example: Using LinkedHashSet
This example creates a hash set filled with
strings, and uses an iterator to traverse the
elements in the list.
Properties:
- Set – all elements unique
- Hash – fast access
- Linked – entry order preserved.
BJ_LinkedHashSet
16
Using LinkedHashSet
– entry order preserved.
// Create a linked hash set
Set set = new LinkedHashSet();
// Initial string
String text = "Have a good day. Have a good class. "
+ "Have a good visit. Have fun!";
// Set action – drop duplicates
[Have, a, good, day, class, visit, fun]
// Print
[Have, a, good, day, class, visit, fun]
Have a good day class visit fun
17
SortedSet Interface and TreeSet Class
SortedSet is a subinterface of Set
- elements in the set must be sorted.
TreeSet is a concrete class that implements
the SortedSet interface.
- Use an iterator to traverse the elements in
the sorted order.
- The elements can be sorted in two ways.
18
Two ways to sort elements in TreeSet Class
One way: Use the Comparable interface.
Second way: order by comparator.
- Specify a comparator for the elements in the set
-if the class for the elements does not implement
the Comparable interface, or
- you don’t want to use the compareTo method in
the class that implements the Comparable
interface.
19
Example: BJ_TestTreeSet
Using TreeSet to Sort Elements in a Set
1. Creates a hash set filled with strings
1.
Set<String> set = new HashSet<String>();
2. Creates a tree set for the same strings
2.
3.
TreeSet<String> treeSet
= new TreeSet<String>(set);
3. Sort the strings in the tree set using the compareTo
method in the Comparable interface
3. How? See the TreeSort constructors in
documentation (next slide).
20
TreeSet(Collection<? extends E> c)




TreeSet
public TreeSet(Collection<? extends E> c) Constructs a new tree set
containing the elements in the specified collection, sorted according to
the natural ordering of its elements. All elements inserted into the set
must implement the Comparable interface. Furthermore, all such
elements must be mutually comparable: e1.compareTo(e2) must not
throw a ClassCastException for any elements e1 and e2 in the set.
Parameters:c - collection whose elements will comprise the new set
Throws: ClassCastException - if the elements in c are not
Comparable, or are not mutually comparable NullPointerException - if
the specified collection is null
21
Output from TreeSort
// Initial string
String text = "Have a good day. Have a good
class. " + "Have a good visit. Have fun!";
// Set action – drop duplicates
[Have, a, good, day, class, visit, fun]
// TreeSort action implicitly
[Have, a, class, day, fun, good, visit]
Have a class day fun good visit
Have a class day fun good visit
22
BJ_TreeSetComparator
GeometricObjectComparator
1. Creates a tree set of geometric objects.
2. Sort the geometric objects using the
compare method in the Comparator
interface.
2
TreeSet(Comparator<? super E> comparator)
Constructs a new, empty tree set, sorted
according to the specified comparator.
23
TreeSet constructor with Comparator
parameter



TreeSet
public TreeSet(Comparator<? super E> comparator)
Constructs a new, empty tree set, sorted according to the
specified comparator. All elements inserted into the set
must be mutually comparable by the specified comparator:
comparator.compare(e1, e2) must not throw a
ClassCastException for any elements e1 and e2 in the set.
If the user attempts to add an element to the set that
violates this constraint, the add call will throw a
ClassCastException.
Parameters:comparator - the comparator that will be used
to order this set. If null, the natural ordering of the
elements will be used.
24
The Comparator Interface
In case:
- you want to insert elements of different types into a
tree set.
- The elements may not be instances of Comparable or
are not comparable.
You can define a comparator to compare these
elements.
create a class that implements the
java.util.Comparator interface. The Comparator
interface has two methods, compare and equals.
25
The Comparator Interface
public int compare(Object element1, Object element2)
Returns:
-a negative value if element1 is less than element2,
-a positive value if element1 is greater than element2,
-and zero if they are equal.
public boolean equals(Object element)
Returns true if the specified object is also a comparator
and imposes the same ordering as this comparator.
26
Example: Using Comparator to Sort
Elements in a Set
Write a program that demonstrates how to
sort elements in a tree set using the
Comparator interface. The example creates
a tree set of geometric objects. The
geometric objects are sorted using the
compare method in the Comparator
interface.
BJ_TestTreeSetComparator
27
The List Interface
A set stores non-duplicate elements.
Use a list to allow duplicate elements to be
stored in a collection
A list can:
- store duplicate elements,
- allow the user to specify where the element is
stored
- The user can access the element by index.
28
The List Interface without Generics, cont.
Collection
List
+add(index: int, element: Object) : boolean Adds a new element at the specified index
+addAll(index: int, collection: Collection) : Adds all elements in the collection to this list at the
boolean
specified index
+get(index: int) : Object
Returns the element in this list at the specified index
+indexOf(element: Object) : int
Returns the index of the first matching element
+lastIndexOf(element: Object) : int
Returns the index of the last matching element
+listIterator() : ListIterator
Returns the list iterator for the elements in this list
+listIterator(startIndex: int) : ListIterator
Returns the iterator for the elements from startIndex
+remove(index: int) : int
Removes the element at the specified index
+set(index: int, element: Object) : Object
Sets the element at the specified index
+subList(fromIndex: int, toIndex: int) : List Returns a sublist from fromIndex to toIndex
29
The List Iterator without Generics
Iterator
ListIterator
+add(o: Object) : void
Adds the specified object to the list
+hasPrevious() : boolean Returns true if this list iterator has more elements
when traversing backward.
+nextIndex() : int
Returns the index of the next element
+previousIndex() : int
Returns the index of the previosu element
+previous() : Object
Returns the previous element in this list iterator
+set(o: Object) : void
Replaces the last element returned by the previous
or next method with the specified element
30
List Interface with Generics
«interface»
java.util.Collection<E>
«interface»
java.util.List<E>
+add(index: int, element:E): boolean
Adds a new element at the specified index.
+addAll(index: int, c: Collection<? extends E>)
: boolean
Adds all the elements in c to this list at the specified
index.
+get(index: int): E
Returns the element in this list at the specified index.
+indexOf(element: Object): int
Returns the index of the first matching element.
+lastIndexOf(element: Object): int
Returns the index of the last matching element.
+listIterator(): ListIterator<E>
Returns the list iterator for the elements in this list.
+listIterator(startIndex: int): ListIterator<E>
Returns the iterator for the elements from startIndex.
+remove(index: int): E
Removes the element at the specified index.
+set(index: int, element: E): E
Sets the element at the specified index.
+subList(fromIndex: int, toIndex: int): List<E>
Returns a sublist from fromIndex to toIndex.
31
ListIterator Interface with Generics
«interface»
java.util.Iterator<E>
«interface»
java.util.ListIterator<E>
+add(o: E): void
Adds the specified object to the list.
+hasPrevious(): boolean
Returns true if this list iterator has more elements
when traversing backward.
+nextIndex(): int
Returns the index of the next element.
+previous(): E
Returns the previous element in this list iterator.
+previousIndex(): int
Returns the index of the previous element.
+set(o: E): void
Replaces the last element returned by the previous or
next method with the specified element.
32
ArrayList and LinkedList
ArrayList class and the LinkedList class:
-- concrete implementations of the List interface.
-- use depends on specific needs
ArrayList most efficient if:
- need to support random access through an index
- without inserting or removing elements from any place other than
the end,
LinkedList if:
- application requires insertion or deletion of elements from any
place in the list
33
List versus Array
A
list can grow or shrink dynamically.
 An array is fixed once it is created.
 If
your application does not require
insertion or deletion of elements, the most
efficient data structure is the array.
34
LinkedList without Generics
List
AbstractSequentialList
LinkedList
+addFirst(o: Object) : void Adds the object to the head of this list
+addLast(o: Object) : void Adds the object to the tail of this list
+getFirst() : Object
Returns the first element from this list
+getLast() : Object
Returns the last element from this list
+removeFirst() : Object
Returns and removes the first element from this list
+removeLast() : Object
Returns and removes the last element from this list
35
LinkedList with Generics
«interface»
java.util.Collection<E>
«interface»
java.util.List<E>
java.util.LinkedList<E>
+LinkedList()
Creates a default empty linked list.
+LinkedList(c: Collection<? extends E>) Creates a linked list from an existing collection.
+addFirst(o: E): void
Adds the object to the head of this list.
+addLast(o: E): void
Adds the object to the tail of this list.
+getFirst(): E
Returns the first element from this list.
+getLast(): E
Returns the last element from this list.
+removeFirst(): E
Returns and removes the first element from this list.
+removeLast(): E
Returns and removes the last element from this list.
36
ArrayList with Generics
«interface»
java.util.Collection<E>
«interface»
java.util.List<E>
java.util.ArrayList<E>
+ArrayList()
Creates an empty list with the default initial capacity.
+ArrayList(c: Collection<? extends E>)
Creates an array list from an existing collection.
+ArrayList(initialCapacity: int)
Creates an empty list with the specified initial capacity.
+trimToSize(): void
Trims the capacity of this ArrayList instance to be the
list's current size.
37
Example: Using ArrayList and LinkedList
- creates an array list filled with Integers
- inserts new elements into specified
locations in the list.
- creates a linked list from the array list ?!
- inserts Strings
- removes the elements from the list.
- traverses the list forward and backward.
BJ_Array_Linked_List
38
Performace Comparison of sets and lists
BJ_Set_List_Performance compares the
performance of:
1. HashSet
2. LinkedHashSet
3. TreeSet
4. ArrayList
5. LinkedList
39
The Vector and Stack Classes
- Java Collections Framework introduced with Java 2.
- Several data structures were supported prior to Java 2.
- -Vector class and the Stack class.
- - redesigned to fit into the Java Collections
Framework
- - old-style methods are retained for compatibility.
40
The Vector Class
- Java 2 Vector is the same as ArrayList
except that Vector contains the synchronized
methods for accessing and modifying the vector.
- None of the new collection data structures are
synchronized.
- If synchronization is required, you can use the
synchronized versions of the collection classes
- These classes are introduced later in the
section, “The Collections Class.”
41
The Vector Class, cont.
List
Vector
+addElement(o: Object): void
Appends the element to the end of this vector
+capacity(): int
Returns the current capacity of this vector
+copyInto(anArray: Object[]): void
Copies the elements in this vector to the array
+elementAt(index: int): Object
Returns the object at the specified index
+elements(): Enumeration
Returns an emulation of this vector
+ensureCapacity(): void
Increases the capacity of this vector
+firstElement(): Object
Returns the first element in this vector
+insertElementAt(o: Object, index: int): void
Inserts o to this vector at the specified index
+lastElement(): Object
Returns the last element in this vector
+removeAllElements() : void
Removes all the elements in this vector
+removeElement(o: Object) : boolean
Removes the first matching element in this vector
+removeElementAt(index: int) : void
Removes the element at the specified index
+setElementAt(o: Object, index: int) : void
Sets a new element at the specified index
+setSize(newSize: int) : void
Sets a new size in this vector
+trimToSize() : void
Trims the capacity of this vector to its size
42
Vector class with Generics
«interface»
java.util.List<E>
java.util.Vector<E>
+Vector()
Creates a default empty vector with initial capacity 10.
+Vector(c: Collection<? extends E>)
Creates a vector from an existing collection.
+Vector(initialCapacity: int)
Creates a vector with the specified initial capacity.
+Vector(initCapacity:int, capacityIncr: int)
Creates a vector with the specified initial capacity and increment.
+addElement(o: E): void
Appends the element to the end of this vector.
+capacity(): int
Returns the current capacity of this vector.
+copyInto(anArray: Object[]): void
Copies the elements in this vector to the array.
+elementAt(index: int): E
Returns the object at the specified index.
+elements(): Enumeration<E>
Returns an enumeration of this vector.
+ensureCapacity(): void
Increases the capacity of this vector.
+firstElement(): E
Returns the first element in this vector.
+insertElementAt(o: E, index: int): void
Inserts o to this vector at the specified index.
+lastElement(): E
Returns the last element in this vector.
+removeAllElements(): void
Removes all the elements in this vector.
+removeElement(o: Object): boolean
Removes the first matching element in this vector.
+removeElementAt(index: int): void
Removes the element at the specified index.
+setElementAt(o: E, index: int): void
Sets a new element at the specified index.
+setSize(newSize: int): void
Sets a new size in this vector.
+trimToSize(): void
Trims the capacity of this vector to its size.
43
The Stack Class without generics
Vector
Stack
The Stack class represents a last-in-firstout stack of objects. The elements are
accessed only from the top of the stack.
You can retrieve, insert, or remove an
element from the top of the stack.
+empty(): boolean
Returns true if this stack is empty
+peek(): Object
Returns the top element in this stack
+pop(): Object
Returns and removes the top element in this stack
+push(o: Object) : Object Adds a new element to the top of this stack
+search(o: Object) : int
Returns the position of the specified element in this stack
44
Stack class with generics
java.util.Vector<E>
java.util.Stack<E>
+Stack()
Creates an empty stack.
+empty(): boolean
Returns true if this stack is empty.
+peek(): E
Returns the top element in this stack.
+pop(): E
Returns and removes the top element in this stack.
+push(o: E) : E
Adds a new element to the top of this stack.
+search(o: Object) : int
Returns the position of the specified element in this stack.
45
Example: Using the Vector Class
Listing 4.11, PrimeNumber.java, determines whether a
number n is prime by checking whether 2, 3, 4, 5, 6, ..., n/2
is a divisor. If a divisor is found, n is not prime.
A more efficient approach to determine whether n is prime
is to check if any of the prime numbers less than or equal
to √n can divide n evenly. If not, n is prime.
Write a program that finds all the prime numbers less than
250.
46
Example: Using the Vector Class,
cont.
The program stores the prime numbers in a vector.
Initially, the vector is empty. For n = 2, 3, 4, 5, ...,
250, the program determines whether n is prime by
checking if any prime number less than or equal to
√n in the vector is a divisor for n. If not, n is prime
and add n to the vector. The program that uses a
vector is given below.
BJ_PrimeFactor_Vector
47
Example: Using the Stack Class
Write a program that reads a positive integer and
displays all its distinct prime factors in decreasing
order. For example, if the input integer is 6, its
distinct prime factors displayed are 3, 2; if the input
integer is 12, the distinct prime factors are also 3
and 2.
48
Example: Using the Stack Class,
cont.
The program uses a stack to store all the distinct
prime factors. Initially, the stack is empty. To find
all the distinct prime factors for an integer n, use
the following algorithm:
BJ_PrimeFactor_Stack
49
The Map Interface
The Map interface maps keys to the elements.
- Keys are like indexes.
- In List, the indexes are integer.
- In Map, the keys can be any objects.
Search keys
Corresponding values
Entry
…
.
.
50
The Map Interface UML Diagram
With Generics
java.util.Map<K, V>
+clear(): void
Removes all mappings from this map.
+containsKey(key: Object): boolean
Returns true if this map contains a mapping for the
specified key.
+containsValue(value: Object): boolean Returns true if this map maps one or more keys to the
specified value.
+entrySet(): Set
Returns a set consisting of the entries in this map.
+get(key: Object): V
Returns the value for the specified key in this map.
+isEmpty(): boolean
Returns true if this map contains no mappings.
+keySet(): Set<K>
Returns a set consisting of the keys in this map.
+put(key: K, value: V): V
Puts a mapping in this map.
+putAll(m: Map): void
Adds all the mappings from m to this map.
+remove(key: Object): V
Removes the mapping for the specified key.
+size(): int
Returns the number of mappings in this map.
+values(): Collection<V>
Returns a collection consisting of the values in this map.
51
The Map Interface UML Diagram
Without Generics
Map
+clear(): void
Removes all mappings from this map
+containsKey(key: Object): boolean
Returns true if this map contains a mapping for the
specified key.
+containsValue(value: Object): boolean
Returns true if this map maps one or more keys to
the specified value.
+entrySet(): Set
Returns a set consisting of the entries in this map
+get(key: Object): Object
Returns the value for the specified key in this map
+isEmpty(): boolean
Returns true if this map contains no mappings
+keySet(): Set
Returns a set consisting of the keys in this map
+put(key: Object, value: Object): Object
Puts a mapping in this map
+putAll(m: Map): void
Adds all mappings from m to this map
+remove(key: Object): Object
Removes the mapping for the specified key
+size(): int
Returns the number of mappings in this map
+values(): Collection
Returns a collection consisting of values in this map
52
Concrete Map classes
«interface»
java.util.Map<K, V>
«interface»
java.util.AbstractMap<K, V>
java.util.SortedMap<K, V>
+firstKey(): K
java.util.HashMap<K, V>
+HashMap()
+HashMap(m: Map)
+lastKey(): K
+comparator(): Comparator<? super K>)
+headMap(toKey: K): SortedMap
+tailMap(fromKey: K): SortedMap
java.util.LinkedHashMap<K, V>
+LinkedHashMap()
java.util.TreeMap<K, V>
+LinkedHashMap(m: Map)
+TreeMap()
+LinkedHashMap(initialCapacity: int,
loadFactor: float, accessOrder: boolean)
+TreeMap(m: Map)
+TreeMap(c: Comparator<? super K>)
53
HashMap and TreeMap
2 concrete implementations of the Map
interface: HashMap and TreeMap classes
HashMap class is efficient for locating a
value, inserting a mapping, and deleting a
mapping.
TreeMap class, implementing SortedMap, is
efficient for traversing the keys in a sorted
order.
54
LinkedHashMap
LinkedHashMap
- introduced in JDK 1.4.
- It extends HashMap with a linked list implementation
that supports an ordering of the entries in the map.
Entries in a HashMap are not ordered
Entries in a LinkedHashMap can be retrieved in some order
55
LinkedHashMap
Two orders to retrieve entries in a LinkedHashMap
- the insertion order
- or (access order) from least recently accessed to most
recently
-How?
The no-arg constructor constructs a LinkedHashMap
with the insertion order.
To construct a LinkedHashMap with the access order,
use the LinkedHashMap(int initialCapacity, float
loadFactor, boolean accessOrder).
56
Example: Using HashMap and TreeMap
-Creates a hash map that maps borrowers to
mortgages.
- Creates a hash map with the borrower’s
name as its key and mortgage as its value.
- Creates a tree map from the hash map
- Displays the mappings in ascending
order of the keys.
BJ_TestMap
BJ_TestMap_Generics
57
58
Map Examples
 BJ_TreeMap
does not apply Generics
– <Name, Loan> pair
 BJ_TreeMap_Generics
applies Generics
– <String, Integer>
 BJ_TreeMap_Generics_2
applies Generics
– <String, Loan>
59
Example: Counting the
Occurrences of Words in a Text
- Counts the occurrences of words in a text and displays the
words and their occurrences in ascending order of the words.
-Uses a hash map to store <word, count>
- For each word, check whether it is already a key in the map.
If not, add the key and value 1 to the map.
- Otherwise, increase the value for the word (key) by 1 in the
map.
- To sort the map, convert it to a tree map.
BJ_CountOccurrenceOfWords
60
The Collections Class
The Collections class contains
• various static methods for operating on collections
•maps, for creating synchronized collection classes, and
• for creating read-only collection classes.
61
The Collections Class UML Diagram
java.util.Collections
List
+sort(list: List): void
Sorts the specified list.
+sort(list: List, c: Comparator): void
Sorts the specified list with the comparator.
+binarySearch(list: List, key: Object): int
Searches the key in the sorted list using binary search.
+binarySearch(list: List, key: Object, c:
Comparator): int
Searches the key in the sorted list using binary search
with the comparator.
+reverse(list: List): void
Reverses the specified list.
+reverseOrder(): Comparator
Returns a comparator with the reverse ordering.
+shuffle(list: List): void
Shuffles the specified list randomly.
+shuffle(list: List): void
Shuffles the specified list with a random object.
+copy(des: List, src: List): void
Copies from the source list to the destination list.
+nCopies(n: int, o: Object): List
Returns a list consisting of n copies of the object.
+fill(list: List, o: Object): void
Fills the list with the object.
+max(c: Collection): Object
Returns the max object in the collection.
+max(c: Collection, c: Comparator): Object Returns the max object using the comparator.
+min(c: Collection): Object
Collection
Returns the min object in the collection.
+min(c: Collection, c: Comparator): Object Returns the min object using the comparator.
+disjoint(c1: Collection, c2: Collection):
boolean
Returns true if c1 and c2 have no elements in common.
+frequency(c: Collection, o: Object): int
Returns the number of occurrences of the specified
element in the collection.
62
Example: Using the Collections
Class
This example demonstrates using the methods
in the Collections class. The example creates
a list, sorts it, and searches for an element.
The example wraps the list into a
synchronized and read-only list.
BJ_TestCollections
63
The Arrays Class
The Arrays class contains:
• various static methods for sorting
•searching arrays,
•for comparing arrays,
•and for filling array elements.
•It also contains a method for converting an array to a
list.
64
The Arrays Class UML Diagram
Arrays
+asList(a: Object[]): List
Returns a list from an array of objects
Overloaded binarySearch method for byte, char,
short, int, long, float, double, and Object.
Overloaded binary search method to search a key
in the array of byte, char, short, int, long, float,
double, and Object
+binarySearch(a: xType[], key: xType): int
Overloaded equals method for boolean, byte,
char, short, int, long, float, double, and Object.
+equals(a: xType[], a2: xType[]): boolean
Overloaded fill method for boolean char, byte,
short, int, long, float, double, and Object.
+fill(a: xType[], val: xType): void
Overloaded equals method that returns true if a is
equal to a2 for a and a2 of the boolean, byte, char,
short, int, long, float, and Object type
Overloaded fill method to fill in the specified
value into the array of the boolean, byte, char,
short, int, long, float, and Object type
+fill(a: xType[], fromIndex: int, toIndex: xType,
val: xType): void
Overloaded sort method for char, byte, short, int,
long, float, double, and Object.
+sort(a: xType[]): void
Overloaded sort method to sort the specified array
of the char, byte, short, int, long, float, double,
and Object type
+sort(a: xType[], fromIndex: int, toIndex: int):
void
65
Example: Using the Arrays Class
This example demonstrates using the methods
in the Arrays class:
- Creates an array of int values
- fills part of the array with 50,
- sorts it,
- searches for an element, and
- compares the array with another array.
BJ_TestArrays
66