Transcript Chapter 20 – Java Utilities Package and Bit Manipulation

Chapter 21 – Java Utilities Package and
Bit Manipulation
Outline
21.1
21.2
21.3
21.4
21.5
Introduction
Vector Class and Enumeration Interface
Stack Class of Package java.util
Hashtable Class
Properties Class
 2003 Prentice Hall, Inc. All rights reserved.
1
2
21.1 Introduction
• Utility classes and interfaces
– Contained in package java.util
• Class Vector (array-like objects that grow and shrink
dynamically)
• Interface Enumeration (enables iteration through the
elements of a container, like a Vector)
• Class Stack (subclass of Vector, standard stack
operations like push and pop)
• Class Hashtable (used to store and retrieve data via
“hashing”)
• Class Properties (support for persistent hash tables)
 2003 Prentice Hall, Inc. All rights reserved.
21.2 Vector Class and Enumeration
Interface
• Class java.util.Vector
– Array-like data structures that can resize themselves
dynamically
– Arrays are fixed in size after memory allocation
(String[] name = new String[25])
– Vector contains a capacity (number of elements always less
than or equal to capacity)
– Grows by capacity increment if it requires additional space
• Vector v = new Vector(); (capacity=10, doubles)
• Vector v = new Vector(n); (capacity=n, doubles)
• Vector v = new Vector(n,p); (capacity=n,
increment=p)
 2003 Prentice Hall, Inc. All rights reserved.
3
21.2 Vector Class and Enumeration
Interface
• Class java.util.Vector
– Vectors store objects (of any type), but they must be objects
and not primitives 
• This is a job for Wrapper classes 
– v.add(object) adds new object as the last element in
the vector
– v.add(i,object) adds new object as element i in the
vector (and shifts everything to the right of this one)
• There must already be an object at element i
– v.remove(object) removes object (and shifts
everything to the left)
– v.remove(i) removes element i (and shifts everything to
the left)
 2003 Prentice Hall, Inc. All rights reserved.
4
21.2 Vector Class and Enumeration
Interface
• Class java.util.Vector
– v.capacity() returns capacity
– v.size() returns current number of elements
– v.trimToSize() sets capacity equal to current number
of elements (size)
• next item added causes capacity to double or increase by p
– v.get(i) returns reference to element i
– v.set(i,object) changes the object at element i
• There must already be an object at element i
– More Vector methods illustrated in the following example…
 2003 Prentice Hall, Inc. All rights reserved.
5
21.2 Vector Class and Enumeration
Interface
• Class java.util.Enumeration
– Enumeration object generates a series of elements
(Enumeration e = v.elements();)
• v is a Vector
• elements() method returns an enumeration of all
elements in the vector
–
–
–
–
e.hasMoreElements()
e.nextElement()
Notice the similarity to StringTokenizer
Enumeration can also be used with Hashtable
 2003 Prentice Hall, Inc. All rights reserved.
6
7
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
Outline
// Fig. 21.1: VectorTest.java
// Using the Vector class.
import java.util.*;
public class VectorTest {
private static final String colors[] = { "red", "white", "blue" };
public VectorTest()
{
Vector vector = new Vector();
printVector( vector ); // print vector
Line 10
17 and 19
Create VectorLines
with14,
initial
capacity of 10 elements and
Line of
24 zero
capacity increment
// add elements to the vector
vector.add( "magenta" );
Line 25
for ( int count = 0; count < colors.length; count++ )
vector.add( colors[ count ] );
vector.add( "cyan" );
printVector( vector ); // print vector
VectorTest.java
Call Vector method add to add
objects to the end of the Vector
Call Vector method firstElement to return
Calla Vector
lastElement
return
reference method
to the first
element in thetoVector
a reference to the last element in the Vector
// output the first and last elements
try {
System.out.println( "First element: " + vector.firstElement() );
System.out.println( "Last element: " + vector.lastElement() );
}
 2003 Prentice Hall, Inc.
All rights reserved.
8
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
Outline
// catch exception if vector is empty Vector method contains returns
that indicates whether
catch ( NoSuchElementException exceptionboolean
) {
exception.printStackTrace();
Vector contains a specific Object
VectorTest.java
}
Line 34
// does vector contain "red"?
if ( vector.contains( "red" ) )
System.out.println( "\n\"red\" found at index " +
Line 36
vector.indexOf( "red" ) + "\n" );
Vector method remove removes the first
else
occurrence of its argument Object fromLine
Vector
40
System.out.println( "\n\"red\" not found\n" );
Vector method indexOf
vector.remove( "red" ); // remove the
stringindex
"red"of first location in
returns
System.out.println( "\"red\" has been removed" );
Vector containing the argument
Lines 52-53
printVector( vector ); // print vector
// does vector contain "red" after remove operation?
if ( vector.contains( "red" ) )
System.out.println( "\"red\" found at index " +
vector.indexOf( "red" ) );
else
System.out.println( "\"red\" not found" );
// print the size and capacity of vector
System.out.println( "\nSize: " + vector.size() +
"\nCapacity: " + vector.capacity() );
} // end constructor
Vector methods size and
capacity return number of
elements in Vector and
Vector capacity, respectively
 2003 Prentice Hall, Inc.
All rights reserved.
9
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
private void printVector( Vector vectorToOutput )
Vector method isEmpty
{
if ( vectorToOutput.isEmpty() )
returns true if there are no
System.out.print( "vector is empty" ); // vectorToOutput
is Vector
empty
elements in the
else { // iterate through the elements
System.out.print( "vector contains: " );
Enumeration items = vectorToOutput.elements();
while ( items.hasMoreElements() )
System.out.print( items.nextElement() + " " );
Outline
VectorTest.java
Line 59
Vector method elements
Line 64
returns Enumeration
for
iterating Vector elements
}
System.out.println( "\n" );
}
public static void main( String args[] )
{
new VectorTest(); // create object and call its constructor
}
} // end class VectorTest
 2003 Prentice Hall, Inc.
