Work out the following exercise. Do not add it to your assignment submission, though you should keep it in your electronic portfolio in your own svn repository.
Problem: Using ArrayList
For this part of the assignment download the Balloons.zip, which contains the following files:
Create a new Project HW9-Balloons and import these files. Don't forget to add the tester library too. In this part of the lab we will work with ArrayLists of Balloons.
The class TopThree now stores the values of the three elements in an ArrayList. Complete the definition of the reorder method. Have a close look at the documentation for the ArrayList and Comparator to decide which methods you should use.
In the Examples class, design the method isSmallerThanIndex that determines whether the radius of the Balloon at the given position (index) in the given ArrayList of Balloons is smaller than the given limit.
Design the method isSameAsIndex that determines whether the balloon at the given position in the given ArrayList of Balloons has the same size and location as the given Balloon.
Design the method inflateAtIndex that increases the radius of a Balloon at the given index by 5. For this you should also design a helper method... where do you think it should be?
Design the method swapAtIndices that swaps the elements of the given ArrayList at the two given positions (indices). Make sure that this method works for any ArrayList... it should be parametrized.
Note 1: We have used the words position in the ArrayList and index in the ArrayList interchangeably. Both are commonly used, so we want to make sure you are comfortable with to both ways of describing locations of elements in an ArrayList.
Note 2: Of course, the tests for these methods will also appear in the Examples class. Make sure that every test can be run independently of all other tests. To do this, you must initialize (reset) the data at the beginning of your test method, then evaluate the test by invoking the appropriate check method. Just to be safe, you may also reset the data after the tests are complete.
These problems should be checked into your pair's SVN repository by the due date.
Project naming requirements
The names of the projects and some of the project files must be exactly the same as specified in the assignment. Failure to do so makes it impossible for the graders to run your submission and results in immediate loss of at least 50% of the homework credit.
Every file you submit must have a header that identifies you and the problem it solves. So, for the first problem the header should look like this:
// Assignment 9 Problem 1 // Partner Name1 // partner1username // Partner Name2 // partner2username // 20 March 2012
Create a project with the name HW09Problem1.
Finish the Binary search problem from Lab 9.
Include examples of ArrayLists with data of the type
Integer and the type Person (where we know
person's name and age). For the type Person order the
persons by their names (lexicographically). You do not need to include
examples of the ArrayLists with data of the type
String as was specified in the lab.
Create a project with the name HW09Problem2.
Your library includes the file DataSet.java that defines the following interface:/** * An interface that represents a data set * where we can add and remove items * * @paramthe type of data items in this data set */ interface DataSet { /** * Add the given item to this data set * * @param t the given data item */ public void add(T t); /** * EFFECT: remove an item from this data set * * @return the item that has been removed * @throws a RuntimeException if this data set is empty */ public T remove(); /** * Produce the number of items in this queue * @return the the number of items in this data set */ public int size(); /** * Produce the 'next to be removed' item in this data set * @return the desired item */ public T current(); }
Design three different implementations of this interface as shown. Next week we will use these data structures to design a card game.
Design the class Stack that implements the DataSet interface using an ArrayList to hold the data items and adds and removes the items at the same end.
The class should contain an ArrayList as one of its fields. You may add other fields that will help you in implementing the interface.
This data structure is also known as LIFO - Last In, First Out organization.
Design the class Queue that implements the DataSet interface using an ArrayList to hold the data items and adds the data items at one end and removes the items from the other end.
This data structure is also known as FIFO - First In, First Out organization.
Design the class QueueList that implements the DataSet interface using an Linked List to hold the data items and adds the data items at one end (the tail of the queue) and removes the items from the other end (the head of the queue). Just like in a grocery store - you get in at the tail end of the queue, and when you are at the head of the queue, it is your turn, you get to pay, and leave the queue.
The class diagram for this data structure would be:
+-----------+
| Node |
+-----------+
| Data data |
| Node next |
+-----------+
/ \
---
|
----------------------------
| |
| +------------+ |
| | Qlist | |
| +------------+ |
| +---| Head front | |
| | | Tail tail |---+ |
| | | int count | | |
| | +------------+ | |
| | | |
| v v |
+------------+ +-----------+
| Head | | Tail |
+------------+ +-----------+
+------------+ +-----------+
The head node has no data (the value of
data is null). If the list is empty, the
next node is the tail.
The tail node has no data (the value of
data is null). The tail has the
job of remembering where is the last
node that has been inserted into the queue, so we can add another
node after the last node when the next add request comes. If
the list is empty, the next node of the tail
is the head node.
The following drawing shows the list-based queue with three nodes:
+--------------+
| Qlist |
+--------------+
+---| front = head |
| | tail = tail |---------------------------------------------------+
| | count = 3 | |
| +--------------+ |
| +-----------------|----+
| +--------+ +--------+ +--------+ | +--------+ | |
| | | | | | | | | | | |
head v | n1 v | n2 v | n3 v v | tail v v |
+-------------+ | +-----------+ | +-----------+ | +-------------+ | +-------------+ |
| Head | | | Node | | | Node | | | Node | | | Tail | |
+-------------+ | +-----------+ | +-----------+ | +-------------+ | +-------------+ |
| data = null | | | data = 7 | | | data = 4 | | | data = 9 | | | data = null | |
| next = n1 |-+ | next = n2 |-+ | next = n3 |-+ | next = tail |-+ | next = n3 |-+
+-------------+ +-----------+ +-----------+ +-------------+ +-------------+