Contents
2. Java Technologies
2.0 Dictionary
Java Transaction API (JTA)
Java Transaction API
JavaOne
JRockit
JTA
2.1 Java Design Patterns
2.1.1 Comet
2.3 Servers
2.3.1 Apache Tomcat
2.4 Pure Java
2.4.1 Basic I/O
2.4.2 Java Collections Framework
2.4.2 Threads
3. Design Patterns
3.0 Dictionary
3.1 Comet Design Pattern
3.1.1 Motivations for using Comet
3.1.2 Comet styles
3.1.3 Sources
3.2 Reverse Ajax
3.3 Server-side push
3.4 Asynchronous HTTP
3.4.1 Synchronous message handling overview
3.4.2 Asynchronous message handling
3.4.3 HTTP pipelining
3.4.4 Message content streaming
3.4.5 Streaming input data
3.4.99 Sources
2. Java Technologies
2.0 Dictionary
The terms are applicable to this document and have other meanings in other documents.
- Java Transaction API (JTA) - JTA, or the Java Transaction API, allows you to demarcate transactions in a manner that is independent of the transaction manager implementation. GlassFish Server implements the transaction manager with the Java Transaction Service (JTS).However, your code doesn’t call the JTS methods directly but instead invokes the JTA methods, which then call the lower-level JTS routines.(Java Transaction API - The Java Transaction API is one of the J2EE APIs allowing distributed transactions to be performed across multiple XA resources, in a manner that that is independent of the transaction manager implementation. It provides for:
- Demarcation of transaction boundaries
- X/Open XA API allowing resources to participate in transactions.
See also XA)
- JavaOne - Aannual conference by Sun Microsystems to discuss Java technologies, primarily among Java developers.
- JRockit - A proprietary JVM of BEA Systems that is part of the Oracle Fusion Middleware. JRockit and HotSpot virtual machine are currently being integrated around the release date of JDK 8. JRockit is free and publically available.
- JTA - See Java Transaction API
2.3 Servers
2.3.1 Apache Tomcat
2.3.1.1 Apache Tomcat 6.0
2.3.1.1.1 Implementing Comet
2.3.1.1.1.1 org.apache.catalina.CometProcessor
public interface org.apache.catalina.CometProcessor extends Servlet
Servlets which implement the org.apache.catalina.CometProcessor interface will have their event method invoked rather than the usual service method, according to the event which occurred. The event object parameter gives access to the usual request and response objects. The main difference is that those objects are fully functional at any time between the BEGIN event until an END or ERROR event.
Also see Apache Tomcat 6.0 - Advanced IO and Tomcat
2.4 Pure Java
2.4.1 Basic I/O
Basic I/O is consisted of:
- I/O Streams - A powerful concept that greatly simplifies I/O operations.
- Serialization - Lets a program write whole objects out to streams and read them back again.
- File I/O (Featuring NIO.2) -
- File system operations -
- Random access files -
2.4.1.1 I/O Streams
2.4.1.1.1 Introduction
An I/O Stream represents an input source or an output destination. A stream can represent many different kinds of sources and destinations, including disk files, devices, other programs, and memory arrays.
2.4.1.1.2 Supported Data
Streams support many different kinds of data, including simple bytes, primitive data types, localized characters, and objects.
2.4.1.1.3 Supported Operations
Some streams simply pass on data; others manipulate and transform the data in useful ways.
2.4.1.1.4 I/O Streams Model
No matter how they work internally, all streams present the same simple model to programs that use them: A stream is a sequence of data. A program uses an input stream to read data from a source, one item at a time:
Reading information into a program.
A program uses an output stream to write data to a destination, one item at time:
Writing information from a program.
The data source and data destination pictured above can be anything that holds, generates, or consumes data. Obviously this includes disk files, but a source or destination can also be another program, a peripheral device, a network socket, or an array.
2.4.1.1.5 I/O Streams Packages
Most of the classes covered in the I/O Streams section are in the java.io package.
2.4.1.1.6 I/O Streams Components
I/O Streams are consisted mainly of the following components:
Component
Description
Byte Streams
Handle I/O of raw binary data.
Character Streams
Handle I/O of character data, automatically handling translation to and from the local character set.
Buffered Streams
Optimize input and output by reducing the number of calls to the native API.
Scanning and Formatting
Allows a program to read and write formatted text.
I/O from the Command Line
Describes the Standard Streams and the Console object.
Data Streams
Handle binary I/O of primitive data type and String values.
Object Streams
Handle binary I/O of objects.
2.4.1.1.6.1 Byte Streams
Programs use byte streams to perform input and output of 8-bit bytes. All byte stream classes are descended from InputStream and OutputStream.
2.4.1.1.6.1.1 Byte Input Streams Main Implementation Hierarchy
Implementation
Description
java.io.InputStream
This abstract class is the superclass of all classes representing an input stream of bytes.
java.io.ByteArrayInputStream
A ByteArrayInputStream contains an internal buffer that contains bytes that may be read from the stream.
java.io.FileInputStream
A FileInputStream obtains input bytes from a file in a file system.
java.io.ObjectInputStream
An ObjectInputStream deserializes primitive data and objects previously written using an ObjectOutputStream.
java.io.FilterInputStream
A FilterInputStream contains some other input stream, which it uses as its basic source of data, possibly transforming the data along the way or providing additional functionality.
java.io.BufferedInputStream
A BufferedInputStream adds functionality to another input stream-namely, the ability to buffer the input and to support the mark and reset methods.
java.io.DataInputStream
A data input stream lets an application read primitive Javadata types from an underlying input stream in a machine-independent way.
java.io.ObjectInputStream
An ObjectInputStream deserializes primitive data and objects previously written using an ObjectOutputStream.
2.4.1.1.6.1.2 Byte Output Streams Main Implementation Hierarchy
Implementation
Description
java.io.OutputStream
This abstract class is the superclass of all classes representing an output stream of bytes.
java.io.ByteArrayOutputStream
This class implements an output stream in which the data is written into a byte array.
java.io.FileOutputStream
A file output stream is an output stream for writing data to a File or to a FileDescriptor.
java.io.ObjectOutputStream
An ObjectOutputStream writes primitive data types and graphs of Java objects to an OutputStream.
java.io.FilterOutputStream
This class is the superclass of all classes that filter output streams.
java.io.BufferedOutputStream
The class implements a buffered output stream.
java.io.DataOutputStream
A data output stream lets an application write primitive Java data types to an output stream in a portable way.
java.io.PrintStream
A PrintStream adds functionality to another output stream, namely the ability to print representations of various data values conveniently.
2.4.1.1.6.1.1 File I/O Byte Streams
The most basic file I/O byte streams implementations are FileInputStream and FileOutputStream. They receive as an input a path that represents the file.
2.4.1.1.6.1.2 Using Byte Streams
2.4.1.1.6.1.2.1 Using Byte Input Streams
Let’s examine a common idium, which uses file input byte stream to read a file one byte at a time.
FileInputStream in = null;
try {
in = new FileInputStream("somefile.txt");
int c;
while ((c = in.read()) != -1) {
System.out.println(c);
}
} finally {
if (in != null) {
in.close();
}
}
}
}
The steps of the above idium are:
1. Initialize the input stream:
in = new FileInputStream("somefile.txt");
2. Reading one byte at a time from the stream until end of file is reached:
while ((c = in.read()) != -1) {
3. Closing the stream at end of process, or in case of an exception:
finally {
if (in != null) {
in.close();
}
}
It spends most of its time in a simple loop that reads the input stream and processes the input, one byte at a time:
Notice that read() returns an int value. If the input is a stream of bytes, why doesn't read() return a byte value? Using an int as a return type allows read() to use -1 to indicate that it has reached the end of the stream.
2.4.1.1.6.1.2.1 Using Byte Output Streams
Let’s take the previous idium one step forward and add it a file byte output stream, to write the bytes read to a file.
FileInputStream in = null;
FileOutputStream out = null;
try {
in = new FileInputStream("xanadu.txt");
out = new FileOutputStream("outagain.txt");
int c;
while ((c = in.read()) != -1) {
out.write(c);
}
} finally {
if (in != null) {
in.close();
}
if (out != null) {
out.close();
}
}
The steps added to the above idium are:
1. Initialize the output stream:
out = new FileOutputStream("outagain.txt");
2. Writing the byte read from the input stream to the output stream:
out.write(c);
3. Closing the output stream at end of process, or in case of an exception:
if (out != null) {
out.close();
}
2.4.1.1.6.1.3 Byte Streams Rules of Thumb
2.4.1.1.6.1.3.1 Always Close Streams
Closing a stream when it's no longer needed is very important — Most programming techniques uses a finally block to guarantee that both streams will be closed even if an error occurs. This practice helps avoid serious resource leaks.
When closing a stream you should check that the object representing it contains a valid object reference to the stream. This is to ensure that a stream really exists. One possible error is that a stream was unable to open. When that happens, the stream variable corresponding to the file never changes from its initial null value. That's why CopyBytes makes sure that each stream variable contains an object reference before invoking close.
2.4.1.1.6.1.3.2 When Not to Use Byte Streams
Byte Streams actually represent a kind of low-level I/O that you should avoid. There are streams for different kinds of datatypes: character streams, object streams etc’. Byte streams should only be used for the most primitive I/O.
So why talk about byte streams? Because all other stream types are built on byte streams.
2.4.1.1.6.2 Character Streams
Java stores character values using Unicode conventions. Character stream I/O automatically translates this internal format to and from the local character set.
Input and output of character streams is done with stream classes that automatically translate to and from the local character set. A program that uses character streams in place of byte streams automatically adapts to the local character set and is ready for internationalization — all without extra effort by the programmer.
2.4.1.1.6.2.1 Internationalization
If internationalization isn't a priority, you can simply use the character stream classes without paying much attention to character set issues. Later, if internationalization becomes a priority, your program can be adapted without extensive recoding. See the Internationalization trail for more information.
2.4.1.1.6.2.2 Character Input Streams Main Implementation Hierarchy
Implementation
Description
java.io.Reader
Abstract class for reading character streams.
java.io.BufferedReader
Reads text from a character-input stream, buffering characters so as to provide for the efficient reading of characters, arrays, and lines.
java.io.LineNumberReader
A buffered character-input stream that keeps track of line numbers.
java.io.CharArrayReader
This class implements a character buffer that can be used as a character-input stream.
java.io.InputStreamReader
An InputStreamReader is a bridge from byte streams to character streams: It reads bytes and decodes them into characters using a specified charset.
java.io.FileReader
Convenience class for reading character files.
java.io.StringReader
A character stream whose source is a string.
2.4.1.1.6.2.3 Character Output Streams Main Implementation Hierarchy
Implementation
Description
java.io.Writer
java.io.BufferedWriter
java.io.CharArrayWriter
java.io.FilterWriter
java.io.OutputStreamWriter
java.io.FileWriter
java.io.PrintWriter
java.io.StringWriter
2.4.1.1.6.2.2 Using Character Streams
All character stream classes are descended from Reader and Writer. As with byte streams, there are character stream classes that specialize in file I/O: FileReader and FileWriter.
The CopyCharacters example illustrates these classes.
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
public class CopyCharacters {
public static void main(String[] args) throws IOException {
FileReader inputStream = null;
FileWriter outputStream = null;
try {
inputStream = new FileReader("xanadu.txt");
outputStream = new FileWriter("characteroutput.txt");
int c;
while ((c = inputStream.read()) != -1) {
outputStream.write(c);
}
} finally {
if (inputStream != null) {
inputStream.close();
}
if (outputStream != null) {
outputStream.close();
}
}
}
}
CopyCharacters is very similar to CopyBytes. The most important difference is that CopyCharacters uses FileReader and FileWriter for input and output in place of FileInputStream and FileOutputStream. Notice that both CopyBytes and CopyCharacters use an int variable to read to and write from. However, in CopyCharacters, the int variable holds a character value in its last 16 bits; in CopyBytes, the int variable holds a byte value in its last 8 bits.
Download the JDK
Search the Tutorials
Hide the TOC
Character Streams that Use Byte Streams
Character streams are often "wrappers" for byte streams. The character stream uses the byte stream to perform the physical I/O, while the character stream handles translation between characters and bytes. FileReader, for example, uses FileInputStream, while FileWriter uses FileOutputStream.
There are two general-purpose byte-to-character "bridge" streams: InputStreamReader and OutputStreamWriter. Use them to create character streams when there are no prepackaged character stream classes that meet your needs. The sockets lesson in the networking trail shows how to create character streams from the byte streams provided by socket classes.
Line-Oriented I/O
Character I/O usually occurs in bigger units than single characters. One common unit is the line: a string of characters with a line terminator at the end. A line terminator can be a carriage-return/line-feed sequence ("\r\n"), a single carriage-return ("\r"), or a single line-feed ("\n"). Supporting all possible line terminators allows programs to read text files created on any of the widely used operating systems.
Let's modify the CopyCharacters example to use line-oriented I/O. To do this, we have to use two classes we haven't seen before, BufferedReader and PrintWriter. We'll explore these classes in greater depth in Buffered I/O and Formatting. Right now, we're just interested in their support for line-oriented I/O.
The CopyLines example invokes BufferedReader.readLine and PrintWriter.println to do input and output one line at a time.
import java.io.FileReader;
import java.io.FileWriter;
import java.io.BufferedReader;
import java.io.PrintWriter;
import java.io.IOException;
public class CopyLines {
public static void main(String[] args) throws IOException {
BufferedReader inputStream = null;
PrintWriter outputStream = null;
try {
inputStream =
new BufferedReader(new FileReader("xanadu.txt"));
outputStream =
new PrintWriter(new FileWriter("characteroutput.txt"));
String l;
while ((l = inputStream.readLine()) != null) {
outputStream.println(l);
}
} finally {
if (inputStream != null) {
inputStream.close();
}
if (outputStream != null) {
outputStream.close();
}
}
}
}
Invoking readLine returns a line of text with the line. CopyLines outputs each line using println, which appends the line terminator for the current operating system. This might not be the same line terminator that was used in the input file.
There are many ways to structure text input and output beyond characters and lines. For more information, see Scanning and Formatting.
« Previous • Trail • Next »
Problems with the examples? Try Compiling and Running the Examples: FAQs.
Complaints? Compliments? Suggestions? Give us your feedback.
Your use of this page and all the material on pages under "The Java Tutorials" banner, and all the material on pages under "The Java Tutorials" banner is subject to the Java SE Tutorial Copyright and License. Additionally, any example code contained in any of these Java Tutorials pages is licensed under the Code Sample License.
duke image
Oracle logo
About Oracle | Oracle Technology Network | Terms of Service
Copyright © 1995, 2011 Oracle and/or its affiliates. All rights reserved.
Previous page: Byte Streams
Next page: Buffered Streams
2.4.1.2 File I/O (Featuring NIO.2)
File I/O consisted mainly of:
Component
Description
What is a Path?
Examines the concept of a path on a file system.
The Path Class
Introduces the cornerstone class of the java.nio.file package.
Path Operations
Looks at methods in the Path class that deal with syntactic operations.
File Operations
Introduces concepts common to many of the file I/O methods.
Checking a File or Directory
Shows how to check a file's existence and its level of accessibility.
Deleting a File or Directory.
Copying a File or Directory.
Moving a File or Directory.
Managing Metadata
Explains how to read and set file attributes.
Reading, Writing and Creating Files
Shows the stream and channel methods for reading and writing files.
Random Access Files
Shows how to read or write files in a non-sequentially manner.
Creating and Reading Directories
Covers API specific to directories, such as how to list a directory's contents.
Links, Symbolic or Otherwise
Covers issues specific to symbolic and hard links.
Walking the File Tree
Demonstrates how to recursively visit each file and directory in a file tree.
Finding Files
Shows how to search for files using pattern matching.
Watching a Directory for Changes
Shows how to use the watch service to detect files that are added, removed or updated in one or more directories.
Other Useful Methods
Covers important API that didn't fit elsewhere in the lesson.
Legacy File I/O Code
Shows how to leverage Path functionality if you have older code using the java.io.File class. A table mapping java.io.File API to java.nio.file API is provided.
2.4.1.2.1 File I/O Packages
Most of the classes covered in the File I/O section are in the java.nio.file package.
2.4.1.3 Summary
A summary of the key points covered in this trail.
2.4.1.4 Questions and Exercises
Test what you've learned in this trail by trying these questions and exercises.
2.4.1.5 The I/O Classes in Action
Many of the examples in the next trail, Custom Networking use the I/O streams described in this lesson to read from and write to network connections.
2.4.1.6 Security consideration
Some I/O operations are subject to approval by the current security manager. The example programs contained in these lessons are standalone applications, which by default have no security manager. To work in an applet, most of these examples would have to be modified. See What Applets Can and Cannot Do for information about the security restrictions placed on applets.
2.4.1.7 API Docs
2.4.1.7.1 FileInputStream
A FileInputStream obtains input bytes from a file in a file system. What files are available depends on the host environment.
FileInputStream is meant for reading streams of raw bytes such as image data. For reading streams of characters, consider using FileReader.
2.4.1.7.1.1 package
java.io
2.4.1.7.1.2 Idium
package java.io;
public class FileInputStream extends InputStream {
public FileInputStream(String paramString) throws FileNotFoundException;
public FileInputStream(File paramFile) throws FileNotFoundException;
public FileInputStream(FileDescriptor paramFileDescriptor);
public native int read;
public int read(byte[] paramArrayOfByte) throws IOException
public int read(byte[] paramArrayOfByte, int paramInt1, int paramInt2) throws IOException;
public native long skip(long paramLong) throws IOException;
public native int available() throws IOException;
public void close() throws IOException;
private native void close0() throws IOException;
}
2.4.1.7.1.3 Main Constructors
public FileInputStream(File file) throws FileNotFoundException
Creates a FileInputStream by opening a connection to an actual file, the file named by the File object file in the file system.
public FileInputStream(String name) throws FileNotFoundException
Creates a FileInputStream by opening a connection to an actual file, the file named by the path name name in the file system.
2.4.1.7.1.4 Main Methods
public void close()throws IOException
Closes this file input stream and releases any system resources associated with the stream.
public int read() throws IOException
Reads a byte of data from this input stream.
public int read(byte[] b) throws IOException
Reads up to b.length bytes of data from this input stream into an array of bytes.
public int read(byte[] b, int off, int len) throws IOException
Reads up to len bytes of data from this input stream into an array of bytes.
public long skip(long n) throws IOException
Skips over and discards n bytes of data from the input stream.
2.4.1.7.2 FileOutputStream
2.4.1.8 Examples
Print the byte input of a file to the console:
import java.io.FileInputStream;
import java.io.IOException;
public class PrintFile {
public static void main(String[] args) throws IOException {
FileInputStream is = null;
try {
is = new FileInputStream("input.txt");
int b;
while ((b = is.read()) != -1) {
System.out.println(b);
}
} catch (IOException e) {
e.printStackTrace();
}
finally {
if (is != null) {
is.close();
}
}
}
}
There are several interesting points in this idium:
Although the read operation returns a byte it is retrieved as an int. Dealing with int instead of byte simplifies the test if the read operation reached the end of the file. In this case the returned value will be -1. The int primitive enables the use of negative values, while byte do not.
The while loop checks for the read operation result on the fly, within the condition construct
Running the program with the following input “hello world!!!” yeilds the following output:
Output
104
101
108
108
111
32
119
111
114
108
100
33
33
33
This is because the printed data is not the character values, but their byte representations
Use a file byte streams to copy a file one byte at a time.
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
public class CopyBytes {
public static void main(String[] args) throws IOException {
FileInputStream in = null;
FileOutputStream out = null;
try {
in = new FileInputStream("xanadu.txt");
out = new FileOutputStream("outagain.txt");
int c;
while ((c = in.read()) != -1) {
out.write(c);
}
} finally {
if (in != null) {
in.close();
}
if (out != null) {
out.close();
}
}
}
}
CopyBytes spends most of its time in a simple loop that reads the input stream and writes the output stream, one byte at a time, as shown in the following figure:
Simple byte stream input and output.
Simple byte stream input and output.
Notice that read() returns an int value. If the input is a stream of bytes, why doesn't read() return a byte value? Using an int as a return type allows read() to use -1 to indicate that it has reached the end of the stream.
Basic I/O topics:
- I/O Streams – a powerful concept that greatly simplifies I/O operations
- I/O Serialization – write whole objects out to streams and read them back again.
- File I/O and file system operations, including random access files.
2.4.1.1 Packages
java.io package – Provides for system input and output through data streams, serialization and the file system. Most of the classes covered in the I/O Streams section are covered here.
java.nio package – Defines buffers, which are containers for data, and provides an overview of the other NIO packages. Most of the classes covered in the File I/O section are covered here.
2.4.1.2 Main components
java.io.InputStream
javax.sound.sampled.AudioInputStream
java.io.ByteArrayInputStream
java.io.FileInputStream
java.io.FilterInputStream
java.io.BufferedInputStream
--------------------------------------------------------------------------------
java.util.zip.CheckedInputStream
--------------------------------------------------------------------------------
javax.crypto.CipherInputStream
--------------------------------------------------------------------------------
java.io.DataInputStream
java.security.DigestInputStream
--------------------------------------------------------------------------------
java.util.zip.InflaterInputStream
java.io.LineNumberInputStream
--------------------------------------------------------------------------------
javax.swing.ProgressMonitorInputStream
--------------------------------------------------------------------------------
java.io.PushbackInputStream
--------------------------------------------------------------------------------
org.omg.CORBA.portable.InputStream
java.io.ObjectInputStream
java.io.PipedInputStream
java.io.SequenceInputStream
java.io.StringBufferInputStream
2.4.1.3 I/O Streams
A stream is a sequence of data. A program uses an input stream to read data from a source, one item at a time, or an output stream to write data to a destination, one item at time.
Streams support many different kinds of data, including simple bytes, primitive data types, localized characters, and objects. Some streams simply pass on data; others manipulate and transform the data in useful ways.
There are 7 types of streams:
- Byte Streams – handle I/O of raw binary data.
- Character Streams – handle I/O of character data, automatically handling translation to and from the local character set.
- Buffered Streams – optimize input and output by reducing the number of calls to the native API.
- Scanning and Formatting – allows a program to read and write formatted text.
- I/O from the Command Line – describes the Standard Streams and the Console object.
- Data Streams – handle binary I/O of primitive data type and String values.
- Object Streams – handle binary I/O of objects.
2.4.1.3.1 Byte Streams
Byte streams are the most basic kind of streams.
2.4.1.3.1.1 Example File
For sample input, we'll use the example file xanadu.txt, which contains the following verse:
In Xanadu did Kubla Khan
A stately pleasure-dome decree:
Where Alph, the sacred river, ran
Through caverns measureless to man
Down to a sunless sea.
2.4.1.4 File I/O (Featuring NIO.2)
2.4.1.99 Sources
- Lesson Basic I-O (The Java™ Tutorials Essential Classes)
2.4.1.99 Basic I/O Considerations
2.4.1.99.1 Character Encoding
When possible, it is best practice to arrange that all the input/output peripherals will pass/store data in the same character encoding. This eliminates the need to convert the data from one character encoding to the other.
2.4.1.99.1.1 JVM Default Character Encoding
To avoid the need to define the character encoding on each time you parse a stream data, you can set the default JVM character encoding. The JVM default character encoding is inherited from the environment it is installed on.
2.4.1.99.1.1.1 Setting the JVM Default Character Encoding
You can set it manually by running the java program with a special JVM property:
-Dfile.encoding=whatever
Alternatively you can define it as an environment variable. Using an environment variable enables to define the JVM property only once, instead of defining it for each java command:
JAVA_TOOL_OPTIONS=-Dfile.encoding=UTF8
2.4.1.99.2 Actual Byte Data
The actual byte data that is saved or stored on a stream may be different from its byte data representation.
Example 1: Using the the ASCII character encoding
The character that represents the English capital letter ‘A’ is represented in ASCII as 41 hex number (1000001 binary).
ASCII characters are saved in the actual disk on a binary byte data, on the 7 less significant bits out of 8. The most significant bit can be ignored, ‘0’, ‘1’ or can serve as a parity bit, i.e. it can be saved on disk as 01000001 or 11000001.
Example 2: Using the the UTF-8 character encoding
The character that represents the currency dollar sign ‘$’ is represented in UTF-8 as U+0024 (24 hex number, 100100 binary).
UTF-8 characters are not saved on the actual disk as their actual value. There is a special binary algorithm for that.
The ‘$’ sign is saved on disk as the following two bytes: 11000010 10100010 (hexadecimal C2 A2).
2.4.2 Java Collections Framework
2.4.2.1 Introduction to Collections
A collection is an object that groups multiple elements into a single unit. Typically, they represent data items that form a natural group.
2.4.2.1.1 Collections Usages
- A poker hand – a collection of cards
- A mail folder – a collection of letters
- A telephone directory – a mapping of names to phone numbers.
2.4.2.1.2 What Is a Collections Framework?
A collections framework is a unified architecture for representing and manipulating collections.
2.4.2.1.2.1 Core Elements
All collections frameworks contain the following:
- Interfaces: Interfaces allow collections to be manipulated independently of the details of their representation.
- Implementations: These are the concrete implementations of the collection interfaces.
- Algorithms: These are the methods that perform useful computations, such as searching and sorting, on objects that implement collection interfaces.
2.4.2.2 Interfaces
2.4.2.2.1 Introduction to Interfaces
The core collection interfaces encapsulate different types of collections. Core collection interfaces are the foundation of the Java Collections Framework.
2.4.2.2.1.1 Why Interfaces
These interfaces allow collections to be manipulated independently of the details of their representation.
2.4.2.2.1.2 Common Interface Hierarchy
The core collection interfaces.
The collection intererfaces consists of two distinct interface hierarchies.
Although a Map is not a true Collection it belongs to the collections framework because of the way that its keys and values are manipulated. To understand the Map interface see the Map interface section.
Common Interface Hierarchy
java.util.Collection
java.util.Queue<E>
java.util.List
java.util.Set
java.util.SortedSet
java.util.Map
java.util.SortedMap
Since java5:
Note that all the core collection interfaces are generic.
2.4.2.2.1.3 Sorted Interfaces
The last two core collection interfaces are merely sorted versions of Set and Map:
- SortedSet — a Set that maintains its elements in ascending order. Sorted sets are used for naturally ordered sets.
- SortedMap — a Map that maintains its mappings in ascending key order. This is the Map analog of SortedSet. Sorted maps are used for naturally ordered collections of key/value pairs.
To understand how the sorted interfaces maintain the order of their elements, see the Object Ordering section.
2.4.2.2.1.4 Helper Interfaces
In addition to the core collection interfaces there are several helper interfaces in the framework that assist to the represention and manipulation of collections.
2.4.2.2.2 The Collection Interface
Collection is the root of the collection hierarchy.
2.4.2.2.2.1 Collection Interface Usages
- It represents a group of objects known as its elements
- It is used when maximum generality is desired, for example when using the Conversion Constructor.
2.4.2.2.2.2 High Level Collection Operations
Operation type
Description
Basic
- Checking size (size,isEmpty)
- Checking if an object is part of the collection (contains)
- Add/Remove (add, remove)
- Traversing (iterator)
Bulk
Operations that impact many elements in the collection (containsAll, addAll, removeAll, retainAll, clear)
Conversion
Translating into an array (toArray);
Comparison
Comparing to other Collection interface (equals, hashCode)
2.4.2.2.2.3 Collection Idium
public interface Collection<E> extends Iterable<E> {
// Basic operations
public abstract int size();
public abstract boolean isEmpty();
public abstract boolean contains(Object element);
public abstract boolean add(E element);
public abstract boolean remove(Object element);
public abstract Iterator<E> iterator();
// Bulk operations
public abstract boolean containsAll(Collection<?> c);
public abstract boolean addAll(Collection<? extends E> c);
public abstract boolean removeAll(Collection<?> c);
public abstract boolean retainAll(Collection<?> c);
public abstract void clear();
// Conversion operations
public abstract Object[] toArray();
public abstract <T> T[] toArray(T[] a);
// Comparison operations
public abstract boolean equals(Object o);
public abstract int hashCode();
}
2.4.2.2.2.4 Compare Collection to Legacy API
No specific legacy API available.
2.4.2.2.2.5 Collection Object Comparisons
Not supported directly by the Collection interface
2.4.2.2.2.6 The Collection Conversion Constructor
Most of the Collection implementations have a Conversion Constructor that allows you to convert the collection's type. It takes a Collection argument and initializes the new collection to contain all of the elements in the specified collection, whatever the given collection's subinterface or implementation type.
Usually the Conversion Constructor is smart enough to fit the limitations of the new collection type.
2.4.2.2.2.7 Collection Basic operations
Method
Description
int size();
boolean isEmpty();
How many elements are in the collection
boolean contains(Object element);
Check whether a given object is in the collection
boolean add(E element);
Add and remove an element from the collection
boolean remove(Object element);
Iterator<E> iterator();
Provide an iterator over the collection
2.4.2.2.2.8 Collection Positional Access and Search Operations
Not supported directly by the interface
2.4.2.2.2.9 Collection Bulk Operations
Bulk operations perform an operation on an entire Collection:
Method
Description
boolean containsAll(Collection<?> c);
Checks if the target collection contains all elements in the specified collection
boolean addAll(Collection<? extends E> c);
Adds all elements in the specified collection to the target collection
boolean removeAll(Collection<?> c);
Removes from the target collection all elements that are in the specified collection. This method can be used with the singletone method to shorten the code
boolean retainAll(Collection<?> c);
Removes from the target collection all elements that are not in the specified collection
void clear();
Removes all elements from the collection
2.4.2.2.2.10 Collection Views
Not Applicable
2.4.2.2.2.10.1 Collection Range-View Operations
Not Applicable
2.4.2.2.2.11 Traversing over a Collection
Traversing a collection can be done with the following options:
Option
Description
Using the Iterator interface.
Every Collection interface has a method that returns an Iterator over the elements in it.
Since java5:
Using the for-each construct
Using the ListIterator interface, when applicable
Some Collection interfaces support traversing a List interface with the ListIterator interface. It adds functionality applicable to List
2.4.2.2.2.12 Translating Collection into an Array
A collection can be translated into an array using the toArray methods.
- Object[] toArray() – creates a new array of Object.
Since java5:
- <T> T[] toArray(T[] a) – The more complex form allows the caller to provide an array and to choose the runtime type of the output array.
2.4.2.2.2.13 Common Collection Implementations
Class
Description
java.util.ArrayList<E>
java.util.HashSet<E>
java.util.LinkedHashSet<E>
java.util.LinkedList<E>
java.util.TreeSet<E>
2.4.2.2.2.14 Collection Algorithms
No special algorithms for this interface in the core API
2.4.2.2.2.15 Collection Performance Considerations
No special performance considerations for this interface
2.4.2.2.2.16 Collection Examples
2.4.2.2.2.16.1 Conversion Constructor Examples
- Create a new ArrayList (implementation of List), containing all elements from another Collection:
List<String> list = new ArrayList<String>(c);
- Removing duplicate values from a Collection by creating a new Set:
Collection<Type> noDups = new HashSet<Type>(c);
- Removing duplicate values and keeping the order:
Collection<Type> noDups = new LinkedHashSet<Type>(c);
- Coding the previous example into a method:
public static <E> Set<E> removeDups(Collection<E> c) {
return new LinkedHashSet<E>(c);
}
2.4.2.2.2.16.2 Removing with an Iterator Example
- Remove from a collection specific elements by using an Iterator:
static void filter(Collection<?> c) {
for (Iterator<?> it = c.iterator(); it.hasNext(); )
if (!cond(it.next()))
it.remove();
}
2.4.2.2.2.16.3 Interface Bulk Operations Examples
- c.removeAll(Collections.singleton(e));
- c.removeAll(Collections.singleton(null));
2.4.2.2.2.16.4 Translating into an Array
Since java5:
- Traslate a collection into an array of Strings:
String[] a = c.toArray(new String[0]);
2.4.2.2.3 The Iterator Interface
The Iterator interface traverses over a collection.
2.4.2.2.3.1 Iterator Inteface Usages
It traverses the elemnts in the collection by generating a series of elements, one at a time. Successive calls to the next method return successive elements of the series.
2.4.2.2.3.2 High Level Iterator Operations
Operation Type
Description
Basic
Traversing over the elements of an Iterator
Removing an element from the Iterator and the backing Collection
2.4.2.2.3.3 Iterator Idium
The following shows the Collection interface:
public abstract interface Iterator<E> {
public abstract boolean hasNext();
public abstract E next();
public abstract void remove();
}
2.4.2.2.3.4 Comparing Iterator to Legacy API
Iterator takes the place of Enumeration in the Java collections framework. Iterators differ from enumerations in two ways:
Iterators allow the caller to remove elements from the underlying collection during the iteration with well-defined semantics.
Method names have been improved.
New implementations should consider using Iterator in preference to Enumeration.
2.4.2.2.3.5 Iterator Object Comparisons
Not Applicable.
2.4.2.2.3.6 Iterator Conversion Constructor
Not Applicable.
2.4.2.2.3.7 Iterator Basic operations
Method
Description
boolean hasNext();
Returns true if the iteration has more elements.
E next();
Returns the next element in the iteration.
void remove();
Removes from the underlying collection the last element returned by the iterator.
2.4.2.2.3.8 Iterator Positional Access and Search Operations
Not Applicable.
2.4.2.2.3.9 Iterator Bulk Operations
Not Applicable.
2.4.2.2.3.10 Iterator Views Operations
Not Applicable
2.4.2.2.3.10.1 Iterator Range-View Operations
Not Applicable
2.4.2.2.3.11 Traversing over an Iterator
Not Applicable.
2.4.2.2.3.12 Translating Iterator into an Array
Not Applicable.
2.4.2.2.3.13 Common Iterator Implementations
The direct use of Iterator implementations is not common.
2.4.2.2.3.14 Iterator Algorithms
No special algorithms for this interface in the core API
2.4.2.2.3.15 Iterator Performance Considerations
No special performance considerations for this interface
2.4.2.2.3.16 Iterator Examples
- Print all elements of a collection c:
Iterator itr = c.iterator();
while (itr.hasNext()) {
System.out.println(itr.next());
}
2.4.2.2.4 The Set Interface
A Set is a Collection that cannot contain duplicate elements.
2.4.2.2.4.1 Set Usages
Example: Storing the Employee ids
2.4.2.2.4.2 High Level Set Operations
Same contract as for the Collection interface
2.4.2.2.4.3 Set Idium
public interface Set<E> extends Collection<E> {
// Basic operations
public abstract int size();
public abstract boolean isEmpty();
public abstract boolean contains(Object element);
public abstract boolean add(E element); //optional
public abstract boolean remove(Object element); //optional
public abstract Iterator<E> iterator();
// Bulk operations
public abstract boolean containsAll(Collection<?> c);
public abstract boolean addAll(Collection<? extends E> c); //optional
public abstract boolean removeAll(Collection<?> c); //optional
public abstract boolean retainAll(Collection<?> c); //optional
public abstract void clear(); //optional
// Array Operations
public abstract Object[] toArray();
public abstract <T> T[] toArray(T[] a);
// Comparison operations
public abstract boolean equals(Object o);
public abstract int hashCode();
}
2.4.2.2.4.4 Compare Set to Legacy API
No specific legacy API available.
2.4.2.2.4.5 Set Object Comparisons
The Set interface adds a stronger contract on the behavior of the equals and hashCode operations, allowing Set instances to be compared meaningfully even if their implementation types differ. Two Set instances are equal if they contain the same elements.
2.4.2.2.4.6 The Set Conversion Constructor
Same contract as for the Collection interface
2.4.2.2.4.7 Set Basic Operations
Method
Description
int size();
boolean isEmpty();
boolean contains(Object element);
Does exactly what you think.
boolean add(E element);
Adds the specified element to the Set if it's not already present; Returns a boolean indicating whether the element was added.
boolean remove(Object element);
Removes the specified element from the Set if it's present and returns a boolean indicating whether the element was present.
Iterator<E> iterator();
Returns an Iterator over the Set
2.4.2.2.4.8 Set Positional Access and Search Operations
Not supported directly by the interface
2.4.2.2.4.9 Set Bulk Operations
Bulk operations are particularly well suited to Sets; when applied, they perform standard set-algebraic operations.
Method
Description
boolean containsAll(Collection<?> c);
Checks if the specified set is a subset of the target collection
boolean addAll(Collection<? extends E> c);
Transforms the target set into the unions of the target set and the specified set
boolean removeAll(Collection<?> c);
Transforms the target set into the (asymmetric) set difference of the target set and the specified set
boolean retainAll(Collection<?> c);
Transforms the target set into the intersection of the target set and the specified set
void clear();
Same contract as for the Collection interface
2.4.2.2.2.10 Set Views Operations
Not Applicable
2.4.2.2.2.10.1 Set Range-View Operations
Not Applicable
2.4.2.2.4.11 Traversing over a Set
Same contract as for the Collection interface
2.4.2.2.4.12 Translating Set into an Array
Same contract as for the Collection interface
2.4.2.2.2.13 Common Set Implementations
Class
Description
java.util.HashSet<E>
- Stores its elements in a hash table
- Best-performing implementation
- It makes no guarantees concerning the order of iteration.
java.util.TreeSet<E>
- Stores its elements in a red-black tree
- It is substantially slower than HashSet.
- Orders its elements based on their values
java.util.LinkedHashSet<E>
- Implemented as a hash table with a linked list running through it
- Spares its clients from the unspecified, generally chaotic ordering provided by HashSet at a cost that is only slightly higher.
- Orders its elements based on the order in which they were inserted into the set (insertion-order).
2.4.2.2.2.14 Set Algorithms
No special algorithms for this interface in the core API
2.4.2.2.2.15 Set Performance Considerations
No special performance considerations for this interface
2.4.2.2.4.16 Set Examples
2.4.2.2.2.16.1 Set Bulk Operations Examples
Checks if s2 is a subset of s1
s1.containsAll(s2)
Transform s1 into the union of s1 and s2
s1.addAll(s2)
- Transforms s1 into the intersection of s1 and s2.
s1.retainAll(s2)
- Transforms s1 into the (asymmetric) set difference of s1 and s2.
s1.removeAll(s2)
- Calculate the union, intersection, and difference of two sets nondestructively:
Set<Type> union = new HashSet<Type>(s1);
union.addAll(s2);
Set<Type> intersection = new HashSet<Type>(s1);
intersection.retainAll(s2);
Set<Type> difference = new HashSet<Type>(s1);
difference.removeAll(s2);
- Parse an argument list and print the unique and duplicate args:
import java.util.*;
public class FindDups2 {
public static void main(String[] args) {
Set<String> uniques = new HashSet<String>();
Set<String> dups = new HashSet<String>();
for (String a : args)
if (!uniques.add(a))
dups.add(a);
// Destructive set-difference
uniques.removeAll(dups);
System.out.println("Unique words: " + uniques);
System.out.println("Duplicate words: " + dups);
}
}
- Find the symmetric set difference:
Set<Type> symmetricDiff = new HashSet<Type>(s1);
symmetricDiff.addAll(s2);
Set<Type> tmp = new HashSet<Type>(s1);
tmp.retainAll(s2));
symmetricDiff.removeAll(tmp);
2.4.2.2.5 The List Interface
A List is an ordered Collection (sometimes called a sequence). Lists may contain duplicate elements.
2.4.2.2.5.1 List Usages
Example:
A List of plates to put on the table
A List of chairs.
2.4.2.2.5.2 List Operations
In addition to the extended Collection interface, the List interface adds the following operations:
Operation
Description
Positional access
Manipulates elements based on their numerical position (their index/indice)
Search
searches for a specified object in the list and returns its numerical position
Iteration
Extends Iterator to take advantage of the list's sequential nature
Range-view
Performs arbitrary range operations on the list.
2.4.2.2.5.3 List Idium
public abstract interface List<E> extends Collection<E> {
// Basic operations
public abstract int size();
public abstract boolean isEmpty();
public abstract boolean contains(Object element);
public abstract boolean add(E element);
public abstract boolean remove(Object element);
public abstract Iterator<E> iterator();
// Bulk operations
public abstract boolean containsAll(Collection<?> c);
public abstract boolean addAll(Collection<? extends E> c);
public abstract boolean removeAll(Collection<?> c);
public abstract boolean retainAll(Collection<?> c);
public abstract void clear();
// Array operations
public abstract Object[] toArray();
public abstract <T> T[] toArray(T[] a);
// Comparison operations
public abstract boolean equals(Object o);
public abstract int hashCode();
// Positional access
public abstract E get(int index);
public abstract E set(int index, E element);
public abstract void add(int index, E element);
public abstract boolean addAll(int index, Collection<? extends E> c);
public abstract E remove(int index);
// Search
public abstract int indexOf(Object o);
public abstract int lastIndexOf(Object o);
// Iteration
public abstract ListIterator<E> listIterator();
public abstract ListIterator<E> listIterator(int index);
// Range-view
public abstract List<E> subList(int from, int to);
}
2.4.2.2.5.4 Compare List to Legacy API
2.4.2.2.5.5.1 Comparison to Vector
List is an interface, while Vector is a concrete implementation.
List fixes several minor API deficiencies in Vector.
2.4.2.2.5.5 List Object Comparison
Like the Set interface, List strengthens the requirements on the equals and hashCode methods so that two List objects can be compared for logical equality without regard to their implementation classes. Two List objects are equal if they contain the same elements in the same order.
2.4.2.2.5.6 The List Conversion Constructor
Same contract as for the Collection interface
2.4.2.2.5.7 List Basic Operations
Most of the basic operations inherited from Collection all do about what you'd expect them to do, assuming you're already familiar with them. The following methods have some new functionality:
Operation
Description
boolean add(E element);
Appends the specified element to the end of this list.
void add(int index, E element);
Inserts the specified element at the specified position in this list.
boolean addAll(Collection<? extends E> c);
Appends all of the elements in the specified collection to the end of this list, in the order that they are returned by the specified collection's iterator.
boolean addAll(int index, Collection<? extends E> c);
Inserts all of the elements in the specified collection into this list at the specified position. Shifts the element currently at that position and any subsequent elements to the right. The new elements will appear in this list in the order that they are returned by the specified collection's iterator.
2.4.2.2.5.8 List Positional Access and Search Operations
Positional access and search operations are applied by the following methods:
Operation
Description
E get(int index);
Returns the element at the specified position in this list
E set(int index, E element);
Replaces the element at the specified position with the specified element. Returns the element previously at the specified position
void add(int index, E element);
Inserts the specified element at the specified position in this list and shifts the element at that position and any subsequent elements to the right.
boolean remove(Object element);
Removes the first occurrence of the specified element from this list, if it is present
E remove(int index);
Removes the element at the specified position in this list and shifts any subsequent elements to the left.
int indexOf(Object o);
Returns the index of the first occurrence of the specified element
int lastIndexOf(Object o);
Returns the index of the last occurrence of the specified element in this list
boolean addAll(int index, Collection<? extends E> c);
Inserts all the elements of the specified Collection starting at the specified position. The elements are inserted in the order they are returned by the specified Collection's iterator.
2.4.2.2.2.9 List Bulk Operations
Same contract as for the Collection interface
2.4.2.2.2.10 List Views Operations
2.4.2.2.2.10.1 List Range-View Operations
The range-view operation, subList(), returns a List view of the portion of this list. It is provided with the following method:
Operation
Description
List<E> subList(int fromIndex, int toIndex)
Returns a view of the portion of this list between the specified fromIndex, inclusive, and toIndex, exclusive.
As the term view implies, the returned List is backed up by the List on which subList was called, so changes in the former are reflected in the latter.
This method eliminates the need for explicit range operations of the sort that commonly exist for arrays. Any operation that expects a List can be used as a range operation by passing a subList view instead of a whole List.
Although the subList operation is extremely powerful, some care must be exercised when using it. The semantics of the List returned by subList become undefined if elements are added to or removed from the backing List in any way other than via the returned List.
2.4.2.2.5.11 Traversing over a List
In addition to the contract of the Collection interface, the List interface also provides a richer iterator, called a ListIterator, which allows you to:
Traverse the list in either direction
Modify the list during iteration
Obtain the current position of the iterator
The ListIterator is provided by calling the following method:
Operation
Description
public abstract ListIterator<E> listIterator();
Returns a list iterator over the elements in this list (in proper sequence).
public abstract ListIterator<E> listIterator(int index);
Returns a list iterator of the elements in this list (in proper sequence), starting at the specified position in this list.
The three methods that ListIterator inherits from Iterator (hasNext, next, and remove) do exactly the same thing in both interfaces. The hasPrevious and the previous operations are exact analogues of hasNext and next. The former operations refer to the element before the (implicit) cursor, whereas the latter refer to the element after the cursor. The previous operation moves the cursor backward, whereas next moves it forward.
2.4.2.2.5.12 Translating List into an Array
Object[] toArray()
Returns an array containing all of the elements in this list in proper sequence (from first to last element).
<T> T[] toArray(T[] a)
Returns an array containing all of the elements in this list in proper sequence (from first to last element); the runtime type of the returned array is that of the specified array.
2.4.2.2.2.13 Common List Implementations
Class
Description
java.util.ArrayList<E>
java.util.LinkedList<E>
2.4.2.2.5.14 List Algorithms
Most polymorphic algorithms in the Collections class apply specifically to List. Here's a summary of these algorithms, which are described in more detail in the Algorithms section.
2.4.2.2.5.15 List Performance Considerations
For many common List implementations, such as ArrayList, the performance of removing elements from the end of the list is substantially better than that of removing elements from the beginning.
2.4.2.2.5.16 List Examples
Removing a range of elements from a List:
list.subList(fromIndex, toIndex).clear();
Search for an element in a range:
int i = list.subList(fromIndex, toIndex).indexOf(o);
int j = list.subList(fromIndex, toIndex).lastIndexOf(o);
A polymorphic algorithm to deal a hand from a deck using subList:
public static <E> List<E> dealHand(List<E> deck, int n) {
int deckSize = deck.size();
List<E> handView = deck.subList(deckSize - n, deckSize);
List<E> hand = new ArrayList<E>(handView);
handView.clear();
return hand;
}
Note that this algorithm removes the hand from the end of the deck. For many common List implementations, such as ArrayList, the performance of removing elements from the end of the list is substantially better than that of removing elements from the beginning.
The following is a program that uses the dealHand method in combination with Collections.shuffle to generate hands from a normal 52-card deck. The program takes two command-line arguments: (1) the number of hands to deal and (2) the number of cards in each hand.
import java.util.*;
public class Deal {
public static void main(String[] args) {
if (args.length < 2) {
System.out.println("Usage: Deal hands cards");
return;
}
int numHands = Integer.parseInt(args[0]);
int cardsPerHand = Integer.parseInt(args[1]);
// Make a normal 52-card deck.
String[] suit = new String[] {
"spades", "hearts", "diamonds", "clubs" };
String[] rank = new String[] {
"ace","2","3","4","5","6","7","8",
"9","10","jack","queen","king" };
List<String> deck = new ArrayList<String>();
for (int i = 0; i < suit.length; i++)
for (int j = 0; j < rank.length; j++)
deck.add(rank[j] + " of " + suit[i]);
// Shuffle the deck.
Collections.shuffle(deck);
if (numHands * cardsPerHand > deck.size()) {
System.out.println("Not enough cards.");
return;
}
for (int i=0; i < numHands; i++)
System.out.println(dealHand(deck, cardsPerHand));
}
public static <E> List<E> dealHand(List<E> deck, int n) {
int deckSize = deck.size();
List<E> handView = deck.subList(deckSize - n, deckSize);
List<E> hand = new ArrayList<E>(handView);
handView.clear();
return hand;
}
}
Running the program produces output like the following:
% java Deal 4 5
[8 of hearts, jack of spades, 3 of spades, 4 of spades,
king of diamonds]
[4 of diamonds, ace of clubs, 6 of clubs, jack of hearts,
queen of hearts]
[7 of spades, 5 of spades, 2 of diamonds, queen of diamonds,
9 of clubs]
[8 of spades, 6 of diamonds, ace of spades, 3 of hearts,
ace of hearts]
the following idiom concatenates one list to another.
list1.addAll(list2);
Here's a nondestructive form of this idiom, which produces a third List consisting of the second list appended to the first.
List<Type> list3 = new ArrayList<Type>(list1);
list3.addAll(list2);
2.4.2.2.5.16.1 Positional Access and Search Operations Examples
A polymorphic method to swap two indexed values in a List:
public static <E> void swap(List<E> a, int i, int j) {
E tmp = a.get(i);
a.set(i, a.get(j));
a.set(j, tmp);
}
A polymorphic algorithm that uses the preceding swap method to shuffle:
public static void shuffle(List<?> list, Random rnd) {
for (int i = list.size(); i > 1; i--)
swap(list, i - 1, rnd.nextInt(i));
}
Print the words on an argument list in random order, using Collections.shuffle():
import java.util.*;
public class Shuffle {
public static void main(String[] args) {
List<String> list = new ArrayList<String>();
for (String a : args)
list.add(a);
Collections.shuffle(list, new Random());
System.out.println(list);
}
}
Taking advantage of Arrays.asList:
import java.util.*;
public class Shuffle {
public static void main(String[] args) {
List<String> list = Arrays.asList(args);
Collections.shuffle(list);
System.out.println(list);
}
}
2.4.2.2.6 The ListIterator interface
The ListIterator is a special iterator for lists. It has more functionality than the standard general Iterator.
2.4.2.2.6.1 ListIterator Usages
- Traverse the list in either direction
- Modify the list during iteration
- Obtain the iterator's current position in the list.
2.4.2.2.6.2 High Level ListIterator Operations
In addition to the gereral Iterator, the ListIterator adds functionality to navigate forward or backward in the Iterator.
2.4.2.2.6.3 ListIterator Idium
public abstract interface ListIterator<E> extends Iterator<E> {
public abstract boolean hasNext();
public abstract E next();
public abstract boolean hasPrevious();
public abstract E previous();
public abstract int nextIndex();
public abstract int previousIndex();
public abstract void remove();
public abstract void set(E paramE);
public abstract void add(E paramE);
}
2.4.2.2.6.4 Compare ListIterator to Legacy API
Not Applicable.
2.4.2.2.6.5 ListIterator Object Comparisons
Not Applicable.
2.4.2.2.6.6 The ListIterator Conversion Constructor
Not Applicable.
2.4.2.2.6.7 ListIterator Basic operations
Operation
Description
boolean hasNext();
Returns true if this list iterator has more elements when traversing the list in the forward direction.
E next();
Returns the next element in the list.
boolean hasPrevious();
Returns true if this list iterator has more elements when traversing the list in the reverse direction.
E previous();
Returns the previous element in the list.
int nextIndex();
Returns the index of the element that would be returned by a subsequent call to next.
int previousIndex();
Returns the index of the element that would be returned by a subsequent call to previous.
void remove();
Removes from the list the last element that was returned by next or previous (optional operation).
void set(E paramE);
Replaces the last element returned by next or previous with the specified element.
void add(E paramE);
Inserts the specified element into the list.
2.4.2.2.6.8 ListIterator Positional Access and Search Operations
The operations of the ListIterator work on the last element returned by next or previous.
2.4.2.2.6.9 ListIterator Bulk Operations
Not Applicable.
2.4.2.2.2.10 ListIterator Views Operations
Not Applicable
2.4.2.2.2.10.1 ListIterator Range-View Operations
Not Applicable
2.4.2.2.6.11 Traversing over a ListIterator
Not Applicable.
2.4.2.2.6.12 Translating ListIterator into an Array
Not Applicable.
2.4.2.2.6.13 Common ListIterator Implementations
The direct use of ListIterator implementations is not common.
2.4.2.2.6.14 ListIterator Algorithms
No special algorithms for this interface in the core API
2.4.2.2.6.15 ListIterator Performance Considerations
No special performance considerations for this interface
2.4.2.2.6.16 ListIterator Examples
- Iterate backward through a list.
for (ListIterator<Type> it = list.listIterator(list.size());
it.hasPrevious(); ) {
Type t = it.previous();
...
}
2.4.2.2.7 The SortedSet Interface
A SortedSet is a Set that maintains its elements in ascending order, sorted according to the elements' natural ordering or according to a Comparator provided at SortedSet creation time.
2.4.2.2.7.1 SortedSet Usages
A set of library books sorted by their name
A set of country names
2.4.2.2.7.2 SortedSet Operations
In addition to the normal Set operations, the SortedSet interface provides operations for the following:
Operation Type
Description
Range view
Allows arbitrary range operations on the sorted set
Endpoints
Returns the first or last element in the sorted set
Comparator access
Returns the Comparator, if any, used to sort the set
The operations that SortedSet inherits from Set behave identically on sorted sets and normal sets with two exceptions:
The Iterator returned by the iterator operation traverses the sorted set in order.
The array returned by toArray contains the sorted set's elements in order.
TreeSet elements must be instances of a class that implements Comparable.
2.4.2.2.7.3 SortedSet Idium
public abstract interface SortedSet<E> extends Set<E> {
// Basic operations
public abstract E first();
public abstract E last();
// Comparison operations
public abstract Comparator<? super E> comparator();
// Range-view
public abstract SortedSet<E> subSet(E paramE1, E paramE2);
public abstract SortedSet<E> headSet(E paramE);
public abstract SortedSet<E> tailSet(E paramE);
}
2.4.2.2.7.4 Compare SortedSet to Legacy API
Not Applicable
2.4.2.2.7.5 SortedSet Object Comparison
Not Applicable
2.4.2.2.7.6 The SortedSet Conversion Constructor
The standard conversion constructor that is defined in Collection sorts the elements only by their natural ordering and does not check the specified collection for a Comparator. To solve it the interface implementations define another constructor with a specified parameter of SortedSet.
2.4.2.2.7.7 SortedSet Basic Operations
Same contract as for the Collection interface
2.4.2.2.7.8 SortedSet Positional Access and Search Operations
Not Applicable
2.4.2.2.7.9 SortedSet Bulk Operations
Same contract as for the Collection interface
2.4.2.2.2.10 SortedSet Views Operations
2.4.2.2.2.10.1 SortedSet Range-View Operations
The range-view operations are somewhat analogous to those provided by the List interface, but there are several big differences:
Range views of a sorted set remain valid even if the backing sorted set is modified directly.
Sorted sets provide three range-view operations. While the subSet operation is very similar to the List.subList operation, SortedSet adds two new endpoint operations to return the first and last elements in the sorted set:
SortedSet<E> subSet(E fromElement, E toElement)
Takes two endpoints, like the List.subList method.
While the subList method takes indices, the endpoints of subSet are objects and must be comparable to the elements in the sorted set, using the Set's Comparator or the natural ordering of its elements, whichever the Set uses to order itself.
Like List.subList, the range is half open, including its low endpoint but excluding the high one.
SortedSet<E> headSet(E toElement)
Take a single Object argument
Returns a view of the initial portion of the backing SortedSet, up to but not including the specified object
SortedSet<E> tailSet(E fromElement)
Take a single Object argument
Returns a view of the final portion of the backing SortedSet, beginning with the specified object and continuing to the end of the backing SortedSet.
2.4.2.2.7.11 Traversing over the SortedSet
Same contract as for the Set interface
2.4.2.2.7.12 Translating SortedSet into an Array
Same contract as for the Set interface
2.4.2.2.2.13 Common SortedSet Implementations
Class
Description
java.util.HashSet<E>
java.util.LinkedHashSet<E>
java.util.TreeSet<E>
2.4.2.2.7.14 SortedSet Algorithms
No special core algorithms are known
2.4.2.2.7.15 SortedSet Performance Considerations
No special performance considerations are known
2.4.2.2.7.16 SortedSet Interface Examples
2.4.2.2.7.16.1 SortedSet Range-View Examples
How many words between "doorbell" and "pickle", including "doorbell" but excluding "pickle", are contained in a SortedSet of strings called dictionary:
int count = dictionary.subSet("doorbell", "pickle").size();
Remove all the elements beginning with the letter f:
dictionary.subSet("f", "g").clear();
A similar trick can be used to print a table telling you how many words begin with each letter:
for (char ch = 'a'; ch <= 'z'; ) {
String from = String.valueOf(ch++);
String to = String.valueOf(ch);
System.out.println(from + ": " +
dictionary.subSet(from, to).size());
}
How many words between "doorbell" and "pickle", including doorbell and pickle, are contained in the dictionary:
count = dictionary.subSet("doorbell", "pickle\0").size();
Calculate the number of words between "doorbell" and "pickle", excluding both:
count = dictionary.subSet("doorbell\0", "pickle").size();
View the dictionary as two disjoint volumes (a-m and n-z):
SortedSet<String> volume1 = dictionary.headSet("n");
SortedSet<String> volume2 = dictionary.tailSet("n");
2.4.2.2.8 The Map Interface
A Map is an object that maps keys to values. A map cannot contain duplicate keys: Each key can map to at most one value. It models the mathematical function abstraction.
2.4.2.2.8.1 Map Interface Usages
For example: A map that maps keys of the personId to the object representing this person
2.4.2.2.8.2 High Level Map Operations
In addition to the contract extended from the Collection interface, map adds operations to handle the Map contract. The operations added are from the following types:
Basic
Bulk
View
Comparison
2.4.2.2.8.3 Map Idium
public interface Map<K,V> {
// Basic operations
public abstract V put(K key, V value);
public abstract V get(Object key);
public abstract V remove(Object key);
public abstract boolean containsKey(Object key);
public abstract boolean containsValue(Object value);
public abstract int size();
public abstract boolean isEmpty();
// Bulk operations
public abstract void putAll(Map<? extends K, ? extends V> m);
public abstract void clear();
// Collection Views
public abstract Set<K> keySet();
public abstract Collection<V> values();
public abstract Set<Entry<K, V>> entrySet();
// Interface for entrySet elements
public interface Entry {
K getKey();
V getValue();
V setValue(V value);
}
// Comparison operations
public abstract boolean equals(Object o);
public abstract int hashCode();
}
2.4.2.2.8.4 Compare Map to Legacy API
2.4.2.2.8.4.1 Comparison to Hashtable
Map is an interface, while Hashtable is a concrete implementation
Map provides Collection views instead of direct support for iteration via Enumeration objects. Collection views greatly enhance the expressiveness of the interface, as discussed later in this section.
Map allows you to iterate over keys, values, or key-value pairs; Hashtable does not provide the third option.
Map provides a safe way to remove entries in the midst of iteration; Hashtable did not.
Map fixes a minor deficiency in the Hashtable interface. Hashtable has a method called contains, which returns true if the Hashtable contains a given value. Given its name, you'd expect this method to return true if the Hashtable contained a given key, because the key is the primary access mechanism for a Hashtable. The Map interface eliminates this source of confusion by renaming the method containsValue. Also, this improves the interface's consistency — containsValue parallels containsKey.
2.4.2.2.8.5 Map Interface Object Comparisons
Like the Set and List interfaces, Map strengthens the requirements on the equals and hashCode methods so that two Map objects can be compared for logical equality without regard to their implementation types. Two Map instances are equal if they represent the same key-value mappings.
2.4.2.2.8.6 The Map Interface Conversion Constructor
By convention, all general-purpose Map implementations provide constructors that take a Map object and initialize the new Map to contain all the key-value mappings in the specified Map. This standard Map conversion constructor is entirely analogous to the standard Collection constructor: It allows the caller to create a Map of a desired implementation type that initially contains all of the mappings in another Map, regardless of the other Map's implementation type.
2.4.2.2.8.7 Map Interface Basic operations
The basic operations of Map (put, get, containsKey, containsValue, size, and isEmpty) behave exactly like their counterparts in Hashtable:
V put(K key, V value);
Associates the specified value with the specified key in this map.
V get(Object key);
Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.
boolean containsKey(Object key);
Returns true if this map contains a mapping for the specified key.
boolean containsValue(Object value);
Returns true if this map maps one or more keys to the specified value.
int size();
Returns the number of key-value mappings in this map.
boolean isEmpty();
Returns true if this map contains no key-value mappings.
2.4.2.2.8.8 Map Positional Access and Search Operations
Not supported directly by the interface
2.4.2.2.8.9 Map Interface Bulk Operations
Bulk operations perform an operation on an entire Collection:
Method
Description
void clear();
The clear operation does exactly what you would think it could do: It removes all the mappings from the Map.
void putAll(Map<? extends K, ? extends V> m);
The putAll operation is the Map analogue of the Collection interface's addAll operation. In addition to its obvious use of dumping one Map into another, it has a second, more subtle use. Suppose a Map is used to represent a collection of attribute-value pairs; the putAll operation, in combination with the Map conversion constructor, provides a neat way to implement attribute map creation with default values.
2.4.2.2.8.10 Map Interface Views Operations
The Collection view methods allow a Map to be viewed as a Collection in these three ways:
Operation
Description
public Set<K> keySet();
The Set of keys contained in the Map.
public Collection<V> values();
The Collection of values contained in the Map. This Collection is not a Set, because multiple keys can map to the same value.
public Set<Map.Entry<K,V>> entrySet();
The Set of key-value pairs contained in the Map. The Map interface provides a small nested interface called Map.Entry, the type of the elements in this Set.
The Collection views provide the only means to iterate over a Map.
At first, many people worry that these operations may be slow because the Map has to create a new Collection instance each time a Collection view operation is called. Rest easy: There's no reason that a Map cannot always return the same object each time it is asked for a given Collection view. This is precisely what all the Map implementations in java.util do.
With all three Collection views, calling an Iterator's remove operation removes the associated entry from the backing Map, assuming that the backing Map supports element removal to begin with.
With the entrySet view, it is also possible to change the value associated with a key by calling a Map.Entry's setValue method during iteration (again, assuming the Map supports value modification to begin with). Note that these are the only safe ways to modify a Map during iteration; the behavior is unspecified if the underlying Map is modified in any other way while the iteration is in progress.
The Collection views support element removal in all its many forms:
Remove
removeAll
retainAll
Clear
Iterator.remove
The Collection views do not support element addition under any circumstances. It would make no sense for the keySet and values views, and it's unnecessary for the entrySet view, because the backing Map's put and putAll methods provide the same functionality.
2.4.2.2.8.10.1 Map Range-View Operations
Not Applicable
2.4.2.2.8.10.2 Fancy Uses of Collection Views: Map Algebra
When applied to the Collection views, bulk operations (containsAll, removeAll, and retainAll) are surprisingly potent tools.
2.4.2.2.8.11 Traversing over a Map
Traversing is done through one of the methods of the Map Views (keyset, values, entrySet).
With all three Collection views, calling an Iterator's remove operation removes the associated entry from the backing Map.
Note that these are the only safe ways to modify a Map during iteration; the behavior is unspecified if the underlying Map is modified in any other way while the iteration is in progress.
2.4.2.2.8.12 Translating Map into an Array
By using one of the Collection Views methods
2.4.2.2.2.13 Common Map Implementations
Class
Description
java.util.HashMap<K,V>
java.util.LinkedHashMap<K,V>
java.util.TreeMap<K,V>
2.4.2.2.8.14 Map Interface Algorithms
2.4.2.2.2.14.1 Multimaps
A multimap is like a Map but it can map each key to multiple values. The Java Collections Framework doesn't include an interface for multimaps because they aren't used all that commonly. It's a fairly simple matter to use a Map whose values are List instances as a multimap. This technique is demonstrated on the examples section
2.4.2.2.8.15 Map Performance Considerations
No special performance considerations for this interface
2.4.2.2.8.16 Map Examples
2.4.2.2.8.16.1 Map Basic Operations Examples
Generate a frequency table of the words found in the argument list.
import java.util.*;
public class Freq {
public static void main(String[] args) {
Map<String, Integer> m = new HashMap<String, Integer>();
// Initialize frequency table from command line
for (String a : args) {
Integer freq = m.get(a);
m.put(a, (freq == null) ? 1 : freq + 1);
}
System.out.println(m.size() + " distinct words:");
System.out.println(m);
}
}
The frequency table maps each word to the number of times it occurs in the argument list.
The only tricky thing about this program is the second argument of the put statement. That argument is a conditional expression that has the effect of setting the frequency to one if the word has never been seen before or one more than its current value if the word has already been seen.
Running this program with the command:
java Freq if it is to be it is up to me to delegate
Yields the following output:
8 distinct words:
{to=3, delegate=1, be=1, it=2, up=1, if=1, me=1, is=2}
Suppose you'd prefer to see the frequency table in alphabetical order:
All you have to do is change the implementation type of the Map from HashMap to TreeMap.
Making this four-character change causes the program to generate the following output from the same command line.
8 distinct words:
{be=1, delegate=1, if=1, is=2, it=2, me=1, to=3, up=1}
Similarly, you could make the program print the frequency table in the order the words first appear on the command line:
Simply by changing the implementation type of the map to LinkedHashMap.
Doing so results in the following output.
8 distinct words:
{if=1, it=2, is=2, to=3, be=1, up=1, me=1, delegate=1}
2.4.2.2.8.16.2 Map Conversion Constructor Examples
For example, suppose you have a Map, named m. The following one-liner creates a new HashMap initially containing all of the same key-value mappings as m.
Map<K, V> copy = new HashMap<K, V>(m);
2.4.2.2.8.16.3 Removing with an Iterator Example
2.4.2.2.8.16.4 Map Bulk Operations Examples
The following is a static factory method that demonstrates how to initialize a Map with default values and populate it with mandatory values:
static <K, V> Map<K, V> newAttributeMap(
Map<K, V>defaults, Map<K, V> overrides) {
Map<K, V> result = new HashMap<K, V>(defaults);
result.putAll(overrides);
return result;
}
2.4.2.2.8.16.5 Translating into an Array
2.4.2.2.8.16.6 Map Views Examples
This example illustrates the standard idiom for iterating over the keys in a Map with a for-each construct:
for (KeyType key : m.keySet())
System.out.println(key);
And with an iterator:
// Filter a map based on some property of its keys.
for (Iterator<Type> it = m.keySet().iterator(); it.hasNext(); )
if (it.next().isBogus())
it.remove();
The idiom for iterating over values
The idiom for iterating over values is analogous.
Following is the idiom for iterating over key-value pairs.
for (Map.Entry<KeyType, ValType> e : m.entrySet())
System.out.println(e.getKey() + ": " + e.getValue());
Suppose you want to know whether one Map is a submap of another — that is, whether the first Map contains all the key-value mappings in the second. The following idiom does the trick.
if (m1.entrySet().containsAll(m2.entrySet())) {
...
}
Along similar lines, suppose you want to know whether two Map objects contain mappings for all of the same keys.
if (m1.keySet().equals(m2.keySet())) {
...
}
Suppose you have a Map that represents a collection of attribute-value pairs, and two Sets representing required attributes and permissible attributes. (The permissible attributes include the required attributes.) The following snippet determines whether the attribute map conforms to these constraints and prints a detailed error message if it doesn't.
static <K, V> boolean validate(Map<K, V> attrMap,
Set<K> requiredAttrs, Set<K>permittedAttrs) {
boolean valid = true;
Set<K> attrs = attrMap.keySet();
if(!attrs.containsAll(requiredAttrs)) {
Set<K> missing = new HashSet<K>(requiredAttrs);
missing.removeAll(attrs);
System.out.println("Missing attributes: " + missing);
valid = false;
}
if (!permittedAttrs.containsAll(attrs)) {
Set<K> illegal = new HashSet<K>(attrs);
illegal.removeAll(permittedAttrs);
System.out.println("Illegal attributes: " + illegal);
valid = false;
}
return valid;
}
Suppose you want to know all the keys common to two Map objects.
Set<KeyType>commonKeys = new HashSet<KeyType>(m1.keySet());
commonKeys.retainAll(m2.keySet());
A similar idiom gets you the common values.
All the idioms presented thus far have been nondestructive; that is, they don't modify the backing Map. Here are a few that do:
Suppose you want to remove all of the key-value pairs that one Map has in common with another.
m1.entrySet().removeAll(m2.entrySet());
Suppose you want to remove from one Map all of the keys that have mappings in another.
m1.keySet().removeAll(m2.keySet());
What happens when you start mixing keys and values in the same bulk operation? Suppose you have a Map, managers, that maps each employee in a company to the employee's manager. We'll be deliberately vague about the types of the key and the value objects. It doesn't matter, as long as they're the same. Now suppose you want to know who all the "individual contributors" (or nonmanagers) are. The following snippet tells you exactly what you want to know.
Set<Employee> individualContributors =
new HashSet<Employee>(managers.keySet());
individualContributors.removeAll(managers.values());
Suppose you want to fire all the employees who report directly to some manager, Simon.
Employee simon = ... ;
managers.values().removeAll(Collections.singleton(simon));
Note that this idiom makes use of Collections.singleton, a static factory method that returns an immutable Set with the single, specified element.
Once you've done this, you may have a bunch of employees whose managers no longer work for the company (if any of Simon's direct-reports were themselves managers). The following code will tell you which employees have managers who no longer works for the company.
Map<Employee, Employee> m =
new HashMap<Employee, Employee>(managers);
m.values().removeAll(managers.keySet());
Set<Employee> slackers = m.keySet();
This example is a bit tricky. First, it makes a temporary copy of the Map, and it removes from the temporary copy all entries whose (manager) value is a key in the original Map. Remember that the original Map has an entry for each employee. Thus, the remaining entries in the temporary Map comprise all the entries from the original Map whose (manager) values are no longer employees. The keys in the temporary copy, then, represent precisely the employees that we're looking for.
Read a word list containing one word per line (all lowercase) and prints out all the anagram groups that meet a size criterion. An anagram group is a bunch of words, all of which contain exactly the same letters but in a different order.
import java.util.*;
import java.io.*;
public class Anagrams {
public static void main(String[] args) {
int minGroupSize = Integer.parseInt(args[1]);
// Read words from file and put into a simulated multimap
Map<String, List<String>> m
= new HashMap<String, List<String>>();
try {
Scanner s = new Scanner(new File(args[0]));
while (s.hasNext()) {
String word = s.next();
String alpha = alphabetize(word);
List<String> l = m.get(alpha);
if (l == null)
m.put(alpha, l=new ArrayList<String>());
l.add(word);
}
} catch (IOException e) {
System.err.println(e);
System.exit(1);
}
// Print all permutation groups above size threshold
for (List<String> l : m.values())
if (l.size() >= minGroupSize)
System.out.println(l.size() + ": " + l);
}
private static String alphabetize(String s) {
char[] a = s.toCharArray();
Arrays.sort(a);
return new String(a);
}
}
The program takes two arguments on the command line:
(1) the name of the dictionary file and
(2) the minimum size of anagram group to print out.
Anagram groups containing fewer words than the specified minimum are not printed.
There is a standard trick for finding anagram groups: For each word in the dictionary, alphabetize the letters in the word (that is, reorder the word's letters into alphabetical order) and put an entry into a multimap, mapping the alphabetized word to the original word. For example, the word bad causes an entry mapping abd into bad to be put into the multimap. A moment's reflection will show that all the words to which any given key maps form an anagram group. It's a simple matter to iterate over the keys in the multimap, printing out each anagram group that meets the size constraint.
Running this program on a 173,000-word dictionary file with a minimum anagram group size of eight produces the following output:
9: [estrin, inerts, insert, inters, niters, nitres, sinter,
triens, trines]
8: [lapse, leaps, pales, peals, pleas, salep, sepal, spale]
8: [aspers, parses, passer, prases, repass, spares, sparse,
spears]
10: [least, setal, slate, stale, steal, stela, taels, tales,
teals, tesla]
8: [enters, nester, renest, rentes, resent, tenser, ternes,
treens]
8: [arles, earls, lares, laser, lears, rales, reals, seral]
8: [earings, erasing, gainers, reagins, regains, reginas,
searing, seringa]
8: [peris, piers, pries, prise, ripes, speir, spier, spire]
12: [apers, apres, asper, pares, parse, pears, prase, presa,
rapes, reaps, spare, spear]
11: [alerts, alters, artels, estral, laster, ratels, salter,
slater, staler, stelar, talers]
9: [capers, crapes, escarp, pacers, parsec, recaps, scrape,
secpar, spacer]
9: [palest, palets, pastel, petals, plates, pleats, septal,
staple, tepals]
9: [anestri, antsier, nastier, ratines, retains, retinas,
retsina, stainer, stearin]
8: [ates, east, eats, etas, sate, seat, seta, teas]
8: [carets, cartes, caster, caters, crates, reacts, recast,
traces]
2.4.2.2.9 The SortedMap Interface
A SortedMap is a Map that maintains its entries in ascending order, according to the keys' natural ordering, or according to a Comparator.
2.4.2.2.9.1 SortedMap Interface Usages
- Example: A binary tree
- Example: A dictionary
The SortedMap interface provides operations for normal Map operations and for the following:2.4.2.2.9.2 High Level SortedMap Operations
- Range view - Performs arbitrary range operations on the sorted map.
- Endpoints - Returns the first or the last key in the sorted map.
- Comparator access - Returns the Comparator, if any, used to sort the map.
The Iterator returned by the iterator operation on any of the sorted map's Collection views traverse the collections in order.
The arrays returned by the Collection views' toArray operations contain the keys, values, or entries in order.
The operations SortedMap inherits from Map behave identically on sorted maps and normal maps with two exceptions:
2.4.2.2.9.3 SortedMap Idium
The following interface is the Map analog of SortedSet.
public interface SortedMap<K, V> extends Map<K, V>{
public abstract Comparator<? super K> comparator();
public abstract SortedMap<K, V> subMap(K fromKey, K toKey);
public abstract SortedMap<K, V> headMap(K toKey);
public abstract SortedMap<K, V> tailMap(K fromKey);
public abstract K firstKey();
public abstract K lastKey();
}
2.4.2.2.9.4 Compare SortedMap to Legacy API
No specific legacy API available.
2.4.2.2.9.5 SortedMap Object Comparisons
Not Applicable
2.4.2.2.9.6 The SortedMap Conversion Constructor
By convention, all general-purpose Map implementations provide a standard conversion constructor that takes a Map; SortedMap implementations are no exception.
In TreeMap, this constructor creates an instance that orders its entries according to their keys' natural ordering. This was probably a mistake. It would have been better to check dynamically to see whether the specified Map instance was a SortedMap and, if so, to sort the new map according to the same criterion (comparator or natural ordering). Because TreeMap took the approach it did, it also provides a constructor that takes a SortedMap and returns a new TreeMap containing the same mappings as the given SortedMap, sorted according to the same criterion. Note that it is the compile-time type of the argument, not its runtime type, that determines whether the SortedMap constructor is invoked in preference to the ordinary map constructor.
SortedMap implementations also provide, by convention, a constructor that takes a Comparator and returns an empty map sorted according to the specified Comparator. If null is passed to this constructor, it returns a Map that sorts its mappings according to their keys' natural ordering.
2.4.2.2.9.7 SortedMap Interface Basic operations
2.4.2.2.9.8 SortedMap Positional Access and Search Operations
Not supported directly by the interface
2.4.2.2.9.9 SortedMap Interface Bulk Operations
Bulk operations perform an operation on an entire Collection:
2.4.2.2.9.10 SortedMap Views Operations
Not Applicable
2.4.2.2.9.10.1 SortedMap Range-View Operations
Not Applicable
2.4.2.2.9.11 Traversing over a SortedMap
Not Applicable.
2.4.2.2.9.12 Translating SortedMap into an Array
Not Applicable.
2.4.2.2.9.13 Common SortedMap Implementations
java.util.TreeMap<K,V>
2.4.2.2.9.14 SortedMap Interface Algorithms
Because this interface is a precise Map analog of SortedSet, all the idioms and code examples in The SortedSet Interface section apply to SortedMap with only trivial modifications.
2.4.2.2.9.15 SortedMap Performance Considerations
Because this interface is a precise Map analog of SortedSet, all the idioms and code examples in The SortedSet Interface section apply to SortedMap with only trivial modifications.
2.4.2.2.9.16 SortedMap Examples
Because this interface is a precise Map analog of SortedSet, all the idioms and code examples in The SortedSet Interface section apply to SortedMap with only trivial modifications.
2.4.2.2.10 Summary of Interfaces
The core collection interfaces are the foundation of the Java Collections Framework.
distinct interface trees
The Java Collections Framework hierarchy consists of two distinct interface trees:
The first tree starts with the Collection interface, which provides for the basic functionality used by all collections, such as add and remove methods. Its subinterfaces — Set, List, and Queue — provide for more specialized collections.
The Set interface does not allow duplicate elements. This can be useful for storing collections such as a deck of cards or student records. The Set interface has a subinterface, SortedSet, that provides for ordering of elements in the set.
The List interface provides for an ordered collection, for situations in which you need precise control over where each element is inserted. You can retrieve elements from a List by their exact position.
The Queue interface enables additional insertion, extraction, and inspection operations. Elements in a Queue are typically ordered in on a FIFO basis.
The second tree starts with the Map interface, which maps keys and values similar to aHashtable.
Map's subinterface, SortedMap, maintains its key-value pairs in ascending order or in an order specified by a Comparator.
These interfaces allow collections to be manipulated independently of the details of their representation.
2.4.2.2.11 Questions and Exercises: Interfaces
2.4.2.2.11.1 Questions
This lesson mentions three ways to traverse a List. Describe them, and note the limitations of each.
Use the enhanced for statement:
List<Thing> list;
for (Thing thing : list) {
}
Limitations: cannot be used to add, remove, or modify elements.
Use the traditional for statement together with an Iterator:
List<Thing> list;
...
for (Iterator<Thing> it = list.iterator(); it.hasNext(); ) {
Thing thing = it.next();
...
}
Limitations: cannot be used to modify elements.
Use the traditional for statement together with an ListIterator:
List<Thing> list;
...
for (ListIterator<Thing> it = list.iterator(); it.hasNext(); ) {
Thing thing = it.next();
...
}
Limitations: none.
Consider the four core interfaces, Set, List, Queue, and Map. For each of the following four assignments, specify which of the four core interfaces is best suited, and explain how to use it to implement the assignment.
Whimsical Toys Inc (WTI) needs to record the names of all its employees. Every month, an employee will be chosen at random from these records to receive a free toy.
Use a List. Choose a random employee by picking a number between 0 and size()-1.
WTI has decided that each new product will be named after an employee — but only first names will be used, and each name will be used only once. Prepare a list of unique first names.
Use a Set. Collections that implement this interface don't allow the same element to be entered more than once.
WTI decides that it only wants to use the most popular names for its toys. Count the number of employees who have each first name.
Use a Map, where the keys are first names, and each value is a count of the number of employees with that first name.
WTI acquires season tickets for the local lacrosse team, to be shared by employees. Create a waiting list for this popular sport.
Use a Queue. Invoke add() to add employees to the waiting list, and remove() to remove them.
The following program is supposed to print the string "Blue". Instead, it throws an error. Why?
import java.util.*;
public class SortMe {
public static void main(String args[]) {
SortedSet<StringBuffer> s = new TreeSet<StringBuffer>();
s.add(new StringBuffer("Red"));
s.add(new StringBuffer("White"));
s.add(new StringBuffer("Blue"));
System.out.println(s.first());
}
}
2.4.2.2.11.2 Exercises
1. Write a program that prints its arguments in random order. Do not make a copy of the argument array.
2. Take the FindDups example and modify it to use a SortedSet instead of a Set. Specify a Comparator so that case is ignored when sorting and identifying set elements.
3. Write a method that takes a List<String> and applies String.trim to each element. To do this, you'll need to pick one of the three iteration idioms that you described in Question 1. Two of these will not give the result you want, so be sure to write a program that demonstrates that the method actually works!
2.4.2.3 Traversing over a Collection
Traversing a collection can be done with the following options:
Option
Description
Using the Iterator interface.
Every Collection interface has a method that returns an Iterator over the elements in it.
Since java5: Using the for-each construct
Using the ListIterator interface, when applicable
Some Collection interfaces support traversing a List interface with the ListIterator interface. It adds functionality applicable to List
2.4.2.3.1 Using the Iterator Interface
2.4.2.3.2 Using the for-each construct
Since java5:
You can also traverse a Collection with the for-each construct. It allows you to concisely traverse a collection or array using a for loop.
Use Iterator instead of the for-each construct when you need to:
- Remove the current element. The for-each construct hides the iterator, so you cannot call remove. Therefore, the for-each construct is not usable for filtering.
- Iterate over multiple collections in parallel.
2.4.2.4 Core Collections Algorithms
2.4.2.4.1 The Collections Class
The Collections class consists exclusively of static methods that operate on or return collections. It contains polymorphic algorithms that operate on collections, "wrappers", which return a new collection backed by a specified collection, and a few other odds and ends.
Below is a list of some of its common algorithms:
<T> Set<T> singleton(T o)
Shortens the lines of creating a Set from an object. Returns an immutable set containing only the specified object. The returned set is serializable.
<T> boolean replaceAll(List<T> list, T oldVal,T newVal)
Replaces all occurrences of one specified value in a list with another.
void shuffle(List<?> list)
Randomly permutes the specified list. All permutations occur with approximately equal likelihood
<T extends Comparable<? super T>> void sort(List<T> list)
Sorts a List using a merge sort algorithm, which provides a fast, stable sort. (A stable sort is one that does not reorder equal elements.)
void reverse(List<?> list)
Reverses the order of the elements in a List
void rotate(List<?> list, int distance)
Rotates all the elements in a List by a specified distance.
void swap(List<?> list, int i, int j)
Swaps the elements at specified positions in a List.
<T> void fill(List<? super T> list, T obj)
Overwrites every element in a List with the specified value.
<T> void copy(List<? super T> dest, List<? extends T> src)
Copies the source List into the destination List.
<T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c)
Searches for an element in an ordered List using the binary search algorithm.
int indexOfSubList(List<?> source, List<?> target)
Returns the index of the first sublist of one List that is equal to another.
int lastIndexOfSubList(List<?> source, List<?> target)
Returns the index of the last sublist of one List that is equal to another.
2.4.2.4.2 The Arrays Class
This class contains various methods for manipulating arrays (such as sorting and searching). This class also contains a static factory that allows arrays to be viewed as lists.
public static <T> List<T> asList(T... a)
Returns a fixed-size list backed by the specified array. This method acts as bridge between array-based and collection-based APIs, in combination with Collection.toArray(). The returned list is serializable and implements RandomAccess.
This method does not copy the array. Changes in the List write through to the array and vice versa. The resulting List is not a general-purpose List implementation, because it doesn't implement the add and remove operations: Arrays are not resizable.
2.4.2.99 Sources
Trail: Collections (The Java™ Tutorials)
2.4.2 Threads
2.4.2.1 V1.4.2
2.4.2.1.1 wait()
public final void java.lang.Object.wait() throws InterruptedException
Causes current thread to wait until another thread invokes the notify() method or the notifyAll() method for this object.
The current thread must own this object's monitor. The thread releases ownership of this monitor and waits until another thread notifies threads waiting on this object's monitor to wake up. The thread then waits until it can re-obtain ownership of the monitor and resumes execution.
2.4.2.1.2 notify()
public final void notify()
Wakes up a single thread that is waiting on this object's monitor. The choice of thread to be awakened is arbitrary. A thread waits on an object's monitor by calling one of the wait methods.
The awakened thread will not be able to proceed until the current thread relinquishes the lock on this object. The awakened thread will compete in the usual manner with any other threads to synchronize on this object.
This method should only be called by a thread that is the owner of this object's monitor.
2.4.2.1.3 notifyAll()
public final void notifyAll()
Wakes up all threads that are waiting on this object's monitor. A thread waits on an object's monitor by calling one of the wait methods.
The awakened threads will not be able to proceed until the current thread relinquishes the lock on this object. The awakened threads will compete in the usual manner with any other threads.
This method should only be called by a thread that is the owner of this object's monitor.
3. Design Patterns
3.1 Comet Design Pattern
Comet Design Pattern (AKA "reverse Ajax", "server-side push"). The idea: push data from the server to the browser without the browser requesting it.
3.1.1 Motivations for using Comet
While Ajax is a popular solution for dynamically pulling data requests from the server, it does nothing to help us push data to the client. Comet enhances the Ajax communication pattern by defining architecture for pushing data from the server to the client.
Comet has popularized asynchronous non-blocking HTTP programming. Instead of a Meta refresh from the server, the server can be contacted asynchronously using Ajax. This type of web development technique claims that it is faster compared to Ajax as it provides the same user experience while improving on interactivity with better overall speed.
Comet is based on creating and maintaining long-lived HTTP connections. Handling these connections efficiently requires a new approach to HTTP programming, i.e. handling asynchronous, non-blocking HTTP programming.
3.1.2 Comet styles
- Polling (normal polling) – The easiest way to enable Comet, but it has some limitations. It is done by using JavaScript XMLHttpRequest and setTimeout. As soon as the response comes back, wait a fixed amount of time, and then call it again.
- Long Polling – The most common "true" Comet technique. Keeps the connection open for a long time. An event on the server is sent to the client and closed, and the poll immediately begins anew. The advantage is that data goes from the server to the client as soon as it is available. A Web-based chat program probably is using this technique.
- Streaming – Long Poll variation. The server does not close the connection. When the connection times out the request is re-initiated. It uses XMLHttpRequest to check for a readyState of 3 (Receiving) (as opposed to 4 [Loaded]) and get the data that is "streaming" from the server. It has an added advantage of making far fewer requests to the server. Unfortunately, this technique only works reliably on the newer versions of Mozilla Firefox.
3.1.3 Sources
- Developing with Comet and Java
- Comet: The Next Stage for Ajax
- Asynchronous HTTP and Comet architectures
3.2 Reverse Ajax
See Comet
3.3 Server-side push
See Comet
3.4 Asynchronous HTTP
Asynchronous HTTP has a role in developing high-performance HTTP proxies and non-blocking HTTP clients, as well as the long-lived HTTP connections associated with Comet.
3.4.1 Synchronous message handling overview
At the message level, when performing a Synchronous call, the caller thread is suspended until the server response returns or a timeout is exceeded.
The synchronous approach requires a dedicated thread for each concurrent request, which consumes a certain amount of memory. This can become a problem if you have many concurrent calls to be performed on the client side.
At the application level, code execution is stopped, waiting for the response before further actions can be taken.
Client-side synchronous message handling is very easy to understand, as illustrated by the example in Listing 1.
Listing 1. Client example -- synchronous call
HttpClient httpClient = new HttpClient();
// create the request message
HttpRequest req = new HttpRequest("GET", "http://tools.ietf.org/html/rfc2616.html");
// the call blocks until the response returns
HttpResponse resp = httpClient.call(req);
int status = resp.getStatus();
// ...
3.4.2 Asynchronous message handling
At the message level (socket/protocol level) Asynchronous Message Handling means that an HTTP client performs a request without waiting for the server response.
When performing an asynchronous call it is necessary to define a handler, which will be notified if the response returns. Typically, such a handler will be passed over by performing the call. The call method returns immediately. The application-level code instructions after the send statement will be processed without waiting for a server response. The server response will be handled by performing the handler's callback method.
If the response returns, the network library will execute the callback method within a network-library-controlled thread. If necessary, the request message has to be synchronized with the response message at the application-code level. An asynchronous call is shown in Listing 2.
Listing 2. Client example -- asynchronous call
HttpClient httpClient = new HttpClient();
// response handler
IHttpResponseHandler responseHandler = new IHttpResponseHandler() {
public void onResponse(HttpResponse resp) throws IOException {
int status = resp.getStatus();
// ...
}
// ...
};
// create the request message
HttpRequest req = new HttpRequest("GET", "http://tools.ietf.org/html/rfc2616.html");
// send the request in an asynchronous way
httpClient.send(req, responseHandler);
// ...
The advantage of this approach is that the caller thread will not be suspended until the response returns. Based on a good network library implementation, no outstanding threads are required. In contrast to the synchronous call approach, the number of outstanding requests is not restricted to the number of possible threads.
3.4.3 HTTP pipelining
Asynchronous message handling also enables HTTP pipelining. Pipelining requires that the underlying HTTP connection is in persistent mode, which is the standard mode with HTTP/1.1. Pipelining has many advantages:
- Send multiple HTTP requests without waiting for the server response to former requests.
- The response messages will be returned by the server in the same order as they were sent.
- In contrast to non-persistent connections, the persistent HTTP connection stays open after the server has returned a response.
- Pipelining can significantly improve application performance when fetching many objects from the same server.
- The implicit persistent mode eliminates the overhead of establishing a new connection for each new request, by allowing for the reuse of connections.
- Pipelining also eliminates the need for additional connection instances to perform concurrent requests.
3.4.4 Message content streaming
Although asynchronous message handling can improve application performance by avoiding waiting threads, another performance bottleneck arises when reading the message content.
It is not unusual for an HTTP message to contain kilobytes of content data. On the transport level, such larger messages will be broken down into several TCP segments. The TCP segment size is limited and depends on the underlying network and link layer. For Ethernet-based networks the maximum TCP segment size is up to 1460 bytes.
Bodyless HTTP messages such as GET requests don't contain body data. Often the size of such bodyless messages is smaller than 1 kilobyte. Listing 3 shows a simple HTTP request:
Listing 3. HTTP request
GET /html/rfc2616.html HTTP/1.1
Host: tools.ietf.org:80
User-Agent: xSocket-http/2.0-alpha-3
The correlating response of the request shown above contains a message body of 0.5 megabytes. On a personal Internet connection, the response message shown in Listing 4 would be broken into several TCP segments when sent:
Listing 4. HTTP response
HTTP/1.1 200 OK
Content-Length: 509497
Accept-Ranges: bytes
Last-Modified: Tue, 20 Nov 2007 03:10:57 GMT
Date: Sun, 03 Feb 2008 09:46:31 GMT
Content-Type: text/html; charset=US-ASCII
ETag: "d4026-7c639-9d13d240"
Server: Apache/2.2.6 (Debian) DAV/2 SVN/1.4.4 mod_python/3.3.1 Python/2.4.4 mod_ssl/2.2.6 OpenSSL/0.9.8g mod_perl/2.0.3 Perl/v5.8.8
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html lang="en" xml:lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=us-ascii" />
<meta name="robots" content="index,follow" />
<meta name="creator" content="rfcmarkup version 1.53" />
<link rel="icon" href="/images/rfc.png" type="image/png" />
<link rel="shortcut icon" href="/images/rfc.png" type="image/png" />
<title>RFC 2616 Hypertext Transfer Protocol -- HTTP/1.1</title>
</small></small></span>
</body></html>
Data transfer fragmentation can be hidden at the API level by accessing the body data as a steady and continuous stream. This approach, known as streaming, avoids the need to buffer large chunks of data before processing it. Streaming can also reduce the latency of HTTP calls, especially if both peers support streaming.
Using streaming allows the receiver to start processing the message content before the entire message has been transmitted. Often an HTTP message contains unstructured or semi-structured data, such as HTML pages, video, or music files, which will be processed immediately by the receiving peer. For instance, most browsers start rendering and displaying HTML pages without waiting for the complete page. For this reason most HTTP libraries support a stream-based API to access the message content.
In contrast to the body data, the message header contains well-structured data entries. To access the message header data most HTTP libraries provide dedicated and typed setter and getter methods. In most use cases the header can only be processed after the complete header has been received. The HTTP/1.1 specification doesn't define the order of the message headers, though it does state that it's a good practice to send general-header fields first, followed by request-header or response-header fields, and ending with the entity-header fields.
3.4.5 Streaming input data
To process received body data in a streaming manner, the receiving peer has to be notified immediately after the message header has been received. Based on the message header information, the receiver is able to determine the type of the received HTTP message, if body data exists, and which type of content the body contains.
The example code in Listing 5 (below) streams a returned HTML page into a file. The response message data will be processed as soon as it appears. Based on the retrieved body channel the FileChannel's transferFrom() implementation calls the body channel's read() method to transfer the data into the filesystem. This occurs in a blocking manner. If the socket read buffer is empty, the body channel's read() method will block until more data is received or the end-of-stream is reached. Blocking the read operation suspends the current caller thread, which can lead to inefficiency in system resource usage.
3.4.99 Sources
- Asynchronous HTTP and Comet architectures
2. Java Technologies
2.0 Dictionary
Java Transaction API (JTA)
Java Transaction API
JavaOne
JRockit
JTA
2.1 Java Design Patterns
2.1.1 Comet
2.3 Servers
2.3.1 Apache Tomcat
2.4 Pure Java
2.4.1 Basic I/O
2.4.2 Java Collections Framework
2.4.2 Threads
3. Design Patterns
3.0 Dictionary
3.1 Comet Design Pattern
3.1.1 Motivations for using Comet
3.1.2 Comet styles
3.1.3 Sources
3.2 Reverse Ajax
3.3 Server-side push
3.4 Asynchronous HTTP
3.4.1 Synchronous message handling overview
3.4.2 Asynchronous message handling
3.4.3 HTTP pipelining
3.4.4 Message content streaming
3.4.5 Streaming input data
3.4.99 Sources
2. Java Technologies
2.0 Dictionary
The terms are applicable to this document and have other meanings in other documents.
- Java Transaction API (JTA) - JTA, or the Java Transaction API, allows you to demarcate transactions in a manner that is independent of the transaction manager implementation. GlassFish Server implements the transaction manager with the Java Transaction Service (JTS).However, your code doesn’t call the JTS methods directly but instead invokes the JTA methods, which then call the lower-level JTS routines.(Java Transaction API - The Java Transaction API is one of the J2EE APIs allowing distributed transactions to be performed across multiple XA resources, in a manner that that is independent of the transaction manager implementation. It provides for:
- Demarcation of transaction boundaries
- X/Open XA API allowing resources to participate in transactions.
See also XA)
- JavaOne - Aannual conference by Sun Microsystems to discuss Java technologies, primarily among Java developers.
- JRockit - A proprietary JVM of BEA Systems that is part of the Oracle Fusion Middleware. JRockit and HotSpot virtual machine are currently being integrated around the release date of JDK 8. JRockit is free and publically available.
- JTA - See Java Transaction API
2.3 Servers
2.3.1 Apache Tomcat
2.3.1.1 Apache Tomcat 6.0
2.3.1.1.1 Implementing Comet
2.3.1.1.1.1 org.apache.catalina.CometProcessor
public interface org.apache.catalina.CometProcessor extends Servlet
Servlets which implement the org.apache.catalina.CometProcessor interface will have their event method invoked rather than the usual service method, according to the event which occurred. The event object parameter gives access to the usual request and response objects. The main difference is that those objects are fully functional at any time between the BEGIN event until an END or ERROR event.
Also see Apache Tomcat 6.0 - Advanced IO and Tomcat
2.4 Pure Java
2.4.1 Basic I/O
Basic I/O is consisted of:
- I/O Streams - A powerful concept that greatly simplifies I/O operations.
- Serialization - Lets a program write whole objects out to streams and read them back again.
- File I/O (Featuring NIO.2) -
- File system operations -
- Random access files -
2.4.1.1 I/O Streams
2.4.1.1.1 Introduction
An I/O Stream represents an input source or an output destination. A stream can represent many different kinds of sources and destinations, including disk files, devices, other programs, and memory arrays.
2.4.1.1.2 Supported Data
Streams support many different kinds of data, including simple bytes, primitive data types, localized characters, and objects.
2.4.1.1.3 Supported Operations
Some streams simply pass on data; others manipulate and transform the data in useful ways.
2.4.1.1.4 I/O Streams Model
No matter how they work internally, all streams present the same simple model to programs that use them: A stream is a sequence of data. A program uses an input stream to read data from a source, one item at a time:
Reading information into a program.
A program uses an output stream to write data to a destination, one item at time:
Writing information from a program.
The data source and data destination pictured above can be anything that holds, generates, or consumes data. Obviously this includes disk files, but a source or destination can also be another program, a peripheral device, a network socket, or an array.
2.4.1.1.5 I/O Streams Packages
Most of the classes covered in the I/O Streams section are in the java.io package.
2.4.1.1.6 I/O Streams Components
I/O Streams are consisted mainly of the following components:
Component
Description
Byte Streams
Handle I/O of raw binary data.
Character Streams
Handle I/O of character data, automatically handling translation to and from the local character set.
Buffered Streams
Optimize input and output by reducing the number of calls to the native API.
Scanning and Formatting
Allows a program to read and write formatted text.
I/O from the Command Line
Describes the Standard Streams and the Console object.
Data Streams
Handle binary I/O of primitive data type and String values.
Object Streams
Handle binary I/O of objects.
2.4.1.1.6.1 Byte Streams
Programs use byte streams to perform input and output of 8-bit bytes. All byte stream classes are descended from InputStream and OutputStream.
2.4.1.1.6.1.1 Byte Input Streams Main Implementation Hierarchy
Implementation
Description
java.io.InputStream
This abstract class is the superclass of all classes representing an input stream of bytes.
java.io.ByteArrayInputStream
A ByteArrayInputStream contains an internal buffer that contains bytes that may be read from the stream.
java.io.FileInputStream
A FileInputStream obtains input bytes from a file in a file system.
java.io.ObjectInputStream
An ObjectInputStream deserializes primitive data and objects previously written using an ObjectOutputStream.
java.io.FilterInputStream
A FilterInputStream contains some other input stream, which it uses as its basic source of data, possibly transforming the data along the way or providing additional functionality.
java.io.BufferedInputStream
A BufferedInputStream adds functionality to another input stream-namely, the ability to buffer the input and to support the mark and reset methods.
java.io.DataInputStream
A data input stream lets an application read primitive Javadata types from an underlying input stream in a machine-independent way.
java.io.ObjectInputStream
An ObjectInputStream deserializes primitive data and objects previously written using an ObjectOutputStream.
2.4.1.1.6.1.2 Byte Output Streams Main Implementation Hierarchy
Implementation
Description
java.io.OutputStream
This abstract class is the superclass of all classes representing an output stream of bytes.
java.io.ByteArrayOutputStream
This class implements an output stream in which the data is written into a byte array.
java.io.FileOutputStream
A file output stream is an output stream for writing data to a File or to a FileDescriptor.
java.io.ObjectOutputStream
An ObjectOutputStream writes primitive data types and graphs of Java objects to an OutputStream.
java.io.FilterOutputStream
This class is the superclass of all classes that filter output streams.
java.io.BufferedOutputStream
The class implements a buffered output stream.
java.io.DataOutputStream
A data output stream lets an application write primitive Java data types to an output stream in a portable way.
java.io.PrintStream
A PrintStream adds functionality to another output stream, namely the ability to print representations of various data values conveniently.
2.4.1.1.6.1.1 File I/O Byte Streams
The most basic file I/O byte streams implementations are FileInputStream and FileOutputStream. They receive as an input a path that represents the file.
2.4.1.1.6.1.2 Using Byte Streams
2.4.1.1.6.1.2.1 Using Byte Input Streams
Let’s examine a common idium, which uses file input byte stream to read a file one byte at a time.
FileInputStream in = null;
try {
in = new FileInputStream("somefile.txt");
int c;
while ((c = in.read()) != -1) {
System.out.println(c);
}
} finally {
if (in != null) {
in.close();
}
}
}
}
The steps of the above idium are:
1. Initialize the input stream:
in = new FileInputStream("somefile.txt");
2. Reading one byte at a time from the stream until end of file is reached:
while ((c = in.read()) != -1) {
3. Closing the stream at end of process, or in case of an exception:
finally {
if (in != null) {
in.close();
}
}
It spends most of its time in a simple loop that reads the input stream and processes the input, one byte at a time:
Notice that read() returns an int value. If the input is a stream of bytes, why doesn't read() return a byte value? Using an int as a return type allows read() to use -1 to indicate that it has reached the end of the stream.
2.4.1.1.6.1.2.1 Using Byte Output Streams
Let’s take the previous idium one step forward and add it a file byte output stream, to write the bytes read to a file.
FileInputStream in = null;
FileOutputStream out = null;
try {
in = new FileInputStream("xanadu.txt");
out = new FileOutputStream("outagain.txt");
int c;
while ((c = in.read()) != -1) {
out.write(c);
}
} finally {
if (in != null) {
in.close();
}
if (out != null) {
out.close();
}
}
The steps added to the above idium are:
1. Initialize the output stream:
out = new FileOutputStream("outagain.txt");
2. Writing the byte read from the input stream to the output stream:
out.write(c);
3. Closing the output stream at end of process, or in case of an exception:
if (out != null) {
out.close();
}
2.4.1.1.6.1.3 Byte Streams Rules of Thumb
2.4.1.1.6.1.3.1 Always Close Streams
Closing a stream when it's no longer needed is very important — Most programming techniques uses a finally block to guarantee that both streams will be closed even if an error occurs. This practice helps avoid serious resource leaks.
When closing a stream you should check that the object representing it contains a valid object reference to the stream. This is to ensure that a stream really exists. One possible error is that a stream was unable to open. When that happens, the stream variable corresponding to the file never changes from its initial null value. That's why CopyBytes makes sure that each stream variable contains an object reference before invoking close.
2.4.1.1.6.1.3.2 When Not to Use Byte Streams
Byte Streams actually represent a kind of low-level I/O that you should avoid. There are streams for different kinds of datatypes: character streams, object streams etc’. Byte streams should only be used for the most primitive I/O.
So why talk about byte streams? Because all other stream types are built on byte streams.
2.4.1.1.6.2 Character Streams
Java stores character values using Unicode conventions. Character stream I/O automatically translates this internal format to and from the local character set.
Input and output of character streams is done with stream classes that automatically translate to and from the local character set. A program that uses character streams in place of byte streams automatically adapts to the local character set and is ready for internationalization — all without extra effort by the programmer.
2.4.1.1.6.2.1 Internationalization
If internationalization isn't a priority, you can simply use the character stream classes without paying much attention to character set issues. Later, if internationalization becomes a priority, your program can be adapted without extensive recoding. See the Internationalization trail for more information.
2.4.1.1.6.2.2 Character Input Streams Main Implementation Hierarchy
Implementation
Description
java.io.Reader
Abstract class for reading character streams.
java.io.BufferedReader
Reads text from a character-input stream, buffering characters so as to provide for the efficient reading of characters, arrays, and lines.
java.io.LineNumberReader
A buffered character-input stream that keeps track of line numbers.
java.io.CharArrayReader
This class implements a character buffer that can be used as a character-input stream.
java.io.InputStreamReader
An InputStreamReader is a bridge from byte streams to character streams: It reads bytes and decodes them into characters using a specified charset.
java.io.FileReader
Convenience class for reading character files.
java.io.StringReader
A character stream whose source is a string.
2.4.1.1.6.2.3 Character Output Streams Main Implementation Hierarchy
Implementation
Description
java.io.Writer
java.io.BufferedWriter
java.io.CharArrayWriter
java.io.FilterWriter
java.io.OutputStreamWriter
java.io.FileWriter
java.io.PrintWriter
java.io.StringWriter
2.4.1.1.6.2.2 Using Character Streams
All character stream classes are descended from Reader and Writer. As with byte streams, there are character stream classes that specialize in file I/O: FileReader and FileWriter.
The CopyCharacters example illustrates these classes.
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
public class CopyCharacters {
public static void main(String[] args) throws IOException {
FileReader inputStream = null;
FileWriter outputStream = null;
try {
inputStream = new FileReader("xanadu.txt");
outputStream = new FileWriter("characteroutput.txt");
int c;
while ((c = inputStream.read()) != -1) {
outputStream.write(c);
}
} finally {
if (inputStream != null) {
inputStream.close();
}
if (outputStream != null) {
outputStream.close();
}
}
}
}
CopyCharacters is very similar to CopyBytes. The most important difference is that CopyCharacters uses FileReader and FileWriter for input and output in place of FileInputStream and FileOutputStream. Notice that both CopyBytes and CopyCharacters use an int variable to read to and write from. However, in CopyCharacters, the int variable holds a character value in its last 16 bits; in CopyBytes, the int variable holds a byte value in its last 8 bits.
Download the JDK
Search the Tutorials
Hide the TOC
Character Streams that Use Byte Streams
Character streams are often "wrappers" for byte streams. The character stream uses the byte stream to perform the physical I/O, while the character stream handles translation between characters and bytes. FileReader, for example, uses FileInputStream, while FileWriter uses FileOutputStream.
There are two general-purpose byte-to-character "bridge" streams: InputStreamReader and OutputStreamWriter. Use them to create character streams when there are no prepackaged character stream classes that meet your needs. The sockets lesson in the networking trail shows how to create character streams from the byte streams provided by socket classes.
Line-Oriented I/O
Character I/O usually occurs in bigger units than single characters. One common unit is the line: a string of characters with a line terminator at the end. A line terminator can be a carriage-return/line-feed sequence ("\r\n"), a single carriage-return ("\r"), or a single line-feed ("\n"). Supporting all possible line terminators allows programs to read text files created on any of the widely used operating systems.
Let's modify the CopyCharacters example to use line-oriented I/O. To do this, we have to use two classes we haven't seen before, BufferedReader and PrintWriter. We'll explore these classes in greater depth in Buffered I/O and Formatting. Right now, we're just interested in their support for line-oriented I/O.
The CopyLines example invokes BufferedReader.readLine and PrintWriter.println to do input and output one line at a time.
import java.io.FileReader;
import java.io.FileWriter;
import java.io.BufferedReader;
import java.io.PrintWriter;
import java.io.IOException;
public class CopyLines {
public static void main(String[] args) throws IOException {
BufferedReader inputStream = null;
PrintWriter outputStream = null;
try {
inputStream =
new BufferedReader(new FileReader("xanadu.txt"));
outputStream =
new PrintWriter(new FileWriter("characteroutput.txt"));
String l;
while ((l = inputStream.readLine()) != null) {
outputStream.println(l);
}
} finally {
if (inputStream != null) {
inputStream.close();
}
if (outputStream != null) {
outputStream.close();
}
}
}
}
Invoking readLine returns a line of text with the line. CopyLines outputs each line using println, which appends the line terminator for the current operating system. This might not be the same line terminator that was used in the input file.
There are many ways to structure text input and output beyond characters and lines. For more information, see Scanning and Formatting.
« Previous • Trail • Next »
Problems with the examples? Try Compiling and Running the Examples: FAQs.
Complaints? Compliments? Suggestions? Give us your feedback.
Your use of this page and all the material on pages under "The Java Tutorials" banner, and all the material on pages under "The Java Tutorials" banner is subject to the Java SE Tutorial Copyright and License. Additionally, any example code contained in any of these Java Tutorials pages is licensed under the Code Sample License.
duke image
Oracle logo
About Oracle | Oracle Technology Network | Terms of Service
Copyright © 1995, 2011 Oracle and/or its affiliates. All rights reserved.
Previous page: Byte Streams
Next page: Buffered Streams
2.4.1.2 File I/O (Featuring NIO.2)
File I/O consisted mainly of:
Component
Description
What is a Path?
Examines the concept of a path on a file system.
The Path Class
Introduces the cornerstone class of the java.nio.file package.
Path Operations
Looks at methods in the Path class that deal with syntactic operations.
File Operations
Introduces concepts common to many of the file I/O methods.
Checking a File or Directory
Shows how to check a file's existence and its level of accessibility.
Deleting a File or Directory.
Copying a File or Directory.
Moving a File or Directory.
Managing Metadata
Explains how to read and set file attributes.
Reading, Writing and Creating Files
Shows the stream and channel methods for reading and writing files.
Random Access Files
Shows how to read or write files in a non-sequentially manner.
Creating and Reading Directories
Covers API specific to directories, such as how to list a directory's contents.
Links, Symbolic or Otherwise
Covers issues specific to symbolic and hard links.
Walking the File Tree
Demonstrates how to recursively visit each file and directory in a file tree.
Finding Files
Shows how to search for files using pattern matching.
Watching a Directory for Changes
Shows how to use the watch service to detect files that are added, removed or updated in one or more directories.
Other Useful Methods
Covers important API that didn't fit elsewhere in the lesson.
Legacy File I/O Code
Shows how to leverage Path functionality if you have older code using the java.io.File class. A table mapping java.io.File API to java.nio.file API is provided.
2.4.1.2.1 File I/O Packages
Most of the classes covered in the File I/O section are in the java.nio.file package.
2.4.1.3 Summary
A summary of the key points covered in this trail.
2.4.1.4 Questions and Exercises
Test what you've learned in this trail by trying these questions and exercises.
2.4.1.5 The I/O Classes in Action
Many of the examples in the next trail, Custom Networking use the I/O streams described in this lesson to read from and write to network connections.
2.4.1.6 Security consideration
Some I/O operations are subject to approval by the current security manager. The example programs contained in these lessons are standalone applications, which by default have no security manager. To work in an applet, most of these examples would have to be modified. See What Applets Can and Cannot Do for information about the security restrictions placed on applets.
2.4.1.7 API Docs
2.4.1.7.1 FileInputStream
A FileInputStream obtains input bytes from a file in a file system. What files are available depends on the host environment.
FileInputStream is meant for reading streams of raw bytes such as image data. For reading streams of characters, consider using FileReader.
2.4.1.7.1.1 package
java.io
2.4.1.7.1.2 Idium
package java.io;
public class FileInputStream extends InputStream {
public FileInputStream(String paramString) throws FileNotFoundException;
public FileInputStream(File paramFile) throws FileNotFoundException;
public FileInputStream(FileDescriptor paramFileDescriptor);
public native int read;
public int read(byte[] paramArrayOfByte) throws IOException
public int read(byte[] paramArrayOfByte, int paramInt1, int paramInt2) throws IOException;
public native long skip(long paramLong) throws IOException;
public native int available() throws IOException;
public void close() throws IOException;
private native void close0() throws IOException;
}
2.4.1.7.1.3 Main Constructors
public FileInputStream(File file) throws FileNotFoundException
Creates a FileInputStream by opening a connection to an actual file, the file named by the File object file in the file system.
public FileInputStream(String name) throws FileNotFoundException
Creates a FileInputStream by opening a connection to an actual file, the file named by the path name name in the file system.
2.4.1.7.1.4 Main Methods
public void close()throws IOException
Closes this file input stream and releases any system resources associated with the stream.
public int read() throws IOException
Reads a byte of data from this input stream.
public int read(byte[] b) throws IOException
Reads up to b.length bytes of data from this input stream into an array of bytes.
public int read(byte[] b, int off, int len) throws IOException
Reads up to len bytes of data from this input stream into an array of bytes.
public long skip(long n) throws IOException
Skips over and discards n bytes of data from the input stream.
2.4.1.7.2 FileOutputStream
2.4.1.8 Examples
Print the byte input of a file to the console:
import java.io.FileInputStream;
import java.io.IOException;
public class PrintFile {
public static void main(String[] args) throws IOException {
FileInputStream is = null;
try {
is = new FileInputStream("input.txt");
int b;
while ((b = is.read()) != -1) {
System.out.println(b);
}
} catch (IOException e) {
e.printStackTrace();
}
finally {
if (is != null) {
is.close();
}
}
}
}
There are several interesting points in this idium:
Although the read operation returns a byte it is retrieved as an int. Dealing with int instead of byte simplifies the test if the read operation reached the end of the file. In this case the returned value will be -1. The int primitive enables the use of negative values, while byte do not.
The while loop checks for the read operation result on the fly, within the condition construct
Running the program with the following input “hello world!!!” yeilds the following output:
Output
104
101
108
108
111
32
119
111
114
108
100
33
33
33
This is because the printed data is not the character values, but their byte representations
Use a file byte streams to copy a file one byte at a time.
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
public class CopyBytes {
public static void main(String[] args) throws IOException {
FileInputStream in = null;
FileOutputStream out = null;
try {
in = new FileInputStream("xanadu.txt");
out = new FileOutputStream("outagain.txt");
int c;
while ((c = in.read()) != -1) {
out.write(c);
}
} finally {
if (in != null) {
in.close();
}
if (out != null) {
out.close();
}
}
}
}
CopyBytes spends most of its time in a simple loop that reads the input stream and writes the output stream, one byte at a time, as shown in the following figure:
Simple byte stream input and output.
Simple byte stream input and output.
Notice that read() returns an int value. If the input is a stream of bytes, why doesn't read() return a byte value? Using an int as a return type allows read() to use -1 to indicate that it has reached the end of the stream.
Basic I/O topics:
- I/O Streams – a powerful concept that greatly simplifies I/O operations
- I/O Serialization – write whole objects out to streams and read them back again.
- File I/O and file system operations, including random access files.
2.4.1.1 Packages
java.io package – Provides for system input and output through data streams, serialization and the file system. Most of the classes covered in the I/O Streams section are covered here.
java.nio package – Defines buffers, which are containers for data, and provides an overview of the other NIO packages. Most of the classes covered in the File I/O section are covered here.
2.4.1.2 Main components
java.io.InputStream
javax.sound.sampled.AudioInputStream
java.io.ByteArrayInputStream
java.io.FileInputStream
java.io.FilterInputStream
java.io.BufferedInputStream
--------------------------------------------------------------------------------
java.util.zip.CheckedInputStream
--------------------------------------------------------------------------------
javax.crypto.CipherInputStream
--------------------------------------------------------------------------------
java.io.DataInputStream
java.security.DigestInputStream
--------------------------------------------------------------------------------
java.util.zip.InflaterInputStream
java.io.LineNumberInputStream
--------------------------------------------------------------------------------
javax.swing.ProgressMonitorInputStream
--------------------------------------------------------------------------------
java.io.PushbackInputStream
--------------------------------------------------------------------------------
org.omg.CORBA.portable.InputStream
java.io.ObjectInputStream
java.io.PipedInputStream
java.io.SequenceInputStream
java.io.StringBufferInputStream
2.4.1.3 I/O Streams
A stream is a sequence of data. A program uses an input stream to read data from a source, one item at a time, or an output stream to write data to a destination, one item at time.
Streams support many different kinds of data, including simple bytes, primitive data types, localized characters, and objects. Some streams simply pass on data; others manipulate and transform the data in useful ways.
There are 7 types of streams:
- Byte Streams – handle I/O of raw binary data.
- Character Streams – handle I/O of character data, automatically handling translation to and from the local character set.
- Buffered Streams – optimize input and output by reducing the number of calls to the native API.
- Scanning and Formatting – allows a program to read and write formatted text.
- I/O from the Command Line – describes the Standard Streams and the Console object.
- Data Streams – handle binary I/O of primitive data type and String values.
- Object Streams – handle binary I/O of objects.
2.4.1.3.1 Byte Streams
Byte streams are the most basic kind of streams.
2.4.1.3.1.1 Example File
For sample input, we'll use the example file xanadu.txt, which contains the following verse:
In Xanadu did Kubla Khan
A stately pleasure-dome decree:
Where Alph, the sacred river, ran
Through caverns measureless to man
Down to a sunless sea.
2.4.1.4 File I/O (Featuring NIO.2)
2.4.1.99 Sources
- Lesson Basic I-O (The Java™ Tutorials Essential Classes)
2.4.1.99 Basic I/O Considerations
2.4.1.99.1 Character Encoding
When possible, it is best practice to arrange that all the input/output peripherals will pass/store data in the same character encoding. This eliminates the need to convert the data from one character encoding to the other.
2.4.1.99.1.1 JVM Default Character Encoding
To avoid the need to define the character encoding on each time you parse a stream data, you can set the default JVM character encoding. The JVM default character encoding is inherited from the environment it is installed on.
2.4.1.99.1.1.1 Setting the JVM Default Character Encoding
You can set it manually by running the java program with a special JVM property:
-Dfile.encoding=whatever
Alternatively you can define it as an environment variable. Using an environment variable enables to define the JVM property only once, instead of defining it for each java command:
JAVA_TOOL_OPTIONS=-Dfile.encoding=UTF8
2.4.1.99.2 Actual Byte Data
The actual byte data that is saved or stored on a stream may be different from its byte data representation.
Example 1: Using the the ASCII character encoding
The character that represents the English capital letter ‘A’ is represented in ASCII as 41 hex number (1000001 binary).
ASCII characters are saved in the actual disk on a binary byte data, on the 7 less significant bits out of 8. The most significant bit can be ignored, ‘0’, ‘1’ or can serve as a parity bit, i.e. it can be saved on disk as 01000001 or 11000001.
Example 2: Using the the UTF-8 character encoding
The character that represents the currency dollar sign ‘$’ is represented in UTF-8 as U+0024 (24 hex number, 100100 binary).
UTF-8 characters are not saved on the actual disk as their actual value. There is a special binary algorithm for that.
The ‘$’ sign is saved on disk as the following two bytes: 11000010 10100010 (hexadecimal C2 A2).
2.4.2 Java Collections Framework
2.4.2.1 Introduction to Collections
A collection is an object that groups multiple elements into a single unit. Typically, they represent data items that form a natural group.
2.4.2.1.1 Collections Usages
- A poker hand – a collection of cards
- A mail folder – a collection of letters
- A telephone directory – a mapping of names to phone numbers.
2.4.2.1.2 What Is a Collections Framework?
A collections framework is a unified architecture for representing and manipulating collections.
2.4.2.1.2.1 Core Elements
All collections frameworks contain the following:
- Interfaces: Interfaces allow collections to be manipulated independently of the details of their representation.
- Implementations: These are the concrete implementations of the collection interfaces.
- Algorithms: These are the methods that perform useful computations, such as searching and sorting, on objects that implement collection interfaces.
2.4.2.2 Interfaces
2.4.2.2.1 Introduction to Interfaces
The core collection interfaces encapsulate different types of collections. Core collection interfaces are the foundation of the Java Collections Framework.
2.4.2.2.1.1 Why Interfaces
These interfaces allow collections to be manipulated independently of the details of their representation.
2.4.2.2.1.2 Common Interface Hierarchy
The core collection interfaces.
The collection intererfaces consists of two distinct interface hierarchies.
Although a Map is not a true Collection it belongs to the collections framework because of the way that its keys and values are manipulated. To understand the Map interface see the Map interface section.
Common Interface Hierarchy
java.util.Collection
java.util.Queue<E>
java.util.List
java.util.Set
java.util.SortedSet
java.util.Map
java.util.SortedMap
Since java5:
Note that all the core collection interfaces are generic.
2.4.2.2.1.3 Sorted Interfaces
The last two core collection interfaces are merely sorted versions of Set and Map:
- SortedSet — a Set that maintains its elements in ascending order. Sorted sets are used for naturally ordered sets.
- SortedMap — a Map that maintains its mappings in ascending key order. This is the Map analog of SortedSet. Sorted maps are used for naturally ordered collections of key/value pairs.
To understand how the sorted interfaces maintain the order of their elements, see the Object Ordering section.
2.4.2.2.1.4 Helper Interfaces
In addition to the core collection interfaces there are several helper interfaces in the framework that assist to the represention and manipulation of collections.
2.4.2.2.2 The Collection Interface
Collection is the root of the collection hierarchy.
2.4.2.2.2.1 Collection Interface Usages
- It represents a group of objects known as its elements
- It is used when maximum generality is desired, for example when using the Conversion Constructor.
2.4.2.2.2.2 High Level Collection Operations
Operation type
Description
Basic
- Checking size (size,isEmpty)
- Checking if an object is part of the collection (contains)
- Add/Remove (add, remove)
- Traversing (iterator)
Bulk
Operations that impact many elements in the collection (containsAll, addAll, removeAll, retainAll, clear)
Conversion
Translating into an array (toArray);
Comparison
Comparing to other Collection interface (equals, hashCode)
2.4.2.2.2.3 Collection Idium
public interface Collection<E> extends Iterable<E> {
// Basic operations
public abstract int size();
public abstract boolean isEmpty();
public abstract boolean contains(Object element);
public abstract boolean add(E element);
public abstract boolean remove(Object element);
public abstract Iterator<E> iterator();
// Bulk operations
public abstract boolean containsAll(Collection<?> c);
public abstract boolean addAll(Collection<? extends E> c);
public abstract boolean removeAll(Collection<?> c);
public abstract boolean retainAll(Collection<?> c);
public abstract void clear();
// Conversion operations
public abstract Object[] toArray();
public abstract <T> T[] toArray(T[] a);
// Comparison operations
public abstract boolean equals(Object o);
public abstract int hashCode();
}
2.4.2.2.2.4 Compare Collection to Legacy API
No specific legacy API available.
2.4.2.2.2.5 Collection Object Comparisons
Not supported directly by the Collection interface
2.4.2.2.2.6 The Collection Conversion Constructor
Most of the Collection implementations have a Conversion Constructor that allows you to convert the collection's type. It takes a Collection argument and initializes the new collection to contain all of the elements in the specified collection, whatever the given collection's subinterface or implementation type.
Usually the Conversion Constructor is smart enough to fit the limitations of the new collection type.
2.4.2.2.2.7 Collection Basic operations
Method
Description
int size();
boolean isEmpty();
How many elements are in the collection
boolean contains(Object element);
Check whether a given object is in the collection
boolean add(E element);
Add and remove an element from the collection
boolean remove(Object element);
Iterator<E> iterator();
Provide an iterator over the collection
2.4.2.2.2.8 Collection Positional Access and Search Operations
Not supported directly by the interface
2.4.2.2.2.9 Collection Bulk Operations
Bulk operations perform an operation on an entire Collection:
Method
Description
boolean containsAll(Collection<?> c);
Checks if the target collection contains all elements in the specified collection
boolean addAll(Collection<? extends E> c);
Adds all elements in the specified collection to the target collection
boolean removeAll(Collection<?> c);
Removes from the target collection all elements that are in the specified collection. This method can be used with the singletone method to shorten the code
boolean retainAll(Collection<?> c);
Removes from the target collection all elements that are not in the specified collection
void clear();
Removes all elements from the collection
2.4.2.2.2.10 Collection Views
Not Applicable
2.4.2.2.2.10.1 Collection Range-View Operations
Not Applicable
2.4.2.2.2.11 Traversing over a Collection
Traversing a collection can be done with the following options:
Option
Description
Using the Iterator interface.
Every Collection interface has a method that returns an Iterator over the elements in it.
Since java5:
Using the for-each construct
Using the ListIterator interface, when applicable
Some Collection interfaces support traversing a List interface with the ListIterator interface. It adds functionality applicable to List
2.4.2.2.2.12 Translating Collection into an Array
A collection can be translated into an array using the toArray methods.
- Object[] toArray() – creates a new array of Object.
Since java5:
- <T> T[] toArray(T[] a) – The more complex form allows the caller to provide an array and to choose the runtime type of the output array.
2.4.2.2.2.13 Common Collection Implementations
Class
Description
java.util.ArrayList<E>
java.util.HashSet<E>
java.util.LinkedHashSet<E>
java.util.LinkedList<E>
java.util.TreeSet<E>
2.4.2.2.2.14 Collection Algorithms
No special algorithms for this interface in the core API
2.4.2.2.2.15 Collection Performance Considerations
No special performance considerations for this interface
2.4.2.2.2.16 Collection Examples
2.4.2.2.2.16.1 Conversion Constructor Examples
- Create a new ArrayList (implementation of List), containing all elements from another Collection:
List<String> list = new ArrayList<String>(c);
- Removing duplicate values from a Collection by creating a new Set:
Collection<Type> noDups = new HashSet<Type>(c);
- Removing duplicate values and keeping the order:
Collection<Type> noDups = new LinkedHashSet<Type>(c);
- Coding the previous example into a method:
public static <E> Set<E> removeDups(Collection<E> c) {
return new LinkedHashSet<E>(c);
}
2.4.2.2.2.16.2 Removing with an Iterator Example
- Remove from a collection specific elements by using an Iterator:
static void filter(Collection<?> c) {
for (Iterator<?> it = c.iterator(); it.hasNext(); )
if (!cond(it.next()))
it.remove();
}
2.4.2.2.2.16.3 Interface Bulk Operations Examples
- c.removeAll(Collections.singleton(e));
- c.removeAll(Collections.singleton(null));
2.4.2.2.2.16.4 Translating into an Array
Since java5:
- Traslate a collection into an array of Strings:
String[] a = c.toArray(new String[0]);
2.4.2.2.3 The Iterator Interface
The Iterator interface traverses over a collection.
2.4.2.2.3.1 Iterator Inteface Usages
It traverses the elemnts in the collection by generating a series of elements, one at a time. Successive calls to the next method return successive elements of the series.
2.4.2.2.3.2 High Level Iterator Operations
Operation Type
Description
Basic
Traversing over the elements of an Iterator
Removing an element from the Iterator and the backing Collection
2.4.2.2.3.3 Iterator Idium
The following shows the Collection interface:
public abstract interface Iterator<E> {
public abstract boolean hasNext();
public abstract E next();
public abstract void remove();
}
2.4.2.2.3.4 Comparing Iterator to Legacy API
Iterator takes the place of Enumeration in the Java collections framework. Iterators differ from enumerations in two ways:
Iterators allow the caller to remove elements from the underlying collection during the iteration with well-defined semantics.
Method names have been improved.
New implementations should consider using Iterator in preference to Enumeration.
2.4.2.2.3.5 Iterator Object Comparisons
Not Applicable.
2.4.2.2.3.6 Iterator Conversion Constructor
Not Applicable.
2.4.2.2.3.7 Iterator Basic operations
Method
Description
boolean hasNext();
Returns true if the iteration has more elements.
E next();
Returns the next element in the iteration.
void remove();
Removes from the underlying collection the last element returned by the iterator.
2.4.2.2.3.8 Iterator Positional Access and Search Operations
Not Applicable.
2.4.2.2.3.9 Iterator Bulk Operations
Not Applicable.
2.4.2.2.3.10 Iterator Views Operations
Not Applicable
2.4.2.2.3.10.1 Iterator Range-View Operations
Not Applicable
2.4.2.2.3.11 Traversing over an Iterator
Not Applicable.
2.4.2.2.3.12 Translating Iterator into an Array
Not Applicable.
2.4.2.2.3.13 Common Iterator Implementations
The direct use of Iterator implementations is not common.
2.4.2.2.3.14 Iterator Algorithms
No special algorithms for this interface in the core API
2.4.2.2.3.15 Iterator Performance Considerations
No special performance considerations for this interface
2.4.2.2.3.16 Iterator Examples
- Print all elements of a collection c:
Iterator itr = c.iterator();
while (itr.hasNext()) {
System.out.println(itr.next());
}
2.4.2.2.4 The Set Interface
A Set is a Collection that cannot contain duplicate elements.
2.4.2.2.4.1 Set Usages
Example: Storing the Employee ids
2.4.2.2.4.2 High Level Set Operations
Same contract as for the Collection interface
2.4.2.2.4.3 Set Idium
public interface Set<E> extends Collection<E> {
// Basic operations
public abstract int size();
public abstract boolean isEmpty();
public abstract boolean contains(Object element);
public abstract boolean add(E element); //optional
public abstract boolean remove(Object element); //optional
public abstract Iterator<E> iterator();
// Bulk operations
public abstract boolean containsAll(Collection<?> c);
public abstract boolean addAll(Collection<? extends E> c); //optional
public abstract boolean removeAll(Collection<?> c); //optional
public abstract boolean retainAll(Collection<?> c); //optional
public abstract void clear(); //optional
// Array Operations
public abstract Object[] toArray();
public abstract <T> T[] toArray(T[] a);
// Comparison operations
public abstract boolean equals(Object o);
public abstract int hashCode();
}
2.4.2.2.4.4 Compare Set to Legacy API
No specific legacy API available.
2.4.2.2.4.5 Set Object Comparisons
The Set interface adds a stronger contract on the behavior of the equals and hashCode operations, allowing Set instances to be compared meaningfully even if their implementation types differ. Two Set instances are equal if they contain the same elements.
2.4.2.2.4.6 The Set Conversion Constructor
Same contract as for the Collection interface
2.4.2.2.4.7 Set Basic Operations
Method
Description
int size();
boolean isEmpty();
boolean contains(Object element);
Does exactly what you think.
boolean add(E element);
Adds the specified element to the Set if it's not already present; Returns a boolean indicating whether the element was added.
boolean remove(Object element);
Removes the specified element from the Set if it's present and returns a boolean indicating whether the element was present.
Iterator<E> iterator();
Returns an Iterator over the Set
2.4.2.2.4.8 Set Positional Access and Search Operations
Not supported directly by the interface
2.4.2.2.4.9 Set Bulk Operations
Bulk operations are particularly well suited to Sets; when applied, they perform standard set-algebraic operations.
Method
Description
boolean containsAll(Collection<?> c);
Checks if the specified set is a subset of the target collection
boolean addAll(Collection<? extends E> c);
Transforms the target set into the unions of the target set and the specified set
boolean removeAll(Collection<?> c);
Transforms the target set into the (asymmetric) set difference of the target set and the specified set
boolean retainAll(Collection<?> c);
Transforms the target set into the intersection of the target set and the specified set
void clear();
Same contract as for the Collection interface
2.4.2.2.2.10 Set Views Operations
Not Applicable
2.4.2.2.2.10.1 Set Range-View Operations
Not Applicable
2.4.2.2.4.11 Traversing over a Set
Same contract as for the Collection interface
2.4.2.2.4.12 Translating Set into an Array
Same contract as for the Collection interface
2.4.2.2.2.13 Common Set Implementations
Class
Description
java.util.HashSet<E>
- Stores its elements in a hash table
- Best-performing implementation
- It makes no guarantees concerning the order of iteration.
java.util.TreeSet<E>
- Stores its elements in a red-black tree
- It is substantially slower than HashSet.
- Orders its elements based on their values
java.util.LinkedHashSet<E>
- Implemented as a hash table with a linked list running through it
- Spares its clients from the unspecified, generally chaotic ordering provided by HashSet at a cost that is only slightly higher.
- Orders its elements based on the order in which they were inserted into the set (insertion-order).
2.4.2.2.2.14 Set Algorithms
No special algorithms for this interface in the core API
2.4.2.2.2.15 Set Performance Considerations
No special performance considerations for this interface
2.4.2.2.4.16 Set Examples
2.4.2.2.2.16.1 Set Bulk Operations Examples
Checks if s2 is a subset of s1
s1.containsAll(s2)
Transform s1 into the union of s1 and s2
s1.addAll(s2)
- Transforms s1 into the intersection of s1 and s2.
s1.retainAll(s2)
- Transforms s1 into the (asymmetric) set difference of s1 and s2.
s1.removeAll(s2)
- Calculate the union, intersection, and difference of two sets nondestructively:
Set<Type> union = new HashSet<Type>(s1);
union.addAll(s2);
Set<Type> intersection = new HashSet<Type>(s1);
intersection.retainAll(s2);
Set<Type> difference = new HashSet<Type>(s1);
difference.removeAll(s2);
- Parse an argument list and print the unique and duplicate args:
import java.util.*;
public class FindDups2 {
public static void main(String[] args) {
Set<String> uniques = new HashSet<String>();
Set<String> dups = new HashSet<String>();
for (String a : args)
if (!uniques.add(a))
dups.add(a);
// Destructive set-difference
uniques.removeAll(dups);
System.out.println("Unique words: " + uniques);
System.out.println("Duplicate words: " + dups);
}
}
- Find the symmetric set difference:
Set<Type> symmetricDiff = new HashSet<Type>(s1);
symmetricDiff.addAll(s2);
Set<Type> tmp = new HashSet<Type>(s1);
tmp.retainAll(s2));
symmetricDiff.removeAll(tmp);
2.4.2.2.5 The List Interface
A List is an ordered Collection (sometimes called a sequence). Lists may contain duplicate elements.
2.4.2.2.5.1 List Usages
Example:
A List of plates to put on the table
A List of chairs.
2.4.2.2.5.2 List Operations
In addition to the extended Collection interface, the List interface adds the following operations:
Operation
Description
Positional access
Manipulates elements based on their numerical position (their index/indice)
Search
searches for a specified object in the list and returns its numerical position
Iteration
Extends Iterator to take advantage of the list's sequential nature
Range-view
Performs arbitrary range operations on the list.
2.4.2.2.5.3 List Idium
public abstract interface List<E> extends Collection<E> {
// Basic operations
public abstract int size();
public abstract boolean isEmpty();
public abstract boolean contains(Object element);
public abstract boolean add(E element);
public abstract boolean remove(Object element);
public abstract Iterator<E> iterator();
// Bulk operations
public abstract boolean containsAll(Collection<?> c);
public abstract boolean addAll(Collection<? extends E> c);
public abstract boolean removeAll(Collection<?> c);
public abstract boolean retainAll(Collection<?> c);
public abstract void clear();
// Array operations
public abstract Object[] toArray();
public abstract <T> T[] toArray(T[] a);
// Comparison operations
public abstract boolean equals(Object o);
public abstract int hashCode();
// Positional access
public abstract E get(int index);
public abstract E set(int index, E element);
public abstract void add(int index, E element);
public abstract boolean addAll(int index, Collection<? extends E> c);
public abstract E remove(int index);
// Search
public abstract int indexOf(Object o);
public abstract int lastIndexOf(Object o);
// Iteration
public abstract ListIterator<E> listIterator();
public abstract ListIterator<E> listIterator(int index);
// Range-view
public abstract List<E> subList(int from, int to);
}
2.4.2.2.5.4 Compare List to Legacy API
2.4.2.2.5.5.1 Comparison to Vector
List is an interface, while Vector is a concrete implementation.
List fixes several minor API deficiencies in Vector.
2.4.2.2.5.5 List Object Comparison
Like the Set interface, List strengthens the requirements on the equals and hashCode methods so that two List objects can be compared for logical equality without regard to their implementation classes. Two List objects are equal if they contain the same elements in the same order.
2.4.2.2.5.6 The List Conversion Constructor
Same contract as for the Collection interface
2.4.2.2.5.7 List Basic Operations
Most of the basic operations inherited from Collection all do about what you'd expect them to do, assuming you're already familiar with them. The following methods have some new functionality:
Operation
Description
boolean add(E element);
Appends the specified element to the end of this list.
void add(int index, E element);
Inserts the specified element at the specified position in this list.
boolean addAll(Collection<? extends E> c);
Appends all of the elements in the specified collection to the end of this list, in the order that they are returned by the specified collection's iterator.
boolean addAll(int index, Collection<? extends E> c);
Inserts all of the elements in the specified collection into this list at the specified position. Shifts the element currently at that position and any subsequent elements to the right. The new elements will appear in this list in the order that they are returned by the specified collection's iterator.
2.4.2.2.5.8 List Positional Access and Search Operations
Positional access and search operations are applied by the following methods:
Operation
Description
E get(int index);
Returns the element at the specified position in this list
E set(int index, E element);
Replaces the element at the specified position with the specified element. Returns the element previously at the specified position
void add(int index, E element);
Inserts the specified element at the specified position in this list and shifts the element at that position and any subsequent elements to the right.
boolean remove(Object element);
Removes the first occurrence of the specified element from this list, if it is present
E remove(int index);
Removes the element at the specified position in this list and shifts any subsequent elements to the left.
int indexOf(Object o);
Returns the index of the first occurrence of the specified element
int lastIndexOf(Object o);
Returns the index of the last occurrence of the specified element in this list
boolean addAll(int index, Collection<? extends E> c);
Inserts all the elements of the specified Collection starting at the specified position. The elements are inserted in the order they are returned by the specified Collection's iterator.
2.4.2.2.2.9 List Bulk Operations
Same contract as for the Collection interface
2.4.2.2.2.10 List Views Operations
2.4.2.2.2.10.1 List Range-View Operations
The range-view operation, subList(), returns a List view of the portion of this list. It is provided with the following method:
Operation
Description
List<E> subList(int fromIndex, int toIndex)
Returns a view of the portion of this list between the specified fromIndex, inclusive, and toIndex, exclusive.
As the term view implies, the returned List is backed up by the List on which subList was called, so changes in the former are reflected in the latter.
This method eliminates the need for explicit range operations of the sort that commonly exist for arrays. Any operation that expects a List can be used as a range operation by passing a subList view instead of a whole List.
Although the subList operation is extremely powerful, some care must be exercised when using it. The semantics of the List returned by subList become undefined if elements are added to or removed from the backing List in any way other than via the returned List.
2.4.2.2.5.11 Traversing over a List
In addition to the contract of the Collection interface, the List interface also provides a richer iterator, called a ListIterator, which allows you to:
Traverse the list in either direction
Modify the list during iteration
Obtain the current position of the iterator
The ListIterator is provided by calling the following method:
Operation
Description
public abstract ListIterator<E> listIterator();
Returns a list iterator over the elements in this list (in proper sequence).
public abstract ListIterator<E> listIterator(int index);
Returns a list iterator of the elements in this list (in proper sequence), starting at the specified position in this list.
The three methods that ListIterator inherits from Iterator (hasNext, next, and remove) do exactly the same thing in both interfaces. The hasPrevious and the previous operations are exact analogues of hasNext and next. The former operations refer to the element before the (implicit) cursor, whereas the latter refer to the element after the cursor. The previous operation moves the cursor backward, whereas next moves it forward.
2.4.2.2.5.12 Translating List into an Array
Object[] toArray()
Returns an array containing all of the elements in this list in proper sequence (from first to last element).
<T> T[] toArray(T[] a)
Returns an array containing all of the elements in this list in proper sequence (from first to last element); the runtime type of the returned array is that of the specified array.
2.4.2.2.2.13 Common List Implementations
Class
Description
java.util.ArrayList<E>
java.util.LinkedList<E>
2.4.2.2.5.14 List Algorithms
Most polymorphic algorithms in the Collections class apply specifically to List. Here's a summary of these algorithms, which are described in more detail in the Algorithms section.
2.4.2.2.5.15 List Performance Considerations
For many common List implementations, such as ArrayList, the performance of removing elements from the end of the list is substantially better than that of removing elements from the beginning.
2.4.2.2.5.16 List Examples
Removing a range of elements from a List:
list.subList(fromIndex, toIndex).clear();
Search for an element in a range:
int i = list.subList(fromIndex, toIndex).indexOf(o);
int j = list.subList(fromIndex, toIndex).lastIndexOf(o);
A polymorphic algorithm to deal a hand from a deck using subList:
public static <E> List<E> dealHand(List<E> deck, int n) {
int deckSize = deck.size();
List<E> handView = deck.subList(deckSize - n, deckSize);
List<E> hand = new ArrayList<E>(handView);
handView.clear();
return hand;
}
Note that this algorithm removes the hand from the end of the deck. For many common List implementations, such as ArrayList, the performance of removing elements from the end of the list is substantially better than that of removing elements from the beginning.
The following is a program that uses the dealHand method in combination with Collections.shuffle to generate hands from a normal 52-card deck. The program takes two command-line arguments: (1) the number of hands to deal and (2) the number of cards in each hand.
import java.util.*;
public class Deal {
public static void main(String[] args) {
if (args.length < 2) {
System.out.println("Usage: Deal hands cards");
return;
}
int numHands = Integer.parseInt(args[0]);
int cardsPerHand = Integer.parseInt(args[1]);
// Make a normal 52-card deck.
String[] suit = new String[] {
"spades", "hearts", "diamonds", "clubs" };
String[] rank = new String[] {
"ace","2","3","4","5","6","7","8",
"9","10","jack","queen","king" };
List<String> deck = new ArrayList<String>();
for (int i = 0; i < suit.length; i++)
for (int j = 0; j < rank.length; j++)
deck.add(rank[j] + " of " + suit[i]);
// Shuffle the deck.
Collections.shuffle(deck);
if (numHands * cardsPerHand > deck.size()) {
System.out.println("Not enough cards.");
return;
}
for (int i=0; i < numHands; i++)
System.out.println(dealHand(deck, cardsPerHand));
}
public static <E> List<E> dealHand(List<E> deck, int n) {
int deckSize = deck.size();
List<E> handView = deck.subList(deckSize - n, deckSize);
List<E> hand = new ArrayList<E>(handView);
handView.clear();
return hand;
}
}
Running the program produces output like the following:
% java Deal 4 5
[8 of hearts, jack of spades, 3 of spades, 4 of spades,
king of diamonds]
[4 of diamonds, ace of clubs, 6 of clubs, jack of hearts,
queen of hearts]
[7 of spades, 5 of spades, 2 of diamonds, queen of diamonds,
9 of clubs]
[8 of spades, 6 of diamonds, ace of spades, 3 of hearts,
ace of hearts]
the following idiom concatenates one list to another.
list1.addAll(list2);
Here's a nondestructive form of this idiom, which produces a third List consisting of the second list appended to the first.
List<Type> list3 = new ArrayList<Type>(list1);
list3.addAll(list2);
2.4.2.2.5.16.1 Positional Access and Search Operations Examples
A polymorphic method to swap two indexed values in a List:
public static <E> void swap(List<E> a, int i, int j) {
E tmp = a.get(i);
a.set(i, a.get(j));
a.set(j, tmp);
}
A polymorphic algorithm that uses the preceding swap method to shuffle:
public static void shuffle(List<?> list, Random rnd) {
for (int i = list.size(); i > 1; i--)
swap(list, i - 1, rnd.nextInt(i));
}
Print the words on an argument list in random order, using Collections.shuffle():
import java.util.*;
public class Shuffle {
public static void main(String[] args) {
List<String> list = new ArrayList<String>();
for (String a : args)
list.add(a);
Collections.shuffle(list, new Random());
System.out.println(list);
}
}
Taking advantage of Arrays.asList:
import java.util.*;
public class Shuffle {
public static void main(String[] args) {
List<String> list = Arrays.asList(args);
Collections.shuffle(list);
System.out.println(list);
}
}
2.4.2.2.6 The ListIterator interface
The ListIterator is a special iterator for lists. It has more functionality than the standard general Iterator.
2.4.2.2.6.1 ListIterator Usages
- Traverse the list in either direction
- Modify the list during iteration
- Obtain the iterator's current position in the list.
2.4.2.2.6.2 High Level ListIterator Operations
In addition to the gereral Iterator, the ListIterator adds functionality to navigate forward or backward in the Iterator.
2.4.2.2.6.3 ListIterator Idium
public abstract interface ListIterator<E> extends Iterator<E> {
public abstract boolean hasNext();
public abstract E next();
public abstract boolean hasPrevious();
public abstract E previous();
public abstract int nextIndex();
public abstract int previousIndex();
public abstract void remove();
public abstract void set(E paramE);
public abstract void add(E paramE);
}
2.4.2.2.6.4 Compare ListIterator to Legacy API
Not Applicable.
2.4.2.2.6.5 ListIterator Object Comparisons
Not Applicable.
2.4.2.2.6.6 The ListIterator Conversion Constructor
Not Applicable.
2.4.2.2.6.7 ListIterator Basic operations
Operation
Description
boolean hasNext();
Returns true if this list iterator has more elements when traversing the list in the forward direction.
E next();
Returns the next element in the list.
boolean hasPrevious();
Returns true if this list iterator has more elements when traversing the list in the reverse direction.
E previous();
Returns the previous element in the list.
int nextIndex();
Returns the index of the element that would be returned by a subsequent call to next.
int previousIndex();
Returns the index of the element that would be returned by a subsequent call to previous.
void remove();
Removes from the list the last element that was returned by next or previous (optional operation).
void set(E paramE);
Replaces the last element returned by next or previous with the specified element.
void add(E paramE);
Inserts the specified element into the list.
2.4.2.2.6.8 ListIterator Positional Access and Search Operations
The operations of the ListIterator work on the last element returned by next or previous.
2.4.2.2.6.9 ListIterator Bulk Operations
Not Applicable.
2.4.2.2.2.10 ListIterator Views Operations
Not Applicable
2.4.2.2.2.10.1 ListIterator Range-View Operations
Not Applicable
2.4.2.2.6.11 Traversing over a ListIterator
Not Applicable.
2.4.2.2.6.12 Translating ListIterator into an Array
Not Applicable.
2.4.2.2.6.13 Common ListIterator Implementations
The direct use of ListIterator implementations is not common.
2.4.2.2.6.14 ListIterator Algorithms
No special algorithms for this interface in the core API
2.4.2.2.6.15 ListIterator Performance Considerations
No special performance considerations for this interface
2.4.2.2.6.16 ListIterator Examples
- Iterate backward through a list.
for (ListIterator<Type> it = list.listIterator(list.size());
it.hasPrevious(); ) {
Type t = it.previous();
...
}
2.4.2.2.7 The SortedSet Interface
A SortedSet is a Set that maintains its elements in ascending order, sorted according to the elements' natural ordering or according to a Comparator provided at SortedSet creation time.
2.4.2.2.7.1 SortedSet Usages
A set of library books sorted by their name
A set of country names
2.4.2.2.7.2 SortedSet Operations
In addition to the normal Set operations, the SortedSet interface provides operations for the following:
Operation Type
Description
Range view
Allows arbitrary range operations on the sorted set
Endpoints
Returns the first or last element in the sorted set
Comparator access
Returns the Comparator, if any, used to sort the set
The operations that SortedSet inherits from Set behave identically on sorted sets and normal sets with two exceptions:
The Iterator returned by the iterator operation traverses the sorted set in order.
The array returned by toArray contains the sorted set's elements in order.
TreeSet elements must be instances of a class that implements Comparable.
2.4.2.2.7.3 SortedSet Idium
public abstract interface SortedSet<E> extends Set<E> {
// Basic operations
public abstract E first();
public abstract E last();
// Comparison operations
public abstract Comparator<? super E> comparator();
// Range-view
public abstract SortedSet<E> subSet(E paramE1, E paramE2);
public abstract SortedSet<E> headSet(E paramE);
public abstract SortedSet<E> tailSet(E paramE);
}
2.4.2.2.7.4 Compare SortedSet to Legacy API
Not Applicable
2.4.2.2.7.5 SortedSet Object Comparison
Not Applicable
2.4.2.2.7.6 The SortedSet Conversion Constructor
The standard conversion constructor that is defined in Collection sorts the elements only by their natural ordering and does not check the specified collection for a Comparator. To solve it the interface implementations define another constructor with a specified parameter of SortedSet.
2.4.2.2.7.7 SortedSet Basic Operations
Same contract as for the Collection interface
2.4.2.2.7.8 SortedSet Positional Access and Search Operations
Not Applicable
2.4.2.2.7.9 SortedSet Bulk Operations
Same contract as for the Collection interface
2.4.2.2.2.10 SortedSet Views Operations
2.4.2.2.2.10.1 SortedSet Range-View Operations
The range-view operations are somewhat analogous to those provided by the List interface, but there are several big differences:
Range views of a sorted set remain valid even if the backing sorted set is modified directly.
Sorted sets provide three range-view operations. While the subSet operation is very similar to the List.subList operation, SortedSet adds two new endpoint operations to return the first and last elements in the sorted set:
SortedSet<E> subSet(E fromElement, E toElement)
Takes two endpoints, like the List.subList method.
While the subList method takes indices, the endpoints of subSet are objects and must be comparable to the elements in the sorted set, using the Set's Comparator or the natural ordering of its elements, whichever the Set uses to order itself.
Like List.subList, the range is half open, including its low endpoint but excluding the high one.
SortedSet<E> headSet(E toElement)
Take a single Object argument
Returns a view of the initial portion of the backing SortedSet, up to but not including the specified object
SortedSet<E> tailSet(E fromElement)
Take a single Object argument
Returns a view of the final portion of the backing SortedSet, beginning with the specified object and continuing to the end of the backing SortedSet.
2.4.2.2.7.11 Traversing over the SortedSet
Same contract as for the Set interface
2.4.2.2.7.12 Translating SortedSet into an Array
Same contract as for the Set interface
2.4.2.2.2.13 Common SortedSet Implementations
Class
Description
java.util.HashSet<E>
java.util.LinkedHashSet<E>
java.util.TreeSet<E>
2.4.2.2.7.14 SortedSet Algorithms
No special core algorithms are known
2.4.2.2.7.15 SortedSet Performance Considerations
No special performance considerations are known
2.4.2.2.7.16 SortedSet Interface Examples
2.4.2.2.7.16.1 SortedSet Range-View Examples
How many words between "doorbell" and "pickle", including "doorbell" but excluding "pickle", are contained in a SortedSet of strings called dictionary:
int count = dictionary.subSet("doorbell", "pickle").size();
Remove all the elements beginning with the letter f:
dictionary.subSet("f", "g").clear();
A similar trick can be used to print a table telling you how many words begin with each letter:
for (char ch = 'a'; ch <= 'z'; ) {
String from = String.valueOf(ch++);
String to = String.valueOf(ch);
System.out.println(from + ": " +
dictionary.subSet(from, to).size());
}
How many words between "doorbell" and "pickle", including doorbell and pickle, are contained in the dictionary:
count = dictionary.subSet("doorbell", "pickle\0").size();
Calculate the number of words between "doorbell" and "pickle", excluding both:
count = dictionary.subSet("doorbell\0", "pickle").size();
View the dictionary as two disjoint volumes (a-m and n-z):
SortedSet<String> volume1 = dictionary.headSet("n");
SortedSet<String> volume2 = dictionary.tailSet("n");
2.4.2.2.8 The Map Interface
A Map is an object that maps keys to values. A map cannot contain duplicate keys: Each key can map to at most one value. It models the mathematical function abstraction.
2.4.2.2.8.1 Map Interface Usages
For example: A map that maps keys of the personId to the object representing this person
2.4.2.2.8.2 High Level Map Operations
In addition to the contract extended from the Collection interface, map adds operations to handle the Map contract. The operations added are from the following types:
Basic
Bulk
View
Comparison
2.4.2.2.8.3 Map Idium
public interface Map<K,V> {
// Basic operations
public abstract V put(K key, V value);
public abstract V get(Object key);
public abstract V remove(Object key);
public abstract boolean containsKey(Object key);
public abstract boolean containsValue(Object value);
public abstract int size();
public abstract boolean isEmpty();
// Bulk operations
public abstract void putAll(Map<? extends K, ? extends V> m);
public abstract void clear();
// Collection Views
public abstract Set<K> keySet();
public abstract Collection<V> values();
public abstract Set<Entry<K, V>> entrySet();
// Interface for entrySet elements
public interface Entry {
K getKey();
V getValue();
V setValue(V value);
}
// Comparison operations
public abstract boolean equals(Object o);
public abstract int hashCode();
}
2.4.2.2.8.4 Compare Map to Legacy API
2.4.2.2.8.4.1 Comparison to Hashtable
Map is an interface, while Hashtable is a concrete implementation
Map provides Collection views instead of direct support for iteration via Enumeration objects. Collection views greatly enhance the expressiveness of the interface, as discussed later in this section.
Map allows you to iterate over keys, values, or key-value pairs; Hashtable does not provide the third option.
Map provides a safe way to remove entries in the midst of iteration; Hashtable did not.
Map fixes a minor deficiency in the Hashtable interface. Hashtable has a method called contains, which returns true if the Hashtable contains a given value. Given its name, you'd expect this method to return true if the Hashtable contained a given key, because the key is the primary access mechanism for a Hashtable. The Map interface eliminates this source of confusion by renaming the method containsValue. Also, this improves the interface's consistency — containsValue parallels containsKey.
2.4.2.2.8.5 Map Interface Object Comparisons
Like the Set and List interfaces, Map strengthens the requirements on the equals and hashCode methods so that two Map objects can be compared for logical equality without regard to their implementation types. Two Map instances are equal if they represent the same key-value mappings.
2.4.2.2.8.6 The Map Interface Conversion Constructor
By convention, all general-purpose Map implementations provide constructors that take a Map object and initialize the new Map to contain all the key-value mappings in the specified Map. This standard Map conversion constructor is entirely analogous to the standard Collection constructor: It allows the caller to create a Map of a desired implementation type that initially contains all of the mappings in another Map, regardless of the other Map's implementation type.
2.4.2.2.8.7 Map Interface Basic operations
The basic operations of Map (put, get, containsKey, containsValue, size, and isEmpty) behave exactly like their counterparts in Hashtable:
V put(K key, V value);
Associates the specified value with the specified key in this map.
V get(Object key);
Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.
boolean containsKey(Object key);
Returns true if this map contains a mapping for the specified key.
boolean containsValue(Object value);
Returns true if this map maps one or more keys to the specified value.
int size();
Returns the number of key-value mappings in this map.
boolean isEmpty();
Returns true if this map contains no key-value mappings.
2.4.2.2.8.8 Map Positional Access and Search Operations
Not supported directly by the interface
2.4.2.2.8.9 Map Interface Bulk Operations
Bulk operations perform an operation on an entire Collection:
Method
Description
void clear();
The clear operation does exactly what you would think it could do: It removes all the mappings from the Map.
void putAll(Map<? extends K, ? extends V> m);
The putAll operation is the Map analogue of the Collection interface's addAll operation. In addition to its obvious use of dumping one Map into another, it has a second, more subtle use. Suppose a Map is used to represent a collection of attribute-value pairs; the putAll operation, in combination with the Map conversion constructor, provides a neat way to implement attribute map creation with default values.
2.4.2.2.8.10 Map Interface Views Operations
The Collection view methods allow a Map to be viewed as a Collection in these three ways:
Operation
Description
public Set<K> keySet();
The Set of keys contained in the Map.
public Collection<V> values();
The Collection of values contained in the Map. This Collection is not a Set, because multiple keys can map to the same value.
public Set<Map.Entry<K,V>> entrySet();
The Set of key-value pairs contained in the Map. The Map interface provides a small nested interface called Map.Entry, the type of the elements in this Set.
The Collection views provide the only means to iterate over a Map.
At first, many people worry that these operations may be slow because the Map has to create a new Collection instance each time a Collection view operation is called. Rest easy: There's no reason that a Map cannot always return the same object each time it is asked for a given Collection view. This is precisely what all the Map implementations in java.util do.
With all three Collection views, calling an Iterator's remove operation removes the associated entry from the backing Map, assuming that the backing Map supports element removal to begin with.
With the entrySet view, it is also possible to change the value associated with a key by calling a Map.Entry's setValue method during iteration (again, assuming the Map supports value modification to begin with). Note that these are the only safe ways to modify a Map during iteration; the behavior is unspecified if the underlying Map is modified in any other way while the iteration is in progress.
The Collection views support element removal in all its many forms:
Remove
removeAll
retainAll
Clear
Iterator.remove
The Collection views do not support element addition under any circumstances. It would make no sense for the keySet and values views, and it's unnecessary for the entrySet view, because the backing Map's put and putAll methods provide the same functionality.
2.4.2.2.8.10.1 Map Range-View Operations
Not Applicable
2.4.2.2.8.10.2 Fancy Uses of Collection Views: Map Algebra
When applied to the Collection views, bulk operations (containsAll, removeAll, and retainAll) are surprisingly potent tools.
2.4.2.2.8.11 Traversing over a Map
Traversing is done through one of the methods of the Map Views (keyset, values, entrySet).
With all three Collection views, calling an Iterator's remove operation removes the associated entry from the backing Map.
Note that these are the only safe ways to modify a Map during iteration; the behavior is unspecified if the underlying Map is modified in any other way while the iteration is in progress.
2.4.2.2.8.12 Translating Map into an Array
By using one of the Collection Views methods
2.4.2.2.2.13 Common Map Implementations
Class
Description
java.util.HashMap<K,V>
java.util.LinkedHashMap<K,V>
java.util.TreeMap<K,V>
2.4.2.2.8.14 Map Interface Algorithms
2.4.2.2.2.14.1 Multimaps
A multimap is like a Map but it can map each key to multiple values. The Java Collections Framework doesn't include an interface for multimaps because they aren't used all that commonly. It's a fairly simple matter to use a Map whose values are List instances as a multimap. This technique is demonstrated on the examples section
2.4.2.2.8.15 Map Performance Considerations
No special performance considerations for this interface
2.4.2.2.8.16 Map Examples
2.4.2.2.8.16.1 Map Basic Operations Examples
Generate a frequency table of the words found in the argument list.
import java.util.*;
public class Freq {
public static void main(String[] args) {
Map<String, Integer> m = new HashMap<String, Integer>();
// Initialize frequency table from command line
for (String a : args) {
Integer freq = m.get(a);
m.put(a, (freq == null) ? 1 : freq + 1);
}
System.out.println(m.size() + " distinct words:");
System.out.println(m);
}
}
The frequency table maps each word to the number of times it occurs in the argument list.
The only tricky thing about this program is the second argument of the put statement. That argument is a conditional expression that has the effect of setting the frequency to one if the word has never been seen before or one more than its current value if the word has already been seen.
Running this program with the command:
java Freq if it is to be it is up to me to delegate
Yields the following output:
8 distinct words:
{to=3, delegate=1, be=1, it=2, up=1, if=1, me=1, is=2}
Suppose you'd prefer to see the frequency table in alphabetical order:
All you have to do is change the implementation type of the Map from HashMap to TreeMap.
Making this four-character change causes the program to generate the following output from the same command line.
8 distinct words:
{be=1, delegate=1, if=1, is=2, it=2, me=1, to=3, up=1}
Similarly, you could make the program print the frequency table in the order the words first appear on the command line:
Simply by changing the implementation type of the map to LinkedHashMap.
Doing so results in the following output.
8 distinct words:
{if=1, it=2, is=2, to=3, be=1, up=1, me=1, delegate=1}
2.4.2.2.8.16.2 Map Conversion Constructor Examples
For example, suppose you have a Map, named m. The following one-liner creates a new HashMap initially containing all of the same key-value mappings as m.
Map<K, V> copy = new HashMap<K, V>(m);
2.4.2.2.8.16.3 Removing with an Iterator Example
2.4.2.2.8.16.4 Map Bulk Operations Examples
The following is a static factory method that demonstrates how to initialize a Map with default values and populate it with mandatory values:
static <K, V> Map<K, V> newAttributeMap(
Map<K, V>defaults, Map<K, V> overrides) {
Map<K, V> result = new HashMap<K, V>(defaults);
result.putAll(overrides);
return result;
}
2.4.2.2.8.16.5 Translating into an Array
2.4.2.2.8.16.6 Map Views Examples
This example illustrates the standard idiom for iterating over the keys in a Map with a for-each construct:
for (KeyType key : m.keySet())
System.out.println(key);
And with an iterator:
// Filter a map based on some property of its keys.
for (Iterator<Type> it = m.keySet().iterator(); it.hasNext(); )
if (it.next().isBogus())
it.remove();
The idiom for iterating over values
The idiom for iterating over values is analogous.
Following is the idiom for iterating over key-value pairs.
for (Map.Entry<KeyType, ValType> e : m.entrySet())
System.out.println(e.getKey() + ": " + e.getValue());
Suppose you want to know whether one Map is a submap of another — that is, whether the first Map contains all the key-value mappings in the second. The following idiom does the trick.
if (m1.entrySet().containsAll(m2.entrySet())) {
...
}
Along similar lines, suppose you want to know whether two Map objects contain mappings for all of the same keys.
if (m1.keySet().equals(m2.keySet())) {
...
}
Suppose you have a Map that represents a collection of attribute-value pairs, and two Sets representing required attributes and permissible attributes. (The permissible attributes include the required attributes.) The following snippet determines whether the attribute map conforms to these constraints and prints a detailed error message if it doesn't.
static <K, V> boolean validate(Map<K, V> attrMap,
Set<K> requiredAttrs, Set<K>permittedAttrs) {
boolean valid = true;
Set<K> attrs = attrMap.keySet();
if(!attrs.containsAll(requiredAttrs)) {
Set<K> missing = new HashSet<K>(requiredAttrs);
missing.removeAll(attrs);
System.out.println("Missing attributes: " + missing);
valid = false;
}
if (!permittedAttrs.containsAll(attrs)) {
Set<K> illegal = new HashSet<K>(attrs);
illegal.removeAll(permittedAttrs);
System.out.println("Illegal attributes: " + illegal);
valid = false;
}
return valid;
}
Suppose you want to know all the keys common to two Map objects.
Set<KeyType>commonKeys = new HashSet<KeyType>(m1.keySet());
commonKeys.retainAll(m2.keySet());
A similar idiom gets you the common values.
All the idioms presented thus far have been nondestructive; that is, they don't modify the backing Map. Here are a few that do:
Suppose you want to remove all of the key-value pairs that one Map has in common with another.
m1.entrySet().removeAll(m2.entrySet());
Suppose you want to remove from one Map all of the keys that have mappings in another.
m1.keySet().removeAll(m2.keySet());
What happens when you start mixing keys and values in the same bulk operation? Suppose you have a Map, managers, that maps each employee in a company to the employee's manager. We'll be deliberately vague about the types of the key and the value objects. It doesn't matter, as long as they're the same. Now suppose you want to know who all the "individual contributors" (or nonmanagers) are. The following snippet tells you exactly what you want to know.
Set<Employee> individualContributors =
new HashSet<Employee>(managers.keySet());
individualContributors.removeAll(managers.values());
Suppose you want to fire all the employees who report directly to some manager, Simon.
Employee simon = ... ;
managers.values().removeAll(Collections.singleton(simon));
Note that this idiom makes use of Collections.singleton, a static factory method that returns an immutable Set with the single, specified element.
Once you've done this, you may have a bunch of employees whose managers no longer work for the company (if any of Simon's direct-reports were themselves managers). The following code will tell you which employees have managers who no longer works for the company.
Map<Employee, Employee> m =
new HashMap<Employee, Employee>(managers);
m.values().removeAll(managers.keySet());
Set<Employee> slackers = m.keySet();
This example is a bit tricky. First, it makes a temporary copy of the Map, and it removes from the temporary copy all entries whose (manager) value is a key in the original Map. Remember that the original Map has an entry for each employee. Thus, the remaining entries in the temporary Map comprise all the entries from the original Map whose (manager) values are no longer employees. The keys in the temporary copy, then, represent precisely the employees that we're looking for.
Read a word list containing one word per line (all lowercase) and prints out all the anagram groups that meet a size criterion. An anagram group is a bunch of words, all of which contain exactly the same letters but in a different order.
import java.util.*;
import java.io.*;
public class Anagrams {
public static void main(String[] args) {
int minGroupSize = Integer.parseInt(args[1]);
// Read words from file and put into a simulated multimap
Map<String, List<String>> m
= new HashMap<String, List<String>>();
try {
Scanner s = new Scanner(new File(args[0]));
while (s.hasNext()) {
String word = s.next();
String alpha = alphabetize(word);
List<String> l = m.get(alpha);
if (l == null)
m.put(alpha, l=new ArrayList<String>());
l.add(word);
}
} catch (IOException e) {
System.err.println(e);
System.exit(1);
}
// Print all permutation groups above size threshold
for (List<String> l : m.values())
if (l.size() >= minGroupSize)
System.out.println(l.size() + ": " + l);
}
private static String alphabetize(String s) {
char[] a = s.toCharArray();
Arrays.sort(a);
return new String(a);
}
}
The program takes two arguments on the command line:
(1) the name of the dictionary file and
(2) the minimum size of anagram group to print out.
Anagram groups containing fewer words than the specified minimum are not printed.
There is a standard trick for finding anagram groups: For each word in the dictionary, alphabetize the letters in the word (that is, reorder the word's letters into alphabetical order) and put an entry into a multimap, mapping the alphabetized word to the original word. For example, the word bad causes an entry mapping abd into bad to be put into the multimap. A moment's reflection will show that all the words to which any given key maps form an anagram group. It's a simple matter to iterate over the keys in the multimap, printing out each anagram group that meets the size constraint.
Running this program on a 173,000-word dictionary file with a minimum anagram group size of eight produces the following output:
9: [estrin, inerts, insert, inters, niters, nitres, sinter,
triens, trines]
8: [lapse, leaps, pales, peals, pleas, salep, sepal, spale]
8: [aspers, parses, passer, prases, repass, spares, sparse,
spears]
10: [least, setal, slate, stale, steal, stela, taels, tales,
teals, tesla]
8: [enters, nester, renest, rentes, resent, tenser, ternes,
treens]
8: [arles, earls, lares, laser, lears, rales, reals, seral]
8: [earings, erasing, gainers, reagins, regains, reginas,
searing, seringa]
8: [peris, piers, pries, prise, ripes, speir, spier, spire]
12: [apers, apres, asper, pares, parse, pears, prase, presa,
rapes, reaps, spare, spear]
11: [alerts, alters, artels, estral, laster, ratels, salter,
slater, staler, stelar, talers]
9: [capers, crapes, escarp, pacers, parsec, recaps, scrape,
secpar, spacer]
9: [palest, palets, pastel, petals, plates, pleats, septal,
staple, tepals]
9: [anestri, antsier, nastier, ratines, retains, retinas,
retsina, stainer, stearin]
8: [ates, east, eats, etas, sate, seat, seta, teas]
8: [carets, cartes, caster, caters, crates, reacts, recast,
traces]
2.4.2.2.9 The SortedMap Interface
A SortedMap is a Map that maintains its entries in ascending order, according to the keys' natural ordering, or according to a Comparator.
2.4.2.2.9.1 SortedMap Interface Usages
- Example: A binary tree
- Example: A dictionary
The SortedMap interface provides operations for normal Map operations and for the following:2.4.2.2.9.2 High Level SortedMap Operations
- Range view - Performs arbitrary range operations on the sorted map.
- Endpoints - Returns the first or the last key in the sorted map.
- Comparator access - Returns the Comparator, if any, used to sort the map.
The Iterator returned by the iterator operation on any of the sorted map's Collection views traverse the collections in order.
The arrays returned by the Collection views' toArray operations contain the keys, values, or entries in order.
The operations SortedMap inherits from Map behave identically on sorted maps and normal maps with two exceptions:
2.4.2.2.9.3 SortedMap Idium
The following interface is the Map analog of SortedSet.
public interface SortedMap<K, V> extends Map<K, V>{
public abstract Comparator<? super K> comparator();
public abstract SortedMap<K, V> subMap(K fromKey, K toKey);
public abstract SortedMap<K, V> headMap(K toKey);
public abstract SortedMap<K, V> tailMap(K fromKey);
public abstract K firstKey();
public abstract K lastKey();
}
2.4.2.2.9.4 Compare SortedMap to Legacy API
No specific legacy API available.
2.4.2.2.9.5 SortedMap Object Comparisons
Not Applicable
2.4.2.2.9.6 The SortedMap Conversion Constructor
By convention, all general-purpose Map implementations provide a standard conversion constructor that takes a Map; SortedMap implementations are no exception.
In TreeMap, this constructor creates an instance that orders its entries according to their keys' natural ordering. This was probably a mistake. It would have been better to check dynamically to see whether the specified Map instance was a SortedMap and, if so, to sort the new map according to the same criterion (comparator or natural ordering). Because TreeMap took the approach it did, it also provides a constructor that takes a SortedMap and returns a new TreeMap containing the same mappings as the given SortedMap, sorted according to the same criterion. Note that it is the compile-time type of the argument, not its runtime type, that determines whether the SortedMap constructor is invoked in preference to the ordinary map constructor.
SortedMap implementations also provide, by convention, a constructor that takes a Comparator and returns an empty map sorted according to the specified Comparator. If null is passed to this constructor, it returns a Map that sorts its mappings according to their keys' natural ordering.
2.4.2.2.9.7 SortedMap Interface Basic operations
2.4.2.2.9.8 SortedMap Positional Access and Search Operations
Not supported directly by the interface
2.4.2.2.9.9 SortedMap Interface Bulk Operations
Bulk operations perform an operation on an entire Collection:
2.4.2.2.9.10 SortedMap Views Operations
Not Applicable
2.4.2.2.9.10.1 SortedMap Range-View Operations
Not Applicable
2.4.2.2.9.11 Traversing over a SortedMap
Not Applicable.
2.4.2.2.9.12 Translating SortedMap into an Array
Not Applicable.
2.4.2.2.9.13 Common SortedMap Implementations
java.util.TreeMap<K,V>
2.4.2.2.9.14 SortedMap Interface Algorithms
Because this interface is a precise Map analog of SortedSet, all the idioms and code examples in The SortedSet Interface section apply to SortedMap with only trivial modifications.
2.4.2.2.9.15 SortedMap Performance Considerations
Because this interface is a precise Map analog of SortedSet, all the idioms and code examples in The SortedSet Interface section apply to SortedMap with only trivial modifications.
2.4.2.2.9.16 SortedMap Examples
Because this interface is a precise Map analog of SortedSet, all the idioms and code examples in The SortedSet Interface section apply to SortedMap with only trivial modifications.
2.4.2.2.10 Summary of Interfaces
The core collection interfaces are the foundation of the Java Collections Framework.
distinct interface trees
The Java Collections Framework hierarchy consists of two distinct interface trees:
The first tree starts with the Collection interface, which provides for the basic functionality used by all collections, such as add and remove methods. Its subinterfaces — Set, List, and Queue — provide for more specialized collections.
The Set interface does not allow duplicate elements. This can be useful for storing collections such as a deck of cards or student records. The Set interface has a subinterface, SortedSet, that provides for ordering of elements in the set.
The List interface provides for an ordered collection, for situations in which you need precise control over where each element is inserted. You can retrieve elements from a List by their exact position.
The Queue interface enables additional insertion, extraction, and inspection operations. Elements in a Queue are typically ordered in on a FIFO basis.
The second tree starts with the Map interface, which maps keys and values similar to aHashtable.
Map's subinterface, SortedMap, maintains its key-value pairs in ascending order or in an order specified by a Comparator.
These interfaces allow collections to be manipulated independently of the details of their representation.
2.4.2.2.11 Questions and Exercises: Interfaces
2.4.2.2.11.1 Questions
This lesson mentions three ways to traverse a List. Describe them, and note the limitations of each.
Use the enhanced for statement:
List<Thing> list;
for (Thing thing : list) {
}
Limitations: cannot be used to add, remove, or modify elements.
Use the traditional for statement together with an Iterator:
List<Thing> list;
...
for (Iterator<Thing> it = list.iterator(); it.hasNext(); ) {
Thing thing = it.next();
...
}
Limitations: cannot be used to modify elements.
Use the traditional for statement together with an ListIterator:
List<Thing> list;
...
for (ListIterator<Thing> it = list.iterator(); it.hasNext(); ) {
Thing thing = it.next();
...
}
Limitations: none.
Consider the four core interfaces, Set, List, Queue, and Map. For each of the following four assignments, specify which of the four core interfaces is best suited, and explain how to use it to implement the assignment.
Whimsical Toys Inc (WTI) needs to record the names of all its employees. Every month, an employee will be chosen at random from these records to receive a free toy.
Use a List. Choose a random employee by picking a number between 0 and size()-1.
WTI has decided that each new product will be named after an employee — but only first names will be used, and each name will be used only once. Prepare a list of unique first names.
Use a Set. Collections that implement this interface don't allow the same element to be entered more than once.
WTI decides that it only wants to use the most popular names for its toys. Count the number of employees who have each first name.
Use a Map, where the keys are first names, and each value is a count of the number of employees with that first name.
WTI acquires season tickets for the local lacrosse team, to be shared by employees. Create a waiting list for this popular sport.
Use a Queue. Invoke add() to add employees to the waiting list, and remove() to remove them.
The following program is supposed to print the string "Blue". Instead, it throws an error. Why?
import java.util.*;
public class SortMe {
public static void main(String args[]) {
SortedSet<StringBuffer> s = new TreeSet<StringBuffer>();
s.add(new StringBuffer("Red"));
s.add(new StringBuffer("White"));
s.add(new StringBuffer("Blue"));
System.out.println(s.first());
}
}
2.4.2.2.11.2 Exercises
1. Write a program that prints its arguments in random order. Do not make a copy of the argument array.
2. Take the FindDups example and modify it to use a SortedSet instead of a Set. Specify a Comparator so that case is ignored when sorting and identifying set elements.
3. Write a method that takes a List<String> and applies String.trim to each element. To do this, you'll need to pick one of the three iteration idioms that you described in Question 1. Two of these will not give the result you want, so be sure to write a program that demonstrates that the method actually works!
2.4.2.3 Traversing over a Collection
Traversing a collection can be done with the following options:
Option
Description
Using the Iterator interface.
Every Collection interface has a method that returns an Iterator over the elements in it.
Since java5: Using the for-each construct
Using the ListIterator interface, when applicable
Some Collection interfaces support traversing a List interface with the ListIterator interface. It adds functionality applicable to List
2.4.2.3.1 Using the Iterator Interface
2.4.2.3.2 Using the for-each construct
Since java5:
You can also traverse a Collection with the for-each construct. It allows you to concisely traverse a collection or array using a for loop.
Use Iterator instead of the for-each construct when you need to:
- Remove the current element. The for-each construct hides the iterator, so you cannot call remove. Therefore, the for-each construct is not usable for filtering.
- Iterate over multiple collections in parallel.
2.4.2.4 Core Collections Algorithms
2.4.2.4.1 The Collections Class
The Collections class consists exclusively of static methods that operate on or return collections. It contains polymorphic algorithms that operate on collections, "wrappers", which return a new collection backed by a specified collection, and a few other odds and ends.
Below is a list of some of its common algorithms:
<T> Set<T> singleton(T o)
Shortens the lines of creating a Set from an object. Returns an immutable set containing only the specified object. The returned set is serializable.
<T> boolean replaceAll(List<T> list, T oldVal,T newVal)
Replaces all occurrences of one specified value in a list with another.
void shuffle(List<?> list)
Randomly permutes the specified list. All permutations occur with approximately equal likelihood
<T extends Comparable<? super T>> void sort(List<T> list)
Sorts a List using a merge sort algorithm, which provides a fast, stable sort. (A stable sort is one that does not reorder equal elements.)
void reverse(List<?> list)
Reverses the order of the elements in a List
void rotate(List<?> list, int distance)
Rotates all the elements in a List by a specified distance.
void swap(List<?> list, int i, int j)
Swaps the elements at specified positions in a List.
<T> void fill(List<? super T> list, T obj)
Overwrites every element in a List with the specified value.
<T> void copy(List<? super T> dest, List<? extends T> src)
Copies the source List into the destination List.
<T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c)
Searches for an element in an ordered List using the binary search algorithm.
int indexOfSubList(List<?> source, List<?> target)
Returns the index of the first sublist of one List that is equal to another.
int lastIndexOfSubList(List<?> source, List<?> target)
Returns the index of the last sublist of one List that is equal to another.
2.4.2.4.2 The Arrays Class
This class contains various methods for manipulating arrays (such as sorting and searching). This class also contains a static factory that allows arrays to be viewed as lists.
public static <T> List<T> asList(T... a)
Returns a fixed-size list backed by the specified array. This method acts as bridge between array-based and collection-based APIs, in combination with Collection.toArray(). The returned list is serializable and implements RandomAccess.
This method does not copy the array. Changes in the List write through to the array and vice versa. The resulting List is not a general-purpose List implementation, because it doesn't implement the add and remove operations: Arrays are not resizable.
2.4.2.99 Sources
Trail: Collections (The Java™ Tutorials)
2.4.2 Threads
2.4.2.1 V1.4.2
2.4.2.1.1 wait()
public final void java.lang.Object.wait() throws InterruptedException
Causes current thread to wait until another thread invokes the notify() method or the notifyAll() method for this object.
The current thread must own this object's monitor. The thread releases ownership of this monitor and waits until another thread notifies threads waiting on this object's monitor to wake up. The thread then waits until it can re-obtain ownership of the monitor and resumes execution.
2.4.2.1.2 notify()
public final void notify()
Wakes up a single thread that is waiting on this object's monitor. The choice of thread to be awakened is arbitrary. A thread waits on an object's monitor by calling one of the wait methods.
The awakened thread will not be able to proceed until the current thread relinquishes the lock on this object. The awakened thread will compete in the usual manner with any other threads to synchronize on this object.
This method should only be called by a thread that is the owner of this object's monitor.
2.4.2.1.3 notifyAll()
public final void notifyAll()
Wakes up all threads that are waiting on this object's monitor. A thread waits on an object's monitor by calling one of the wait methods.
The awakened threads will not be able to proceed until the current thread relinquishes the lock on this object. The awakened threads will compete in the usual manner with any other threads.
This method should only be called by a thread that is the owner of this object's monitor.
3. Design Patterns
3.1 Comet Design Pattern
Comet Design Pattern (AKA "reverse Ajax", "server-side push"). The idea: push data from the server to the browser without the browser requesting it.
3.1.1 Motivations for using Comet
While Ajax is a popular solution for dynamically pulling data requests from the server, it does nothing to help us push data to the client. Comet enhances the Ajax communication pattern by defining architecture for pushing data from the server to the client.
Comet has popularized asynchronous non-blocking HTTP programming. Instead of a Meta refresh from the server, the server can be contacted asynchronously using Ajax. This type of web development technique claims that it is faster compared to Ajax as it provides the same user experience while improving on interactivity with better overall speed.
Comet is based on creating and maintaining long-lived HTTP connections. Handling these connections efficiently requires a new approach to HTTP programming, i.e. handling asynchronous, non-blocking HTTP programming.
3.1.2 Comet styles
- Polling (normal polling) – The easiest way to enable Comet, but it has some limitations. It is done by using JavaScript XMLHttpRequest and setTimeout. As soon as the response comes back, wait a fixed amount of time, and then call it again.
- Long Polling – The most common "true" Comet technique. Keeps the connection open for a long time. An event on the server is sent to the client and closed, and the poll immediately begins anew. The advantage is that data goes from the server to the client as soon as it is available. A Web-based chat program probably is using this technique.
- Streaming – Long Poll variation. The server does not close the connection. When the connection times out the request is re-initiated. It uses XMLHttpRequest to check for a readyState of 3 (Receiving) (as opposed to 4 [Loaded]) and get the data that is "streaming" from the server. It has an added advantage of making far fewer requests to the server. Unfortunately, this technique only works reliably on the newer versions of Mozilla Firefox.
3.1.3 Sources
- Developing with Comet and Java
- Comet: The Next Stage for Ajax
- Asynchronous HTTP and Comet architectures
3.2 Reverse Ajax
See Comet
3.3 Server-side push
See Comet
3.4 Asynchronous HTTP
Asynchronous HTTP has a role in developing high-performance HTTP proxies and non-blocking HTTP clients, as well as the long-lived HTTP connections associated with Comet.
3.4.1 Synchronous message handling overview
At the message level, when performing a Synchronous call, the caller thread is suspended until the server response returns or a timeout is exceeded.
The synchronous approach requires a dedicated thread for each concurrent request, which consumes a certain amount of memory. This can become a problem if you have many concurrent calls to be performed on the client side.
At the application level, code execution is stopped, waiting for the response before further actions can be taken.
Client-side synchronous message handling is very easy to understand, as illustrated by the example in Listing 1.
Listing 1. Client example -- synchronous call
HttpClient httpClient = new HttpClient();
// create the request message
HttpRequest req = new HttpRequest("GET", "http://tools.ietf.org/html/rfc2616.html");
// the call blocks until the response returns
HttpResponse resp = httpClient.call(req);
int status = resp.getStatus();
// ...
3.4.2 Asynchronous message handling
At the message level (socket/protocol level) Asynchronous Message Handling means that an HTTP client performs a request without waiting for the server response.
When performing an asynchronous call it is necessary to define a handler, which will be notified if the response returns. Typically, such a handler will be passed over by performing the call. The call method returns immediately. The application-level code instructions after the send statement will be processed without waiting for a server response. The server response will be handled by performing the handler's callback method.
If the response returns, the network library will execute the callback method within a network-library-controlled thread. If necessary, the request message has to be synchronized with the response message at the application-code level. An asynchronous call is shown in Listing 2.
Listing 2. Client example -- asynchronous call
HttpClient httpClient = new HttpClient();
// response handler
IHttpResponseHandler responseHandler = new IHttpResponseHandler() {
public void onResponse(HttpResponse resp) throws IOException {
int status = resp.getStatus();
// ...
}
// ...
};
// create the request message
HttpRequest req = new HttpRequest("GET", "http://tools.ietf.org/html/rfc2616.html");
// send the request in an asynchronous way
httpClient.send(req, responseHandler);
// ...
The advantage of this approach is that the caller thread will not be suspended until the response returns. Based on a good network library implementation, no outstanding threads are required. In contrast to the synchronous call approach, the number of outstanding requests is not restricted to the number of possible threads.
3.4.3 HTTP pipelining
Asynchronous message handling also enables HTTP pipelining. Pipelining requires that the underlying HTTP connection is in persistent mode, which is the standard mode with HTTP/1.1. Pipelining has many advantages:
- Send multiple HTTP requests without waiting for the server response to former requests.
- The response messages will be returned by the server in the same order as they were sent.
- In contrast to non-persistent connections, the persistent HTTP connection stays open after the server has returned a response.
- Pipelining can significantly improve application performance when fetching many objects from the same server.
- The implicit persistent mode eliminates the overhead of establishing a new connection for each new request, by allowing for the reuse of connections.
- Pipelining also eliminates the need for additional connection instances to perform concurrent requests.
3.4.4 Message content streaming
Although asynchronous message handling can improve application performance by avoiding waiting threads, another performance bottleneck arises when reading the message content.
It is not unusual for an HTTP message to contain kilobytes of content data. On the transport level, such larger messages will be broken down into several TCP segments. The TCP segment size is limited and depends on the underlying network and link layer. For Ethernet-based networks the maximum TCP segment size is up to 1460 bytes.
Bodyless HTTP messages such as GET requests don't contain body data. Often the size of such bodyless messages is smaller than 1 kilobyte. Listing 3 shows a simple HTTP request:
Listing 3. HTTP request
GET /html/rfc2616.html HTTP/1.1
Host: tools.ietf.org:80
User-Agent: xSocket-http/2.0-alpha-3
The correlating response of the request shown above contains a message body of 0.5 megabytes. On a personal Internet connection, the response message shown in Listing 4 would be broken into several TCP segments when sent:
Listing 4. HTTP response
HTTP/1.1 200 OK
Content-Length: 509497
Accept-Ranges: bytes
Last-Modified: Tue, 20 Nov 2007 03:10:57 GMT
Date: Sun, 03 Feb 2008 09:46:31 GMT
Content-Type: text/html; charset=US-ASCII
ETag: "d4026-7c639-9d13d240"
Server: Apache/2.2.6 (Debian) DAV/2 SVN/1.4.4 mod_python/3.3.1 Python/2.4.4 mod_ssl/2.2.6 OpenSSL/0.9.8g mod_perl/2.0.3 Perl/v5.8.8
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html lang="en" xml:lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=us-ascii" />
<meta name="robots" content="index,follow" />
<meta name="creator" content="rfcmarkup version 1.53" />
<link rel="icon" href="/images/rfc.png" type="image/png" />
<link rel="shortcut icon" href="/images/rfc.png" type="image/png" />
<title>RFC 2616 Hypertext Transfer Protocol -- HTTP/1.1</title>
</small></small></span>
</body></html>
Data transfer fragmentation can be hidden at the API level by accessing the body data as a steady and continuous stream. This approach, known as streaming, avoids the need to buffer large chunks of data before processing it. Streaming can also reduce the latency of HTTP calls, especially if both peers support streaming.
Using streaming allows the receiver to start processing the message content before the entire message has been transmitted. Often an HTTP message contains unstructured or semi-structured data, such as HTML pages, video, or music files, which will be processed immediately by the receiving peer. For instance, most browsers start rendering and displaying HTML pages without waiting for the complete page. For this reason most HTTP libraries support a stream-based API to access the message content.
In contrast to the body data, the message header contains well-structured data entries. To access the message header data most HTTP libraries provide dedicated and typed setter and getter methods. In most use cases the header can only be processed after the complete header has been received. The HTTP/1.1 specification doesn't define the order of the message headers, though it does state that it's a good practice to send general-header fields first, followed by request-header or response-header fields, and ending with the entity-header fields.
3.4.5 Streaming input data
To process received body data in a streaming manner, the receiving peer has to be notified immediately after the message header has been received. Based on the message header information, the receiver is able to determine the type of the received HTTP message, if body data exists, and which type of content the body contains.
The example code in Listing 5 (below) streams a returned HTML page into a file. The response message data will be processed as soon as it appears. Based on the retrieved body channel the FileChannel's transferFrom() implementation calls the body channel's read() method to transfer the data into the filesystem. This occurs in a blocking manner. If the socket read buffer is empty, the body channel's read() method will block until more data is received or the end-of-stream is reached. Blocking the read operation suspends the current caller thread, which can lead to inefficiency in system resource usage.
3.4.99 Sources
- Asynchronous HTTP and Comet architectures
No comments:
Post a Comment