Solutions Manual: Chapter 20 Big Java, by Cay Horstmann 1
Review Exercises
R20.1
A set is a collection that has no duplicate elements. A map is a data structure for storing key/value pairs. The keys have no duplicates, but the values may be duplicated.
R20.3
The fundamental operations on the abstract set type are:
- adding an element
- removing an element
- testing whether an element is present in the set
- enumerating the set elements
The Set interface provides additional methods such as:
counting the elements
adding and removing multiple elements
- copying the elements to an array
R20.5
Set union = new HashSet(s1);
union.addAll(s2);
Set intersection = new HashSet(s1);
intersection.retainAll(s2);
R20.7
Define a class Pair as:
public class Pair
{
public Pair(Object aKey, Object aValue)
{
key = aKey;
value = aValue;
}
public Object getKey() { return key; }
public Object getValue() { return value; }
public int hashCode() { ... } // see R20-8
private Object key;
private Object value;
}
Then implement a map like this:
public class MapImpl implements Map
{
public MapImpl() { set = new HashSet(); }
public void put(Object k, Object v)
{
Pair p = new Pair(k, v);
set.remove(p);
set.add(p);
}
. . .
}
R20.9
Jim:
31 * (31 * 'J' + 'i') + 'm'
31 * (31 * 74 + 105) + 109 = 74478
Joe:
31 * (31 * 'J' + 'o') + 'e'
31 * (31 * 74 + 111) + 101 = 74656
R20.11
In a binary search tree, each subtree has the property that all descendants to the left are smaller than the value in the subtree's root, and that all descendants to the right are larger than the subtree's root.
Here is a binary tree that isn't a binary search tree:
Harry
/ \
Tom Dick
Here is a binary tree that is a binary search tree:
Dick
\
Tom
/
Harry
R20.13
Adam
\
Eve
/ \
Dick Romeo
/ \
Juliet Tom
/
Harry
R20.15
2 7 4 1 8 5 3 9 6 10
Programming Exercises
P20.1
ExP20_1.java
import java.util.Set;
import java.util.TreeSet;
import java.util.Iterator;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
/**
A program to split a line of words.
*/
public class ExP20_1
{
public static void main(String[] args)
throws IOException
{
Set s = new TreeSet();
BufferedReader console = new BufferedReader(
new InputStreamReader(System.in));
String inputLine = console.readLine();
StringTokenizer tokenizer
= new StringTokenizer(inputLine);
while (tokenizer.hasMoreTokens())
{
String word = tokenizer.nextToken();
s.add(word);
}
Iterator iter = s.iterator();
while (iter.hasNext())
System.out.println(iter.next());
System.out.println("size=" + s.size());
}
}
P20.3
HashSet.java
import java.util.Iterator;
import java.util.AbstractSet;
/**
A hash set stores an unordered collection of objects, using
a hash table.
*/
public class HashSet extends AbstractSet
{
/**
Constructs a hash table.
@param bucketsLength the length of the buckets array
*/
public HashSet(int bucketsLength)
{
buckets = new Link[bucketsLength];
size = 0;
}
/**
Tests for set membership.
@param x an object
@return true if x is an element of this set
*/
public boolean contains(Object x)
{
int h = x.hashCode();
if (h < 0) h = -h;
h = h % buckets.length;
Link current = buckets[h];
while (current != null)
{
if (current.data.equals(x)) return true;
current = current.next;
}
return false;
}
/**
Adds an element to this set.
@param x an object
@return true if x is a new object, false if x was
already in the set
*/
public boolean add(Object x)
{
int h = x.hashCode();
if (h < 0) h = -h;
h = h % buckets.length;
Link current = buckets[h];
while (current != null)
{
if (current.data.equals(x))
return false; // already in the set
current = current.next;
}
Link newLink = new Link();
newLink.data = x;
newLink.next = buckets[h];
buckets[h] = newLink;
size++;
return true;
}
/**
Removes an object from this set.
@param x an object
@return true if x was removed from this set, false
if x was not an element of this set
*/
public boolean remove(Object x)
{
int h = x.hashCode();
if (h < 0) h = -h;
h = h % buckets.length;
Link current = buckets[h];
Link previous = null;
while (current != null)
{
if (current.data.equals(x))
{
if (previous == null) buckets[h] = current.next;
else previous.next = current.next;
size--;
return true;
}
previous = current;
current = current.next;
}
return false;
}
/**
Prints all buckets.
*/
public void debug()
{
for (int i = 0; i < buckets.length; i++)
{
if (buckets[i] != null)
{
System.out.print(i + ":");
for (Link c = buckets[i]; c != null; c = c.next)
{
System.out.print(" " + c.data);
}
System.out.println();
}
}
}
/**
Returns an iterator that traverses the elements of this set.
@param a hash set iterator
*/
public Iterator iterator()
{
return new HashSetIterator();
}
/**
Gets the number of elements in this set.
@return the number of elements
*/
public int size()
{
return size;
}
private Link[] buckets;
private int size;
private class Link
{
public Object data;
public Link next;
}
private class HashSetIterator implements Iterator
{
/**
Constructs a hash set iterator that points to the
first element of the hash set.
*/
public HashSetIterator()
{
bucket = 0;
previous = null;
previousBucket = buckets.length;
// set bucket to the index of the first nonempty bucket
while (bucket < buckets.length & buckets[bucket] == null)
bucket++;
if (bucket < buckets.length) current = buckets[bucket];
else current = null;
}
public boolean hasNext()
{
return current != null;
}
public Object next()
{
Object r = current.data;
if (current.next == null) // move to next bucket
{
previousBucket = bucket;
bucket++;
while (bucket < buckets.length & buckets[bucket] == null)
bucket++;
if (bucket < buckets.length)
current = buckets[bucket];
else
current = null;
}
else // move to next element in bucket
{
previous = current;
current = current.next;
}
return r;
}
public void remove()
{
if (previous != null)
previous.next = previous.next.next;
else if (previousBucket < buckets.length)
buckets[previousBucket] = null;
else
throw new IllegalStateException();
previous = null;
previousBucket = buckets.length;
}
private int bucket;
private Link current;
private int previousBucket;
private Link previous;
}
}
SetTest.java
import java.util.Iterator;
import java.util.Set;
/**
This program tests the hash set class.
*/
public class SetTest
{
public static void main(String[] args)
{
HashSet names = new HashSet(101); // 101 is a prime
names.add("Sue");
names.add("Harry");
names.add("Nina");
names.add("Susannah");
names.add("Larry");
names.add("Eve");
names.add("Sarah");
names.add("Adam");
names.add("Tony");
names.add("Katherine");
names.add("Juliet");
names.add("Romeo");
System.out.println("After adding");
names.debug();
names.remove("Romeo");
names.remove("George");
System.out.println("After removing");
names.debug();
Iterator iter = names.iterator();
while (iter.hasNext())
System.out.println(iter.next());
}
}
P20.5
Student.java
/**
A student with an ID.
*/
public class Student
{
/**
Constructs a Student object.
@param aFirstName the first name
@param aLastName the last name
@param anId the ID
*/
public Student(String aFirstName, String aLastName, int anId)
{
firstName = aFirstName;
lastName = aLastName;
id = anId;
}
/**
Gets the student's first name
@return firstName the first name
*/
public String getFirstName()
{
return firstName;
}
/**
Gets the student's last name
@return lastName the last name
*/
public String getLastName()
{
return lastName;
}
/**
Gets the student's ID
@return id the ID
*/
public int getId()
{
return id;
}
private String firstName;
private String lastName;
private int id;
}
StudentComparator.java
import java.util.Comparator;
/**
A comparsion class for Student.
*/
public class StudentComparator implements Comparator
{
/**
Compares two student objects
@param o1 the first student
@param o2 the second student
@return -1 if the first object is smaller, 0 if they are equal,
1 if the seond object is smaller
*/
public int compare(Object o1, Object o2)
{
Student s1 = (Student)o1;
Student s2 = (Student)o2;
if (s1.getLastName().compareTo(s2.getLastName()) < 0)
return -1;
if (s1.getLastName().compareTo(s2.getLastName()) == 0)
{
if (s1.getFirstName().compareTo(s2.getFirstName()) < 0)
return -1;
if (s1.getFirstName().compareTo(s2.getFirstName()) == 0)
{
if (s1.getId() < s2.getId())
return -1;
if (s1.getId() == s2.getId())
return 0;
return 1;
}
return 1;
}
return 1;
}
}
ExP20_5.java
import java.util.Map;
import java.util.HashMap;
import java.util.Set;
import java.util.Iterator;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import javax.swing.JOptionPane;
/**
A test program for Student class.
*/
public class ExP20_5
{
public static void main(String[] args)
{
Map m = new HashMap();
boolean done = false;
while(!done)
{
String input = JOptionPane.showInputDialog(
"A)dd R)emove M)odify P)rint");
if (input == null)
done = true;
else if (input.equalsIgnoreCase("A"))
{
boolean done1 = false;
while (!done1)
{
String fName = JOptionPane.showInputDialog(
"Enter the student's first name, Cancel to quit:");
String lName = JOptionPane.showInputDialog(
"Enter the student's last name, Cancel to quit:");
String ident = JOptionPane.showInputDialog(
"Enter the student's ID, Cancel to quit:");
String grade = JOptionPane.showInputDialog(
"Enter the student's grade, Cancel to quit:");
if (fName == null || lName == null
|| ident == null || grade == null)
done1 = true;
else
{
int id = Integer.parseInt(ident);
Student s = new Student(fName, lName, id);
m.put(s, grade);
}
}
}
else if (input.equalsIgnoreCase("R"))
{
boolean done2 = false;
while (!done2)
{
String ident = JOptionPane.showInputDialog(
"Enter the student's ID, Cancel to quit:");
if (ident == null)
done2 = true;
else
{
int id = Integer.parseInt(ident);
remove(id, m);
}
}
}
else if (input.equalsIgnoreCase("M"))
{
boolean done3 = false;
while (!done3)
{
String ident = JOptionPane.showInputDialog(
"Enter the student's ID, Cancel to quit:");
String grade = JOptionPane.showInputDialog(
"Enter the student's grade, Cancel to quit:");
if (ident == null || grade == null)
done3 = true;
else
{
int id = Integer.parseInt(ident);
modify(id, grade, m);
}
}
}
else if (input.equalsIgnoreCase("P"))
{
print(m);
}
else
done = true;
}
System.exit(0);
}
/**
Removes a student from a map.
@param id the integer ID
@param m a map
*/
private static void remove(int id, Map m)
{
int studentId = 0;
Set keySet = m.keySet();
Iterator iter = keySet.iterator();
while(iter.hasNext())
{
Object key = iter.next();
Student s = (Student)key;
studentId = s.getId();
if (studentId == id)
m.remove(s);
}
}
/**
Modifies a student from a map.
@param id the integer ID
@param grade the student's grade
@param m the map
*/
private static void modify(int id, String grade, Map m)
{
int studentId = 0;
Set keySet = m.keySet();
Iterator iter = keySet.iterator();
while(iter.hasNext())
{
Object key = iter.next();
Object value = m.get(key);
Student s = (Student)key;
studentId = s.getId();
if (studentId == id)
m.put(s, grade);
}
}
/**
Prints the contents of a map.
@param m a map
*/
private static void print(Map m)
{
List keys = new ArrayList(m.keySet());
Comparator comp = new StudentComparator();
Collections.sort(keys, comp);
Iterator iter = keys.iterator();
while(iter.hasNext())
{
Object key = iter.next();
Object value = m.get(key);
Student s = (Student)key;
System.out.println(s.getFirstName() + " " + s.getLastName() + " " + s.getId()
+ ": " + value);
}
System.out.println("");
}
}
P20.7
BankAccount.java
/**
A bank account has a balance that can be changed by
deposits and withdrawals.
*/
public class BankAccount
{
/**
Constructs a bank account with a zero balance
*/
public BankAccount()
{
balance = 0;
}
/**
Constructs a bank account with a given balance
@param initialBalance the initial balance
*/
public BankAccount(double initialBalance)
{
balance = initialBalance;
}
/**
Deposits money into the bank account.
@param amount the amount to deposit
*/
public void deposit(double amount)
{
double newBalance = balance + amount;
balance = newBalance;
}
/**
Withdraws money from the bank account.
@param amount the amount to withdraw
*/
public void withdraw(double amount)
{
double newBalance = balance - amount;
balance = newBalance;
}
/**
Gets the current balance of the bank account.
@return the current balance
*/
public double getBalance()
{
return balance;
}
/**
Determines if the accounts are equal.
@param otherObject the other account
@return true if the accounts are equal, false otherwise
*/
public boolean equals(Object otherObject)
{
if (otherObject == null) return false;
if (getClass() != otherObject.getClass())
return false;
BankAccount other = (BankAccount)otherObject;
return balance == other.balance;
}
/**
Computes the hash code.
@return the hash code
*/
public int hashCode()
{
return new Double(balance).hashCode();
}
/**
Displays a string representation of the bank account object.
@return a string describing the bank account object.
*/
public String toString()
{
return
"BankAccount[balance=" + balance + "]";
}
private double balance;
}
ExP20_7.java
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
/**
A program to test hash codes of bank accounts.
*/
public class ExP20_7
{
public static void main(String[] args)
{
BankAccount acct1 = new BankAccount(10000);
BankAccount acct2 = new BankAccount(3400);
BankAccount acct3 = new BankAccount(100);
BankAccount acct4 = new BankAccount(98000);
System.out.println("hash code of acct1="
+ acct1.hashCode());
System.out.println("hash code of acct2="
+ acct2.hashCode());
System.out.println("hash code of acct3="
+ acct3.hashCode());
System.out.println("hash code of acct4="
+ acct4.hashCode());
Set accounts = new HashSet();
accounts.add(acct1);
accounts.add(acct2);
accounts.add(acct3);
accounts.add(acct4);
Iterator iter = accounts.iterator();
while (iter.hasNext())
System.out.println(iter.next());
}
}
P20.9
IntSet.java
import java.util.TreeSet;
import java.util.Iterator;
/**
A data structure to hold a set of integers.
*/
public class IntSet
{
/**
Constructs an empty set.
*/
public IntSet()
{
elements = new TreeSet();
}
/**
Adds an integer if it is not present.
@param x the integer to add
*/
public void add(int x)
{
elements.add(new Integer(x));
}
/**
Removes an integer if it is present.
@param x the integer to remove
*/
public void remove(int x)
{
elements.remove(new Integer(x));
}
/**
Prints all elements currently in the set.
*/
public void print()
{
System.out.print("{ ");
Iterator iterator = elements.iterator();
while (iterator.hasNext())
{
System.out.print(iterator.next() + " ");
}
System.out.println("}");
}
/**
Returns a new set iterator.
@return set iterator
*/
public IntSetIterator intSetIterator()
{
return new IntSetIterator(elements.iterator());
}
private TreeSet elements;
}
IntSetIterator.java
import java.util.Iterator;
/**
A integer set iterator that supports only
the hasNext/next methods.
*/
public class IntSetIterator
{
/**
Construct a new IntSetIterator object.
@param iter the Iterator
*/
public IntSetIterator(Iterator iter)
{
iterator = iter;
}
/**
Determines if the set has a next element.
@return true if the set has a next element, false otherwise
*/
public boolean hasNext()
{
return iterator.hasNext();
}
/**
Returns the next element in the set.
@return next element in set
*/
public int next()
{
Integer element = (Integer)iterator.next();
return element.intValue();
}
private Iterator iterator;
}
ExP20_9.java
/**
A test program for IntSet and IntSetIterator classes.
*/
public class ExP20_9
{
public static void main(String[] args)
{
IntSet s = new IntSet();
s.add(2);
s.add(3);
s.add(5);
s.add(7);
s.add(9);
s.add(7);
s.remove(9);
IntSetIterator iterator = s.intSetIterator();
while (iterator.hasNext())
{
System.out.println(iterator.next());
}
}
}
P20.11
IntSet.java
import java.util.TreeSet;
import java.util.Iterator;
/**
A data structure to hold a set of integers.
*/
public class IntSet
{
/**
Constructs an empty set.
*/
public IntSet()
{
elements = new TreeSet();
}
/**
Adds an integer if it is not present.
@param x the integer to add
*/
public void add(int x)
{
elements.add(new Integer(x));
}
/**
Removes an integer if it is present.
@param x the integer to remove
*/
public void remove(int x)
{
elements.remove(new Integer(x));
}
/**
Prints all elements currently in the set.
*/
public void print()
{
System.out.print("{ ");
Iterator iterator = elements.iterator();
while (iterator.hasNext())
{
System.out.print(iterator.next() + " ");
}
System.out.println("}");
}
private TreeSet elements;
}
ExP20_11.java
/**
A test program that implements the sieve of Eratosthenes.
*/
public class ExP20_11
{
public static void main(String[] args)
{
IntSet s = new IntSet();
int n = 100;
for (int i = 2; i <= n; i++)
s.add(i);
for (int k = 2; k * k <= n; k++)
for (int i = 2; i * k <= n; i++)
s.remove(i * k);
s.print();
}
}
P20.13
Tree.java
/**
This class implements a binary search tree whose
nodes hold objects that implement the Comparable
interface.
*/
public class Tree
{
/**
Constructs an empty tree.
*/
public Tree()
{
root = null;
}
/**
Returns the smallest object in this tree
@return the smallest object or null if the tree is empty
*/
public Comparable smallest()
{
if (root == null) return null;
else return root.smallest();
}
/**
Inserts a new node into the tree.
@param obj the object to insert
*/
public void insert(Comparable obj)
{
Node newNode = new Node();
newNode.data = obj;
newNode.left = null;
newNode.right = null;
if (root == null) root = newNode;
else root.insertNode(newNode);
}
/**
Prints the contents of the tree in sorted order.
*/
public void print()
{
if (root != null)
root.printNodes();
}
private Node root;
private class Node
{
/**
Returns the smallest descendant of this node
@return the smallest descendant
*/
public Comparable smallest()
{
if (left == null) return data;
else return left.smallest();
}
/**
Inserts a new node as a descendant of this node.
@param newNode the node to insert
*/
public void insertNode(Node newNode)
{
if (newNode.data.compareTo(data) < 0)
{
if (left == null) left = newNode;
else left.insertNode(newNode);
}
else
{
if (right == null) right = newNode;
else right.insertNode(newNode);
}
}
/**
Prints this node and all of its descendants
in sorted order.
*/
public void printNodes()
{
if (left != null)
left.printNodes();
System.out.println(data);
if (right != null)
right.printNodes();
}
public Comparable data;
public Node left;
public Node right;
}
}
ExP20_13.java
/**
A test program for Tree class.
*/
public class ExP20_13
{
public static void main(String[] args)
{
Tree staff = new Tree();
staff.insert("Romeo");
staff.insert("Juliet");
staff.insert("Tom");
staff.insert("Dick");
staff.insert("Harry");
System.out.println(staff.smallest());
}
}
P20.15
Tree.java
/**
This class implements a binary search tree whose
nodes hold objects that implement the Comparable
interface.
*/
public class Tree
{
/**
Constructs an empty tree.
*/
public Tree()
{
root = null;
}
/**
Inserts a new node into the tree.
@param obj the object to insert
*/
public void insert(Comparable obj)
{
Node newNode = new Node();
newNode.data = obj;
newNode.left = null;
newNode.right = null;
if (root == null) root = newNode;
else root.insertNode(newNode);
}
/**
Prints the contents of the tree in sorted order.
*/
public void print()