All rights reserved.
10
vector is empty
Outline
vector contains: magenta red white blue cyan
First element: magenta
Last element: cyan
VectorTest.java
"red" found at index 1
"red" has been removed
vector contains: magenta white blue cyan
"red" not found
Size: 4
Capacity: 10
 2003 Prentice Hall, Inc.
All rights reserved.
11
21.3 Stack Class of Package java.util
• Stack
–
–
–
–
Implements stack data structure
Extends class Vector
Stores references to Objects (as does Vector)
Methods
• Stack() (the only constructor, creates empty stack)
• push(object) (put object on top of stack)
• pop() (remove and return object on top of stack)
• peek() (look at item on top of stack without removing it)
• empty() (boolean)
• search(object) (returns distance from top of stack to
where item is located or -1)
 2003 Prentice Hall, Inc. All rights reserved.
12
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
Outline
// Fig. 21.2: StackTest.java
// Program to test java.util.Stack.
import java.util.*;
StackTest.java
public class StackTest {
Line 9
public StackTest()
{
Stack stack = new Stack();
Create empty
Stack
Lines
18, 20, 22 and
// create objects to store in the stack
Boolean bool = Boolean.TRUE;
Character character = new Character( '$' );
Integer integer = new Integer( 34567 );
String string = "hello";
// use push
stack.push(
printStack(
stack.push(
printStack(
stack.push(
printStack(
stack.push(
printStack(
method
bool );
stack );
character );
stack );
integer );
stack );
string );
stack );
24
Stack method push adds
Object to top of Stack
 2003 Prentice Hall, Inc.
All rights reserved.
13
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
// remove items from stack
try {
Object removedObject = null;
Outline
Stack method pop removes
Object from top of Stack
while ( true ) {
removedObject = stack.pop(); // use pop method
System.out.println( removedObject.toString() + " popped" );
printStack( stack );
}
StackTest.java
Line 32
Line 46
}
// catch exception if stack is empty when item popped
catch ( EmptyStackException emptyStackException ) {
emptyStackException.printStackTrace();
}
}
Line 51
Stack method isEmpty returns
true if Stack is empty
private void printStack( Stack stack )
{
if ( stack.isEmpty() )
System.out.print( "stack is empty" ); // the stack is empty
else {
System.out.print( "stack contains: " );
Enumeration items = stack.elements();
Stack extends Vector, so
class Stack may use method
elements to obtain
Enumeration for Stack
 2003 Prentice Hall, Inc.
All rights reserved.
14
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// iterate through the elements
while ( items.hasMoreElements() )
System.out.print( items.nextElement() + " " );
}
Outline
StackTest.java
System.out.println( "\n" ); // go to the next line
}
public static void main( String args[] )
{
new StackTest();
}
} // end class StackTest
 2003 Prentice Hall, Inc.
All rights reserved.
15
stack contains: true
stack contains: true $
Outline
StackTest.java
stack contains: true $ 34567
stack contains: true $ 34567 hello
hello popped
stack contains: true $ 34567
34567 popped
stack contains: true $
$ popped
stack contains: true
true popped
stack is empty
java.util.EmptyStackException
at java.util.Stack.peek(Stack.java:79)
at java.util.Stack.pop(Stack.java:61)
at StackTest.<init>(StackTest.java:32)
at StackTest.main(StackTest.java:63)
 2003 Prentice Hall, Inc.
