Java程序辅导

DCS235 Software Engineering
Exercise Sheet 3
Using Java Collections
October 2003
Prerequisites

 You should understand Java ‘interfaces’.  If you need to revise this, see Jia section 4.4.7 and
5.3.

 You should be able to use the Java library documentation.

 Read about Java’s ‘Collections Classes’.  Section 8.2 of Jia’s book is a good description; there
is also a section in Sun’s Java tutorial see:
http://java.sun.com/docs/books/tutorial/collections/index.html.  It is not necessary to
appreciate all the details to start this exercise.
Aims
The aim of this exercise is to gain some practical experience using The Java collections framework.
In this exercise, you will design and implement a simple program using classes from the collection
framework. 
Section 1 describes the problem scenario and the requirements.  The other sections contain some
hints for the design and implementation.  The task is to write a program to meet these requirements.
You are advised to use Together.
This exercise can be done individually or in a small group.
DCS 235 – Lab Exercise 3 (version 1.1, 18 Oct 03) Page 1 of 5
1.Problem Scenario
In a large family, there are many uncles (and aunts) and many nieces (and nephews).  Each uncle
buys a present for each niece on her birthday every year.  Unfortunately, this can cause all sorts of
problems:

 Last year Amy received a charming book (‘The Wonder of Computers’) from Uncle Albert.
Unfortunately, Uncle Bill gave it to her too.

 When Beatrice opened her present from Uncle Charlie, she found it was the same thing he had
given to Claire.  “How could he?” she shouted rudely, “I’m not at all like Claire!”.

 Uncle David is getting forgetful.  Little Emily was so upset not to get a present.
1.1 Program Requirements
The family decide they need a computer program to manage the giving of presents.  The
requirements are:
1. Uncles and nieces can be added to the system.  The date of each niece’s birthday is recorded.
2. A list of uncles can be generated – in alphabetical order by name.
3. A list of nieces can be generated – in order of birthday.
4. The system holds a list of the presents selected by each uncle for the next birthday of one of
his nieces.  Each present is described in a few words.
5. An uncle can enter the present he intends to give to one of his nieces.  The program ensures
that: 
i. each niece receives something different from each uncle
ii. each uncles gives something different to each niece.
6. A list of the presents given by one of the uncles can be generated, showing the niece who is to
receive it.  The nieces for whom no present has been chosen should also be listed.
7. A list of presents to be received by one of the nieces can be generated, showing the uncle
giving it.  The uncles who have no present for the niece should also be listed.
8. The list of presents for a niece can be deleted (that’s done when her birthday is past).
1.2 Your Task
Write a program to meet the requirements.  To make a start, write classes to provide the behaviour,
without a user interface.  The public classes you should provide are: Family, Niece and Uncle.  The
public methods of these classes create an interface (often called an API – Application Program
Interface) to which a user interface could be attached.  The API is described below; note that your
program will also contain other classes and methods.
Class Family
Class representing a family.
Constructor Summary
Family() 
          Create an empty family with no uncles, nieces or presents.
DCS 235 – Lab Exercise 3 (version 1.1, 18 Oct 03) Page 2 of 5
  
Method Summary
 boolean addNiece(java.lang.String name, int day, int month) 
          Add a new niece.  If there is already a niece of this name, false is returned and
          nothing is added.
 boolean addUncle(java.lang.String name) 
          Add a new uncle.  If there is already an uncle of the name, false is returned and
          nothing is added.
 Niece findNiece(java.lang.String name) 
          Lookup a niece by name; return null if not found.
 Uncle findUncle(java.lang.String name) 
          Lookup an uncle by name; return null if not found.
 void listNieces() 
          List (to the console) the nieces recorded.
 void listUncles() 
          List (to the console) the uncles recorded.
Class Uncle
Class representing an uncle.  Note that the constructor is not public – use Family.addUncle(). 
Method Summary
 boolean addPresent(Niece recipient,
           java.lang.String description) 
     Adds a new present, given by this uncle.  Return true if the present is allowed.
 void listPresents() 
     Lists (to the console) the presents given by this uncle, showing the recipient.
     Nieces with no present from this uncle are also listed.
