Review Questions
15.16 Which statements about collections are true?
Select the two correct answers.
(a) Some operations on a collection may throw an UnsupportedOperationException.
(b) Methods calling optional operations in a collection must either catch an UnsupportedOperationException or declare it in their throws clause.
(c) A List can have duplicate elements.
(d) An ArrayList can only accommodate a fixed number of elements.
(e) The Collection interface contains a method named get.
15.17 What will be the result of attempting to compile and run the following program?
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.TreeSet;
public class Sets {
public static void main(String[] args) {
HashSet<Integer> set1 = new HashSet<Integer>();
addRange(set1, 1);
ArrayList<Integer> list1 = new ArrayList<Integer>();
addRange(list1, 2);
TreeSet<Integer> set2 = new TreeSet<Integer>();
addRange(set2, 3);
LinkedList<Integer> list2 = new LinkedList<Integer>();
addRange(list2, 5);
set1.removeAll(list1);
list1.addAll(set2);
list2.addAll(list1);
set1.removeAll(list2);
System.out.println(set1);
}
static void addRange(Collection<Integer> col, int step) {
for (int i = step*2; i<=25; i+=step)
col.add(i);
}
}
Select the one correct answer.
(a) The program will fail to compile, since operations are performed on incompatible collection implementations.
(b) The program will fail to compile, since the TreeSet referenced by set2 has not been given a Comparator to use when sorting its elements.
(c) The program will compile without error, but will throw an UnsupportedOperationException, when run.
(d) The program will compile without error and will print all primes below 25, when run.
15.18 Which of these methods are defined in the Collection<E> interface?
Select the three correct answers.
(a) add(E o)
(b) retainAll(Collection<?> c)
(c) get(int index)
(d) iterator()
(e) indexOf(Object o)
15.19 What will the following program print?
import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;
public class Iterate {
public static void main(String[] args) {
List<String> l = new ArrayList<String>();
l.add("A"); l.add("B"); l.add("C"); l.add("D"); l.add("E");
ListIterator<String> i = l.listIterator();
i.next(); i.next(); i.next(); i.next();
i.remove();
i.previous(); i.previous();
i.remove();
System.out.println(l);
}
}
Select the one correct answer.
(a) It will print [A, B, C, D, E].
(b) It will print [A, C, E].
(c) It will print [B, D, E].
(d) It will print [A, B, D].
(e) It will print [B, C, E].
(f) It will throw a NoSuchElementException.
15.20 Which sequence of digits will the following program print?
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class Lists {
public static void main(String[] args) {
List<String> list = new ArrayList<String>();
list.add("1");
list.add("2");
list.add(1, "3");
List<String> list2 = new LinkedList<String>(list);
list.addAll(list2);
list2 = list.subList(2, 5);
list2.clear();
System.out.println(list);
}
}
Select the one correct answer.
(a) [1, 3, 2]
(b) [1, 3, 3, 2]
(c) [1, 3, 2, 1, 3, 2]
(d) [3, 1, 2]
(e) [3, 1, 1, 2]
(f) None of the above.
15.21 Which of these methods from the Collection interface will return the value true if the collection was modified during the operation?
Select the two correct answers.
(a) contains()
(b) add()
(c) containsAll()
(d) retainAll()
(e) clear()
15.22 Which statements, when inserted independently at (1), will guarantee that the following program will print [1, 9]?
import java.util.*;
public class RightOne {
public static void main(String[] args) {
// (1) INSERT DECLARATION HERE.
collection.add(1); collection.add(9); collection.add(1);
System.out.println(collection);
}
}
Select the four correct answers.
(a) Collection<Integer> collection = new HashSet<Integer>();
(b) Set<Integer> collection = new HashSet<Integer>();
(c) HashSet<Integer> collection = new LinkedHashSet<Integer>();
(d) Set<Integer> collection = new LinkedHashSet<Integer>();
(e) Collection<Integer> collection = new TreeSet<Integer>();
(f) NavigableSet<Integer> collection = new TreeSet<Integer>();
15.23 What will the program print when it is compiled and run?
import static java.lang.System.out;
import java.util.Collections;
import java.util.NavigableSet;
import java.util.TreeSet;
public class RQ400_300 {
public static void main(String[] args) {
NavigableSet<String> strSetA = new TreeSet<String>();
Collections.addAll(strSetA, "set", "shell", "soap");
out.print(strSetA.ceiling("shell") + " ");
out.print(strSetA.floor("shell") + " ");
out.print(strSetA.higher("shell") + " ");
out.println(strSetA.lower("shell"));
}
}
Select the one correct answer.
(a) shell soap shell set
(b) soap set shell shell
(c) shell shell soap set
(d) set shell shell soap
15.24 Which statement, when inserted independently at (1), will result in program output that does not include the word shell?
import static java.lang.System.out;
import java.util.Collections;
import java.util.NavigableSet;
import java.util.TreeSet;
public class RQ400_400 {
public static void main(String[] args) {
NavigableSet<String> strSetA = new TreeSet<String>();
Collections.addAll(strSetA, "set", "shell", "soap", "swan");
// (1) INSERT STATEMENT HERE.
}
}
Select the two correct answers.
(a) out.println(strSetA.headSet("soap", true));
(b) out.println(strSetA.headSet("soap", false));
(c) out.println(strSetA.tailSet("soap", true));
(d) out.println(strSetA.tailSet("soap", false));
(e) out.println(strSetA.subSet("set", false, "soap", true));
(f) out.println(strSetA.subSet("set", true, "soap", false));
15.25 Which collection types, when inserted at (1), will result in a generic method that will compile without errors?
public static <T> T justDoIt(_____/* (1) INSERT TYPE HERE */______<T> collection)
{
return collection.poll();
}
Select the three correct answers.
(a) NavigableSet
(b) PriorityQueue
(c) LinkedList
(d) Queue
(e) TreeSet
(f) LinkedHashSet
15.26 Which loop, when inserted independently at (1), will guarantee that the program will print sea|sells|she|shells|?
import static java.lang.System.out;
import java.util.Collections;
import java.util.PriorityQueue;
public class RQ400_500 {
public static void main(String[] args) {
PriorityQueue<String> strPQ = new PriorityQueue<String>();
Collections.addAll(strPQ, "shells", "she", "sells", "sea");
// (1) INSERT LOOP HERE
out.println();
}
}
Select the one correct answer.
(a) for (String word : strPQ) {
out.print(word + "|");
}
(b) for (String word : strPQ) {
out.print(strPQ.peek() + "|");
}
(c) while (strPQ.peek() != null) {
out.print(strPQ.poll() + "|");
}
(d) for (String word : strPQ) {
out.print(strPQ.poll() + "|");
}
A Map defines mappings from keys to values. The <key, value> pair is called an entry. A map does not allow duplicate keys, in other words, the keys are unique. Each key maps to one value at the most, implementing what is called a single-valued map. Thus, there is a many-to-one relation between keys and values. For example, in a student-grade map, a grade (value) can be awarded to many students (keys), but each student has only one grade.
Both the keys and the values must be objects, with primitive values being wrapped in their respective primitive wrapper objects when they are put in a map.
A map is not a collection and the Map interface does not extend the Collection interface. However, the mappings can be viewed as a collection in various ways: a key set, a value collection, or an entry set. These collection views are the only means of traversing a map.
The Map interface specifies some optional methods. Implementations should throw an UnsupportedOperationException if they do not support such an operation. The implementations of maps from the java.util package support all the optional operations of the Map interface (see Table 15.2 and Figure 15.3).
These operations constitute the basic functionality provided by a map.
The put() method inserts the <key, value> entry into the map. It returns the old value previously associated with the specified key, if any. Otherwise, it returns the null value.
The get() method returns the value to which the specified key is mapped, or null if no entry is found.
The remove() method deletes the entry for the specified key. It returns the value previously associated with the specified key, if any. Otherwise, it returns the null value.
The containsKey() method returns true if the specified key is mapped to a value in the map.
The containsValue() method returns true if there exists one or more keys that are mapped to the specified value.
int size()
boolean isEmpty()
These methods return the number of entries (i.e., number of unique keys in the map) and whether the map is empty or not.
Bulk operations can be performed on an entire map.
The first method copies all entries from the specified map to the current map, and the second method deletes all entries from the current map.
Views allow information in a map to be represented as collections.
Set<K> keySet()
Collection<V> values()
Set<Map, Entry<K, V>> entrySet()
These methods provide different views of a map. Changes in the map are reflected in the view, and vice versa. These methods return a set view of keys, a collection view of values, and a set view of <key, value> entries, respectively. Note that the Collection returned by the values() method is not a Set, as several keys can map to the same value, that is, duplicate values can be included in the returned collection. Each <key, value> in the entry set view is represented by an object implementing the nested Map.Entry interface. An entry in the entry set view can be manipulated by methods defined in this interface, which are selfexplanatory:
interface Entry<K, V> {
K getKey();
V getValue();
V setValue(V value);
}
Elements can be removed from a map via a view, but cannot be added. An iterator over a view will throw an exception if the underlying map is modified concurrently.
Figure 15.3 shows four implementations of the Map interface in the java.util package: HashMap, LinkedHashMap, TreeMap, and Hashtable.
The classes HashMap and Hashtable implement unordered maps. The class LinkedHashMap implements ordered maps, which are discussed below. The class TreeMap implements sorted maps (see Section 15.10, p. 826).
While the HashMap class is not thread-safe and permits one null key, the Hashtable class is thread-safe and permits non-null keys and values only. The thread-safety provided by the Hashtable class comes with a performance penalty. Thread-safe use of maps is also provided by the methods in the Collections class (see Section 15.11, p. 838). Like the Vector class, the Hashtable class is also a legacy class that has been retrofitted to implement the Map interface.
These map implementations are based on a hashing algorithm. Operations on a map thus rely on the hashCode() and equals() methods of the key objects (see Section 15.1, p. 748).
The LinkedHashMap implementation is a subclass of the HashMap class. The relationship between the map classes LinkedHashMap and HashMap is analogous to the relationship between their counterpart set classes LinkedHashSet and HashSet. Elements of a HashMap (and a HashSet) are unordered. The elements of a LinkedHashMap (and a LinkedHashSet) are ordered. By default, the entries of a LinkedHashMap are in key insertion order, that is, the order in which the keys are inserted in the map. This order does not change if a key is re-inserted, because no new entry is created if the key’s entry already exists. The elements in a LinkedHashSet are in (element) insertion order. However, a LinkedHashMap can also maintain its elements in (element) access order, that is, the order in which its entries are accessed, from least-recently accessed to most-recently accessed entries. This ordering mode can be specified in one of the constructors of the LinkedHashMap class.
Both the HashMap and the LinkedHashMap classes provide comparable performance, but the HashMap class is the natural choice if ordering is not an issue. Operations such as adding, removing, or finding an entry based on a key are in constant time, as these hash the key. Operations such as finding the entry with a particular value are in linear time, as these involve searching through the entries.
Adding, removing, and finding entries in a LinkedHashMap can be slightly slower than in a HashMap, as an ordered doubly-linked list has to be maintained. Traversal of a map is through one of its collection-views. For an underlying LinkedHashMap, the traversal time is proportional to the size of the map—regardless of its capacity. However, for an underlying HashMap, it is proportional to the capacity of the map.
The concrete map implementations override the toString() method. The standard textual representation generated by the toString() method for a map is
{ key1 = value1, key2 = value2 , ..., keyn = valuen}
where each keyi and each valuei is the textual representation generated by the toString() method of the individual key and value objects in the map, respectively.
As was the case with collections, implementation classes provide a standard constructor that creates a new empty map, and a constructor that creates a new map based on an existing one. Additional constructors create empty maps with given initial capacities and load factors. The HashMap class provides the following constructors:
HashMap()
HashMap(int initialCapacity)
HashMap(int initialCapacity, float loadFactor)
Constructs a new, empty HashMap, using either specified or default initial capacity and load factor.
HashMap(Map<? extends K,? extends V> otherMap)
Constructs a new map containing the elements in the specified map.
The LinkedHashMap and Hashtable classes have constructors analogous to the four constructors for the HashMap class. In addition, the LinkedHashMap class provides a constructor where the ordering mode can also be specified:
LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)
Constructs a new, empty LinkedHashMap with the specified initial capacity, the specified load factor, and the specified ordering mode. The ordering mode is true for access order and false for key insertion order.
Example 15.21 prints a textual histogram for the frequency of weight measurements in a weight group, where a weight group is defined as an interval of five units. The weight measurements are supplied as program arguments. The example illustrates the use of maps, the creation of key views, and the use of a for(:) loop to traverse a map. The program proceeds as follows:
• An empty HashMap<Integer, Integer> is created at (1), where the key is the weight group and the value is the frequency.
• A for(:) loop is used at (2) to read the weights specified as program arguments, converting each weight to its corresponding weight group and updating the frequency of the weight group:
The weight group is determined at (3). The count is incremented at (4), if necessary, and a new entry is registered at (5). Since keys are unique in a map, any previous entry is overwritten.
Generic types guarantee that the keys and the values in the map are of the correct type, and autoboxing/unboxing of primitive values guarantees the correct type of an operand in an expression:
Integer frequency = groupFreqMap.get(weightGroup); // (4)
frequency = (frequency == null) ? 1 : frequency+1; // (5)
groupFreqMap.put(weightGroup, frequency); // (6)
• The program creates a sorted set of keys (which are weight groups) from the groupFreqMap at (7). The keySet() method returns a set view of keys, which is passed as argument to a TreeSet.
SortedSet<Integer> groupSet
= new TreeSet<Integer>(groupFreqMap.keySet()); // (7)
• The histogram is printed by traversing the sorted key set in a for(:) loop at (8), looking up the frequency in the groupFreqMap. A map can only be traversed through one of its views.
For each key, the corresponding value (i.e., the frequency) is retrieved at (9):
int frequency = groupFreqMap.get(group); // (9)
A bar (char[]) for each frequency is created using the Arrays.fill() method at (10), which is converted to string and printed.
Example 15.21 Using Maps
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.SortedSet;
import java.util.TreeSet;
public class WeightGroups {
public static void main(String[] args) {
// Create a map to store the frequency for each group.
Map<Integer, Integer> groupFreqMap = new HashMap
<Integer, Integer>(); // (1)
// Determine the frequencies:
for (String argument : args) { // (2)
// Get the value from an argument and group
into intervals of 5.
double weight = Double.parseDouble(argument);
int weightGroup = (int) Math.round(weight/5)*5; // (3)
Integer frequency = groupFreqMap.get(weightGroup); // (4)
// Increment frequency if necessary.
frequency = (frequency == null) ? 1 : frequency+1; // (5)
groupFreqMap.put(weightGroup, frequency); // (6)
}
// Print the histogram:
// Create a sorted set of groups (keys)
SortedSet<Integer> groupSet
= new TreeSet<Integer>(groupFreqMap.keySet()); // (7)
// Traverse the keys, looking up the frequency from
the map.
for (int group : groupSet) { // (8)
int frequency = groupFreqMap.get(group); // (9)
/* Use the Arrays.fill() method to fill a char array with equivalent
* number of '*' as the frequency value.
* Convert the char array to string in order to
print. */
char[] bar = new char[frequency];
Arrays.fill(bar, '*'), // (10)
System.out.println(group + ": " + new String(bar));
}
}
}
Running the program with the following arguments:
>java WeightGroups 74 75 93 75 93 82 61 92 10 185
gives the following output:
10: *
60: *
75: ***
80: *
90: *
95: **
185: *
The SortedMap and NavigableMap interfaces are the analogs of the SortedSet and the NavigableSet interfaces, respectively.
The SortedMap interface extends the Map interface to provide the functionality for implementing maps with sorted keys. Its operations are analogous to those of the SortedSet interface (p. 800), applied to maps and keys rather than to sets and elements.
Return the smallest key and the largest key in the sorted map, respectively. They throw a NoSuchElementException if the set is empty.
// Range-view operationsSortedMap<K,V> headMap(K toKey) Sorted set: headSet()SortedMap<K,V> tailMap(K fromKey) Sorted set: tailSet()SortedMap<K,V> subMap(K fromKey, K toKey) Sorted set: subSet()
Return set views analogous to that of a SortedSet. The set views include the fromKey if it is present in the map, but the toKey is excluded.
// Comparator access
Comparator<? super K> comparator()
Returns the key comparator, if the map has one. Otherwise returns null.
Analogous to the NavigableSet interface extending the SortedSet interface, the NavigableMap interface extends the SortedMap interface with navigation methods to find the closest matches for specific search targets. The NavigableMap interface replaces the SortedMap interface and is the preferred choice when a sorted map is needed.
In addition to the methods of the SortedMap interface, the NavigableMap interface adds the new methods shown below, where the analogous methods from the NavigableSet interface are also identified. Note that where a NavigableMap method returns a Map.Entry object representing a mapping, the corresponding NavigableSet method returns an element of the set.
// First-last elements
Map.Entry<K, V> pollFirstEntry()
Navigable set: pollFirst()
Map.Entry<K, V> pollLastEntry()
Navigable set: pollLast()
Map.Entry<K, V> firstEntry()
Map.Entry<K, V> lastEntry()
The pollFirstEntry() method removes and returns the first entry, and the pollLastEntry() method removes and returns the last entry currently in this navigable map. The entry is determined according to the ordering policy employed by the map—e.g., natural ordering. Both return null if the navigable set is empty. The last two methods only retrieve, and do not remove, the value that is returned.
// Range-view operations
NavigableMap<K, V> headMap(K toElement,
boolean inclusive)
Navigable set: headSet()
NavigableMap<K, V> tailMap(K fromElement,
boolean inclusive)
Navigable set: tailSet()
NavigableMap<K, V> subMap(K fromElement,
boolean fromInclusive,
K toElement,
boolean toInclusive)
Navigable set: subSet()
These operations are analogous to the ones in the SortedMap interface (p. 826), returning different views of the underlying navigable map, depending on the bound elements. However, the bound elements can be excluded or included by the operation, depending on the value of the boolean argument inclusive.
// Closest-matches
Map.Entry<K, V> ceilingEntry(K key)
K ceilingKey(K key)
Navigable set: ceiling()
Map.Entry<K, V> floorEntry(K key)
K floorKey(K key)
Navigable set: floor()
Map.Entry<K, V> higherEntry(K key)
K higherKey(K key)
Navigable set: higher()
Map.Entry<K, V> lowerEntry(K key)
K lowerKey(K key)
Navigable set: lower()
The ceiling methods return the least entry (or key) in the navigable map >= to the argument key. The floor methods return the greatest entry (or key) in the navigable map <= to the argument key. The higher methods return the least entry (or key) in the navigable map > the argument key. The lower methods return the greatest entry (or key) in the navigable map < the argument key. All methods return null if there is no such key.
// Navigation
NavigableMap<K, V> descendingMap()
NavigableSet<K> descendingKeySet()
NavigableSet<K> navigableKeySet()
Navigable set: descendingSet()
The first method returns a reverse-order view of the entries in the navigable map. The second method returns a reverse-order key set for the entries in the navigable map. The last method returns a forward-order key set for the entries in the navigable map.
The TreeMap class is the analog of the TreeSet class (p. 802), but in this case for maps. It provides an implementation that sorts its entries in a specific order (see also Figures 15.2 and 15.3).
The TreeMap class implements the NavigableMap interface, and thereby the SortedMap interface. By default, operations on sorted maps rely on the natural ordering of the keys. However, a total ordering can be specified by passing a customized comparator to the constructor.
The TreeMap implementation uses balanced trees, which deliver excellent performance for all operations. However, searching in a HashMap can be faster than in a TreeMap, as hashing algorithms usually offer better performance than the search algorithms for balanced trees.
The TreeMap class provides four constructors, analogous to the ones in the TreeSet class:
TreeMap()
A standard constructor used to create a new empty sorted map, according to the natural ordering of the keys.
A constructor that takes an explicit comparator for the keys, that is used to order the entries in the map.
TreeMap(Map<? extends K, ? extends V> m)
A constructor that can create a sorted map based on a map, according to the natural ordering of the keys.
TreeMap(SortedMap<K, ? extends V> m)
A constructor that creates a new map containing the same entries as the specified sorted map, with the same ordering for the keys.
Example 15.22 illustrates using navigable maps. It also prints a textual histogram like the one in Example 15.21, but in addition, it prints some statistics about the navigable map.
• An empty NavigableMap<Integer, Integer> is created at (1), where the key is the weight group and the value is the frequency.
• The procedure at (2) reads the weights specified as program arguments, converting each weight to its corresponding weight group, and the updating of the frequency of the weight group is the same as in Example 15.21. Printing the contents of the navigable map at (3), and its size at (4), shows that there are 7 entries ordered in ascending key order:
Group frequency map: {10=1, 60=1, 75=3, 80=1, 90=1, 95=2, 185=1}
No. of weight groups: 7
• Calls to the methods firstEntry() and lastEntry() at (5) and (6) return the following entries, respectively:
First entry: 10=1
Last entry: 185=1
• Calls to the methods floorEntry() and higherKey() with the key value 77 at (7) and (8) return the following values, respectively:
Greatest entry <= 77: 75=3
Smallest key > 90: 95
• Calls to the methods tailMap(75, true) and headMap(75, false) at (9) and (10) return the following map views, respectively:
Groups >= 75: {75=3, 80=1, 90=1, 95=2, 185=1}
Groups < 75: {10=1, 60=1}
• The method printHistogram() at (13) prints a histogram of the frequencies in a navigable map:
public static <K> int printHistogram(NavigableMap<K, Integer> freqMap){ ... }
It is a generic method with one type parameter, K, that specifies the type of the keys, and the type of the values (i.e., frequencies) is Integer. The method creates an entry set at (14). Since this entry set is backed by a navigable map, traversal of the entry set is in ascending key order. A for(:) loop is used at (15) to traverse the entry set, printing the histogram for the navigable map. The method also counts the number of values on which the frequencies are based (i.e., it sums the frequencies).
A call to the printHistogram() method at (11) with the navigable map of frequencies gives the following results:
Histogram:
10: *
60: *
75: ***
80: *
90: *
95: **
185: *
Number of weights registered: 10
It is possible to call the printHistogram() method with a map view to print partial histograms. Based on the navigable map of frequencies in Example 15.22, the following code:
System.out.println("Partial histogram:");
int count = printHistogram(groupFreqMap.subMap(75, true, 185, false));
System.out.println("Number of weights registered: " + count);
prints the following partial histogram:
Partial histogram:
75: ***
80: *
90: *
95: **
Number of weights registered: 7
• Polling of a navigable map is shown at (12). For each entry, its key and its value is printed.
Histogram (by polling):
10: 1
60: 1
75: 3
80: 1
90: 1
95: 2
185: 1
Number of weights registered: 10
Polling is done directly on the navigable map, and the retrieved entry is removed from the map. A map is not Iterable. However, an iterator or a for(:) loop can be used to traverse a set view of the map.
Example 15.22 Using Navigable Maps
import java.util.Arrays;
import java.util.Map;
import java.util.NavigableMap;
import java.util.Set;
import java.util.TreeMap;
public class WeightGroups2 {
public static void main(String[] args) {
// Create a navigable map to store the frequency
for each group.
NavigableMap<Integer, Integer> groupFreqMap =
new TreeMap<Integer, Integer>(); // (1)
// Determine the frequencies: // (2)
for (String argument : args) {
// Get the value from an argument and group into intervals of 5.
double weight = Double.parseDouble(argument);
int weightGroup = (int) Math.round(weight/5)*5;
Integer frequency = groupFreqMap.get(weightGroup);
// Increment frequency if necessary.
frequency = (frequency == null) ? 1 : frequency+1;
groupFreqMap.put(weightGroup, frequency);
}
// Print statistics about the frequency map:
System.out.println("Group frequency map: " + groupFreqMap); // (3)
System.out.println("No. of weight groups: " + groupFreqMap.size()); // (4)
System.out.println("First entry: " + groupFreqMap.firstEntry()); // (5)
System.out.println("Last entry: " + groupFreqMap.lastEntry()); // (6)
System.out.println("Greatest entry <= 77: " +
groupFreqMap.floorEntry(77)); // (7)
System.out.println("Smallest key > 90: " +
groupFreqMap.higherKey(90)); // (8)
System.out.println("Groups >= 75: " + groupFreqMap.tailMap(75, true)); // (9)
System.out.println("Groups < 75: " + groupFreqMap.headMap(75, false)); // (10)
// Print the histogram for the weight groups:
System.out.println("Histogram:");
int numRegistered = printHistogram(groupFreqMap); // (11)
System.out.println("Number of weights registered: " + numRegistered);
// Poll the navigable map: (12)
System.out.println("Histogram (by polling):");
int sumValues = 0;
while (!groupFreqMap.isEmpty()) {
Map.Entry<Integer, Integer> entry =
groupFreqMap.pollFirstEntry();
int frequency = entry.getValue();
sumValues += frequency;
System.out.printf("%5s: %s%n", entry.getKey(), frequency);
}
System.out.println("Number of weights registered: " + sumValues);
}
/** Prints histogram from a navigable map containing
frequencies.
* Returns the sum of frequencies. */
public static <K> int printHistogram(NavigableMap<K, Integer> freqMap) { // (13)
// Create a set of entries in ascending key order.
Set<Map.Entry<K, Integer>> navEntrySet = freqMap.entrySet(); // (14)
int sumValues= 0;
// Traverse the set of entries to print the histogram:
for (Map.Entry<K, Integer> entry : navEntrySet) { // (15)
/* Extract frequency value from entry.
* Use the Arrays.fill() method to fill a char array with equivalent
* number of '*' as the frequency value.
* Convert the char array to string in order to print. */
int frequency = entry.getValue();
sumValues += frequency;
char[] bar = new char[frequency];
Arrays.fill(bar, '*'),
// Print key and bar.
System.out.printf("%5s: %s%n", entry.getKey(), new String(bar));
}
return sumValues;
}
}
Running the program with the following argument:
>java WeightGroups2 74 75 93 75 93 82 61 92 10 185
gives the following output:
Group frequency map: {10=1, 60=1, 75=3, 80=1, 90=1, 95=2, 185=1}
No. of weight groups: 7
First entry: 10=1
Last entry: 185=1
Greatest entry <= 77: 75=3
Smallest key > 90: 95
Groups >= 75: {75=3, 80=1, 90=1,
95=2, 185=1}
Groups < 75: {10=1, 60=1}
Histogram:
10: *
60: *
75: ***
80: *
90: *
95: **
185: *
Number of weights registered: 10
Histogram (by polling):
10: 1
60: 1
75: 3
80: 1
90: 1
95: 2
185: 1
Number of weights registered: 10
Review Questions
15.27 Which of these methods can be called on objects implementing the Map<K, V> interface?
Select the two correct answers.
(a) contains(Object o)
(b) addAll(Map<? extends K, ? extends V> m)
(c) remove(Object o)
(d) values()
(e) toArray()
15.28 Which statements are true about maps?
Select the two correct answers.
(a) The return type of the values() method is Set.
(b) Changes made in the set view returned by keySet() will be reflected in the original map.
(c) The Map interface extends the Collection interface.
(d) All keys in a map are unique.
(e) All Map implementations keep the keys sorted.
15.29 Which of these classes have a comparator() method?
Select the two correct answers.
(a) ArrayList
(b) HashMap
(c) TreeSet
(d) HashSet
(e) TreeMap
15.30 Which methods are defined by the java.util.Map.Entry<K, V> interface?
Select the two correct answers.
(a) K getKey()
(b) K setKey(K value)
(c) V getValue()
(d) V setValue(V value)
(e) void set(K key, V value)
15.31 Which statements are true about the following program?
import java.util.Collection;
import java.util.Collections;
import java.util.NavigableSet;
import java.util.TreeSet;
public class ConstructingSortedSets {
public static void main(String[] args) {
NavigableSet<Integer> navSet
= new TreeSet<Integer>(Collections.reverseOrder());
Collections.addAll(navSet, 2010, 3001, 2001);
NavigableSet<Integer> ss1 = new TreeSet<Integer>(navSet);
NavigableSet<Integer> ss2 = new TreeSet<Integer>((Collection<Integer>)navSet);
for (Integer iRef : navSet) // (1)
System.out.print(iRef + "|");
System.out.println();
for (Integer iRef : ss1) // (2)
System.out.print(iRef + "|");
System.out.println();
for (Integer iRef : ss2) // (3)
System.out.print(iRef + "|");
System.out.println();
while (!ss1.isEmpty()) // (4)
System.out.print(ss1.pollFirst() + "|");
System.out.println();
while (!ss2.isEmpty()) // (5)
System.out.print(ss2.pollFirst() + "|");
}
}
Select the three correct answers.
(a) The loop at (1) prints 3001|2010|2001|.
(b) The loops at (1), (2) and (4) print the same output.
(c) The loop at (3) prints 3001|2010|2001|.
(d) All the loops print the same output.
(e) The loops at (3) and (5) print the same output.
15.32 Which code, when inserted independently at (1), will result in the following output from the program: {be=2, not=1, or=1, to=2}?
import java.util.Map;
import java.util.TreeMap;
public class FreqMap {
public static void main(String[] args) {
Map<String, Integer> freqMap = new TreeMap<String, Integer>();
for (String key : new String[] {"to", "be", "or", "not", "to", "be"}) {
// (1) INSERT CODE HERE ...
}
System.out.println(freqMap);
}
}
Select the two correct answers.
(a) Integer frequency = freqMap.get(key);
frequency = (frequency == 0) ? 1 : frequency+1;
freqMap.put(key, frequency);
(b) Integer frequency = freqMap.get(key);
frequency = (frequency == null) ? 1 : frequency+1;
freqMap.put(key, frequency);
(c) int frequency = freqMap.get(key);
frequency = (frequency == 0) ? 1 : frequency+1;
freqMap.put(key, frequency);
(d) Integer frequency = (!freqMap.containsKey(key)) ? 1 : freqMap.get(key)+1;
freqMap.put(key, frequency);
15.33 What will the program print when compiled and run?
import java.util.Collection;
import java.util.Map;
import java.util.NavigableMap;
import java.util.TreeMap;
public class MapModify {
public static void main(String[] args) {
NavigableMap<String, Integer> grades = new TreeMap
<String, Integer>();
grades.put("A", 5); grades.put("B", 10); grades.put("C", 15);
grades.put("D", 20); grades.put("E", 25);
System.out.printf("1:%d, ", grades.get(grades.firstKey()));
System.out.printf("2:%d, ", sumValues(grades.headMap("D")));
System.out.printf("3:%d, ", sumValues(grades.subMap("B", false, "D", true)));
grades.subMap(grades.firstKey(), false, grades.lastKey(), false).clear();
System.out.printf("4:%d%n", sumValues(grades));
}
public static <K, M extends Map<K, Integer>> int sumValues(M freqMap) {
Collection<Integer> values = freqMap.values();
int sumValues= 0;
for (int value : values)
sumValues += value;
return sumValues;
}
}
Select the one correct answer.
(a) 1:5, 2:50, 3:35, 4:30
(b) 1:5, 2:30, 3:35, 4:30
(c) 1:5, 2:30, 3:25, 4:30
(d) 1:5, 2:30, 3:35, 4:75
15.34 Which code, when inserted independently at (1), will result in the following output from the program: {Soap=10, Salts=10}?
import java.util.*;
public class Mapping {
public static void main(String[] args) {
NavigableMap<String, Integer> myMap
= new TreeMap<String, Integer>(Collections.reverseOrder());
myMap.put("Soap", 10); myMap.put("Shampoo", 5); myMap.put("Salts", 10);
// (1) INSERT CODE HERE ...
System.out.println(myMap);
}
}
Select the two correct answers.
(a) for (Map.Entry<String, Integer> entry : myMap.entrySet())
if (entry.getKey().equals("Shampoo"))
myMap.remove("Shampoo");
(b) for (Iterator<String> iterator = myMap.keySet().iterator();
iterator.hasNext();)
if (iterator.next().equals("Shampoo"))
iterator.remove();
(c) for (Iterator<String> iterator = myMap.keySet().iterator();
iterator.hasNext();) {
if (iterator.next().equals("Shampoo"))
myMap.remove("Shampoo");
(d) for (Map.Entry<String, Integer> entry : myMap.entrySet())
if (entry.getKey().equals("Shampoo"))
myMap.remove(entry);
(e) myMap.subMap("Shampoo", true, "Shampoo", true).clear();
15.35 Which code, when inserted independently at (1), will result in the following output from the program: {1=Odd, 2=Even, 3=Odd}?
import java.util.Map;
import java.util.TreeMap;
public class StringBuilderMap {
public static void main(String[] args) {
Map<Integer, StringBuilder> myMap = new TreeMap
<Integer, StringBuilder>();
for (Integer key : new int[] {1, 2, 1, 3, 1, 2, 3, 3}) {
// (1) INSERT CODE HERE ...
}
System.out.println(myMap);
}
private static StringBuilder toggle(StringBuilder strBuilder) {
String value = "Odd";
if (strBuilder.toString().equals(value))
value = "Even";
return strBuilder.replace(0, strBuilder.length(), value);
}
}
Select the one correct answer.
(a) StringBuilder value = myMap.get(key);
myMap.put(key, (value == null) ? new StringBuilder("Odd") :
StringBuilderMap.toggle(value));
(b) StringBuilder value = myMap.get(key);
if (value == null)
value = new StringBuilder("Odd");
else
StringBuilderMap.toggle(value);
myMap.put(key, value);
(c) StringBuilder value = myMap.get(key);
if (!myMap.containsKey(key))
myMap.put(key, new StringBuilder("Odd"));
else
StringBuilderMap.toggle(value);
(d) All of the above.
15.36 Which code, when inserted independently at (1), will result in the following output from the program: {1=Odd, 2=Even, 3=Odd}?
import java.util.Map;
import java.util.TreeMap;
public class StringMap {
public static void main(String[] args) {
Map<Integer, String> myMap = new TreeMap<Integer, String>();
for (Integer key : new int[] {1, 2, 1, 3, 1, 2, 3, 3}) {
// (1) INSERT CODE HERE ...
}
System.out.println(myMap);
}
private static String toggle(String str) {
if (str.equals("Odd"))
str = str.replace("Odd", "Even");
else
str = str.replace("Even", "Odd");
return str;
}
}
Select the one correct answer.
(a) String value = myMap.get(key);
myMap.put(key, (value == null) ? "Odd" : StringMap.toggle(value));
(b) String value = myMap.get(key);
if (value == null)
value = "Odd";
else
StringMap.toggle(value);
myMap.put(key, value);
(c) String value = myMap.get(key);
if (!myMap.containsKey(key))
myMap.put(key, "Odd");
else
StringMap.toggle(value);
(d) All of the above.
The Java Collections Framework also contains two classes, Collections and Arrays, that provide various operations on collections and arrays, such as sorting and searching, or creating customized collections. Practically any operation on a list can be done using the methods covered in this section.
The methods provided are all public and static, therefore these two keywords will be omitted in their method header declarations in this section.
The methods also throw a NullPointerException if the specified collection or array references passed to them are null.
The Collections class provides two static methods for sorting lists.
<E extends Comparable<? super E>> void sort(List<E> list)
<E> void sort(List<E> list, Comparator<? super E> c)
The first method sorts the elements in the list according to their natural ordering. The second method does the sorting according to the total ordering defined by the comparator. In addition, all elements in the list must be mutually comparable: the method call e1.compareTo(e2) (or e1.compare(e2) in case of the comparator) must not throw a ClassCastException for any elements e1 and e2 in the list. In other words, it should be possible to compare any two elements in the list. Note that the second method does not require that the type parameter E is Comparable.
<E> Comparator<E> reverseOrder()
<E> Comparator<E> reverseOrder(Comparator<E> comparator)
The first method returns a comparator that enforces the reverse of the natural ordering. The second one reverses the total ordering defined by the comparator. Both are useful for maintaining objects in reverse-natural or reverse-total ordering in sorted collections and arrays.
This code shows how a list of strings is sorted according to different criteria.
List<String> strList = new ArrayList<String>();
strList.add("biggest"); strList.add("big");
strList.add("bigger"); strList.add("Bigfoot");
Collections.sort(strList); // Natural order
Collections.sort(strList, Collections.reverseOrder()); // Reverse natural order
Collections.sort(strList, String.CASE_INSENSITIVE_ORDER);
// Case insensitive order
Collections.sort(strList, // Reverse case insensitive order
Collections.reverseOrder(String.CASE_INSENSITIVE_ORDER));
The output below shows the list before sorting, followed by the results from the calls to the sort() methods above, respectively:
Before sorting: [biggest, big,
bigger, Bigfoot]
After sorting in natural order: [Bigfoot, big,
bigger, biggest]
After sorting in reverse natural order: [biggest,
bigger, big, Bigfoot]
After sorting in case insensitive order: [big, Bigfoot,
bigger, biggest]
After sorting in reverse case insensitive order: [biggest, bigger,
Bigfoot, big]
It is important to note that the element type of the list must implement the Comparable interface, otherwise the compiler will report an error. The following code shows that a list of StringBuilders cannot be sorted because the class StringBuilder does not implement the Comparable interface.
List<StringBuilder> sbList = new ArrayList<StringBuilder>();
sbList.add(new StringBuilder("smallest"));
sbList.add(new StringBuilder("small"));
sbList.add(new StringBuilder("smaller"));
Collections.sort(sbList); // Compile-time error!
Below is an example of a list whose elements are not mutually comparable. Raw types are used intentionally to create such a list. Predictably the sort() method throws an exception because the primitive wrapper classes do not permit interclass comparison.
List freakList = new ArrayList(); // Raw types.
freakList.add(23); freakList.add(3.14); freakList.add(10L);
Collections.sort(freakList); // ClassCastException
The comparator returned by the reverseOrder() method can be used with sorted collections. The elements in the following sorted set would be maintained in descending order:
Set<Integer> intSet = new TreeSet<Integer>(Collections.reverseOrder());
intSet.add(9); intSet.add(11);
intSet.add(-4); intSet.add(1);
System.out.println(intSet); // [11, 9, 1, -4]
The following utility methods apply to any list, regardless of whether the elements are Comparable or not:
void reverse(List<?> list)
Reverses the order of the elements in the list.
void rotate(List<?> list, int distance)
Rotates the elements towards the end of the list by the specified distance. A negative value for the distance will rotate toward the start of the list.
void shuffle(List<?> list)
void shuffle(List<?> list, Random rnd)
Randomly permutes the list, that is, shuffles the elements.
void swap(List<?> list, int i, int j)
Swaps the elements at indices i and j.
The effect of these utility methods can be limited to a sublist, that is, a segment of the list. The following code illustrates rotation of elements in a list. Note how the rotation in the sublist view is reflected in the original list.
// intList refers to the following list: [9, 11, -4, 1, 7]
Collections.rotate(intList, 2); // Two to the right. [1, 7, 9, 11, -4]
Collections.rotate(intList, -2); // Two to the left. [9, 11, -4, 1, 7]
List intSublist = intList.subList(1,4);// Sublist: [11, -4, 1]
Collections.rotate(intSublist, -1); // One to the left. [-4, 1, 11]
// intList is now: [9, -4, 1, 11, 7]
The Collections class provides two static methods for finding elements in sorted lists.
<E> int binarySearch(List<? extends Comparable<? super E>> list, E key)
<E> int binarySearch(List<? extends E> list, E key,
Comparator<? super E> c))
The methods use a binary search to find the index of the key element in the specified sorted list. The first method requires that the list is sorted according to natural ordering, whereas the second method requires that it is sorted according to the total ordering dictated by the comparator. The elements in the list and the key must also be mutually comparable.
Successful searches return the index of the key in the list. A non-negative value indicates a successful search. Unsuccessful searches return a negative value given by the formula -(insertion point + 1), where insertion point is the index where the key would have been, had it been in the list. In the code below the return value -3 indicates that the key would have been at index 2 had it been in the list.
// Sorted String list (natural order): [Bigfoot, big,
bigger, biggest]
Collections.sort(strList);
// Search in natural order:
out.println(Collections.binarySearch(strList, "bigger")); // Successful: 2
out.println(Collections.binarySearch(strList, "bigfeet")); // Unsuccessful: -3
out.println(Collections.binarySearch(strList, "bigmouth")); // Unsuccessful: -5
Proper use of the search methods requires that the list is sorted, and the search is performed according to the same sort ordering. Otherwise, the search results are unpredictable. The example below shows the results of the search when the list strList above was sorted in reverse natural ordering, but was searched assuming natural ordering. Most importantly, the return values reported for unsuccessful searches for the respective keys are incorrect in the list that was sorted in reverse natural ordering.
// Sort in reverse natural order: [biggest, bigger, big, Bigfoot]
Collections.sort(strList, Collections.reverseOrder());
// Searching in natural order:
out.println(Collections.binarySearch(strList, "bigger")); // 1
out.println(Collections.binarySearch(strList, "bigfeet")); // -1 (INCORRECT)
out.println(Collections.binarySearch(strList, "bigmouth")); // -5 (INCORRECT)
Searching the list in reverse natural ordering requires that an appropriate comparator is supplied during the search (as during the sorting), resulting in correct results:
// Sort in reverse natural order: [biggest, bigger, big, Bigfoot]
Collections.sort(strList, Collections.reverseOrder());
// Searching in reverse natural order:
out.println(Collections.binarySearch(strList, "bigger",
Collections.reverseOrder())); // 1
out.println(Collections.binarySearch(strList, "bigfeet",
Collections.reverseOrder())); // -3
out.println(Collections.binarySearch(strList, "bigmouth",
Collections.reverseOrder())); // -1
The following methods search for sublists:
int indexOfSubList(List<?> source, List<?> target)
int lastIndexOfSubList(List<?> source, List<?> target)
These two methods find the first or last occurrence of the target list in the source list, respectively. They return the starting position of the target list in the source list. The methods are applicable to lists of any type.
The following methods find the minimum and maximum elements in a collection:
<E extends Object & Comparable<? super E>>
E max(Collection<? extends E> c)
<E> E max(Collection<? extends E> c, Comparator<? super E> comp)
<E extends Object & Comparable<? super E>>
E min(Collection<? extends E> c)
<E> E min(Collection<? extends E> cl, Comparator<? super E> comp)
The one-argument methods require that the elements have a natural ordering, i.e., are Comparable. The other methods require that the elements have a total ordering enforced by the comparator. Calling any of the methods with an empty collection as parameter results in an NoSuchElementException.
The time for the search is proportional to the size of the collection.
These methods are analogous to the methods first() and last() in the SortedSet class and the methods firstKey() and lastKey() in the SortedMap class.
The majority of the methods in this category accept a List, while one method operates on arbitrary Collections. They all change the contents of the collection in some way.
<E> boolean addAll(Collection<? super E> collection, E... elements)
Adds the specified elements to the specified collection. Convenient method for loading a collection with a variable argument list or an array.
Adds the elements from the source list to the destination list.
<E> void fill(List<? super E> list, E element)
Replaces all of the elements of the list with the specified element.
<E> boolean replaceAll(List<E> list, E oldVal, E newVal)
Replaces all elements equal to oldVal with newVal in the list; returns true if the list was modified.
<E> List<E> nCopies(int n, E element)
Creates an immutable list with n copies of the specified element.
The addAll() method is a convenient method for loading a collection with elements from a variable-argument list or an array. Several examples of its usage can be found in this chapter, but more are given below. The array passed should be an array of objects. Note also the autoboxing of the int values specified in (1) and (2). The addAll() method does not allow primitive arrays as vararg arguments, as attempted at (3).
List<Integer> intList = new ArrayList<Integer>();
Collections.addAll(intList, 9, 1, 1); // (1) A var-arg list
Collections.addAll(intList, new Integer[] {9, 1, 1}); // (2) An array of Integers
Collections.addAll(intList, new int[] {9, 1, 1}); // (3) Compile-time error!
The Arrays class provides enough overloaded versions of the sort() method to sort practically any type of array. The discussion on sorting lists (p. 838) is also applicable to sorting arrays.
void sort(type [] array)
void sort(type [] array, int fromIndex, int toIndex)
These methods sort the elements in the array according to their natural ordering. Permitted type for elements include byte, char, double, float, int, long, short and Object. In the case of an array of objects being passed as argument, the objects must be mutually comparable according to the natural ordering defined by the Comparable interface.
<E> void sort(E[] array, Comparator<? super E> comp)
<E> void sort(E[] array, int fromIndex, int toIndex,
Comparator<? super E> comp)
The two generic methods above sort the array according to the total ordering dictated by the comparator. In particular, the methods require that the elements are mutually comparable according to this comparator.
The bounds, if specified in the methods above, define a half-open interval. Only elements in this interval are then sorted.
The experiment from p. 838 with a list of strings is now repeated with an array of strings, giving identical results. A array of strings is sorted according to different criteria.
String[] strArray = {"biggest", "big", "bigger", "Bigfoot"};
Arrays.sort(strArray); // Natural order
Arrays.sort(strArray, Collections.reverseOrder()); // Reverse natural order
Arrays.sort(strArray, String.CASE_INSENSITIVE_ORDER);
// Case insensitive order
Arrays.sort(strArray, // Reverse case insensitive order
Collections.reverseOrder(String.CASE_INSENSITIVE_ORDER));
The output below shows the array before sorting, followed by the results from the calls to the sort() methods above, respectively:
Before sorting: [biggest, big,
bigger, Bigfoot]
After sorting in natural order: [Bigfoot, big,
bigger, biggest]
After sorting in reverse natural order: [biggest,
bigger, big, Bigfoot]
After sorting in case insensitive order: [big, Bigfoot,
bigger, biggest]
After sorting in reverse case insensitive order: [biggest,
bigger, Bigfoot, big]
The examples below illustrate sorting an array of primitive values (int) at (1), an array of type Object containing mutually comparable elements (String) at (2), and a half-open interval in reverse natural ordering at (3). A ClassCastException is thrown when the elements are not mutually comparable at (4) and (5).
int[] intArray = {5, 3, 7, 1}; // int
Arrays.sort(intArray); // (1) Natural order: [1, 3, 5, 7]
Object[] objArray1 = {"I", "am", "OK"}; // String
Arrays.sort(objArray1); // (2) Natural order: [I, OK, am]
Comparable<Integer>[] comps = new Integer[] {5, 3, 7, 1}; // Integer
Arrays.sort(comps, 1, 4, Collections.reverseOrder());// (3) Reverse natural order:
// [5, 7, 3, 1]
Object[] objArray2 = {23, 3.14, "ten"}; // Not mutually comparable
// Arrays.sort(objArray2); // (4) ClassCastException
Number[] numbers = {23, 3.14, 10L}; // Not mutually comparable
// Arrays.sort(numbers); // (5) ClassCastException
The Arrays class provides enough overloaded versions of the binarySearch() method to search in practically any type of array that is sorted. The discussion on searching in lists (p. 840) is also applicable to searching in arrays.
The methods below return the index to the key in the sorted array, if the key exists. If not, a negative index is returned, corresponding to (-insertion point)-1, where insertion point is the index of the element where the key would have been found if it had been in the array. In case there are duplicate elements equal to the key, there is no guarantee which duplicate’s index will be returned. The elements and the key must be mutually comparable.
The bounds, if specified in the methods below, define a half-open interval. The search is then confined to this interval.
int binarySearch(type [] array, type key)
int binarySearch(type [] array, int fromIndex, int toIndex, type key)
Permitted type for elements include byte, char, double, float, int, long, short, and Object. In the case where an array of objects is passed as argument, the objects must be sorted in natural ordering, as defined by the Comparable interface.
<E> int binarySearch(E[] array, E key, Comparator<? super E> c)
<E> int binarySearch(E[] array, int fromIndex, int toIndex, E key,
Comparator<? super E> c)
The two generic methods above require that the array is sorted according to the total ordering dictated by the comparator. In particular, its elements are mutually comparable according to this comparator. The comparator must be equivalent to the one that was used for sorting the array, otherwise the results are unpredictable.
The experiment from p. 840 with a list of strings is now repeated with an array of strings, giving identical results. In the code below the return value -3 indicates that the key would have been found at index 2 had it been in the list.
// Sorted String array (natural order): [Bigfoot, big, bigger,
biggest]
Arrays.sort(strArray);
// Search in natural order:
out.println(Arrays.binarySearch(strArray, "bigger")); // Successful: 2
out.println(Arrays.binarySearch(strArray, "bigfeet")); // Unsuccessful: -3
out.println(Arrays.binarySearch(strArray, "bigmouth")); // Unsuccessful: -5
Results are unpredictable if the array is not sorted or the ordering used in the search is not the same as the sort ordering. Searching in the strArray using reverse natural ordering when the array is sorted in natural ordering gives the wrong result:
out.println(Arrays.binarySearch(strArray, "bigger",
Collections.reverseOrder())); // -1 (INCORRECT)
A ClassCastException is thrown if the key and the elements are not mutually comparable:
out.println(Arrays.binarySearch(strArray, 4)); // Key: 4 => ClassCastException
However, this incompatibility is caught at compile time in the case of arrays with primitive values:
// Sorted int array (natural order): [1, 3, 5, 7]
out.println(Arrays.binarySearch(intArray, 4.5));// Key: 4.5 => Compile time error!
The asList() method in the Arrays class and the toArray() method in the Collection interface provide the bidirectional bridge between arrays and collections. The asList() method of the Arrays class creates List views of arrays.
<E> List<E> asList(E... elements)
Returns a fixed-size list view backed by the array corresponding to the vararg argument elements.
Changes to the List view reflect in the array, and vice versa. The List is said to be backed by the array. The List size is equal to the array length and cannot be changed.
The code below illustrates using the asList() method. The list1 is backed by the array1 at (1). The list2 is backed by an implicit array of Integers at (2). An array of primitive type cannot be passed as argument to this method, as evident by the compile time error at (3).
Integer[] array1 = new Integer[] {9, 1, 1};
int[] array2 = new int[] {9, 1, 1};
List<Integer> list1 = Arrays.asList(array1); // (1) An array of Integers
List<Integer> list2 = Arrays.asList(9, 1, 1); // (2) A var-arg list
// List<Integer> intList3 = Arrays.asList(array2); // (3) Compile-time error!
Various operations on the list1 show how changes are reflected in the backing array1. Elements cannot be added to the list view (shown at (5)), and elements cannot be removed from a list view (shown at (10)). An UnsupportedOperationException is thrown in both cases. An element at a given position can be changed, as shown at (6). The change is reflected in the list1 and the array1, as shown at (7a) and (7b), respectively. A sublist view is created from the list1 at (8), and sorted at (11). The changes in the sublist1 are reflected in the list1 and the backed array1.
System.out.println(list1); // (4) [9, 1, 1]
// list1.add(10); // (5) UnsupportedOperationException
list1.set(0, 10); // (6)
System.out.println(list1); // (7a) [10, 1, 1]
System.out.println(Arrays.toString(array1)); // (7b) [10, 1, 1]
List<Integer> sublist1 = list1.subList(0, 2); // (8)
System.out.println(sublist1); // (9) [10, 1]
// sublist1.clear(); // (10) UnsupportedOperationException
Collections.sort(sublist1); // (11)
System.out.println(sublist1); // (12a) [1, 10]
System.out.println(list1); // (12b) [1, 10, 1]
System.out.println(Arrays.toString(array1)); // (12c) [1, 10, 1]
The code below shows how duplicates can be eliminated from an array using these two methods:
String[] jiveArray = new String[] {"java", "jive", "java", "jive"};
Set<String> jiveSet = new HashSet<String>(Arrays.asList(jivearray)); // (1)
String[] uniqueJiveArray = jiveSet.toArray(new String[0]); // (2)
At (1), the jiveArray is used to create a List, which, in turn, is used to create a Set. At (2) the argument to the toArray() method specifies the type of the array to be created from the set. The final array uniqueJiveArray does not contain duplicates.
The methods toString() (p. 845) and fill() (Example 15.21, Example 15.22) have previously been used in this chapter. The type can be any primitive type or Object in these methods.
void fill(type [] a, type val)
void fill(type [] a, int fromIndex, int toIndex, type val)
Assigns the specified value to each element of the specified array or specified range.
String toString(type [] a)
String deepToString(Object[] a)
Returns a text representation of the contents (or “deep contents”) of the specified array.
Review Questions
15.37 Which statement is true about the following program?
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class WhatIsThis {
public static void main(String[] args) {
List<StringBuilder> list = new ArrayList<StringBuilder>();
list.add(new StringBuilder("B"));
list.add(new StringBuilder("A"));
list.add(new StringBuilder("C"));
Collections.sort(list, Collections.reverseOrder());
System.out.println(list.subList(1,2));
}
}
Select the one correct answer.
(a) The program will compile and print the following when run: [B].
(b) The program will compile and print the following when run: [B, A].
(c) The program will compile, but throw an exception when run.
(d) The program will not compile.
15.38 Which statement is true about the following program?
// NEW RQ
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class WhatIsThat {
public static void main(String[] args) {
List<StringBuilder> list = new ArrayList<StringBuilder>();
list.add(new StringBuilder("B"));
list.add(new StringBuilder("A"));
list.add(new StringBuilder("D"));
list.add(new StringBuilder("C"));
StringBuilder[] sbArray = list.toArray(new StringBuilder[0]);
Collections.sort(list);
Collections.sort(list, null);
Collections.sort(list, Collections.reverseOrder());
System.out.println("List: " + list);
Arrays.sort(sbArray);
Arrays.sort(sbArray, null);
Arrays.sort(sbArray, Collections.reverseOrder());
System.out.println("Array: " + Arrays.toString(sbArray));
}
}
Select the one correct answer.
(a) The program will compile and print the following when run: [B].
(b) The program will compile and print the following when run: [B, A].
(c) The program will compile, but throw an exception when run.
(d) The program will not compile.
15.39 Which statements are true about the following program?
import java.util.Arrays;
public class GetThatIndex {
public static void main(String[] args) {
if (args.length != 1) return;
printIndex(args[0]);
}
public static void printIndex(String key) {
String[] strings = {"small", "smaller", "smallest", "tiny"};
System.out.println(Arrays.binarySearch(strings , key));
}
}
Select the two correct answers.
(a) The largest value ever printed by the printIndex() method is 3.
(b) The largest value ever printed by the printIndex() method is 4.
(c) The largest value ever printed by the printIndex() method is 5.
(d) The smallest value ever printed by the printIndex() method is 0.
(e) The smallest value ever printed by the printIndex() method is -4.
(f) The smallest value ever printed by the printIndex() method is -5.
(g) The smallest value ever printed by the printIndex() method is -3.
15.40 Given that the following program compiles and prints the following output when run: 1 1 1.
import java.util.*;
public class SoulSearching {
public static void main(String[] args) {
String[] array = {"smallest", "small", "tiny", "smaller"};
List<String> list1 = Arrays.___________(array);
Collections.__________(list1);
int index1 = Collections._____________(list1, "smaller");
System.out.print(index1 + " ");
List<String> list2 = Arrays.___________(array);
Collections.__________(list2);
int index2 = list2.__________("smaller");
System.out.print(index2 + " ");
Arrays._________(array);
int index3 = Arrays.____________(array, "smaller");
System.out.println(index3);
}
}
Which method names can be used to fill the blanks without violating the behavior of the program?
Select the four correct answers.
(a) asList
(b) contains
(c) sort
(d) findIndex
(e) indexOf
(f) binarySearch
(g) search
(h) toList
(i) toArray
(j) subList
15.41 What will the program print when compiled and run?
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class LastOrders {
public static void main(String[] args) {
String[] array = {"slurs", "slush", "slurps", "slurry"};
List<String> list1 = Arrays.asList(array);
Collections.sort(list1, LastOrders.comparatorX());
int index1 = Collections.binarySearch(list1, "slurry",
LastOrders.comparatorX());
System.out.println (list1 + ": slurry at " + index1);
}
public static Comparator<String> comparatorX() {
return new Comparator<String>() {
public int compare(String str1, String str2) {
StringBuilder sb1 = new StringBuilder(str1);
StringBuilder sb2 = new StringBuilder(str2);
return sb2.reverse().toString().compareTo(sb1.reverse().toString());
}
};
}
}
Select the one correct answer.
(a) [slush, slurs, slurry, slurps]: slurry at 2
(b) [slush, slurps, slurs, slurry]: slurry at 3
(c) [slurry, slurs, slurps, slush]: slurry at 0
(d) [slurps, slurry, slurs, slush]: slurry at 1
Chapter Summary
The following information was included in this chapter:
• overriding the equals() and the hashCode() methods from the Object class.
• implementing the Comparable and the Comparator interfaces for ordering of elements.
• an overview of the collections framework in the java.util package: core interfaces and their implementations.
• functionality specified by the Collection interface and its role in the collections framework.
• sets, and how their functionality is defined by the Set interface and implemented by HashSet and LinkedHashSet.
• sorted and navigable sets, and how their functionality is defined by the SortedSet and NavigableSet interfaces, respectively, and implemented by TreeSet.
• lists, and how their functionality is defined by the List interface and implemented by ArrayList, Vector, and LinkedList.
• queues and deques, and how their functionality is defined by the Queue and Deque interfaces, and implemented by PriorityQueue and ArrayDeque, respectively.
• maps, and how their functionality is defined by the Map interface and implemented by HashMap, LinkedHashMap, and Hashtable.
• sorted and navigable maps, and how their functionality is defined by the SortedMap and NavigableMap interfaces, respectively, and implemented by TreeMap.
• utility methods found in the Collections and Arrays classes, with emphasis on sorting and searching in lists and arrays.
Programming Exercises
15.1 Write a method that takes a string and returns the number of unique characters in the string. It is expected that a string with the same character sequence may be passed several times to the method. Since the counting operation can be time consuming, the method should cache the results so that when the method is given a string previously encountered, it will simply retrieve the stored result. Use collections and maps where appropriate.
15.2 Write a program that creates a concordance of characters occurring in a string (i.e., which characters occur where in a string). Read the string from the command line.
Here is an example of how to run the program:
>java Concordance Hello World
{d=[9], o=[4, 6], r=[7], W=[5], H=[0], l=[2, 3, 8], e=[1]}