All rights reserved.
16
21.4 Hashtable Class
• Hashtable
– Data structure that uses hashing
• Algorithm for determining a key in table
– Keys in tables have associated values (data)
– Each table cell is a hash “bucket”
• Linked list of all key-value pairs that hash to that cell
• Minimizes collisions (handled via hash again, next cell,
buckets)
– Hashtable() creates empty hashtable with capacity 11
and load factor .75 (table grows larger automatically to meet
load factor requirement)
 2003 Prentice Hall, Inc. All rights reserved.
17
21.4 Hashtable Class
• Hashtable
– containsKey(key) tests if the object is in the hashtable
– put(key,object) puts the object in the hashtable using
the key
– get(key) returns the object in the hashtable using the key
 2003 Prentice Hall, Inc. All rights reserved.
18
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// Fig. 21.3: WordTypeCount.java
// Count the number of occurrences of each word in a string.
import java.awt.*;
import java.awt.event.*;
import java.util.*;
import javax.swing.*;
public class WordTypeCount extends JFrame {
private JTextArea inputField;
private JLabel prompt;
private JTextArea display;
private JButton goButton;
Outline
WordTypeCount.j
ava
Line 21
private Hashtable table;
public WordTypeCount()
{
super( "Word Type Count" );
inputField = new JTextArea( 3, 20 );
table = new Hashtable();
Create empty Hashtable
goButton = new JButton( "Go" );
goButton.addActionListener(
 2003 Prentice Hall, Inc.
All rights reserved.
19
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
new ActionListener() { // anonymous inner class
public void actionPerformed( ActionEvent event )
{
createTable();
display.setText( createOutput() );
}
}
Outline
WordTypeCount.j
ava
// end anonymous inner class
); // end call to addActionListener
prompt = new JLabel( "Enter a string:" );
display = new JTextArea( 15, 20 );
display.setEditable( false );
JScrollPane displayScrollPane = new JScrollPane( display );
// add components to GUI
Container container = getContentPane();
container.setLayout( new FlowLayout() );
container.add( prompt );
container.add( inputField );
container.add( goButton );
container.add( displayScrollPane );
 2003 Prentice Hall, Inc.
All rights reserved.
20
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
setSize( 400, 400 );
setVisible( true );
} // end constructor
method
// create table from userHashtable
input
private void createTable()
{
containsKey
determines
String input = inputField.getText();
method get obtains
whether the keyHashtable
specified as an
StringTokenizer words = new StringTokenizer(
input,
" \n\t\r"
);
Object associated with
key from
Outline
WordTypeCount.j
ava
Line 66
argument is in the hash table
Line 68
Hashtable (returns null if
while ( words.hasMoreTokens() ) {
Hashtable method put adds
neither key nor Object
exist)
String word = words.nextToken().toLowerCase();
// get word
key and valueLines
to Hashtable
71 and 74
(returns
null
if
key
has been
// if the table contains the word
inserted previously)
if ( table.containsKey( word ) ) {
Integer count = (Integer) table.get( word ); // get value
// and increment it
table.put( word, new Integer( count.intValue() + 1 ) );
}
else // otherwise add the word with a value of 1
table.put( word, new Integer( 1 ) );
} // end while
 2003 Prentice Hall, Inc.
All rights reserved.
21
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
} // end method createTable
// create string containing table values
private String createOutput() {
String output = "";
Enumeration keys = table.keys();
Outline
WordTypeCount.j
ava
Line 83
Hashtable method keys returns an
returns
Enumeration of keys inLine
the hash
93 table
Hashtable
method
isEmpty returns
the number
of key-value
pairs
that indicates whether
the key-value pairs
in boolean
the hash table
Line 94
currentKey + "\t" Hashtable
+ table.get( currentKey
) +
"\n";
contains any
Objects
// iterate through the keys
while ( keys.hasMoreElements() ) {
Hashtable method size
Object currentKey = keys.nextElement();
// output
output +=
}
output += "size: " + table.size() + "\n";
output += "isEmpty: " + table.isEmpty() + "\n";
return output;
} // end method createOutput
 2003 Prentice Hall, Inc.
All rights reserved.
22
100
101
102
103
104
105
106
public static void main( String args[] )
{
WordTypeCount application = new WordTypeCount();
application.setDefaultCloseOperation( JFrame.EXIT_ON_CLOSE );
}
Outline
WordTypeCount.j
ava
} // end class WordTypeCount
 2003 Prentice Hall, Inc.
All rights reserved.
23
21.5 Properties Class
• Properties
– Persistent Hashtable
– Properties prop = new Properties();
• Can be written to output stream
– prop.list(OutputStream);
• Can be read from input stream
– prop.load(InputStream);
 2003 Prentice Hall, Inc. All rights reserved.