Class Niece
Class representing a niece.  Note that the constructor is not public – use Family.addNiece(). 
Method Summary
 int clearPresents() 
       Delete all the presents chosen for this niece.  Return the number removed.
 void listPresents() 
       Lists (to the console) the presents to be received by this niece, showing the
       giver.  Uncles with no present for this niece are also listed.
DCS 235 – Lab Exercise 3 (version 1.1, 18 Oct 03) Page 3 of 5
2.Specification
In this section two method of understanding the problem in more detail are suggested.
2.1 Sets and Function
We can describe the problem using simple sets and functions.
Describe the other constraint in the same style.
2.2 Class Diagram
Draw a class diagram to describe the problem.  As well as the public classes in the API, consider
classes ‘Person’ and ‘Present’.  Show the attributes of each class.
DCS 235 – Lab Exercise 3 (version 1.1, 18 Oct 03) Page 4 of 5
There is a set People. The uncles and nieces are people:
Uncles ⊂ People Nieces ⊂ People
There is a set Presents. We assume that each present has a description;
we write the description of present p as pD. It is possible for two differ-
ent presents p1, p2 to have the same description (p
D
1
= pD
2
), implying that
presents p1, p2 must not both be given to one of the nieces.
The presents recipient and giver of each present is described by the functions
r and g:
r ∈ Presents → Nieces g ∈ Presents → Uncles
For example, if Bill gives Amy p1 = “book”, David gives Amy p2 = “toy”
and Bill gives Emily p3 = “sweets” then
r p1 = Amy r p2 = Amy r p3 = Emily
and
g p1 = Bill g p2 = David g p3 = Bill
The presents given by uncle u, paired with their recipients, are:
{(p, r p) | g p = u}
The constraint that all the presents received by a niece are different is ex-
pressed as:
∀p1, p2 ∈ Presents • p1 6= p2 ∧ r p1 = r p2 ⇒ p
D
1
6= pD
2
3.Design and Implementation Hints
For this exercise, you should use the classes from the Java collections framework (in package
java.util) to hold the data1.  
3.1 Design 1
A possible design would be to hold the data as a list of presents, with each present having a
reference to the giver and recipient.  This design is simple.  What is the disadvantage of this design
(remember, the family is very large)?  Use a class diagram and/or simple mathematics to specify the
classes, attributes and operations in this design.
3.2 Design 2
An alternative design is to hold a map from each uncle to the set of presents given and from each
niece to the set of presents received.  
With this data structure, adding a present means inserting it into each map.  Generating the lists of
presents is also easy, and is much more efficient than in the first design.  However, deleting the
presents for one of the nieces is more complex.
3.3 Implementation
Testing
To test your program, write a main method which creates a family and adds nieces, uncles and
presents.
Constraints
It is suggested that you first implement the program without the constraints.  Then consider how
they are checked in each design.
Dates
The date (day and month only) of the birthday for each niece is recorded.  The Java Date class is
rather complex; it is suggested that you implement your own simple DayMonth class.
4.Additional Exercises
4.1 User Interface
Add a simple command line user interface.
4.2 More Sorting
The requirements given above can be implemented using a single ‘natural order’ for uncles and
nieces.  However, presents have no order, so the lists of presents appear in an arbitrary order.  It
would be better to show the presents given by an uncle in alphabetic order of the name of the niece
getting the present, and similarly the list of presents received should in order of the uncle’s name.
[Hint: you need to implement two classes implementing Comparator for Present.]
4.3 Performance Measurements
Measure the performance when very large number of entities are present.  Compare different
designs and different implementations of List and Map.
4.4 Deleting Uncles
Occasionally an uncle dies.  Implement a method to delete an uncle.  [WARNING: Be careful not
to create a space leak by leaving a present referring to the uncle, so that the uncle is not garbage
collected,]
1 A ‘real’ system would use a database, but that’s another course!
DCS 235 – Lab Exercise 3 (version 1.1, 18 Oct 03) Page 5 of 5