- •Contents
- •Preface
- •Introduction to Computers, the Internet and the Web
- •1.3 Computer Organization
- •Languages
- •1.9 Java Class Libraries
- •1.12 The Internet and the World Wide Web
- •1.14 General Notes about Java and This Book
- •Sections
- •Introduction to Java Applications
- •2.4 Displaying Text in a Dialog Box
- •2.5 Another Java Application: Adding Integers
- •2.8 Decision Making: Equality and Relational Operators
- •Introduction to Java Applets
- •3.2 Sample Applets from the Java 2 Software Development Kit
- •3.3 A Simple Java Applet: Drawing a String
- •3.4 Two More Simple Applets: Drawing Strings and Lines
- •3.6 Viewing Applets in a Web Browser
- •3.7 Java Applet Internet and World Wide Web Resources
- •Repetition)
- •Class Attributes
- •5.8 Labeled break and continue Statements
- •5.9 Logical Operators
- •Methods
- •6.2 Program Modules in Java
- •6.7 Java API Packages
- •6.13 Example Using Recursion: The Fibonacci Series
- •6.16 Methods of Class JApplet
- •Class Operations
- •Arrays
- •7.6 Passing Arrays to Methods
- •7.8 Searching Arrays: Linear Search and Binary Search
- •Collaboration Among Objects
- •8.2 Implementing a Time Abstract Data Type with a Class
- •8.3 Class Scope
- •8.4 Controlling Access to Members
- •8.5 Creating Packages
- •8.7 Using Overloaded Constructors
- •8.9 Software Reusability
- •8.10 Final Instance Variables
- •Classes
- •8.16 Data Abstraction and Encapsulation
- •9.2 Superclasses and Subclasses
- •9.5 Constructors and Finalizers in Subclasses
- •Conversion
- •9.11 Type Fields and switch Statements
- •9.14 Abstract Superclasses and Concrete Classes
- •9.17 New Classes and Dynamic Binding
- •9.18 Case Study: Inheriting Interface and Implementation
- •9.19 Case Study: Creating and Using Interfaces
- •9.21 Notes on Inner Class Definitions
- •Strings and Characters
- •10.2 Fundamentals of Characters and Strings
- •10.21 Card Shuffling and Dealing Simulation
- •Handling
- •Graphics and Java2D
- •11.2 Graphics Contexts and Graphics Objects
- •11.5 Drawing Lines, Rectangles and Ovals
- •11.9 Java2D Shapes
- •12.12 Adapter Classes
- •Cases
- •13.3 Creating a Customized Subclass of JPanel
- •Applications
- •Controller
- •Exception Handling
- •14.6 Throwing an Exception
- •14.7 Catching an Exception
- •Multithreading
- •15.3 Thread States: Life Cycle of a Thread
- •15.4 Thread Priorities and Thread Scheduling
- •15.5 Thread Synchronization
- •15.9 Daemon Threads
- •Multithreading
- •Design Patterns
- •Files and Streams
- •16.2 Data Hierarchy
- •16.3 Files and Streams
- •Networking
- •17.2 Manipulating URIs
- •17.3 Reading a File on a Web Server
- •17.4 Establishing a Simple Server Using Stream Sockets
- •17.5 Establishing a Simple Client Using Stream Sockets
- •17.9 Security and the Network
- •18.2 Loading, Displaying and Scaling Images
- •18.3 Animating a Series of Images
- •18.5 Image Maps
- •18.6 Loading and Playing Audio Clips
- •18.7 Internet and World Wide Web Resources
- •Data Structures
- •19.4 Linked Lists
- •20.8 Bit Manipulation and the Bitwise Operators
- •Collections
- •21.8 Maps
- •21.9 Synchronization Wrappers
- •21.10 Unmodifiable Wrappers
- •22.2 Playing Media
- •22.3 Formatting and Saving Captured Media
- •22.5 Java Sound
- •22.8 Internet and World Wide Web Resources
- •Hexadecimal Numbers
21
Collections
Objectives
•To understand what collections are.
•To understand Java 2’s new array capabilities.
•To use the collections framework implementations.
•To be able to use collections framework algorithms to manipulate various collections.
•To be able to use the collections framework interfaces to program polymorphically.
•To be able to use iterators to walk through the elements of a collection.
•To understand synchronization wrappers and modifiability wrappers.
I think this is the most extraordinary collection of talent, of human knowledge, that has ever been gathered together at the White House—with the possible exception of when Thomas Jefferson dines alone.
John F. Kennedy
The shapes a bright container can contain!
Theodore Roethke
Journey over all the universe in a map.
Miguel de Cervantes
It is an immutable law in business that words are words, explanations are explanations, promises are promises — but only performance is reality.
Harold S. Green
© Copyright 1992–2002 by Deitel & Associates, Inc. All Rights Reserved. 7/12/01
1202 |
Collections |
Chapter 21 |
Outline
21.1Introduction
21.2Collections Overview
21.3Class Arrays
21.4Interface Collection and Class Collections
21.5Lists
21.6Algorithms
21.6.1Algorithm sort
21.6.2Algorithm shuffle
21.6.3Algorithms reverse, fill, copy, max and min
21.6.4Algorithm binarySearch
21.7Sets
21.8Maps
21.9Synchronization Wrappers
21.10Unmodifiable Wrappers
21.11Abstract Implementations
21.12(Optional) Discovering Design Patterns: Design Patterns Used in Package java.util
Summary • Terminology • Self-Review Exercises • Answers to Self-Review Exercises • Exercises
21.1 Introduction
In Chapter 19, we discussed how to create and manipulate data structures. The discussion was “low level,” in the sense that we painstakingly created each element of each data structure dynamically with new and modified the data structures by directly manipulating their elements and references to their elements. In this chapter, we consider the Java collections framework, which gives the programmer access to prepackaged data structures, as well as algorithms for manipulating those data structures.
With collections, instead of creating data structures, the programmer simply uses existing data structures, without concern for how the data structures are implemented. This methodology is a marvelous example of code reuse. Programmers can code faster and can expect excellent performance, maximizing execution speed and minimizing memory consumption. We will discuss the interfaces of the collections framework, the implementation classes, the algorithms that process them and the iterators that “walk” through them.
Some examples of collections are the cards you hold in a card game, your favorite songs stored in your computer and the real-estate records in your local registry of deeds (which map book numbers and page numbers to property owners). Java 2 provides an entire collections framework, whereas earlier versions of Java provided just a few collection classes, such as Hashtable, Stack and Vector (see Chapter 20), as well as built-in array capabilities. If you know C++, you will be familiar with its collections framework,
© Copyright 1992–2002 by Deitel & Associates, Inc. All Rights Reserved. 7/12/01
Chapter 21 |
Collections |
1203 |
which is called the Standard Template Library (STL). (See Chapter 20 of C++ How to Program, Third Edition, by H. M. Deitel and P. J. Deitel, ©2001, Prentice Hall).
The Java collections framework provides ready-to-go, reusable componentry; you do not need to write your own collection classes. The collections are standardized so applications can share them easily, without having to be concerned with the details of their implementation. These collections are written for broad reuse. They are tuned for rapid execution as well as efficient use of memory. The collections framework encourages further reusability. As new data structures and algorithms are developed that fit this framework, a large base of programmers already will be familiar with the interfaces and algorithms implemented by those data structures.
21.2 Collections Overview
A collection is a data structure—actually, an object—that can hold other objects. The collection interfaces define the operations that a program can perform on each type of collection. The collection implementations execute the operations in particular ways, some more appropriate than others for specific kinds of applications. Thecollection implementations are carefully constructed for rapid execution and efficient use of memory. Collections encourage software reuse by providing convenient functionality.
The collections framework provides interfaces that define the operations to be performed generically on various types of collections. Some of the interfaces are Collection, Set, List and Map. Several implementations of these interfaces are provided within the framework. Programmers may also provide implementations specific to their own requirements.
The collections framework includes a number of other features that minimize the amount of coding programmers need to do to create and manipulate collections.
The classes and interfaces that comprise the collections framework are members of package java.util. In the next section, we begin our discussion by examining the capabilities that have been added for array manipulation.
21.3 Class Arrays
We begin our discussion of the collections framework by looking at class Arrays, which provides static methods for manipulating arrays. In Chapter 7, our discussion of array manipulation was “low level,” in the sense that we wrote the actual code to sort and search arrays. Class Arrays provides “high-level” methods, such as binarySearch for searching a sorted array, equals for comparing arrays, fill for placing values into an array and sort for sorting an array. These methods are overloaded for primitive-type arrays and Object arrays. Figure 21.1 demonstrates the use of these methods.
1 // Fig. 21.1: UsingArrays.java
2 // Using Java arrays.
3
4 // Java core packages
5import java.util.*;
Fig. 21.1 Using methods of class Arrays (part 1 of 3).
© Copyright 1992–2002 by Deitel & Associates, Inc. All Rights Reserved. 7/12/01
1204 |
Collections |
Chapter 21 |
6
7public class UsingArrays {
8private int intValues[] = { 1, 2, 3, 4, 5, 6 };
9 private double doubleValues[] = { 8.4, 9.3, 0.2, 7.9, 3.4 }; 10 private int filledInt[], intValuesCopy[];
11
12// initialize arrays
13public UsingArrays()
14{
15filledInt = new int[ 10 ];
16intValuesCopy = new int[ intValues.length ];
18 |
Arrays.fill( |
filledInt, 7 |
); |
// |
fill with 7s |
19 |
|
|
|
|
|
20 |
Arrays.sort( |
doubleValues |
); |
// |
sort doubleValues |
21 |
|
|
|
|
|
22 |
System.arraycopy( intValues, 0, intValuesCopy, |
230, intValues.length );
24}
25
26// output values in each array
27public void printArrays()
28{
29System.out.print( "doubleValues: " );
31 |
for ( int count = 0; count < doubleValues.length; count++ ) |
32 |
System.out.print( doubleValues[ count ] + " " ); |
33 |
|
34 |
System.out.print( "\nintValues: " ); |
35 |
|
36 |
for ( int count = 0; count < intValues.length; count++ ) |
37 |
System.out.print( intValues[ count ] + " " ); |
38 |
|
39 |
System.out.print( "\nfilledInt: " ); |
40 |
|
41 |
for ( int count = 0; count < filledInt.length; count++ ) |
42 |
System.out.print( filledInt[ count ] + " " ); |
43 |
|
44 |
System.out.print( "\nintValuesCopy: " ); |
45 |
|
46 |
for ( int count = 0; count < intValuesCopy.length; count++ ) |
47 |
System.out.print( intValuesCopy[ count ] + " " ); |
48 |
|
49System.out.println();
50}
51
52// find value in array intValues
53public int searchForInt( int value )
54{
55return Arrays.binarySearch( intValues, value );
56}
57
Fig. 21.1 Using methods of class Arrays (part 2 of 3).
© Copyright 1992–2002 by Deitel & Associates, Inc. All Rights Reserved. 7/12/01
Chapter 21 |
Collections |
1205 |
58// compare array contents
59public void printEquality()
60{
61boolean b = Arrays.equals( intValues, intValuesCopy );
63 |
System.out.println( "intValues " + ( b ? "==" : "!=" ) |
64 |
+ " intValuesCopy" ); |
65 |
|
66 |
b = Arrays.equals( intValues, filledInt ); |
67 |
|
68 |
System.out.println( "intValues " + ( b ? "==" : "!=" ) |
69 |
+ " filledInt" ); |
70 |
} |
71 |
|
72// execute application
73public static void main( String args[] )
74{
75UsingArrays usingArrays = new UsingArrays();
77usingArrays.printArrays();
78usingArrays.printEquality();
80int location = usingArrays.searchForInt( 5 );
81System.out.println( ( location >= 0 ?
82 |
"Found 5 at element " + location : "5 not found" ) + |
83 |
" in intValues" ); |
84 |
|
85location = usingArrays.searchForInt( 8763 );
86System.out.println( ( location >= 0 ?
87 |
"Found 8763 at element " + location : |
88"8763 not found" ) + " in intValues" );
89}
90
91 } // end class UsingArrays
doubleValues: 0.2 3.4 7.9 8.4 9.3 intValues: 1 2 3 4 5 6 filledInt: 7 7 7 7 7 7 7 7 7 7 intValuesCopy: 1 2 3 4 5 6 intValues == intValuesCopy intValues != filledInt
Found 5 at element 4 in intValues 8763 not found in intValues
Fig. 21.1 Using methods of class Arrays (part 3 of 3).
Line 18 calls Arrays static method fill to populate all 10 elements of array filledInt with 7s. Overloaded versions of fill allow the programmer to populate a specific range of elements with the same value.
Line 20 sorts the elements of array doubleValues. Overloaded versions of sort allow the programmer to sort a specific range of elements. Arrays static method sort orders the array’s elements in ascending order by default. We discuss how to sort in descending order later in the chapter.
© Copyright 1992–2002 by Deitel & Associates, Inc. All Rights Reserved. 7/12/01
1206 |
Collections |
Chapter 21 |
Lines 22–23 copy array intValues into array intValuesCopy. The first argument (intValues) passed to System static method arraycopy is the array from which elements are copied. The second argument (0) is the array (i.e., intValues) subscript that specifies the starting point in the range of elements to copy. This value can be any valid array subscript. The third argument (intValuesCopy) specifies the array that stores the copy. The fourth argument (0) specifies the subscript in the destination array (i.e., intValuesCopy) where the first copied element is stored. The last argument (intValues.length) specifies the number of source-array (i.e., intValues) elements to copy.
Line 55 calls Arrays static method binarySearch to perform a binary search on intValues, using value as the key. If value is found, binarySearch returns the subscript location where value was found. If value is not found, binarySearch returns a negative value. The negative value returned is based on the search key’s insertion point—the index where the key would be inserted in the binary search tree if this were an insert operation. After binarySearch determines the insertion point, it changes the insertion point’s sign to negative and subtracts 1 to obtain the return value. For example, in Fig. 21.1, the insertion point for the value 8763 is the element with subscript 6 in the array. Method binarySearch changes the insertion point to –6 and subtracts 1 from it, then returns the value –7. This return value is useful for adding elements to a sorted array.
Common Programming Error 21.1
Passing an unsorted array to binarySearch is a logic error. The value returned by binarySearch is undefined.
Lines 61 and 66 call method equals to determine whether the elements of two arrays are equivalent. If they are equal, method equals returns true; otherwise, it returns false.
One of the most important features of the collection framework is the ability to manipulate the elements of one collection type through a different collection type, regardless of the collection’s internal implementation. The public set of methods through which collections are manipulated is called a view.
Class Arrays provides static method asList for viewing an array as a List collection type (a type that encapsulates behavior similar to that of the linked lists created in Chapter 19; we will say more about Lists later in the chapter). A List view allows the programmer to manipulate the array programmatically as if it were a List by calling List methods. Any modifications made through the List view change the array, and any modifications made to the array change the List view. Figure 21.2 demonstrates method asList.
1 // Fig. 21.2: UsingAsList.java
2 // Using method asList
3
4 // Java core packages
5 import java.util.*;
6
7public class UsingAsList {
8 private String values[] = { "red", "white", "blue" }; 9 private List list;
10
Fig. 21.2 Using static method asList (part 1 of 2).
© Copyright 1992–2002 by Deitel & Associates, Inc. All Rights Reserved. 7/12/01
Chapter 21 |
Collections |
1207 |
11// initialize List and set value at location 1
12public UsingAsList()
13{
14 |
list = Arrays.asList( values ); |
// |
get List |
|
15 |
list.set( 1, "green" ); |
// |
change a |
value |
16 |
} |
|
|
|
17 |
|
|
|
|
18// output List and array
19public void printElements()
20{
21System.out.print( "List elements : " );
23 |
for ( int count = 0; count < list.size(); count++ ) |
24 |
System.out.print( list.get( count ) + " " ); |
25 |
|
26 |
System.out.print( "\nArray elements: " ); |
27 |
|
28 |
for ( int count = 0; count < values.length; count++ ) |
29 |
System.out.print( values[ count ] + " " ); |
30 |
|
31System.out.println();
32}
33
34// execute application
35public static void main( String args[] )
36{
37new UsingAsList().printElements();
38}
39
40 } // end class UsingAsList
List elements : red green blue
Array elements: red green blue
Fig. 21.2 Using static method asList (part 2 of 2).
Line 9 declares a List reference called list. Line 14 uses static Arrays method asList to obtain a fixed-size List view of array values.
Performance Tip 21.1
Arrays.asList creates a fixed-size List that operates faster than any of the provided List implementations.
Common Programming Error 21.2
A List created with Arrays.asList is fixed in size; calling methods add or remove throws an UnsupportedOperationException.
Line 15 calls List method set to change the contents of List element 1 to "green". Because the program views the array as a List, line 15 changes array element values[ 1 ] from "white" to "green". Any changes made to the List view are made to the underlying array object.
© Copyright 1992–2002 by Deitel & Associates, Inc. All Rights Reserved. 7/12/01
1208 Collections Chapter 21
Software Engineering Observation 21.1
With the collections framework, there are many methods that apply to Lists and Collec- tions that you would like to be able to use for arrays. Arrays.asList allows you to pass an array into a List or Collection parameter.
Line 23 calls List method size to get the number of items in the List. Line 24 calls List method get to retrieve an individual item from the List. Notice that the value returned by size is equal to the number of elements in array values and that the items returned by get are the elements of array values.
21.4 Interface Collection and Class Collections
Interface Collection is the root interface in the collections hierarchy from which interfaces Set (a collection that does not contain duplicates—discussed in Section 21.7) and List are derived. Interface Collection contains bulk operations (i.e., operations performed on the entire collection) for adding, clearing, comparing and retaining objects (also called elements) in the collection. Collections can also be converted to arrays. In addition, interface Collection provides a method that returns an Iterator. Iterators are similar to the Enumerations introduced in Chapter 20. The primary difference between an Iterator and an Enumeration is that Iterators can remove elements from a collection, whereas Enumerations cannot. Other methods of interface Collection enable a program to determine a collection’s size, a collection’s hash code and whether a collection is empty.
Software Engineering Observation 21.2
Collection is used commonly as a method parameter type to allow polymorphic process- ing of all objects that implement interface Collection.
Software Engineering Observation 21.3
Most collection implementations provide a constructor that takes a Collection argu- ment, thereby allowing one collection type to be treated as another collection type.
Class Collections provides static methods that manipulate collections polymorphically. These methods implement algorithms for searching, sorting, and so on. You will learn more about these algorithms in Section 21.6. Other Collections methods include wrapper methods that return new collections. We discuss wrapper methods in Section 21.9 and Section 21.10.
21.5 Lists
A List is an ordered Collection that can contain duplicate elements. A List is sometimes called a sequence. Like arrays, Lists are zero based (i.e., the first element’s index is zero). In addition to the interface methods inherited from Collection, List provides methods for manipulating elements via their indices, manipulating a specified range of elements, searching the elements and getting a ListIterator to access the elements.
Interface List is implemented by classes ArrayList, LinkedList and Vector. Class ArrayList is a resizable-array implementation of a List. Class ArrayList’s behavior and capabilities are similar to those of the Vector class, introduced in Chapter 20. A LinkedList is a linked-list implementation of a List.
© Copyright 1992–2002 by Deitel & Associates, Inc. All Rights Reserved. 7/12/01
Chapter 21 |
Collections |
1209 |
Performance Tip 21.2 |
ArrayLists behave like unsynchronized Vectors and therefore execute faster than |
Vectors, because ArrayLists are not thread safe. |
Software Engineering Observation 21.4
LinkedLists can be used to create stacks, queues, trees and deques (double-ended queues).
Figure 21.3 uses an ArrayList to demonstrate some of the capabilities of Collection interfaces. The program places Strings and Colors in an ArrayList and uses an Iterator to remove the Strings from the ArrayList collection.
1 // Fig. 21.3: CollectionTest.java
2 // Using the Collection interface
3
4 // Java core packages
5 import java.awt.Color;
6 import java.util.*;
7
8public class CollectionTest {
9 private String colors[] = { "red", "white", "blue" };
10
11// create ArrayList, add objects to it and manipulate it
12public CollectionTest()
13{
14ArrayList list = new ArrayList();
15 |
|
|
16 |
// add objects to list |
|
17 |
list.add( Color.magenta ); |
// add a color object |
18 |
|
|
19 |
for ( int count = 0; count < colors.length; count++ ) |
|
20 |
list.add( colors[ count ] ); |
|
21 |
|
|
22 |
list.add( Color.cyan ); |
// add a color object |
23 |
|
|
24// output list contents
25System.out.println( "\nArrayList: " );
27 for ( int count = 0; count < list.size(); count++ ) 28 System.out.print( list.get( count ) + " " );
29
30// remove all String objects
31removeStrings( list );
32
33// output list contents
34System.out.println( "\n\nArrayList after calling" +
35 |
" removeStrings: " ); |
36 |
|
37 |
for ( int count = 0; count < list.size(); count++ ) |
38System.out.print( list.get( count ) + " " );
39}
Fig. 21.3 Using an ArrayList to demonstrate interface Collection (part 1 of 2).
© Copyright 1992–2002 by Deitel & Associates, Inc. All Rights Reserved. 7/12/01
1210 |
Collections |
Chapter 21 |
40
41// remove String objects from Collection
42public void removeStrings( Collection collection )
43{
44// get iterator
45Iterator iterator = collection.iterator();
46
47// loop while collection has items
48while ( iterator.hasNext() )
49 |
|
50 |
if ( iterator.next() instanceof String ) |
51 |
iterator.remove(); // remove String object |
52 |
} |
53 |
|
54// execute application
55public static void main( String args[] )
56{
57new CollectionTest();
58}
59
60 } // end class CollectionTest
ArrayList:
java.awt.Color[r=255,g=0,b=255] red white blue java.awt.Color [r=0,g=255,b=255]
ArrayList after calling removeStrings: java.awt.Color[r=255,g=0,b=255] java.awt.Color[r=0,g=255,b=255]
Fig. 21.3 Using an ArrayList to demonstrate interface Collection (part 2 of 2).
Line 14 creates reference list and initializes it with an instance of an ArrayList. Lines 17–22 populate list with Color and String objects. Lines 25–28 output each element of list. Line 27 calls List method size to get the number of ArrayList elements. Line 28 uses List method get to retrieve individual element values. Line 31 calls programmer-defined method removeStrings (defined on lines 42–52), passing list to it as an argument. Method removeStrings deletes Strings from a collection. Lines 34–38 print the elements of list after removeStrings removes the String objects from the list. Notice that the output in Fig. 21.3 contains only Colors.
Method removeStrings declares one parameter of type Collection that allows any Collection to be passed as an argument to this method. The method accesses the elements of the Collection via an Iterator. Line 45 calls method iterator to get an Iterator for the Collection. The while loop condition on line 48 calls Iterator method hasNext to determine if the Collection contains any more elements. Method hasNext returns true if another element exists and false otherwise.
The if condition at line 50 calls Iterator method next to obtain a reference to the next element, then uses instanceof to determine whether the object is a String. If so, line 51 calls Iterator method remove to remove the String from the Collection.
© Copyright 1992–2002 by Deitel & Associates, Inc. All Rights Reserved. 7/12/01
Chapter 21 |
Collections |
1211 |
Common Programming Error 21.3
When iterating through a collection with an Iterator, use Iterator method remove to delete an element from the collection. Using the collection’s remove method will result in a ConcurrentModificationException.
Figure 21.4 demonstrates operations on LinkedLists. The program creates two LinkedLists that each contain Strings. The elements of one List are added to the other. Then, all the Strings are converted to uppercase, and a range of elements is deleted.
1 // Fig. 21.4: ListTest.java
2 // Using LinkLists
3
4 // Java core packages
5 import java.util.*;
6
7public class ListTest {
8 private String colors[] = { "black", "yellow", "green",
9"blue", "violet", "silver" };
10private String colors2[] = { "gold", "white", "brown",
11"blue", "gray", "silver" };
12
13// set up and manipulate LinkedList objects
14public ListTest()
15{
16LinkedList link = new LinkedList();
17LinkedList link2 = new LinkedList();
18
19// add elements to each list
20for ( int count = 0; count < colors.length; count++ ) {
21 |
link.add( colors[ count ] ); |
22link2.add( colors2[ count ] );
23}
24 |
|
|
25 |
link.addAll( link2 ); |
// concatenate lists |
26 |
link2 = null; |
// release resources |
27 |
|
|
28 |
printList( link ); |
|
29 |
|
|
30 |
uppercaseStrings( link ); |
|
31 |
|
|
32 |
printList( link ); |
|
33 |
|
|
34System.out.print( "\nDeleting elements 4 to 6..." );
35removeItems( link, 4, 7 );
36
37printList( link );
38}
39
40// output List contents
41public void printList( List list )
42{
43System.out.println( "\nlist: " );
Fig. 21.4 Using Lists and ListIterators (part 1 of 2).
© Copyright 1992–2002 by Deitel & Associates, Inc. All Rights Reserved. 7/12/01
1212 |
Collections |
Chapter 21 |
44
45 for ( int count = 0; count < list.size(); count++ ) 46 System.out.print( list.get( count ) + " " );
47
48System.out.println();
49}
50
51// locate String objects and convert to uppercase
52public void uppercaseStrings( List list )
53{
54ListIterator iterator = list.listIterator();
56 |
while ( iterator.hasNext() ) { |
|
57 |
Object object = iterator.next(); |
// get item |
58 |
|
|
59 |
if ( object instanceof String ) |
// check for String |
60 |
iterator.set( |
|
61 |
( ( String ) object ).toUpperCase() ); |
62}
63}
64
65// obtain sublist and use clear method to delete sublist items
66public void removeItems( List list, int start, int end )
67{
68list.subList( start, end ).clear(); // remove items
69}
70
71// execute application
72public static void main( String args[] )
73{
74new ListTest();
75}
76
77 } // end class ListTest
list:
black yellow green blue violet silver gold white brown blue gray silver
list:
BLACK YELLOW GREEN BLUE VIOLET SILVER GOLD WHITE BROWN BLUE GRAY SILVER
Deleting elements 4 to 6...
list:
BLACK YELLOW GREEN BLUE WHITE BROWN BLUE GRAY SILVER
Fig. 21.4 Using Lists and ListIterators (part 2 of 2).
Lines 16–17 create LinkedLists link and link2, respectively. Lines 20–23 call method add to append elements from arrays colors and colors2 to the end of
LinkedLists link and link2, respectively.
Line 25 calls method addAll to append all elements of link2 to the end of link. Line 26 sets link2 to null, so LinkedList can be garbage collected. Line 28 calls programmer-defined method printList (lines 41–49) to output the link’s contents.
© Copyright 1992–2002 by Deitel & Associates, Inc. All Rights Reserved. 7/12/01
Chapter 21 |
Collections |
1213 |
Line 30 calls programmer-defined method uppercaseStrings (lines 52–63) to convert the String elements to uppercase; then line 32 calls printList to display the modified Strings. Line 34 calls programmer-defined method removeItems (lines 66– 69) to remove the elements at positions 4 through 6 of the list.
Method uppercaseStrings (lines 52–63) changes lowercase String elements in the List passed to it to uppercase Strings. Line 54 calls method listIterator to get a bidirectional iterator (i.e., an iterator that can traverse a List backward or forward) for the List. The while condition calls method hasNext to determine whether the List contains another element. Line 57 gets the next Object from the List and assigns it to object. The if condition tests object to determine whether it is an instanceof class String. If so, lines 60–61 cast object to a String, call method toUpperCase to get an uppercase version of the String and call method set to replace the current String to which iterator refers with the String returned by method toUpperCase.
Programmer-defined method removeItems (lines 66–69) removes a range of items from the list. Line 68 calls method subList to obtain a portion of the List called a sublist. The sublist is simply a view into the List on which subList is called. Method subList takes two arguments—the beginning index for the sublist and the ending index for the sublist. Note that the ending index is not part of the range of the sublist. In this example, we pass 4 for the beginning index and 7 for the ending index to subList. The sublist returned is the elements with indices 4 through 6. Next, the program calls method clear on the sublist to remove the elements of the sublist from the List. Any changes made to a sublist are made to the original List.
Figure 21.5 uses method toArray to get an array from a collection (i.e., LinkedList). The program adds a series of Strings to a LinkedList and calls method toArray to get an array from the LinkedList.
1 // Fig. 21.5: UsingToArray.java
2 // Using method toArray
3
4 // Java core packages
5 import java.util.*;
6
7 public class UsingToArray {
8
9// create LinkedList, add elements and convert to array
10public UsingToArray()
11{
12LinkedList links;
13String colors[] = { "black", "blue", "yellow" };
15 |
links = new LinkedList( Arrays.asList( colors ) ); |
||||
16 |
|
|
|
|
|
17 |
links.addLast( "red" |
); |
// |
add |
as last item |
18 |
links.add( "pink" ); |
|
// |
add |
to the end |
19links.add( 3, "green" ); // add at 3rd index
20links.addFirst( "cyan" ); // add as first item
Fig. 21.5 Using method toArray (part 1 of 2).
© Copyright 1992–2002 by Deitel & Associates, Inc. All Rights Reserved. 7/12/01
1214 |
Collections |
Chapter 21 |
22// get LinkedList elements as an array
23colors = ( String [] ) links.toArray(
24 |
new String[ links.size() ] ); |
25 |
|
26 |
System.out.println( "colors: " ); |
27 |
|
28 |
for ( int count = 0; count < colors.length; count++ ) |
29System.out.println( colors[ count ] );
30}
31
32// execute application
33public static void main( String args[] )
34{
35new UsingToArray();
36}
37
38 } // end class UsingToArray
colors: cyan black blue yellow green red pink
Fig. 21.5 Using method toArray (part 2 of 2).
Line 15 constructs a LinkedList containing the elements of array colors and assigns the LinkedList to links. Line 17 calls method addLast to add "red" to the end of links. Lines 18–19 call method add to add "pink" as the last element and "green" as the element at index 3 (i.e., the fourth element). Line 20 calls addFirst to add "cyan" as the new first item in the LinkedList. [Note: When "cyan" is added as the first element, "green" becomes the fifith element in the LinkedList.]
Lines 23–24 call method toArray to get a String array from links. The array is a copy of the list elements—modifying the contents of the array does not modify the LinkedList. The array passed to method toArray is of the same data type as that returned by toArray. If the number of elements in the array is greater than the number of elements in the LinkedList, toArray copies the list elements into its array argument and returns that array. If the LinkedList has more elements than the number of elements in the array passed to toArray, toArray allocates a new array of the same type it receives as an argument, copies the list elements into the new array and returns the new array.
Common Programming Error 21.4
Passing an array that contains data to toArray can create logic errors. If the number of elements in the array is smaller than the number of elements in the Object calling toArray, new memory is allocated to store the Object’s elements—without preserving the array’s elements. If the number of elements in the array is greater than the number of elements in the Object, the elements of the array (starting at subscript 0) are overwritten with the Object’s elements. Array elements that are not overwritten retain their values.
© Copyright 1992–2002 by Deitel & Associates, Inc. All Rights Reserved. 7/12/01
Chapter 21 |
Collections |
1215 |
21.6 Algorithms
The collections framework provides a variety of high-performance algorithms for manipulating collection elements. These algorithms are implemented as static methods. Algorithms sort, binarySearch, reverse, shuffle, fill and copy operate on
Lists. Algorithms min and max operate on Collections.
Algorithm reverse reverses the elements of a List, fill sets every List element to refer to a specified Object and copy copies references from one List into another.
Software Engineering Observation 21.5
The collections framework algorithms are polymorphic. That is, each algorithm can operate on objects that offer given interfaces without concern to the underlying implementations.
21.6.1 Algorithm sort
Algorithm sort sorts the elements of a List. The order is determined by the natural order of the elements’ type. The sort call may specify as a second argument a Comparator object that specifies how to determine the ordering of the elements.
Algorithm sort uses a stable sort (i.e., a sort that does not reorder equivalent elements while sorting). The sort algorithm is fast. For readers who have studied some complexity theory in data structures or algorithms courses, this sort runs in n log(n) time. (Readers not familiar with complexity theory, may rest assured that this algorithm is extremely fast .
Software Engineering Observation 21.6
The Java API documentation sometimes provides implementation details. For example, sort is implemented as a modified merge sort. Avoid writing code that is dependent on implementation details, because they can change.
Figure 21.6 uses algorithm sort to order the elements of an ArrayList into ascending order (line 21).
1 // Fig. 21.6: Sort1.java
2 // Using algorithm sort
3
4 // Java core packages
5 import java.util.*;
6
7public class Sort1 {
8private static String suits[] =
9 { "Hearts", "Diamonds", "Clubs", "Spades" };
10
11// display array elements
12public void printElements()
13{
14// create ArrayList
15ArrayList list = new ArrayList( Arrays.asList( suits ) );
17// output list
18System.out.println( "Unsorted array elements:\n" + list );
Fig. 21.6 Using algorithm sort (part 1 of 2).
© Copyright 1992–2002 by Deitel & Associates, Inc. All Rights Reserved. 7/12/01
1216 |
Collections |
Chapter 21 |
19
20// sort ArrayList
21Collections.sort( list );
23// output list
24System.out.println( "Sorted array elements:\n" + list );
25}
26
27// execute application
28public static void main( String args[] )
29{
30new Sort1().printElements();
31}
32
33 } // end class Sort1
Unsorted array elements:
[Hearts, Diamonds, Clubs, Spades] Sorted array elements:
[Clubs, Diamonds, Hearts, Spades]
Fig. 21.6 Using algorithm sort (part 2 of 2).
Figure 21.7 sorts the same Strings used in Fig. 21.6 into descending order. The example introduces the Comparator object, for sorting a Collection’s elements in a different order.
1// Fig. 21.7: Sort2.java
2 // Using a Comparator object with algorithm sort
3
4 // Java core packages
5 import java.util.*;
6
7public class Sort2 {
8private static String suits[] =
9 { "Hearts", "Diamonds", "Clubs", "Spades" };
10
11// output List elements
12public void printElements()
13{
14// create List
15List list = Arrays.asList( suits );
17// output List elements
18System.out.println( "Unsorted array elements:\n" + list );
20// sort in descending order using a comparator
21Collections.sort( list, Collections.reverseOrder() );
Fig. 21.7 Using a Comparator object in sort (part 1 of 2).
© Copyright 1992–2002 by Deitel & Associates, Inc. All Rights Reserved. 7/12/01
Chapter 21 |
Collections |
1217 |
23// output List elements
24System.out.println( "Sorted list elements:\n" + list );
25}
26
27// execute application
28public static void main( String args[] )
29{
30new Sort2().printElements();
31}
32
33 } // end class Sort2
Unsorted array elements:
[Hearts, Diamonds, Clubs, Spades] Sorted list elements:
[Spades, Hearts, Diamonds, Clubs]
Fig. 21.7 Using a Comparator object in sort (part 2 of 2).
Line 21 calls Collections’s method sort to order the List view of the array into descending order. The static Collections method reverseOrder returns a Comparator object that represents the collection’s reverse order. For sorting a List view of a String array, the reverse order is a lexicographical comparison—the comparator compares the Unicode values that represent each element—in descending order.
21.6.2 Algorithm shuffle
Algorithm shuffle randomly orders a List’s elements. In Chapter 10, we presented a card shuffling and dealing simulation where we used a loop to shuffle a deck of cards. In Fig. 21.8, we use algorithm shuffle to shuffle the deck of cards. Much of the code is the same as in Fig. 10.19. The shuffling of the deck occurs on line 63, which calls static Collections method shuffle to shuffle the array through the array’s List view.
1// Fig. 21.8: Cards.java
2 // Using algorithm shuffle
3
4 // Java core packages
5 import java.util.*;
6
7 // class to represent a Card in a deck of cards
8class Card {
9 private String face;
10 private String suit;
11
12// initialize a Card
13public Card( String initialface, String initialSuit )
14{
15face = initialface;
16suit = initialSuit;
17}
Fig. 21.8 Card shuffling and dealing example (part 1 of 3).
© Copyright 1992–2002 by Deitel & Associates, Inc. All Rights Reserved. 7/12/01
1218 |
Collections |
Chapter 21 |
18
19// return face of Card
20public String getFace()
21{
22return face;
23}
24
25// return suit of Card
26public String getSuit()
27{
28return suit;
29}
30
31// return String representation of Card
32public String toString()
33{
34StringBuffer buffer =
35 |
new StringBuffer( |
face + " of " + suit ); |
36 |
|
|
37 |
buffer.setLength( 20 |
); |
38 |
|
|
39return buffer.toString();
40}
41
42 } // end class Card
43
44// class Cards definition
45public class Cards {
46private static String suits[] =
47{ "Hearts", "Clubs", "Diamonds", "Spades" };
48private static String faces[] = { "Ace", "Deuce", "Three",
49"Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten",
50"Jack", "Queen", "King" };
51private List list;
52
53// set up deck of Cards and shuffle
54public Cards()
55{
56Card deck[] = new Card[ 52 ];
57 |
|
|
58 |
for ( int count = 0; count < deck.length; count++ ) |
|
59 |
deck[ count ] = new Card( faces[ count % 13 ], |
|
60 |
suits[ count / 13 ] ); |
|
61 |
|
|
62 |
list = Arrays.asList( deck ); |
// get List |
63 |
Collections.shuffle( list ); |
// shuffle deck |
64 |
} |
|
65 |
|
|
66// output deck
67public void printCards()
68{
69int half = list.size() / 2 - 1;
Fig. 21.8 Card shuffling and dealing example (part 2 of 3).
© Copyright 1992–2002 by Deitel & Associates, Inc. All Rights Reserved. 7/12/01
Chapter 21 |
Collections |
1219 |
|
|
|
|
|
71 |
for ( int i = 0, j = half; i <= half; i++, j++ ) |
|
|
72 |
|
System.out.println( |
|
73 |
|
list.get( i ).toString() + list.get( j ) ); |
|
74 |
} |
|
|
75 |
|
|
|
76// execute application
77public static void main( String args[] )
78{
79new Cards().printCards();
80}
81
82 } // end class Cards
King of Diamonds |
Ten of Spades |
Deuce of Hearts |
Five of Spades |
King of Clubs |
Five of Clubs |
Jack of Diamonds |
Jack of Spades |
King of Spades |
Ten of Clubs |
Six of Clubs |
Three of Clubs |
Seven of Clubs |
Jack of Clubs |
Seven of Hearts |
Six of Spades |
Eight of Hearts |
Six of Diamonds |
King of Hearts |
Nine of Diamonds |
Ace of Hearts |
Four of Hearts |
Jack of Hearts |
Queen of Diamonds |
Queen of Clubs |
Six of Hearts |
Seven of Diamonds |
Ace of Spades |
Three of Spades |
Deuce of Spades |
Seven of Spades |
Five of Diamonds |
Ten of Hearts |
Queen of Hearts |
Ten of Diamonds |
Eight of Clubs |
Nine of Spades |
Three of Diamonds |
Four of Spades |
Ace of Clubs |
Four of Clubs |
Four of Diamonds |
Nine of Clubs |
Three of Hearts |
Eight of Diamonds |
Deuce of Diamonds |
Deuce of Clubs |
Nine of Hearts |
Eight of Spades |
Five of Hearts |
Ten of Spades |
Queen of Spades |
|
|
Fig. 21.8 Card shuffling and dealing example (part 3 of 3).
21.6.3 Algorithms reverse, fill, copy, max and min
Class Collections provides algorithms for reversing, filling and copying Lists. Algorithm reverse reverses the order of the elements in a List, and algorithm fill overwrites elements in a List with a specified value. The fill operation is useful for reinitializing a List. Algorithm copy takes two arguments: A destination List and a source List. Each source List element is copied to the destination List. The destination List must be at least as long as the source List: otherwise, an IndexOutOfBoundsException is thrown. If the destination List is longer, the elements not overwritten are unchanged.
© Copyright 1992–2002 by Deitel & Associates, Inc. All Rights Reserved. 7/12/01
1220 |
Collections |
Chapter 21 |
Each of the algorithms we have seen so far operates on Lists. Algorithms min and max each operate on Collections.
Algorithm min returns the smallest element in a List (remember a List is a Collection) and algorithm max returns the largest element in a List. Both of these algorithms can be called with a Comparator object as a second argument. Figure 21.9 demonstrates the use of algorithms reverse, fill, copy, min and max.
1// Fig. 21.9: Algorithms1.java
2 // Using algorithms reverse, fill, copy, min and max
3
4 // Java core packages
5 import java.util.*;
6
7public class Algorithms1 {
8 private String letters[] = { "P", "C", "M" }, lettersCopy[]; 9 private List list, copyList;
10
11// create a List and manipulate it with algorithms from
12// class Collections
13public Algorithms1()
14{
15 |
list = Arrays.asList( letters ); |
// get List |
16lettersCopy = new String[ 3 ];
17copyList = Arrays.asList( lettersCopy );
19System.out.println( "Printing initial statistics: " );
20printStatistics( list );
21 |
|
|
22 |
Collections.reverse( list ); |
// reverse order |
23 |
System.out.println( "\nPrinting statistics after " + |
24"calling reverse: " );
25printStatistics( list );
27Collections.copy( copyList, list ); // copy List
28System.out.println( "\nPrinting statistics after " +
29"copying: " );
30printStatistics( copyList );
32 System.out.println( "\nPrinting statistics after " +
33"calling fill: " );
34Collections.fill( list, "R" );
35printStatistics( list );
36}
37
38// output List information
39private void printStatistics( List listRef )
40{
41System.out.print( "The list is: " );
42 |
|
|
43 |
for ( int k = 0; k < |
listRef.size(); k++ ) |
44 |
System.out.print( |
listRef.get( k ) + " " ); |
45 |
|
|
Fig. 21.9 Using algorithms reverse, fill, copy, max and min (part 1 of 2).
© Copyright 1992–2002 by Deitel & Associates, Inc. All Rights Reserved. 7/12/01
Chapter 21 |
Collections |
1221 |
46System.out.print( "\nMax: " + Collections.max( listRef ) );
47System.out.println(
48" Min: " + Collections.min( listRef ) );
49}
50
51// execute application
52public static void main( String args[] )
53{
54new Algorithms1();
55}
56
57 } // end class Algorithms1
Printing |
initial |
statistics: |
The list |
is: P C |
M |
Max: P |
Min: C |
|
Printing |
statistics after calling reverse: |
|
The list |
is: M C |
P |
Max: P |
Min: C |
|
Printing |
statistics after copying: |
|
The list |
is: M C |
P |
Max: P |
Min: C |
|
Printing |
statistics after calling fill: |
|
The list |
is: R R |
R |
Max: R |
Min: R |
|
|
|
|
Fig. 21.9 Using algorithms reverse, fill, copy, max and min (part 2 of 2).
Line 22 calls Collections method reverse to reverse the order of list. Method reverse takes one List argument. (list is a List view of String array letters.) Array letters now has its elements in reverse order.
Line 27 copies the elements of list into copyList with Collections method copy. Changes to copyList do not change letters—this is a separate List that is not a List view for letters. Method copy requires two List arguments.
Line 34 calls Collections method fill to place the String "R" in each element of list. Because list is a List view of letters, this operation changes each element in letters to "R". Method fill requires a List for the first argument and an Object for the second argument.
Lines 46 and 48, call Collection methods max and min to find the largest element and the smallest element, respectively, in list.
21.6.4 Algorithm binarySearch
Earlier in this text, we studied the high-speed binary search algorithm. This algorithm is built right into the Java collections framework. The binarySearch algorithm locates an
Object in a List (i.e., LinkedList, Vector or ArrayList) If the Object is found, the index (position relative to 0) of that Object is returned. If the Object is not found, binarySearch returns a negative value. Algorithm binarySearch determines this negative value by first calculating the insertion point and changing the insertion point’s sign to negative. Finally, binarySearch subtracts one from the insertion point to obtain the return value.
© Copyright 1992–2002 by Deitel & Associates, Inc. All Rights Reserved. 7/12/01
1222 |
Collections |
Chapter 21 |
Figure 21.10 uses the binarySearch algorithm to search for a series of Strings in an ArrayList.
1 // Fig. 21.10: BinarySearchTest.java
2 // Using algorithm binarySearch
3
4 // Java core packages
5 import java.util.*;
6
7public class BinarySearchTest {
8 private String colors[] = { "red", "white", "blue", "black",
9"yellow", "purple", "tan", "pink" };
10 |
private ArrayList list; |
// ArrayList reference |
11 |
|
|
12// create, sort and output list
13public BinarySearchTest()
14{
15list = new ArrayList( Arrays.asList( colors ) );
16 |
Collections.sort( list ); // sort the ArrayList |
17System.out.println( "Sorted ArrayList: " + list );
18}
19
20// search list for various values
21public void printSearchResults()
22{
23printSearchResultsHelper( colors[ 3 ] ); // first item
24printSearchResultsHelper( colors[ 0 ] ); // middle item
25printSearchResultsHelper( colors[ 7 ] ); // last item
26printSearchResultsHelper( "aardvark" ); // below lowest
27 |
printSearchResultsHelper( "goat" ); |
// does |
not |
exist |
28 |
printSearchResultsHelper( "zebra" ); |
// does |
not |
exist |
29 |
} |
|
|
|
30 |
|
|
|
|
31// helper method to perform searches
32private void printSearchResultsHelper( String key )
33{
34int result = 0;
35
36System.out.println( "\nSearching for: " + key );
37result = Collections.binarySearch( list, key );
38System.out.println(
39 |
( result >= 0 ? "Found at index " + result : |
40"Not Found (" + result + ")" ) );
41}
42
43// execute application
44public static void main( String args[] )
45{
46new BinarySearchTest().printSearchResults();
47}
48
49 } // end class BinarySearchTest
Fig. 21.10 Using algorithm binarySearch (part 1 of 2).
© Copyright 1992–2002 by Deitel & Associates, Inc. All Rights Reserved. 7/12/01
Chapter 21 |
Collections |
1223 |
Sorted ArrayList: black blue pink purple red tan white yellow Searching for: black
Found at index 0
Searching for: red
Found at index 4
Searching for: pink
Found at index 2
Searching for: aardvark
Not Found (-1)
Searching for: goat
Not Found (-3)
Searching for: zebra
Not Found (-9)
Fig. 21.10 Using algorithm binarySearch (part 2 of 2).
Line 16 calls Collections method sort to sort list into ascending order. Line 37 calls Collections method binarySearch to search list for the specified key. Method binarySearch takes a List as the first argument and an Object as the second argument. An overloaded version of binarySearch takes a Comparator object as its third argument, to specify how binarySearch should compare elements.
If the search key is found, method binarySearch returns the List index of the element containing the search key. When a search key is found in the List, the value returned by binarySearch is greater than or equal to zero. If the search key is not found, method binarySearch returns a negative number.
Software Engineering Observation 21.7
Java does not guarantee which item will be found first when a binarySearch is per- formed on a List containing multiple elements equivalent to the search key.
21.7 Sets
A Set is a Collection that contains unique elements (i.e., no duplicate elements). The collections framework contains two Set implementations: —HashSet and TreeSet. HashSet stores its elements in a hash table, and TreeSet stores its elements in a tree. Figure 21.11 uses a HashSet to remove duplicate Strings from an ArrayList.
Programmer-defined method printNonDuplicates (lines 23–35) takes a Collection argument. Line 26 constructs a HashSet from the Collection received as an argument to printNonDuplicates. When the HashSet is constructed, it removes any duplicates in the Collection. By definition, Sets do not contain any duplicates. Line 27 gets an Iterator for the HashSet. The while loop (lines 31–32) calls Iterator methods hasNext and next to access the HashSet elements.
Interface SortedSet extends Set and maintains its elements in sorted order (i.e., the elements’ natural order or an order specified by a Comparator). Class TreeSet implements SortedSet.
© Copyright 1992–2002 by Deitel & Associates, Inc. All Rights Reserved. 7/12/01
1224 |
Collections |
Chapter 21 |
1// Fig. 21.11: SetTest.java
2 // Using a HashSet to remove duplicates
3
4 // Java core packages
5 import java.util.*;
6
7public class SetTest {
8private String colors[] = { "red", "white", "blue",
9 "green", "gray", "orange", "tan", "white", "cyan", 10 "peach", "gray", "orange" };
11
12// create and output ArrayList
13public SetTest()
14{
15ArrayList list;
16
17list = new ArrayList( Arrays.asList( colors ) );
18System.out.println( "ArrayList: " + list );
19printNonDuplicates( list );
20}
21
22// create set from array to eliminate duplicates
23public void printNonDuplicates( Collection collection )
24{
25// create a HashSet and obtain its iterator
26HashSet set = new HashSet( collection );
27Iterator iterator = set.iterator();
28 |
|
29 |
System.out.println( "\nNonduplicates are: " ); |
30 |
|
31 |
while ( iterator.hasNext() ) |
32 |
System.out.print( iterator.next() + " " ); |
33 |
|
34System.out.println();
35}
36
37// execute application
38public static void main( String args[] )
39{
40new SetTest();
41}
42
43 } // end class SetTest
ArrayList: [red, white, blue, green, gray, orange, tan, white, cyan, peach, gray, orange]
Nonduplicates are:
orange cyan green tan white blue peach red gray
Fig. 21.11 Using a HashSet to remove duplicates.
© Copyright 1992–2002 by Deitel & Associates, Inc. All Rights Reserved. 7/12/01
Chapter 21 |
Collections |
1225 |
The program of Fig. 21.12 places Strings into a TreeSet. The Strings are sorted automatically when they are added to the TreeSet. Also, range-view methods (i.e., methods that enable a program to view a portion of a collection) are demonstrated in this example.
1 // Fig. 21.12: SortedSetTest.java
2 // Using TreeSet and SortedSet
3
4 // Java core packages
5 import java.util.*;
6
7public class SortedSetTest {
8 private static String names[] = { "yellow", "green", "black", 9 "tan", "grey", "white", "orange", "red", "green" };
10
11// create a sorted set with TreeSet, then manipulate it
12public SortedSetTest()
13{
14TreeSet tree = new TreeSet( Arrays.asList( names ) );
16System.out.println( "set: " );
17printSet( tree );
18
19// get headSet based upon "orange"
20System.out.print( "\nheadSet (\"orange\"): " );
21printSet( tree.headSet( "orange" ) );
22
23// get tailSet based upon "orange"
24System.out.print( "tailSet (\"orange\"): " );
25printSet( tree.tailSet( "orange" ) );
26
27// get first and last elements
28System.out.println( "first: " + tree.first() );
29System.out.println( "last : " + tree.last() );
30}
31
32// output set
33public void printSet( SortedSet set )
34{
35Iterator iterator = set.iterator();
37 |
while ( iterator.hasNext() ) |
38 |
System.out.print( iterator.next() + " " ); |
39 |
|
40System.out.println();
41}
42
43// execute application
44public static void main( String args[] )
45{
46new SortedSetTest();
47}
Fig. 21.12 Using SortedSets and TreeSets.
© Copyright 1992–2002 by Deitel & Associates, Inc. All Rights Reserved. 7/12/01