Part-1
1. Suppose we have a Rectangle class that includes length and width attributes of type int, both set by the constructor. Create a compareTo method for this class so that rectangle objects are ordered based on their a) Perimeter, and b) Area.
2. Give examples from the "real world" of unsorted lists, sorted lists, indexed lists, lists that permit duplicate elements, and lists that do not permit duplicate elements.
3. Someone suggests that, instead of shifting list elements to the left when an object is removed, the array location holding that object should just be set to null. Discuss the ramifications of such an approach for each of our three list types.
4. Can the linear search algorithm be encoded using recursion? If not, why not? If so, outline an approach and discuss its advantages and disadvantages. Share your thoughts with others in the class.
5. Expand the RefUnsortedList class with a public method endInsert, which inserts an element at the end of the list. Do not add any instance variables to the class.
protected boolean found: // true if element found, else false
protected LLNode location; // node containing element, if found
protected LLNode previous; // node preceeding location
protected LLNode list; // first node on the list
public RefUnsortedList()
(
numElements = 0;
list = null;
currentPos = null: 1
}
public void add(T element)
// Adds element to this list.
{
LLNode newNode = new LLNode(element);
newNode.setLink(list);
list = newNode: numElements++;
}
Protected void find(T target)
// Searches list for an occurrence of an element e such that
// e.equals(target). If successful, sets instance variables
// found to true, location to node containing e, and previous
// to the node that links to location. If not successful, sets
// found to false.
location - list;
found = false:
while (location != null)
{
if (location.getInfo().equals(target)) // if they match
{
found = true; return;
}
{
else {
previous = location;
location = location.getLink();
}
}
}
public void endInsert(T element)
Part-2
Description:
The fancy new French restaurant La Food is very popular for its authentic cuisine and high prices. This restaurant does not take reservations. To help improve the efficiency of their operations, the Maitre De has hired you to write a program that simulates people waiting for tables. The goal is to determine the average amount of time people spend waiting for tables.
Your program will read in a list of event descriptions from a text file, one description per line.
1. Arrival: A party has arrived to eat. Add them to the end of the list of waiting parties (a Queue) and tell them to wait at the bar (where strong drinks are served) until called. This event is described in the following format:
A t n name
Here tis the time of arrival (in minutes past opening time), n is the number of people in the party, and name is the name to call when the table is ready.
2. Table: A table has become available; remove the party that has been waiting the longest from your list, and seat them. This event is described in the following form:
T t
Here tis the time the table became available (again, in minutes past opening time),
3. Quit: This is a sentinel event indicating the end of the input file. It has the following form:
Q
When the events in the file have been processed, compute and print the average waiting time per customer. If there are still people waiting for tables, print a summary of who is still waiting.
Sample Data File
Here is a sample data file. You may use this if you like, or you can make up your own.
A 3 3 Merlin
A 8 2 Arthur Pendragon
T 10
A 12 2 Sir Lancelot
T 15
A 17 3 The Green Knight
T 20
Q
Here is the corresponding output from the simulator program. The user's input appears in italics.
*** Welcome to the La Food Restaurant Simulator ***
Enter data file name: data.txt
Please wait at the bar,
party Merlin of 3 people. (time=3)
Please wait at the bar,
party Arthur Pendragon of 2 people. (time=8)
Table for Merlin! (time=10)
Please wait at the bar,
party Sir Lancelot of 2 people. (time=12)
Table for Arthur Pendragon! (time=15)
Please wait at the bar,
party The Green Knight of 3 people. (time=17)
Table for Sir Lancelot! (time=20)
** Simulation Terminated **
The average waiting time was: 7.28
The following parties were never seated:
party The Green Knight of 3 people
Have a nice meal!
Notes
1. Before you begin programming, sketch a high level design of what you want to implement using the UML notation. At the very least, you should have a use case diagram, class diagram (for the Party class) and a sequence diagram.
2. Remember to include comments at the top of your program and 1-2 lines for each function (including pre-and post-conditions). Use javadoccompatible comments.
3. Develop a Queue class. Hint: Check out the sample Queue java source files in the text book. Declare a class Party to hold one party.
4. Read one line of the text file, and then process it, before moving on to the next line. Do not try to read in the entire file before processing it. Reading the text file is probably the trickiest part of this assignment.
5. To compute the average waiting time, keep track of the total number of people seated, and keep track of the total time spent waiting using something like this:
totmins = totmins + partysize*(tos - toa)
wheretosis the time of seating, and toais the time of arrival. Since you need to know both times, this must be done when the party is seated.
6. Start right away!
Hand In
1. Listing (print-out) of your nicely formatted program source code (with comments and headers)
2. Print-out of the text file that contains your restaurant information
3. Screen captures of at least three sample runs/scenario output
4. High level design using UML notation (minimum of a use case diagram, a class diagram for Party class, & a sequence diagram)
5. Utilize the submission template provided in the course module.
Source code listing here....
/*******************************************************************************
* Party Class
*
* Description here....
*
* Preconditions:
* Postconditions:
*
* @authorStudent Name
* @dateDate
* @version 1.0
*
******************************************************************************/
publicclass Party {
// logic here....
publicintgetTime() {
returntime;
}
/**
* Method for accessing the name of the object.
* @return String name
*/
public String getName() {
returnname;
}
/**
* Method for accessing the size of the object.
* @returnint size
*/
publicintgetSize() {
returnsize;
}
}
/*******************************************************************************
* QueueArrayClass
*
* Description here....
*
* Preconditions:
* Postconditions:
*
* @authorStudent Name
* @dateDate
* @version 1.0
*
******************************************************************************/
publicclassQueueArrayimplements Queue
{
// logic here...
publicQueueArray(intmaxsize)
{
// logic here...
}
// Transformers/Mutators
publicvoidenqueue(Object x)
{
// logic here....
}
public Object dequeue()
{
// logic here...
}
publicvoidmakeEmpty()
{
// logic here...
}
// Observers/Accessors
public Object getFront()
{
// logic here....
}
publicint size() { // logic here.... }
publicbooleanisEmpty() { logic here.... }
publicbooleanisFull() { // logic here... }
}
/*******************************************************************************
* Queue Interface
*
* Description here....
*
* Preconditions:
* Postconditions:
*
* @authorStudent Name
* @dateDate
* @version 1.0
*
******************************************************************************/
publicinterface Queue
{
// Transformers/Mutators
publicvoidenqueue(Object x);
public Object dequeue();
publicvoidmakeEmpty();
// Observers/Accessors
public Object getFront();
publicint size();
publicbooleanisEmpty();
publicbooleanisFull();
}
/*******************************************************************************
* Driver Main Class
*
* Description here....
*
* Preconditions:
* Postconditions:
*
* @authorStudent Name
* @dateDate
* @version 1.0
*
******************************************************************************/
import java.io.*;
importjava.text.DecimalFormat;
importjava.util.Scanner;
publicclass Driver {
publicstaticvoid main(String[] args) throwsIOException {
FileReaderinFile = newFileReader("data.txt");
Scanner sFile = newScanner(inFile);
intqSize = 4;
intpTime = 0;
inttTime = 0;
intwaitTime = 0;
intsSize = 0;
doubletotTime;
// logic here...
}
Place screen captures here of at least 3 runs (different scenarios) of your program (be sure they are readable)...
Insert text file data here
Insert UML design diagrams here (use case, class, and sequence diagram)...