prog06/.classpath
prog06/.project
JavaWordProject
org.eclipse.jdt.core.javabuilder
org.eclipse.jdt.core.javanature
prog06/prog02/ArrayBasedPD.class
package prog02;
public synchronized class ArrayBasedPD implements PhoneDirectory {
protected static final int INITIAL_CAPACITY = 100;
protected int size;
protected DirectoryEntry[] theDirectory;
protected String sourceName;
public void ArrayBasedPD();
public void loadData(String);
public String addOrChangeEntry(String, String);
protected int find(String);
protected DirectoryEntry add(int, DirectoryEntry);
protected DirectoryEntry remove(int);
protected void reallocate();
public String removeEntry(String);
public void save();
public String lookupEntry(String);
}
prog06/prog02/ArrayBasedPD.java
prog06/prog02/ArrayBasedPD.java
package prog02;
import java.io.*;
import java.util.Scanner;
/** This is an implementation of the PhoneDirectory interface that uses
* an unsorted array to store the entries.
*/
public class ArrayBasedPD
implements PhoneDirectory {
/** The initial capacity of the array */
protected static final int INITIAL_CAPACITY = 100;
/** The current size of the array (number of directory entries) */
protected int size = 0;
/** The array to contain the directory data */
protected DirectoryEntry[] theDirectory =
new DirectoryEntry[INITIAL_CAPACITY];
/** The data file that contains the directory data */
protected String sourceName = null;
/** Method to load the data file.
pre: The directory storage has been created and it is empty.
If the file exists, it consists of name-number pairs
on adjacent lines.
post: The data from the file is loaded into the directory.
@param sourceName The name of the data file
*/
public void loadData (String sourceName) {
// Remember the source name.
this.sourceName = sourceName;
try {
// Create a BufferedReader for the file.
Scanner in = new Scanner(new File(sourceName));
String name;
String number;
// Read each name and number and add the entry to the array.
while (in.hasNextLine()) {
name = in.nextLine();
number = in.nextLine();
// Add an entry for this name and number.
addOrChangeEntry(name, number);
}
// Close the file.
in.close();
} catch (FileNotFoundException ex) {
// Do nothing: no data to load.
System.out.println(sourceName + ": file not found.");
System.out.println(ex);
return;
}
}
/** Add an entry or change an existing entry.
@param name The name of the person being added or changed
@param number The new number to be assigned
@return The old number or, if a new entry, null
*/
public String addOrChangeEntry (String name, String number) {
int index = find(name);
if (index >= 0) {
String oldNumber = theDirectory[index].getNumber();
theDirectory[index].setNumber(number);
return oldNumber;
} else {
add(-index - 1, new DirectoryEntry(name, number));
return null;
}
}
/** Find an entry in the directory.
@param name The name to be found
@return The index of the entry with that name or, if it is not
there, (-insert_index - 1), where insert_index is the index
where should be added.
*/
protected int find (String name) {
for (int i = 0; i < size; i++)
if (theDirectory[i].getName().equals(name))
return i;
return -size - 1;
}
/** Add an entry to the directory.
@param index The index at which to add the entry in theDirectory.
@param newEntry The new entry to add.
@return The DirectoryEntry that was just added.
*/
protected DirectoryEntry add (int index, DirectoryEntry newEntry) {
if (size == theDirectory.length)
reallocate();
theDirectory[size] = theDirectory[index];
theDirectory[index] = newEntry;
size++;
return newEntry;
}
/** Remove an entry from the directory.
@param index The index in theDirectory of the entry to remove.
@return The DirectoryEntry that was just removed.
*/
protected DirectoryEntry remove (int index) {
DirectoryEntry entry = theDirectory[index];
theDirectory[index] = theDirectory[size-1];
size--;
return entry;
}
/** Allocate a new array to hold the directory. */
protected void reallocate() {
DirectoryEntry[] newDirectory =
new DirectoryEntry[2 * theDirectory.length];
System.arraycopy(theDirectory, 0, newDirectory, 0,
theDirectory.length);
theDirectory = newDirectory;
}
/** Remove an entry from the directory.
@param name The name of the person to be removed
@return The current number. If not in directory, null is
returned
*/
public String removeEntry (String name) {
int index = find(name);
if (index >= 0)
return remove(index).getNumber();
else
return null;
}
/** Method to save the directory.
pre: The directory has been loaded with data.
post: Contents of directory written back to the file in the
form of name-number pairs on adjacent lines.
*/
public void save() {
try {
// Create PrintWriter for the file.
PrintWriter out = new PrintWriter(
new FileWriter(sourceName));
// Write each directory entry to the file.
for (int i = 0; i < size; i++) {
// Write the name.
out.println(theDirectory[i].getName());
// Write the number.
out.println(theDirectory[i].getNumber());
}
out.close();
} catch (Exception ex) {
System.err.println("Save of directory failed");
ex.printStackTrace();
System.exit(1);
}
}
/** Look up an entry.
@param name The name of the person
@return The number. If not in the directory, null is returned
*/
public String lookupEntry (String name) {
int index = find(name);
if (index >= 0)
return theDirectory[index].getNumber();
else
return null;
}
}
prog06/prog02/ConsoleUI.class
package prog02;
public synchronized class ConsoleUI implements UserInterface {
private java.util.Scanner scIn;
public void ConsoleUI();
public int getCommand(String[]);
public void sendMessage(String);
public String getInfo(String);
public static void main(String[]);
}
prog06/prog02/ConsoleUI.java
prog06/prog02/ConsoleUI.java
package prog02;
import java.io.*;
import java.util.*;
/**
* An implementation of UserInterface using the console and text.
* @author vjm
*/
public class ConsoleUI implements UserInterface {
/** Scanner to read from input console. */
private Scanner scIn = null;
/** Creates a new instance of ConsoleUI */
public ConsoleUI() {
scIn = new Scanner(System.in);
}
/** presents set of commands for user to choose one of
@param commands the commands to choose from
@return the index of the command in the array
*/
public int getCommand (String[] commands) {
int choice = -1;
do {
for (int i = 0; i < commands.length; i++) {
System.out.println("Select " + i + ": "
+ commands[i]);
}
try {
choice = scIn.nextInt(); // Read the next choice.
scIn.nextLine(); // Skip trailing newline.
if (choice >= 0 && choice < commands.length)
return choice;
System.out.println("*** Invalid choice "
+ choice
+ " - try again!");
choice = -1;
}
catch (InputMismatchException ex) {
System.out.println("*** Incorrect data entry - "
+ "enter an integer between 0 and "
+ (commands.length-1));
scIn.nextLine(); // Discard bad input.
choice = -1;
}
} while (choice == -1);
return -1;
}
/** tell the user something
@param message string to print out to the user
*/
public void sendMessage (String message) {
System.out.println(message);
}
/** prompts the user for a string
@param prompt the request
@return what the user enters, null if nothing
*/
public String getInfo (String prompt) {
System.out.println(prompt + " ");
String result = scIn.nextLine();
if (result.equals(""))
return null;
return result;
}
public static void main (String[] args) {
UserInterface ui = new ConsoleUI();
String[] commands = { "hello", "how", "are", "you" };
int choice = ui.getCommand(commands);
ui.sendMessage("You chose " + choice);
String result = ui.getInfo("say something");
ui.sendMessage("You said " + result);
}
}
prog06/prog02/DirectoryEntry.class
package prog02;
public synchronized class DirectoryEntry {
private String name;
private String number;
public void DirectoryEntry(String, String);
public String getName();
public String getNumber();
public void setNumber(String);
}
prog06/prog02/DirectoryEntry.java
prog06/prog02/DirectoryEntry.java
package prog02;
/** The DirectoryEntry contains the name and number, both
* stored as strings. The name is not changable.
* @author Koffman and Wolfgang
*/
public class DirectoryEntry {
/** The name of the indiviual represented in the directory. */
private String name;
/** The home number for this individual. */
private String number;
/** Creates a new instance of DirectoryEntry
@param name Name of Person
@param number Phone number of Person */
public DirectoryEntry (String name, String number) {
this.name = name;
this.number = number;
}
/** Retrieves the name
@return the name of the individual
*/
public String getName () {
return name;
}
/** Retrieves the number
@return the number of the individual
*/
public String getNumber () {
return number;
}
/** Sets the number to a different value.
@param number the new number to set it to
*/
public void setNumber (String number) {
this.number = number;
}
}
prog06/prog02/GUI.class
package prog02;
public synchronized class GUI implements UserInterface {
private String windowTitle;
public void GUI(String);
public int getCommand(String[]);
public void sendMessage(String);
public String getInfo(String);
public static void main(String[]);
}
prog06/prog02/GUI.java
prog06/prog02/GUI.java
package prog02;
import javax.swing.*;
/**
* An implementation of UserInterface using popup windows and buttons.
* @author vjm
*/
public class GUI implements UserInterface {
private String windowTitle;
/** Creates a new instance of GUI
@param windowTitle window title to put on top of window
*/
public GUI(String windowTitle) {
this.windowTitle = windowTitle;
}
/** presents set of commands for user to choose one of
@param commands the commands to choose from
@return the index of the command in the array
*/
public int getCommand (String[] commands) {
return JOptionPane.showOptionDialog
(null, // No parent
"Select a Command", // Prompt message
windowTitle, // Window title
JOptionPane.YES_NO_CANCEL_OPTION, // Option type
JOptionPane.QUESTION_MESSAGE, // Message type
null, // Icon
commands, // List of commands
commands[commands.length - 1]);
}
/** tell the user something
@param message string to print out to the user
*/
public void sendMessage (String message) {
JOptionPane.showMessageDialog(null, message);
}
/** prompts the user for a string
@param prompt the request
@return what the user enters, null if nothing
*/
public String getInfo (String prompt) {
return JOptionPane.showInputDialog(prompt);
}
public static void main (String[] args) {
UserInterface ui = new GUI("Test GUI");
String[] commands = { "hello", "how", "are", "you" };
int choice = ui.getCommand(commands);
ui.sendMessage("You chose " + choice);
String result = ui.getInfo("say something");
ui.sendMessage("You said " + result);
}
}
prog06/prog02/Main.class
package prog02;
public synchronized class Main {
public void Main();
public static void processCommands(String, UserInterface, PhoneDirectory);
public static void main(String[]);
}
prog06/prog02/Main.java
prog06/prog02/Main.java
package prog02;
/**
* A program to query and modify the phone directory stored in csc220.txt.
* @author vjm
*/
public class Main {
/** Processes user's commands on a phone directory.
@param fn The file containing the phone directory.
@param ui The UserInterface object to use
to talk to the user.
@param pd The PhoneDirectory object to use
to process the phone directory.
*/
public static void processCommands(String fn, UserInterface ui, PhoneDirectory pd) {
pd.loadData(fn);
boolean changed = false;
String[] commands = {
"Add/Change Entry",
"Look Up Entry",
"Remove Entry",
"Save Directory",
"Exit"};
String name, number, oldNumber;
while (true) {
int c = ui.getCommand(commands);//presenting menu
switch (c) {
case -1://pressed x
ui.sendMessage("You shut down the program, restarting. Use Exit to exit.");
break;
case 0:
name= ui.getInfo("Enter a name");
if (name==null) {
ui.sendMessage("you pressed cancel");
break;
}
if(name.equals("")) {
ui.sendMessage("you entered in a empty name, try again");
break;
}
number=ui.getInfo("enter the new number");
///calling the method
oldNumber = pd.addOrChangeEntry(name, number);
if (oldNumber == null)
{
ui.sendMessage (name +" is added into the directory.");
ui.sendMessage(name+ "'s number: "+ number);
//
changed=true;
//
}
else
{
ui.sendMessage(name+"'s number has changed ");
ui.sendMessage("new number:" +number);
}
break;
///------------------------------------------------------------------------------
case 1://look up entry
name = ui.getInfo("Enter name");//prompt user for string
if (name==null) {
ui.sendMessage("you pressed cancel");
break;
}
if(name.equals("")) {
ui.sendMessage("you entered in a empty name, try again");
break;
}
number = pd.lookupEntry(name);
if (number == null)
{
ui.sendMessage (name +" is not in the directory");
}
else
{
ui.sendMessage(name+" has number "+ number);
}
break;
case 2: //remove entry
name= ui.getInfo("Enter the name");
if (name==null) {
ui.sendMessage("you pressed cancel");
break;
}
if(name.equals("")) {
ui.sendMessage("you entered in a empty name, try again");
break;
}
ui.sendMessage("Remove entry of "+ name+" and number");
number=pd.removeEntry(name);
if (number==null)
{
ui.sendMessage("name is not in the directory");
break;
}
else
{
ui.sendMessage(name +" with number" + number +" is not in the directory");
}
break;
case 3://save entry
pd.save();
ui.sendMessage("you have saved any changes");
changed=false;
break;
case 4://exit
if (changed=true){
ui.sendMessage("Do you really want to exit without saving?");
String option=ui.getInfo("1.yes 2.no");
if (option.equals("yes")) {
ui.sendMessage("now ending program");
return;
}
else if(option.equals("no")) {
break;
}
}
}
}}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
String fn = "csc220.txt";
PhoneDirectory pd = new SortedPD();
UserInterface ui = new GUI("Phone Directory");
processCommands(fn, ui, pd);
}
}
prog06/prog02/main.txt
jmin220 Joanna Minott
case 1:
Enter name
? Fred
Fred is not in the directory
case 1:
Enter name
? Victor
Victor has number [email protected]
case 2:
Enter the name
? Victor
Remove entry of Victor and number
Victor with [email protected] is not in the directory
case 2:
Enter the name
? Victor
Remove entry of Victor and number
name is not in the directory
case 0:
Enter a name
? Victor
enter the new number
?
Victor is added into the directory.
Victor's number:
case 0:
Enter a name
? Fred
enter the new number
? fred
Fred is added into the directory.
Fred's number: fred
case 0:
Enter a name
? Fred
enter the new number
? 777
Fred's number has changed
new number:777
case 0:
Enter a name
? Victor
enter the new number
? null
Victor's number has changed
ERROR (-3 points): message contains null.
new number:null
case 1:
Enter name
? null
you pressed cancel
case 1:
Enter name
?
you entered in a empty name, try again
case 2:
Enter the name
? null
you pressed cancel
case 2:
Enter the name
?
you entered in a empty name, try again
case 0:
Enter a name
? null
you pressed cancel
case 0:
Enter a name
?
you entered in a empty name, try again
case 4:
Do you really want to exit without saving?
1.yes 2.no
ERROR (-3 points): missing break.
Exception in thread "main" java.lang.NullPointerException
at prog02.Main.processCommands(Main.java:141)
at prog02.Main.main(Main.java:161)
SCORE: 6
prog06/prog02/perfect-Main.txt
case 1:
Enter name
? Fred
Fred is not listed in the directory
case 1:
Enter name
? Victor
The number for Victor is [email protected]
case 2:
Enter name
? Victor
Removed entry with name Victor and number [email protected]
case 2:
Enter name
? Victor
Victor is not listed in the directory
case 0:
Enter name
? Victor
Enter number
?
Victor was added to the directory
New number:
case 0:
Enter name
? Fred
Enter number
? fred
Fred was added to the directory
New number: fred
case 0:
Enter name
? Fred
Enter number
? 777
Number for Fred was changed
Old number: fred
New number: 777
case 0:
Enter name
? Victor
Enter number
? null
case 1:
Enter name
? null
case 1:
Enter name
?
case 2:
Enter name
? null
case 2:
Enter name
?
case 0:
Enter name
? null
case 0:
Enter name
?
case 4:
The directory is changed. I am going to ask you if you want to exit without saving.
commands: YES NO
selecting NO
-3 if it does not do a case 3 (save) before exiting
case 3:
case 4:
prog06/prog02/perfect-SortedPD.txt
A:a,B:b,C:c,D:d,null,null size = 4
Calling remove(0)
returned A:a
B:b,C:c,D:d,D:d,null,null size = 3
SUCCESS
A:a,null,null,null,null,null size = 1
Calling remove(0)
returned A:a
A:a,null,null,null,null,null size = 0
SUCCESS
A:a,B:b,C:c,D:d,E:e,null size = 5
Calling remove(2)
returned C:c
A:a,B:b,D:d,E:e,E:e,null size = 4
SUCCESS
A:a,B:b,C:c,D:d,E:e,F:f size = 6
Calling remove(5)
returned F:f
A:a,B:b,C:c,D:d,E:e,F:f size = 5
SUCCESS
A:a,B:b,C:c,D:d,E:e,null size = 5
Calling add(0, {X, x})
returned X:x
X:x,A:a,B:b,C:c,D:d,E:e size = 6
SUCCESS
A:a,B:b,C:c,D:d,E:e,null size = 5
Calling add(2, {X, x})
returned X:x
A:a,B:b,X:x,C:c,D:d,E:e size = 6
SUCCESS
A:a,B:b,C:c,D:d,E:e,null size = 5
Calling add(5, {X, x})
returned X:x
A:a,B:b,C:c,D:d,E:e,X:x size = 6
SUCCESS
A:a,B:b,C:c,D:d,E:e,F:f size = 6
Calling add(0, {X, x})
returned X:x
X:x,A:a,B:b,C:c,D:d,E:e,F:f,null,null,null,null,null size = 7
SUCCESS
B:b,D:d,F:f,H:h,J:j,L:l size = 5
find(C)
returned -2
SUCCESS
B:b,D:d,F:f,H:h,J:j,L:l size = 0
find(A)
returned -1
SUCCESS
B:b,D:d,F:f,H:h,J:j,L:l size = 1
find(A)
returned -1
SUCCESS
B:b,D:d,F:f,H:h,J:j,L:l size = 1
find(B)
returned 0
SUCCESS
B:b,D:d,F:f,H:h,J:j,L:l size = 1
find(C)
returned -2
SUCCESS
B:b,D:d,F:f,H:h,J:j,L:l size = 2
find(A)
returned -1
SUCCESS
B:b,D:d,F:f,H:h,J:j,L:l size = 2
find(B)
returned 0
SUCCESS
B:b,D:d,F:f,H:h,J:j,L:l size = 2
find(C)
returned -2
SUCCESS
B:b,D:d,F:f,H:h,J:j,L:l size = 2
find(D)
returned 1
SUCCESS
B:b,D:d,F:f,H:h,J:j,L:l size = 2
find(E)
returned -3
SUCCESS
SCORE: 60
prog06/prog02/PhoneDirectory.class
package prog02;
public abstract interface PhoneDirectory {
public abstract void loadData(String);
public abstract String lookupEntry(String);
public abstract String addOrChangeEntry(String, String);
public abstract String removeEntry(String);
public abstract void save();
}
prog06/prog02/PhoneDirectory.java
prog06/prog02/PhoneDirectory.java
package prog02;
/** The interface for the telephone directory.
* @author Koffman and Wolfgang
*/
public interface PhoneDirectory {
/** Load the data file containing the directory, or
establish a connection with the data source.
@param sourceName The name of the file (data source)
with the phone directory entries
*/
void loadData(String sourceName);
/** Look up an entry.
@param name The name of the person to look up
@return The number or null if name is not in the directory
*/
String lookupEntry(String name);
/** Add an entry or change an existing entry.
@param name The name of the person being added or changed
@param number The new number to be assigned
@return The old number or, if a new entry, null
*/
String addOrChangeEntry(String name, String number);
/** Remove an entry from the directory.
@param name The name of the person to be removed
@return The current number. If not in directory, null is
returned
*/
String removeEntry(String name);
/** Method to save the directory.
pre: The directory has been loaded with data.
post: Contents of directory written back to the file in the
form of name-number pairs on adjacent lines,
modified is reset to false.
*/
void save();
}
prog06/prog02/SortedPD.class
package prog02;
public synchronized class SortedPD extends ArrayBasedPD {
public void SortedPD();
protected int find(String);
protected DirectoryEntry add(int, DirectoryEntry);
protected DirectoryEntry remove(int, String);
protected void reallocate();
}
prog06/prog02/SortedPD.java
prog06/prog02/SortedPD.java
package prog02;
/**
* This is an implementation of PhoneDirectory that uses a sorted
* array to store the entries.
* @author vjm
*/
public class SortedPD extends ArrayBasedPD {
/** Find an entry in the directory.
@param name The name to be found
@return The index of the entry with that name or, if it is not
there, (-insert_index - 1), where insert_index is the index
where should be added.
*/
protected int find (String name) {
int first=0;
int last=(size-1);
while(first<=last) {
int middle=(last+first)/2;
if (theDirectory[middle].getName().compareTo(name)>0){
first=middle-1;
}
else if(theDirectory[middle].getName().compareTo(name)<0) {
last=middle+1;
}
else if (theDirectory[middle].getName().compareTo(name)==0) {
return middle;
}
}
return -1;
}
/** Add an entry to the directory.
@param index The index at which to add the entry in theDirectory.
@param newEntry The new entry to add.
@return The DirectoryEntry that was just added.
*/
protected DirectoryEntry add (int index, DirectoryEntry newEntry) {
if (size == theDirectory.length)
reallocate();
theDirectory[size] = theDirectory[index];
//comparing new name to old name in same location
while (index >0 && newEntry.getName().compareTo(theDirectory[index-1].getName())<0)
{
theDirectory[index]=theDirectory[index-1];
index--;
}
theDirectory[index]=newEntry;
size++;
return newEntry;
}
/** Remove an entry from the directory.
@param index The index in theDirectory of the entry to remove.
@return The DirectoryEntry that was just removed.
*/
protected DirectoryEntry remove (int index, String name) {
index=find(name);
DirectoryEntry entry = theDirectory[index];
System.arraycopy(theDirectory,index+1,theDirectory, index,size-index-1);
size--;
return entry;
}
/** Allocate a new array to hold the directory. */
protected void reallocate() {
DirectoryEntry[] newDirectory =
new DirectoryEntry[2 * theDirectory.length];
System.arraycopy(theDirectory, 0, newDirectory, 0,
theDirectory.length);
theDirectory = newDirectory;
}
}
prog06/prog02/sortedpd.txt
jmin220 Joanna Minott
A:a,B:b,C:c,D:d,null,null size = 4
Calling remove(0)
returned A:a
D:d,B:b,C:c,D:d,null,null size = 3
remove not implemented
ERROR -20
A:a,B:b,C:c,D:d,E:e,null size = 5
Calling add(0, {X, x})
returned X:x
X:x,B:b,C:c,D:d,E:e,A:a size = 6
add not implemented
ERROR -20
B:b,D:d,F:f,H:h,J:j,L:l size = 5
find(C)
INFINITE LOOP
SCORE: 0
prog06/prog02/TestPD.class
package prog02;
public synchronized class TestPD extends SortedPD {
DirectoryEntry[] dirR;
int[] indexR;
DirectoryEntry[][] dirsR;
int[] sizesR;
DirectoryEntry[] dirA;
DirectoryEntry deA;
int[] indexA;
DirectoryEntry[][] dirsA;
int[] sizesA;
int[] lengthsA;
DirectoryEntry[] dirF;
int[] sizeF;
String[] nameF;
int[] retF;
int lastRet;
int totalError;
public void TestPD();
void print();
boolean testRemove(int);
void testRemove();
boolean testAdd(int);
boolean equals(DirectoryEntry, DirectoryEntry);
void testAdd();
boolean testFind(int);
void testFind();
void test();
public static void main(String[]);
}
prog06/prog02/TestPD.java
prog06/prog02/TestPD.java
package prog02;
public class TestPD extends SortedPD {
void print () {
for (int i = 0; i < theDirectory.length; i++) {
if (theDirectory[i] == null)
System.out.print("null");
else
System.out.print(theDirectory[i].getName() + ":" +
theDirectory[i].getNumber());
if (i != theDirectory.length-1)
System.out.print(",");
}
System.out.println(" size = " + size);
}
DirectoryEntry[] dirR = { new DirectoryEntry("A", "a"),
new DirectoryEntry("B", "b"),
new DirectoryEntry("C", "c"),
new DirectoryEntry("D", "d"),
new DirectoryEntry("E", "e"),
new DirectoryEntry("F", "f") };
int indexR[] = { 0, 0, 2, 5 };
DirectoryEntry[][] dirsR = { { dirR[1], dirR[2], dirR[3], dirR[4], dirR[5] },
{ },
{ dirR[0], dirR[1], dirR[3], dirR[4], dirR[5] },
{ dirR[0], dirR[1], dirR[2], dirR[3], dirR[4] } };
int sizesR[] = { 4, 1, 5, 6 };
boolean testRemove (int i) {
size = sizesR[i];
theDirectory = new DirectoryEntry[6];
for (int j = 0; j < size; j++)
theDirectory[j] = dirR[j];
print();
DirectoryEntry ret;
try {
System.out.println("Calling remove(" + indexR[i] + ")");
ret = remove(indexR[i]);
}
catch (Exception e) {
System.out.println(e);
System.out.println("crashed");
return false;
}
if (ret == null)
System.out.println("returned null");
else
System.out.println("returned " + ret.getName() + ":" + ret.getNumber());
if (ret != dirR[indexR[i]])
return false;
print();
if (size != sizesR[i]-1)
return false;
if (theDirectory.length != 6) {
System.out.println("wrong length");
return false;
}
for (int j = 0; j < size; j++)
if (theDirectory[j] != dirsR[i][j])
return false;
return true;
}
void testRemove () {
for (int i = 0; i < indexR.length; i++)
if (testRemove(i))
System.out.println("SUCCESS");
else {
if (i == 0 && theDirectory[0] == dirR[3]) {
System.out.println("remove not implemented");
System.out.println("ERROR -20");
totalError += 20;
return;
}
System.out.println("ERROR -5");
totalError += 5;
}
}
DirectoryEntry[] dirA = { new DirectoryEntry("A", "a"),
new DirectoryEntry("B", "b"),
new DirectoryEntry("C", "c"),
new DirectoryEntry("D", "d"),
new DirectoryEntry("E", "e"),
new DirectoryEntry("F", "f") };
DirectoryEntry deA = new DirectoryEntry("X", "x");
int indexA[] = { 0, 2, 5, 0 };
DirectoryEntry[][] dirsA = { { deA, dirR[0], dirR[1], dirR[2], dirR[3], dirR[4] },
{ dirR[0], dirR[1], deA, dirR[2], dirR[3], dirR[4] },
{ dirR[0], dirR[1], dirR[2], dirR[3], dirR[4], deA },
{ deA, dirR[0], dirR[1], dirR[2], dirR[3], dirR[4], dirR[5] } };
int sizesA[] = { 5, 5, 5, 6 };
int lengthsA[] = { 6, 6, 6, 12 };
boolean testAdd (int i) {
theDirectory = new DirectoryEntry[6];
size = sizesA[i];
for (int j = 0; j < size; j++)
theDirectory[j] = dirA[j];
print();
DirectoryEntry ret;
try {
System.out.println("Calling add(" + indexA[i] + ", {" + deA.getName() + ", " + deA.getNumber() + "})");
ret = add(indexA[i], new DirectoryEntry(deA.getName(), deA.getNumber()));
}
catch (Exception e) {
System.out.println(e);
System.out.println("crashed");
return false;
}
System.out.println("returned " + ret.getName() + ":" + ret.getNumber());
if (!equals(ret, deA))
return false;
print();
if (size != sizesA[i]+1)
return false;
if (theDirectory.length != lengthsA[i]) {
System.out.println("wrong length");
return false;
}
for (int j = 0; j < size; j++)
if (!equals(theDirectory[j], dirsA[i][j]))
return false;
return true;
}
boolean equals (DirectoryEntry a, DirectoryEntry b) {
if (a == null || b == null)
return false;
return a.getName().equals(b.getName()) && a.getNumber().equals(b.getNumber());
}
void testAdd () {
for (int i = 0; i < indexA.length; i++)
if (testAdd(i))
System.out.println("SUCCESS");
else {
if (i == 0 && theDirectory[5] == dirA[0]) {
System.out.println("add not implemented");
System.out.println("ERROR -20");
totalError += 20;
return;
}
System.out.println("ERROR -5");
totalError += 5;
}
}
DirectoryEntry[] dirF = { new DirectoryEntry("B", "b"),
new DirectoryEntry("D", "d"),
new DirectoryEntry("F", "f"),
new DirectoryEntry("H", "h"),
new DirectoryEntry("J", "j"),
new DirectoryEntry("L", "l") };
int sizeF[] = { 5, 0, 1, 1, 1, 2, 2, 2, 2, 2 };
String nameF[] = { "C", "A", "A", "B", "C", "A", "B", "C", "D", "E" };
int retF[] = { -2, -1, -1, 0, -2, -1, 0, -2, 1, -3 };
int lastRet;
boolean testFind (int i) {
size = sizeF[i];
int ret;
print();
try {
System.out.println("find(" + nameF[i] + ")");
ret = find(nameF[i]);
} catch (Exception e) {
System.out.println(e);
System.out.println("crashed");
return false;
}
System.out.println("returned " + ret);
lastRet = ret;
return ret == retF[i];
}
void testFind () {
theDirectory = dirF;
for (int i = 0; i < nameF.length; i++)
if (testFind(i))
System.out.println("SUCCESS");
else {
if (i == 0 && lastRet == -6) {
System.out.println("find not implemented");
System.out.println("ERROR -20");
totalError += 20;
return;
}
System.out.println("ERROR -2");
totalError += 2;
}
}
int totalError = 0;
void test () {
testRemove();
testAdd();
testFind();
System.out.println("SCORE: " + (60 - totalError));
}
public static void main (String[] args) {
new TestPD().test();
}
}
prog06/prog02/TestUI.class
package prog02;
public synchronized class TestUI implements UserInterface {
int iCase;
int[] cases;
int iInfo;
String[][] info;
public void TestUI();
public void TestUI(String);
public int getCommand(String[]);
public void sendMessage(String);
public String getInfo(String);
public static void main(String[]);
}
prog06/prog02/TestUI.java
prog06/prog02/TestUI.java
package prog02;
import javax.swing.*;
/**
*
* @author vjm
*/
public class TestUI implements UserInterface {
/** Creates a new instance of TestUI */
public TestUI() {
}
/** Creates a new instance of TestUI */
public TestUI(String s) {
}
int iCase = -1;
int[] cases = { 1, 1, 2, 2, 0, 0, 0, 0, 1, 1, 2, 2, 0, 0, 4, 3, 4 };
int iInfo = 0;
String[][] info =
{ { "Fred" }, { "Victor" },
{ "Victor" }, { "Victor" },
{ "Victor", "" },
{ "Fred", "fred" }, { "Fred", "777" },
{ "Victor", null },
{ null }, { "" }, { null }, { "" }, { null }, { "" },
{ },
{ },
{ } };
/** presents set of commands for user to choose one of
@param commands the commands to choose from
@return the index of the command in the array
*/
public int getCommand (String[] commands) {
if (commands.length == 2) {
System.out.println("commands: " + commands[0] + " " + commands[1]);
int i = commands[1].equalsIgnoreCase("yes") ? 0 : 1;
System.out.println("selecting " + commands[i]);
System.out.println("-3 if it does not do a case 3 (save) before exiting");
return i;
}
if (iCase >= 0 && iInfo < info[iCase].length)
System.out.println("ERROR (-3 points): break too soon.");
System.out.println("\t" + "case " + cases[++iCase] + ":");
iInfo = 0;
return cases[iCase];
}
/** tell the user something
@param message string to print out to the user
*/
public void sendMessage (String message) {
if (message == null || message.contains("null"))
System.out.println("ERROR (-3 points): message contains null.");
System.out.println(message);
}
/** prompts the user for a string
@param prompt the request
@return what the user enters, null if nothing
*/
public String getInfo (String prompt) {
System.out.println("\t" + prompt);
if (iInfo == info[iCase].length) {
System.out.println("ERROR (-3 points): missing break.");
return null;
}
String ret = info[iCase][iInfo++];
System.out.println("\t" + "? " + ret);
return ret;
}
public static void main (String[] args) {
UserInterface ui = new TestUI();
String[] commands = { "hello", "how", "are", "you" };
int choice = ui.getCommand(commands);
ui.sendMessage("You chose " + choice);
String result = ui.getInfo("say something");
ui.sendMessage("You said " + result);
}
}
prog06/prog02/UserInterface.class
package prog02;
public abstract interface UserInterface {
public abstract int getCommand(String[]);
public abstract void sendMessage(String);
public abstract String getInfo(String);
}
prog06/prog02/UserInterface.java
prog06/prog02/UserInterface.java
package prog02;
/** A general interface for a user interface
* @author vjm
*/
public interface UserInterface {
/** presents set of commands for user to choose one of
@param commands the commands to choose from
@return the index of the command in the array or -1 if the
user shuts down the program
*/
int getCommand (String[] commands);
/** tell the user something
@param message string to print out to the user
*/
void sendMessage (String message);
/** prompts the user for a string
@param prompt the request
@return what the user enters, empty string if the user enters
nothing, null if the user cancels
*/
String getInfo (String prompt);
}
prog06/prog03/ConstantFib.class
package prog03;
public synchronized class ConstantFib extends PowerFib {
public void ConstantFib();
public double O(int);
protected double pow(double, int);
}
prog06/prog03/ConstantFib.java
prog06/prog03/ConstantFib.java
package prog03;
public class ConstantFib extends PowerFib {
/** The order O() of the implementation.
@param n index
@return the function of n inside the O()
*/
public double O (int n) {
return Math.log(n);
}
/** Raise x to the n'th power
@param x x
@param n n
@return x to the n'th power
*/
protected double pow (double x, int n) {
if (n <= 0)
return 1;
double y = Math.pow(x, n / 2);
if (n % 2 == 0)
return y * y;
else
return x * y * y;
}
}
prog06/prog03/ExponentialFib.class
package prog03;
public synchronized class ExponentialFib extends PowerFib {
public void ExponentialFib();
public double fib(int);
public double O(int);
}
prog06/prog03/ExponentialFib.java
prog06/prog03/ExponentialFib.java
package prog03;
/**
*
* @author vjm
*/
public class ExponentialFib extends PowerFib {
/** The Fibonacci number generator 0, 1, 1, 2, 3, 5, ...
@param n index
@return nth Fibonacci number
*/
public double fib (int n) {
if (n <= 1)
return n;
return fib(n-2) + fib(n-1);
}
/** The order O() of the implementation.
@param n index
@return the function of n inside the O()
*/
public double O (int n) {
double r = (1 + Math.sqrt(5)) / 2;
return Math.pow(r, n);
}
}
prog06/prog03/Fib.class
package prog03;
public abstract interface Fib {
public abstract double fib(int);
public abstract double O(int);
}
prog06/prog03/Fib.java
prog06/prog03/Fib.java
package prog03;
/**
*
* @author vjm
*/
public interface Fib {
/** The Fibonacci number generator 0, 1, 1, 2, 3, 5, ...
@param n index
@return nth Fibonacci number
*/
double fib (int n);
//index starts a t 0
/** The order O() of the implementation.
@param n index
@return the function of n inside the O()
*/
double O (int n);
//tells big o of the fib
}
prog06/prog03/lab.txt
Quick IQ test: what's the next number in this sequence?
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ?
This is the famous Fibonacci sequence.
For this lab, you will create implementations of the Fibonacci
sequences with different running times and test your ability to
predict their running times using the O() analysis you learned in
class.
0. Test prog03.jar.
Try different starting buttons. Each has a different O() time:
O(1), O(log n), O(n) and O(phi^n)
The last one is phi to the n'th power, where
phi = (sqrt(5)+1)/2 = 1.61803399...
**VERIFY** that the percentage error it is calculating is CORRECT.
(Also do this for YOUR program later!)
1. Run Eclipse. Create package prog03 and install the java files I provided.
Implement Main.averageTime(fib, n, ncalls).
Run Main. You should see something like this:
prog03.ExponentialFib@3abfe836
0 0.0
1 1.0
2 1.0
3 2.0
4 3.0
5 5.0
6 8.0
7 13.0
8 21.0
9 34.0
10 55.0
n1 20 time1 31.67975600000006
c 0.002094252405529497
n2 30 estimated time 3896.352411981697
n2 30 actual time 3660.8320700000013
What the program did was use the running time on n=20 to determine the
constant and then estimate the running time for n=30. My run was
pretty accurate, but I think I got lucky. How did you do?
2. I picked 1000 calls for n1 and 100 calls for n2. What numbers
would correspond to one second of total calling time? Don't forget
the times are given in microseconds. So if it takes 50
microseconds, then you can call it 20,000 times in one second,
right? So how many times for the number of microseconds you got?
Modify your program to use these numbers of calls.
3. Using the comments I provided, write Main.accurateTime(fib, n),
which does the same thing automatically.
Modify Main.labExperiments to call this method instead.
4. Add code to estimate how long it would take to compute fib(100).
Would it finish running before end of lab? If not, when will it
finish?
5. Implement LinearFib that computes fib(n) in O(n) time. How? Set
previous=0 and current=1. If you have the previous element and
current element, what is the value of the next element? Set next
equal to that. Now move over one: previous is current and current
is next. Use a loop to do this n times. Which one do you want to
return?
What should the O() method return? 1, log(n), or n?
5. Switch to LinearFib in Main. Test.
HOMEWORK DUE WEDNESDAY AT 11AM
6. Ditto LogFib.
7. Implement ConstantFib, which is just like LogFib only it calls
Math.pow instead of the private pow. Test its running time.
8. Fix getInteger so it does the right thing if the user enters a
negative integer or a non-integer. You will need to use try catch
for the latter. (CSC120 review.) Test using the call from main.
9. Write a method doExperiments(Fib fib) in Main. It should loop
forever (while (true)...).
a. Prompt the user for an integer n using getInteger. If it returns
-1, meaning the user clicked CANCEL, return.
b. Call accurateTime to get the running time for fib(n). Calculate
the constant for the the O().
c. Display n, fib(n) (stored in fibn), the running time, and the
constant for that O() (using sendMessage).
d. Modify main to call doExperiments(new ExponentialFib()) to test it.
10. Modify doExperiments:
a. Save the constant in a variable declared outside the loop,
initially zero. Before calculating the constant, check if it has
been calculated in a previous loop (it is not zero). If so, use
the previous constant to estimate the current running time and
display the estimate. This estimate will appear in a sendMessage
before the sendMessage in 8c.
b. Instead of displaying the new constant in the 8c sendMessage,
display the percentage error between the estimate and the actual
running time.
11. Write a method doExperiments() in Main.
It should give the user the choice of testing one of the five Fib
implementations and then call doExperiments(fib) on that one.
Modify main to call it.
12. MysteryFib inherits ExponentialFib's O() method, but that is
clearly wrong. Try overriding the O() method in MysteryFib with
different functions to figure out which one is best. Leave the
best one in your solution.
prog06/prog03/LinearFib.class
package prog03;
public synchronized class LinearFib implements Fib {
public void LinearFib();
public double fib(int);
public double O(int);
}
prog06/prog03/LinearFib.java
prog06/prog03/LinearFib.java
package prog03;
public class LinearFib implements Fib{
@Override
public double fib(int n) {
// TODO Auto-generated method
double current=0;
double previous=1;
double next=0;
for(int i=0; i
next=previous+current;
previous=current;
current=next;
}
return next;
}
@Override
public double O(int n) {
// TODO Auto-generated method stub
return n ;
}
}
prog06/prog03/LogFib.class
package prog03;
public synchronized class LogFib extends PowerFib {
public void LogFib();
public double O(int);
protected double pow(double, int);
}
prog06/prog03/LogFib.java
prog06/prog03/LogFib.java
package prog03;
/**
*
* @author vjm
*/
public class LogFib extends PowerFib {
/** The order O() of the implementation.
@param n index
@return the function of n inside the O()
*/
public double O (int n) {
return Math.log(n);
}
/** Raise x to the n'th power
@param x x
@param n n
@return x to the n'th power
*/
protected double pow (double x, int n) {
if (n <= 0)
return 1;
double y = pow(x, n / 2);
if (n % 2 == 0)
return y * y;
else
return x * y * y;
}
}
prog06/prog03/Main.class
package prog03;
public synchronized class Main {
public static double fibn;
private static prog02.UserInterface ui;
static void
();
public void Main();
public static double averageTime(Fib, int, double);
public static double accurateTime(Fib, int);
static int getInteger();
public static void doExperiments(Fib);
public static void doExperiments();
static void labExperiments();
public static void main(String[]);
}
prog06/prog03/Main.java
prog06/prog03/Main.java
package prog03;
import prog02.UserInterface;
import prog02.GUI;
/**
*
* @author vjm
*/
public class Main {
/** Use this variable to store the result of each call to fib. */
public static double fibn;
/** Determine the average time in microseconds it takes to calculate
the n'th Fibonacci number.
@param fib an object that implements the Fib interface
@param n the index of the Fibonacci number to calculate
@param ncalls the number of calls to average over
@return the average time per call
*/
public static double averageTime (Fib fib, int n, double ncalls) {
// Get the current time in nanoseconds.
long start = System.nanoTime();
// Call fib(n) ncalls times (needs a loop!).
for (int i=0;i fibn = fib.fib(n);
}
//Get the current time in nanoseconds.
long end = System.nanoTime();
// Return the average time converted to microseconds averaged over ncalls.
return (end - start) / 1000.0 / ncalls;
}
/** Determine the time in microseconds it takes to to calculate the
n'th Fibonacci number. Average over enough calls for a total
time of at least one second.
@param fib an object that implements the Fib interface
@param n the index of the Fibonacci number to calculate
@return the time it it takes to compute the n'th Fibonacci number
*/
public static double accurateTime (Fib fib, int n) {
// Get the time in microseconds using the time method above.
double t = averageTime(fib, n, 1);
// If the time is (equivalent to) more than a second, return it.
if (t>1e6) {
return t;}
// Estimate the number of calls that would add up to one second.
// Use (int)(YOUR EXPESSION) so you can save it into an int variable.
int numcalls = (int)(1e6/t);
// Get the average time using averageTime above and that many
// calls and return it.
return averageTime(fib, n, numcalls);
}
private static UserInterface ui = new GUI("Fibonacci experiments");
/** Get a non-negative integer from the using using ui.
If the user enters a negative integer, like -2, say
"-2 is negative...invalid"
If the user enters a non-integer, like abc, say
"abc is not an integer"
If the user clicks cancel, return -1.
@return the non-negative integer entered by the user or -1 for cancel.
*/
static int getInteger () {
//if user enters negative number or 0 create exception try catch
while(true)
{
String n = ui.getInfo("Enter n");
try {
if(Integer.parseInt(n)<0){
ui.sendMessage("integer cannot be negative");
continue;
}
}
catch(Exception e) {
if (n !=null) {
ui.sendMessage("n must be a integer");
continue;
}
return -1;
}
return Integer.parseInt(n) ;
}
}
public static void doExperiments (Fib fib) {
String[] ans= { "yes",
"no"};
//9A
double co=0;
while (true) {
int num= getInteger();
//return if n is -1
if (num<0)
{
break;
}
if (co!=0) {
double timeEst=co*fib.O(num);
ui.sendMessage("estimated time:"+ timeEst);
if (timeEst>3.6e9) {
ui.sendMessage("time is longer than an hour. do you want to continue");
int a=ui.getCommand(ans);
switch(a){
case 0:
break;
case 1:
continue;
}
}
//9B call accurate time
Double time= accurateTime(fib,num);
double P_error= (timeEst-time)/(time)*100;
co= time /fib.O(num);
ui.sendMessage("constant:"+ co);
//10A
//check if constant isnt zero
//find constant
// estimating the current running time with the previous constant
ui.sendMessage("running time:"+ time );
ui.sendMessage("precent error"+ P_error);
//9C& 10B
ui.sendMessage ("N="+num+ " fib("+num+")="+fibn+" running time="+ time+" microseconds. percent error= "+P_error +"%");
break;
}
else {
Double time= accurateTime(fib,num);
co= time /fib.O(num);
ui.sendMessage ("N="+num+ " fib("+num+")="+fibn+" running time="+ time+" microseconds. constant= "+co +"%");
}
}
}
//11
public static void doExperiments () {
String[] choices = { "ExponentialFib",
"LinearFib",
"LogFib",
"ConstantFib",
"MysteryFib",
"EXIT" };
while (true)
{
int c = ui.getCommand(choices);//presenting menu
switch (c) {
case -1://pressed x
ui.sendMessage("You shut down the program, restarting. Use Exit to exit.");
break;
case 0:
doExperiments(new ExponentialFib());
break;
case 1:
doExperiments(new LinearFib());
break;
case 2:
doExperiments(new LogFib());
break;
case 3:
doExperiments(new ConstantFib());
break;
case 4:
doExperiments(new MysteryFib());
break;
case 5:
String[] options = {"no",
"yes"};
ui.sendMessage("Do you really want to exit? press ok to continue.");
int d=ui.getCommand(options);
switch (d) {
case 0:
break;
case 1:
return;
}
}
}
}
static void labExperiments () {
// Create (Exponential time) Fib object and test it.
Fib efib = new ExponentialFib();
System.out.println(efib);
for (int i = 0; i < 11; i++)
System.out.println(i + " " + efib.fib(i));
// Determine running time for n1 = 20 and print it out.
int n1 = 20;
double time1 = averageTime(efib, n1, 1000);
System.out.println("n1 " + n1 + " time1 " + time1);
//quizz
//c=time/oc?
//time1/o(20)=o(n)
// if linfib = time1/20
//time=c*O(n)
// Calculate constant: time = constant times O(n).
double c = time1 / efib.O(n1);
System.out.println("c " + c);
// Estimate running time for n2=30.
int n2 = 30;
double time2est = c * efib.O(n2);
System.out.println("n2 " + n2 + " estimated time " + time2est);
// Calculate actual running time for n2=30.
double time2 = averageTime(efib, n2, 100);
System.out.println("n2 " + n2 + " actual time " + time2);
///step 2= calculate average time for 1 second
double ncalls=(1e6/time2);
//print out what ncall is
System.out.println("ncall is"+ ncalls);
time2=averageTime(efib,n2,ncalls);
//print out time2
System.out.println("n2 " + n2 + " actual time " + time2);
///step #3: test your accurateTime() method//call accurate time
time2=accurateTime(efib,n2);
//step4: estimate fib(100)
int n3=100;
double time3est=c*efib.O(n3);
System.out.println("n3 " + n3 + " estimated time " + time3est);
//convert time3est from microseconds to years
int years=(int)(time3est/3.154e+13);
System.out.println("which is"+ Math.round(years)+"years");
}
/**
* @param args the command line arguments
*/
public static void main (String[] args) {
//9DTEST
doExperiments();
}
}
prog06/prog03/main.txt
jmin220 Joanna Minott
UI 0:ExponentialFib
UI 1:LinearFib
UI 2:LogFib
UI 3:ConstantFib
UI 4:MysteryFib
UI 5:EXIT
UI command 0
UI Enter n
UI ?
UI n must be a integer
UI Enter n
UI ? abc
UI n must be a integer
UI Enter n
UI ? 10
UI N=10 fib(10)=55.0 running time=0.28160108945743445 microseconds. constant= 0.0022895910995916406%
UI Enter n
UI ? 10
UI estimated time:0.28160108945743445
UI constant:0.0019391169576901202
UI running time:0.238495619575179
UI precent error18.07390423314155
UI N=10 fib(10)=55.0 running time=0.238495619575179 microseconds. percent error= 18.07390423314155%
UI 0:ExponentialFib
UI 1:LinearFib
UI 2:LogFib
UI 3:ConstantFib
UI 4:MysteryFib
UI 5:EXIT
ERROR (-5 points): break too soon.
UI command 1
UI Enter n
UI ? 100
UI N=100 fib(100)=3.54224848179262E20 running time=0.1183664790662064 microseconds. constant= 0.0011836647906620639%
UI Enter n
UI ? 100
UI estimated time:0.11836647906620638
UI constant:5.814918252602315E-4
UI running time:0.058149182526023156
UI precent error103.55656592976959
UI N=100 fib(100)=3.54224848179262E20 running time=0.058149182526023156 microseconds. percent error= 103.55656592976959%
UI 0:ExponentialFib
UI 1:LinearFib
UI 2:LogFib
UI 3:ConstantFib
UI 4:MysteryFib
UI 5:EXIT
ERROR (-5 points): break too soon.
UI command 2
UI Enter n
UI ? 100
UI N=100 fib(100)=3.5422484817926226E20 running time=0.21844017646611394 microseconds. constant= 0.04743368163260293%
UI Enter n
UI ? 100
UI estimated time:0.21844017646611397
UI constant:0.013935621554830366
UI running time:0.06417590890751781
UI precent error240.37722283123762
UI N=100 fib(100)=3.5422484817926226E20 running time=0.06417590890751781 microseconds. percent error= 240.37722283123762%
UI 0:ExponentialFib
UI 1:LinearFib
UI 2:LogFib
UI 3:ConstantFib
UI 4:MysteryFib
UI 5:EXIT
ERROR (-5 points): break too soon.
UI command 3
UI Enter n
UI ? 100
UI N=100 fib(100)=3.542248481792631E20 running time=0.1379507957768673 microseconds. constant= 0.02995563469002794%
UI Enter n
UI ? 100
UI estimated time:0.1379507957768673
UI constant:0.012577147743654633
UI running time:0.057919905813845714
UI precent error138.1751037721651
UI N=100 fib(100)=3.542248481792631E20 running time=0.057919905813845714 microseconds. percent error= 138.1751037721651%
UI 0:ExponentialFib
UI 1:LinearFib
UI 2:LogFib
UI 3:ConstantFib
UI 4:MysteryFib
UI 5:EXIT
ERROR (-5 points): break too soon.
UI command 4
UI Enter n
UI ? 100
UI N=100 fib(100)=3.54224848179263E20 running time=1.1135850369311413 microseconds. constant= 0.011135850369311412%
UI Enter n
UI ? 100
UI estimated time:1.1135850369311413
UI constant:0.0026261618671774376
UI running time:0.2626161867177438
UI precent error324.0351864251258
UI N=100 fib(100)=3.54224848179263E20 running time=0.2626161867177438 microseconds. percent error= 324.0351864251258%
UI 0:ExponentialFib
UI 1:LinearFib
UI 2:LogFib
UI 3:ConstantFib
UI 4:MysteryFib
UI 5:EXIT
ERROR (-5 points): break too soon.
UI command 0
UI Enter n
UI ? 10
UI N=10 fib(10)=55.0 running time=0.2297862060573789 microseconds. constant= 0.0018683040367904217%
UI Enter n
UI ? 20
UI estimated time:28.261835041020824
UI constant:0.0017737717608295425
UI running time:26.831845308809847
UI precent error5.329449822601134
UI N=20 fib(20)=6765.0 running time=26.831845308809847 microseconds. percent error= 5.329449822601134%
UI 0:ExponentialFib
UI 1:LinearFib
UI 2:LogFib
UI 3:ConstantFib
UI 4:MysteryFib
UI 5:EXIT
ERROR (-5 points): break too soon.
UI command 5
UI Do you really want to exit? press ok to continue.
UI 0:no
UI 1:yes
UI command 0
UI 0:ExponentialFib
UI 1:LinearFib
UI 2:LogFib
UI 3:ConstantFib
UI 4:MysteryFib
UI 5:EXIT
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 7
at prog02.GUI.getCommand(GUI.java:83)
at prog03.Main.doExperiments(Main.java:174)
at prog03.Main.main(Main.java:274)
A 10/10 handles bad inputs
B 10/10 correctly calculates percentages
C 5/10 ExponentialFib accuracy
D 5/10 LinearFib accuracy
E 5/10 LogFib accuracy
F 0/10 ConstantFib accuracy (Not O(1).)
G 10/10 MysteryFib accuracy
H 5/5 Ask if I want to run fib(100).
Only letting me do two numbers for each fib???
SCORE: 50
prog06/prog03/MysteryFib.class
package prog03;
public synchronized class MysteryFib extends PowerFib {
private double[] save;
public void MysteryFib();
public double fib(int);
public double O(int);
}
prog06/prog03/MysteryFib.java
prog06/prog03/MysteryFib.java
package prog03;
/**
*
* @author vjm
*/
public class MysteryFib extends PowerFib {
private double[] save;
/** The Fibonacci number generator 0, 1, 1, 2, 3, 5, ...
@param n index
@return nth Fibonacci number
*/
public double fib (int n) {
if (save == null) {
save = new double[n+1];
for (int i = 0; i < save.length; i++)
save[i] = -1;
double f = fib(n);
save = null;
return f;
}
if (save[n] == -1)
save[n] = super.fib(n);
return save[n];
}
public double O(int n) {
// TODO Auto-generated method stub
return n ;
}
}
prog06/prog03/perfect-Main.txt
UI Main calls getCommand with choices
UI 0:ExponentialFib
UI 1:LinearFib
UI 2:LogFib
UI 3:ConstantFib
UI 4:MysteryFib
UI 5:EXIT
UI getCommand returns 0
doExperiments prog03.ExponentialFib@2aaf7cc2
UI Main calls getInfo("Enter n")
UI getInfo returns ""
UI Main calls sendMessage(" is not an integer.")
UI Main calls getInfo("Enter n")
UI getInfo returns "abc"
UI Main calls sendMessage("abc is not an integer.")
UI Main calls getInfo("Enter n")
UI getInfo returns "-10"
UI Main calls sendMessage("-10 is negative...invalid")
UI Main calls getInfo("Enter n")
UI getInfo returns "10"
UI Main calls sendMessage("fib(10) = 55.0 in 0.292252282043333 microseconds.")
UI Main calls getInfo("Enter n")
UI getInfo returns "10"
UI Main calls sendMessage("Estimated time on input 10 is 0.292252282043333 microseconds.")
UI Main calls sendMessage("fib(10) = 55.0 in 0.2403948044404042 microseconds. 21.57179633047546% error.")
UI Main calls getInfo("Enter n")
UI getInfo returns "10"
UI Main calls sendMessage("Estimated time on input 10 is 0.2403948044404042 microseconds.")
UI Main calls sendMessage("fib(10) = 55.0 in 0.237258458886619 microseconds. 1.3219109525127586% error.")
UI Main calls getInfo("Enter n")
UI getInfo returns "20"
UI Main calls sendMessage("Estimated time on input 20 is 29.180861384978357 microseconds.")
UI Main calls sendMessage("fib(20) = 6765.0 in 27.394535630530626 microseconds. 6.520737487723313% error.")
UI Main calls getInfo("Enter n")
UI getInfo returns "30"
UI Main calls sendMessage("Estimated time on input 30 is 3369.305148030065 microseconds.")
UI Main calls sendMessage("fib(30) = 832040.0 in 3391.660737113402 microseconds. -0.6591340000109601% error.")
UI Main calls getInfo("Enter n")
UI getInfo returns "40"
UI Main calls sendMessage("Estimated time on input 40 is 417146.6943645461 microseconds.")
UI Main calls sendMessage("fib(40) = 1.02334155E8 in 411796.749 microseconds. 1.2991713454605462% error.")
UI Main calls getInfo("Enter n")
UI getInfo returns null
UI Main calls getCommand with choices
UI 0:ExponentialFib
UI 1:LinearFib
UI 2:LogFib
UI 3:ConstantFib
UI 4:MysteryFib
UI 5:EXIT
UI getCommand returns 1
doExperiments prog03.LinearFib@22f71333
UI Main calls getInfo("Enter n")
UI getInfo returns "100"
UI Main calls sendMessage("fib(100) = 3.54224848179262E20 in 0.2590352355808286 microseconds.")
UI Main calls getInfo("Enter n")
UI getInfo returns "100"
UI Main calls sendMessage("Estimated time on input 100 is 0.2590352355808286 microseconds.")
UI Main calls sendMessage("fib(100) = 3.54224848179262E20 in 0.05411768595706248 microseconds. 378.6517217058205% error.")
UI Main calls getInfo("Enter n")
UI getInfo returns "100"
UI Main calls sendMessage("Estimated time on input 100 is 0.05411768595706247 microseconds.")
UI Main calls sendMessage("fib(100) = 3.54224848179262E20 in 0.058210964433501725 microseconds. -7.031799792829889% error.")
UI Main calls getInfo("Enter n")
UI getInfo returns "200"
UI Main calls sendMessage("Estimated time on input 200 is 0.11642192886700345 microseconds.")
UI Main calls sendMessage("fib(200) = 2.8057117299251016E41 in 0.17832621945009144 microseconds. -34.71407108499448% error.")
UI Main calls getInfo("Enter n")
UI getInfo returns "400"
UI Main calls sendMessage("Estimated time on input 400 is 0.3566524389001829 microseconds.")
UI Main calls sendMessage("fib(400) = 1.760236806450138E83 in 0.4151852624012124 microseconds. -14.098001254309114% error.")
UI Main calls getInfo("Enter n")
UI getInfo returns "800"
UI Main calls sendMessage("Estimated time on input 800 is 0.8303705248024249 microseconds.")
UI Main calls sendMessage("fib(800) = 6.928308186422468E166 in 0.8848943952676607 microseconds. -6.161624568629291% error.")
UI Main calls getInfo("Enter n")
UI getInfo returns null
UI Main calls getCommand with choices
UI 0:ExponentialFib
UI 1:LinearFib
UI 2:LogFib
UI 3:ConstantFib
UI 4:MysteryFib
UI 5:EXIT
UI getCommand returns 2
doExperiments prog03.LogFib@6aaa5eb0
UI Main calls getInfo("Enter n")
UI getInfo returns "100"
UI Main calls sendMessage("fib(100) = 3.5422484817926226E20 in 0.11463964891634794 microseconds.")
UI Main calls getInfo("Enter n")
UI getInfo returns "100"
UI Main calls sendMessage("Estimated time on input 100 is 0.11463964891634795 microseconds.")
UI Main calls sendMessage("fib(100) = 3.5422484817926226E20 in 0.04230329427218362 microseconds. 170.99461374980632% error.")
UI Main calls getInfo("Enter n")
UI getInfo returns "100"
UI Main calls sendMessage("Estimated time on input 100 is 0.04230329427218362 microseconds.")
UI Main calls sendMessage("fib(100) = 3.5422484817926226E20 in 0.035501984926068694 microseconds. 19.15754671260875% error.")
UI Main calls getInfo("Enter n")
UI getInfo returns "1000"
UI Main calls sendMessage("Estimated time on input 1000 is 0.053252977389103034 microseconds.")
UI Main calls sendMessage("fib(1000) = 4.3466557686937765E208 in 0.045874236109967215 microseconds. 16.0847174903314% error.")
UI Main calls getInfo("Enter n")
UI getInfo returns "10000"
UI Main calls sendMessage("Estimated time on input 10000 is 0.06116564814662296 microseconds.")
UI Main calls sendMessage("fib(10000) = Infinity in 0.06340824186906374 microseconds. -3.536754302495369% error.")
UI Main calls getInfo("Enter n")
UI getInfo returns "100000"
UI Main calls sendMessage("Estimated time on input 100000 is 0.07926030233632966 microseconds.")
UI Main calls sendMessage("fib(100000) = Infinity in 0.13131012250427146 microseconds. -39.63884822836003% error.")
UI Main calls getInfo("Enter n")
UI getInfo returns null
UI Main calls getCommand with choices
UI 0:ExponentialFib
UI 1:LinearFib
UI 2:LogFib
UI 3:ConstantFib
UI 4:MysteryFib
UI 5:EXIT
UI getCommand returns 3
doExperiments prog03.ConstantFib@1a407d53
UI Main calls getInfo("Enter n")
UI getInfo returns "100"
UI Main calls sendMessage("fib(100) = 3.542248481792631E20 in 0.11468448750149503 microseconds.")
UI Main calls getInfo("Enter n")
UI getInfo returns "100"
UI Main calls sendMessage("Estimated time on input 100 is 0.11468448750149503 microseconds.")
UI Main calls sendMessage("fib(100) = 3.542248481792631E20 in 0.054438870961153546 microseconds. 110.66654299890148% error.")
UI Main calls getInfo("Enter n")
UI getInfo returns "100"
UI Main calls sendMessage("Estimated time on input 100 is 0.054438870961153546 microseconds.")
UI Main calls sendMessage("fib(100) = 3.542248481792631E20 in 0.05288922404897067 microseconds. 2.9299860983931976% error.")
UI Main calls getInfo("Enter n")
UI getInfo returns "1000"
UI Main calls sendMessage("Estimated time on input 1000 is 0.05288922404897067 microseconds.")
UI Main calls sendMessage("fib(1000) = 4.3466557686938915E208 in 0.0655909046492713 microseconds. -19.365002919565214% error.")
UI Main calls getInfo("Enter n")
UI getInfo returns "10000"
UI Main calls sendMessage("Estimated time on input 10000 is 0.0655909046492713 microseconds.")
UI Main calls sendMessage("fib(10000) = Infinity in 0.051777746613776904 microseconds. 26.677789086748355% error.")
UI Main calls getInfo("Enter n")
UI getInfo returns "100000"
UI Main calls sendMessage("Estimated time on input 100000 is 0.051777746613776904 microseconds.")
UI Main calls sendMessage("fib(100000) = Infinity in 0.0514684052868967 microseconds. 0.6010314971988381% error.")
UI Main calls getInfo("Enter n")
UI getInfo returns null
UI Main calls getCommand with choices
UI 0:ExponentialFib
UI 1:LinearFib
UI 2:LogFib
UI 3:ConstantFib
UI 4:MysteryFib
UI 5:EXIT
UI getCommand returns 4
doExperiments prog03.MysteryFib@5ebec15
UI Main calls getInfo("Enter n")
UI getInfo returns "100"
UI Main calls sendMessage("fib(100) = 3.54224848179262E20 in 1.7544097781382146 microseconds.")
UI Main calls getInfo("Enter n")
UI getInfo returns "100"
UI Main calls sendMessage("Estimated time on input 100 is 1.7544097781382149 microseconds.")
UI Main calls sendMessage("fib(100) = 3.54224848179262E20 in 0.8359635752004101 microseconds. 109.86677292938519% error.")
UI Main calls getInfo("Enter n")
UI getInfo returns "100"
UI Main calls sendMessage("Estimated time on input 100 is 0.83596357520041 microseconds.")
UI Main calls sendMessage("fib(100) = 3.54224848179262E20 in 0.6389079165039582 microseconds. 30.842575840149415% error.")
UI Main calls getInfo("Enter n")
UI getInfo returns "200"
UI Main calls sendMessage("Estimated time on input 200 is 1.2778158330079163 microseconds.")
UI Main calls sendMessage("fib(200) = 2.8057117299251016E41 in 1.2703540271808125 microseconds. 0.587380026941247% error.")
UI Main calls getInfo("Enter n")
UI getInfo returns "500"
UI Main calls sendMessage("Estimated time on input 500 is 3.175885067952031 microseconds.")
UI Main calls sendMessage("fib(500) = 1.394232245616977E104 in 2.9515786688814645 microseconds. 7.599539915213247% error.")
UI Main calls getInfo("Enter n")
UI getInfo returns "1000"
UI Main calls sendMessage("Estimated time on input 1000 is 5.903157337762929 microseconds.")
UI Main calls sendMessage("fib(1000) = 4.346655768693743E208 in 7.503395767049384 microseconds. -21.326856252388897% error.")
UI Main calls getInfo("Enter n")
UI getInfo returns null
UI Main calls getCommand with choices
UI 0:ExponentialFib
UI 1:LinearFib
UI 2:LogFib
UI 3:ConstantFib
UI 4:MysteryFib
UI 5:EXIT
UI getCommand returns 0
doExperiments prog03.ExponentialFib@21bcffb5
UI Main calls getInfo("Enter n")
UI getInfo returns "10"
UI Main calls sendMessage("fib(10) = 55.0 in 0.31893424199855724 microseconds.")
UI Main calls getInfo("Enter n")
UI getInfo returns "20"
UI Main calls sendMessage("Estimated time on input 20 is 39.2263186330927 microseconds.")
UI Main calls sendMessage("fib(20) = 6765.0 in 40.81318204507084 microseconds. -3.888114899312997% error.")
UI Main calls getInfo("Enter n")
UI getInfo returns "30"
UI Main calls sendMessage("Estimated time on input 30 is 5019.689555120296 microseconds.")
UI Main calls sendMessage("fib(30) = 832040.0 in 4867.487159722222 microseconds. 3.1269192995007336% error.")
UI Main calls getInfo("Enter n")
UI getInfo returns "40"
UI Main calls sendMessage("Estimated time on input 40 is 598661.344963439 microseconds.")
UI Main calls sendMessage("fib(40) = 1.02334155E8 in 597169.379 microseconds. 0.24983966290057963% error.")
UI Main calls getInfo("Enter n")
UI getInfo returns "100"
UI Main calls sendMessage("Estimated time on input 100 is 2.06707362379236454E18 microseconds.")
UI Main calls sendMessage("Estimated time is more than an hour.
I will ask you if you really want to run it.")
UI Main calls getCommand with choices
UI 0:yes
UI 1:no
UI getCommand returns 1
UI Main calls getInfo("Enter n")
UI getInfo returns null
UI Main calls getCommand with choices
UI 0:ExponentialFib
UI 1:LinearFib
UI 2:LogFib
UI 3:ConstantFib
UI 4:MysteryFib
UI 5:EXIT
UI getCommand returns 5
prog06/prog03/PowerFib.class
package prog03;
public synchronized class PowerFib implements Fib {
protected double sqrt5;
protected double g1;
protected double g2;
public void PowerFib();
public double fib(int);
public double O(int);
protected double pow(double, int);
}
prog06/prog03/PowerFib.java
prog06/prog03/PowerFib.java
package prog03;
/**
*
* @author vjm
*/
public class PowerFib implements Fib {
/** The Fibonacci number generator 0, 1, 1, 2, 3, 5, ...
@param n index
@return nth Fibonacci number
*/
public double fib (int n) {
return (pow(g1, n) - pow(g2, n)) / sqrt5;
}
/** The order O() of the implementation.
@param n index
@return the function of n inside the O()
*/
public double O (int n) {
return n;
}
protected double sqrt5 = Math.sqrt(5);
protected double g1 = (1 + sqrt5) / 2;
protected double g2 = (1 - sqrt5) / 2;
/** Raise x to the n'th power
@param x x
@param n n
@return x to the n'th power
*/
protected double pow (double x, int n) {
double y = 1;
for (int i = 0; i < n; i++)
y *= x;
return y;
}
}
prog06/prog03/prog03.jar
META-INF/MANIFEST.MF
Manifest-Version: 1.0
Class-Path: .
Main-Class: prog03.Main
prog01/Lamb.class
package prog01;
public synchronized class Lamb {
String[] array;
int size;
public void Lamb();
void insert(String, int);
void print();
public static void main(String[]);
}
prog01/Main.class
package prog01;
public synchronized class Main {
public void Main();
public static void main(String[]);
}
prog01/Laptop.class
package prog01;
public synchronized class Laptop extends Computer {
private double screenSize;
private double weight;
public void Laptop(String, String, double, int, double, double, double);
public String toString();
public double getScreenSize();
public double getWeight();
public double computePower();
}
prog01/Computer.class
package prog01;
public synchronized class Computer {
private String manufacturer;
private String processor;
private double ramSize;
private int diskSize;
private double processorSpeed;
public void Computer(String, String, double, int, double);
public double getRamSize();
public double getProcessorSpeed();
public int getDiskSize();
public String toString();
public double computePower();
}
prog01/images/18.01.17.14.21.16/0.png
prog01/images/18.01.17.14.21.16/1.png
prog01/images/18.01.17.14.21.16/2.png
prog01/images/18.01.17.14.21.16/3.png
prog01/images/18.01.17.14.21.16/4.png
prog01/images/18.01.17.14.58.41/0.png
prog01/images/18.01.17.14.58.41/1.png
prog02/Main.class
package prog02;
public synchronized class Main {
public void Main();
public static void processCommands(String, UserInterface, PhoneDirectory);
public static void main(String[]);
}
prog02/ArrayBasedPD.class
package prog02;
public synchronized class ArrayBasedPD implements PhoneDirectory {
protected static final int INITIAL_CAPACITY = 100;
protected int size;
protected DirectoryEntry[] theDirectory;
protected String sourceName;
protected boolean modified;
public void ArrayBasedPD();
public void loadData(String);
public String addOrChangeEntry(String, String);
public String lookupEntry(String);
public void save();
protected FindOutput find(String);
protected void reallocate();
public String removeEntry(String);
}
prog02/ConsoleUI.class
package prog02;
public synchronized class ConsoleUI implements UserInterface {
private java.util.Scanner scIn;
public void ConsoleUI();
public int getCommand(String[]);
public void sendMessage(String);
public String getInfo(String);
public static void main(String[]);
}
prog02/DirectoryEntry.class
package prog02;
public synchronized class DirectoryEntry {
private String name;
private String number;
public void DirectoryEntry(String, String);
public String getName();
public String getNumber();
public void setNumber(String);
}
prog02/FindOutput.class
package prog02;
public synchronized class FindOutput {
public final boolean found;
public final int index;
void FindOutput(boolean, int);
}
prog02/GUI.class
package prog02;
public synchronized class GUI implements UserInterface {
public void GUI();
public int getCommand(String[]);
public void sendMessage(String);
public String getInfo(String);
public static void main(String[]);
}
prog02/PhoneDirectory.class
package prog02;
public abstract interface PhoneDirectory {
public abstract void loadData(String);
public abstract String lookupEntry(String);
public abstract String addOrChangeEntry(String, String);
public abstract String removeEntry(String);
public abstract void save();
}
prog02/SortedPD.class
package prog02;
public synchronized class SortedPD extends ArrayBasedPD {
public void SortedPD();
}
prog02/UserInterface.class
package prog02;
public abstract interface UserInterface {
public abstract int getCommand(String[]);
public abstract void sendMessage(String);
public abstract String getInfo(String);
}
prog03/ConstantFib.class
package prog03;
public synchronized class ConstantFib extends PowerFib {
public void ConstantFib();
public double o(int);
protected double pow(double, int);
}
prog03/Fib.class
package prog03;
public abstract interface Fib {
public abstract double fib(int);
public abstract double o(int);
}
prog03/LogFib.class
package prog03;
public synchronized class LogFib extends PowerFib {
public void LogFib();
public double o(int);
protected double pow(double, int);
}
prog03/MysteryFib.class
package prog03;
public synchronized class MysteryFib extends ExponentialFib {
private double[] save;
public void MysteryFib();
public double fib(int);
public double o(int);
}
prog03/Main.class
package prog03;
public synchronized class Main {
public static double fibn;
private static prog02.UserInterface ui;
static void ();
public void Main();
public static double time(Fib, int);
public static double averageTime(Fib, int, int);
public static double accurateTime(Fib, int);
public static void doExperiments(Fib);
public static void doExperiments();
static void labExperiments();
static void toasterSimulation();
public static void main(String[]);
}
prog03/LinearFib.class
package prog03;
public synchronized class LinearFib implements Fib {
public void LinearFib();
public double fib(int);
public double o(int);
}
prog03/PowerFib.class
package prog03;
public synchronized class PowerFib implements Fib {
protected double sqrt5;
protected double g1;
protected double g2;
public void PowerFib();
public double fib(int);
public double o(int);
protected double pow(double, int);
}
prog03/ExponentialFib.class
package prog03;
public synchronized class ExponentialFib extends PowerFib {
public void ExponentialFib();
public double fib(int);
public double o(int);
}
prog03/Main.java~
package prog03;
import prog02.UserInterface;
import prog02.GUI;
/**
*
* @author vjm
*/
public class Main {
/** Use this variable to store the result of each call to fib. */
public static double fibn;
/** Determine the time in microseconds it takes to calculate the
n'th Fibonacci number.
@param fib an object that implements the Fib interface
@param n the index of the Fibonacci number to calculate
@return the time for the call to fib(n)
*/
public static double time (Fib fib, int n) {
// Get the current time in nanoseconds.
long start = System.nanoTime();
// Calculate the n'th Fibonacci number. Store the
// result in fibn.
fibn = fib.fib(n);
// Get the current time in nanoseconds.
long end = System.nanoTime();
// System.out.println("start " + start + " end " + end);
// Return the difference between the end time and the
// start time divided by 1000.0 to convert to microseconds.
return (end - start) / 1000.0;
}
/** Determine the average time in microseconds it takes to calculate
the n'th Fibonacci number.
@param fib an object that implements the Fib interface
@param n the index of the Fibonacci number to calculate
@param ncalls the number of calls to average over
@return the average time per call
*/
public static double averageTime (Fib fib, int n, long ncalls) {
double totalTime = 0;
// Add up the total call time for ncalls calls to time (above).
// Use long for the counter.
for (long counter = 0; counter < ncalls; counter++)
totalTime += time(fib, n);
// Return the average time.
return totalTime / ncalls;
}
/** Determine the time in microseconds it takes to to calculate
the n'th Fibonacci number ACCURATE TO THREE SIGNIFICANT FIGURES.
@param fib an object that implements the Fib interface
@param n the index of the Fibonacci number to calculate
@return the time it it takes to compute the n'th Fibonacci number
*/
public static double accurateTime (Fib fib, int n) {
// Get the time using the time method above.
double t = time(fib, n);
// Since it is not very accurate, it might be zero. If so set it to 0.1
if (t == 0)
t = 1;
// Calculate the number of calls to average over that will give
// three figures of accuracy. You will need to "cast" it to int
// by putting (int) in front of the formula.
int ncalls = (int) (1e6 / (t * t));
// Make sure ncalls is at least 1.
if (ncalls == 0)
ncalls = 1;
// Get the accurate time using averageTime.
return averageTime(fib, n, ncalls);
}
private static UserInterface ui = new GUI();
public static void doExperiments (Fib fib) {
double c = 0;
while (true) {
String sn = ui.getInfo("Enter n");
if (sn == null)
return;
int n = 0;
boolean nIsOK = true;
try {
n = Integer.parseInt(sn);
if (n < 0) {
ui.sendMessage(n + " is negative...invalid.");
nIsOK = false;
}
} catch (Exception e) {
ui.sendMessage(sn + " is not an integer.");
nIsOK = false;
}
if (nIsOK) {
int choice = 0;
if (c != 0) {
double estTime = c * fib.o(n);
ui.sendMessage("Estimated time on input " + n + " is " +
estTime + " microseconds.");
if (estTime > 1000000.0 * 60 * 60) {
ui.sendMessage("Estimated time is more than an hour.\n" +
"I will ask you if you really want to run it.");
String choices[] = { "yes", "no" };
choice = ui.getCommand(choices);
}
}
if (choice == 0) {
double fn = fib.fib(n);
double newTime = accurateTime(fib, n);
// double newTime = time(fib, n);
c = newTime / fib.o(n);
ui.sendMessage("fib(" + n + ") = " + fn + " in " +
newTime + " microseconds.");
}
}
}
}
public static void doExperiments () {
String[] choices =
{ "ExponentialFib", "LinearFib", "LogFib", "ConstantFib" };
int choice = ui.getCommand(choices);
switch (choice) {
case 0:
doExperiments(new ExponentialFib());
break;
case 1:
doExperiments(new LinearFib());
break;
case 2:
doExperiments(new LogFib());
break;
case 3:
doExperiments(new ConstantFib());
break;
}
}
static void labExperiments () {
// Create (Exponential time) Fib object and test it.
Fib efib = new ExponentialFib();
System.out.println(efib);
for (int i = 0; i < 11; i++)
System.out.println(i + " " + efib.fib(i));
// Determine running time for n1 = 20 and print it out.
int n1 = 20;
double time1 = averageTime(efib, n1, 1000);
System.out.println("n1 " + n1 + " time1 " + time1);
int ncalls = (int) (1e6 / (time1 * time1));
System.out.println("ncalls " + ncalls);
time1 = averageTime(efib, n1, ncalls);
System.out.println("ncalls " + ncalls + " n1 " + n1 + " time1 " + time1);
time1 = accurateTime(efib, n1);
System.out.println("accurate time: n1 " + n1 + " time1 " + time1);
// Calculate constant: time = constant times O(n).
double c = time1 / efib.o(n1);
System.out.println("c " + c);
// Estimate running time for n2=30.
int n2 = 30;
double time2est = c * efib.o(n2);
System.out.println("n2 " + n2 + " estimated time " + time2est);
// Calculate actual running time for n2=30.
double time2 = averageTime(efib, n2, 100);
System.out.println("n2 " + n2 + " actual time " + time2);
time2 = averageTime(efib, n2, 100);
System.out.println("n2 " + n2 + " actual time " + time2);
ncalls = (int) (1e6 / (time2 * time2));
System.out.println("ncalls " + ncalls);
if (ncalls == 0)
ncalls = 1;
time2 = averageTime(efib, n2, ncalls);
System.out.println("ncalls " + ncalls + " n2 " + n2 + " time2 " + time2);
time2 = accurateTime(efib, n2);
System.out.println("accurate time: n2 " + n2 + " time2 " + time2);
int n3 = 100;
double time3est = c * efib.o(n3);
System.out.println("n3 " + n3 + " estimated time " + time3est);
double years = time3est / 1e6 / 3600 / 24 / 365.25;
System.out.println("which is " + years + " years.");
}
static void toasterSimulation () {
double i3 = 1.0 / 3;
double total = 0;
long ntimes = 0;
for (long p = 1; p <= 1000000000; p *= 10) {
while (ntimes < p) {
if (Math.random() > i3)
total += 2;
else
total += 3;
ntimes++;
}
double mean = (double) total / ntimes;
System.out.println(ntimes + " " + mean);
}
}
/**
* @param args the command line arguments
*/
public static void main (String[] args) {
doExperiments();
// labExperiments();
}
}
prog03/MysteryFib.java~
package prog03;
/**
*
* @author vjm
*/
public class MysteryFib extends ExponentialFib {
private int[] save;
/** The Fibonacci number generator 0, 1, 1, 2, 3, 5, ...
@param n index
@return nth Fibonacci number
*/
public double fib (int n) {
if (save == null || save.length <= n) {
save = new int[n+1];
for (int i = 0; i < save.length; i++)
save[i] = -1;
}
if (save[n] == -1)
save[n] = super.fib(n);
return save[n];
}
/** The order O() of the implementation.
@param n index
@return the function of n inside the O()
*/
public double o (int n) {
double r = (1 + Math.sqrt(5)) / 2;
return Math.pow(r, n);
}
}
prog03/lab.txt
Quick IQ test: what's the next number in this sequence?
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ?
This is the famous Fibonacci sequence.
For this lab, you will create implementations of the Fibonacci
sequences with different running times and test your ability to
predict their running times using the O() analysis you learned in
class.
0. Test prog03.jar.
Try different starting buttons. Each has a different O() time:
O(1), O(log n), O(n) and O(phi^n)
The last one is phi to the n'th power, where
phi = (sqrt(5)+1)/2 = 1.61803399...
1. Run Eclipse. Create package prog03 and install the java files I provided.
Implement Main.time(fib, n) and Main.averageTime(fib, n, ncalls).
Run Main. You should see something like this:
prog03.ExponentialFib@7ac260c5
0 0.0
1 1.0
2 1.0
3 2.0
4 3.0
5 5.0
6 8.0
7 13.0
8 21.0
9 34.0
10 55.0
n1 20 time1 94.46656500000046
c 0.006244897561501395
n2 30 estimated time 11618.619423374877
n2 30 actual time 10657.382309999997
What the program did was use the running time on n=20 to determine the
constant and then estimate the running time for n=30. It's close but
has only one digit of accuracy.
2. I picked 1000 calls for n1 and 100 calls for n2. What numbers
would correspond to one second of total calling time? Modify your
program to use these numbers of calls.
3. Using the comments I provided, write Main.accurateTime(fib, n),
which does the same thing automatically.
Modify Main.labExperiments to call this method instead.
4. Add code to estimate how long it would take to compute fib(100).
Would it finish running before end of lab? If not, when will it
finish?
5. Implement LinearFib that computes fib(n) in O(n) time. How? Set
a=0 and b=1. What do you have to do to make a=1 and b=1? a=1 and
b=2? a=2 and b=3? a=3 and b=5? a=5 and b=8?
What should the o() method return?
5. Switch to LinearFib in Main.
6. Ditto LogFib.
7. Implement ConstantFib, which is just like LogFib only it calls
Math.pow instead of the private pow. Test its running time.
HOMEWORK DUE WEDNESDAY AT 11AM
8. Write a method doExperiments(Fib fib) in Main. It should loop
forever until the user clicks CANCEL.
a. Prompt the user for an integer. To use a class or interface from
prog02, just put, for example,
import prog02.GUI;
at the top of Main.java. Convert the string to an integer n using
what you learned in CSC120.
b. Call accurateTime to get the running time for fib(n). Calculate
the constant for the the o().
c. Display n, fib(n) (stored in fibn), the running time, and the
constant for that o() (using sendMessage).
d. Modify main to call doExperiments(new LinearFib()) to test it.
9. Modify doExperiments:
a. If the user enters blank, a non-integer, or a negative integer,
give a warning and ask again until the user provides a positive
integer or selects CANCEL.
b. Store the constant in a variable declared outside the loop,
initially zero. Before calculating the constant, check if it has
been calculated in a previous loop (it is not zero). If so, use
the previous constant to estimate the current running time and
display the estimate. This estimate will appear in a sendMessage
before the sendMessage in 8c.
c. Instead of displaying the new constant in the 8c sendMessage,
display the percentage error between the estimate and the actual
running time.
10. Write a method doExperiments() in Main.
It should give the user the choice of testing one of the five Fib
implementations and then call doExperiments(fib) on that one.
11. MysteryFib inherits ExponentialFib's o() method, but that is
clearly wrong. Try overriding the o() method in MysteryFib with
different functions to figure out which one is best. Leave the
best one in your solution.
prog03/lab.txt~
Quick IQ test: what's the next number in this sequence?
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ?
This is the famous Fibonacci sequence.
For this lab, you will create implementations of the Fibonacci
sequences with different running times and test your ability to
predict their running times using the O() analysis you learned in
class.
0. Test prog03.jar.
Try different starting buttons. Each has a different O() time:
O(1), O(log n), O(n) and O(phi^n)
The last one is phi to the n'th power, where
phi = (sqrt(5)+1)/2 = 1.61803399...
1. Run Eclipse. Create package prog03 and install the java files I provided.
Implement Main.callTime(fib, n) and Main.averageTime(fib, n, ncalls).
Run Main. You should see something like this:
prog03.ExponentialFib@7ac260c5
0 0.0
1 1.0
2 1.0
3 2.0
4 3.0
5 5.0
6 8.0
7 13.0
8 21.0
9 34.0
10 55.0
n1 20 time1 94.46656500000046
c 0.006244897561501395
n2 30 estimated time 11618.619423374877
n2 30 actual time 10657.382309999997
What the program did was use the running time on n=20 to determine the
constant and then estimate the running time for n=30. It's close but
has only one digit of accuracy.
2. I picked 1000 calls for n1 and 100 calls for n2. We learned a
formula in class for the right number of calls to get three figures
of accuracy. How many calls should I have used for n1? For n2?
Modify your program to use these numbers of calls.
3. Using the comments I provided, write Main.accurateTime(fib, n),
which does the same thing automatically.
Modify Main.labExperiments to call this method instead.
4. Add code to estimate how long it would take to compute fib(100).
Would it finish running before end of lab? If not, when will it
finish?
5. Implement LinearFib which computes fib(n) in O(n) time. How? Set
a=0 and b=1. What do you have to do to make a=1 and b=1? a=1 and
b=2? a=2 and b=3?
What should the o() method return?
5. Switch to LinearFib in Main.
6. Ditto LogFib.
7. Implement ConstantFib, which is just like LogFib only it calls
Math.pow instead of the private pow. Test its running time.
FOR HOMEWORK
8. Write a method doExperiments(Fib fib) in Main.
It should repeatedly prompt the user for n using GUI.java and stop
when the user enters a blank.
For each n, it should call accurateTime(fib, n) to get a good time for
n, and figure out the new constant.
If this is not the first n, it should use the constant from the
previous n to estimate the time for the current n. It should display
the value of n, fib(n), estimated time, actual time, and new constant.
To use a class or interface from prog02, just put, for example,
import prog02.GUI;
at the top of Main.java.
9. Write a method doExperiments() in Main.
It should give the user the choice of testing one of the four Fib
implementations and then call doExperiments(fib) on that one.
prog06/prog03/test.txt
UI 0:ExponentialFib
UI 1:LinearFib
UI 2:LogFib
UI 3:ConstantFib
UI 4:MysteryFib
UI 5:EXIT
UI command 0
doExperiments prog03.ExponentialFib@2aaf7cc2
UI Enter n
UI ?
UI is not an integer.
UI Enter n
UI ? abc
UI abc is not an integer.
UI Enter n
UI ? 10
UI fib(10) = 55.0 in 0.3286978970764779 microseconds.
UI Enter n
UI ? 10
UI Estimated time on input 10 is 0.3286978970764779 microseconds.
UI fib(10) = 55.0 in 0.2819715033157001 microseconds. 16.5713177435743% error.
UI Enter n
UI ? 10
UI Estimated time on input 10 is 0.2819715033157001 microseconds.
UI fib(10) = 55.0 in 0.2760587938317509 microseconds. 2.141829789908009% error.
UI Enter n
UI ? 20
UI Estimated time on input 20 is 33.95298711249855 microseconds.
UI fib(20) = 6765.0 in 30.170761364653522 microseconds. 12.536063316837877% error.
UI Enter n
UI ? 30
UI Estimated time on input 30 is 3710.7583408941573 microseconds.
UI fib(30) = 832040.0 in 3776.832126436782 microseconds. -1.7494498916201846% error.
UI Enter n
UI ? 40
UI Estimated time on input 40 is 464519.64356959966 microseconds.
UI fib(40) = 1.02334155E8 in 448060.392 microseconds. 3.673444889009442% error.
UI Enter n
UI ? null
UI 0:ExponentialFib
UI 1:LinearFib
UI 2:LogFib
UI 3:ConstantFib
UI 4:MysteryFib
UI 5:EXIT
UI command 1
doExperiments prog03.LinearFib@6fadae5d
UI Enter n
UI ? 100
UI fib(100) = 3.54224848179262E20 in 0.23873717526050423 microseconds.
UI Enter n
UI ? 100
UI Estimated time on input 100 is 0.23873717526050423 microseconds.
UI fib(100) = 3.54224848179262E20 in 0.1470277027051659 microseconds. 62.375641370961894% error.
UI Enter n
UI ? 100
UI Estimated time on input 100 is 0.1470277027051659 microseconds.
UI fib(100) = 3.54224848179262E20 in 0.14838617504856547 microseconds. -0.9154979181550723% error.
UI Enter n
UI ? 200
UI Estimated time on input 200 is 0.29677235009713093 microseconds.
UI fib(200) = 2.8057117299251016E41 in 0.2768903992039067 microseconds. 7.180440690752465% error.
UI Enter n
UI ? 400
UI Estimated time on input 400 is 0.5537807984078134 microseconds.
UI fib(400) = 1.760236806450138E83 in 0.536229425129554 microseconds. 3.2731089447429995% error.
UI Enter n
UI ? 800
UI Estimated time on input 800 is 1.072458850259108 microseconds.
UI fib(800) = 6.928308186422468E166 in 1.090977258140076 microseconds. -1.6974146567031807% error.
UI Enter n
UI ? null
UI 0:ExponentialFib
UI 1:LinearFib
UI 2:LogFib
UI 3:ConstantFib
UI 4:MysteryFib
UI 5:EXIT
UI command 2
doExperiments prog03.LogFib@2d6e8792
UI Enter n
UI ? 100
UI fib(100) = 3.5422484817926226E20 in 0.12653699720372577 microseconds.
UI Enter n
UI ? 100
UI Estimated time on input 100 is 0.12653699720372577 microseconds.
UI fib(100) = 3.5422484817926226E20 in 0.07654741462697624 microseconds. 65.3053833631797% error.
UI Enter n
UI ? 100
UI Estimated time on input 100 is 0.07654741462697624 microseconds.
UI fib(100) = 3.5422484817926226E20 in 0.0743908415524443 microseconds. 2.898976580351759% error.
UI Enter n
UI ? 1000
UI Estimated time on input 1000 is 0.11158626232866643 microseconds.
UI fib(1000) = 4.3466557686937765E208 in 0.09336254331218151 microseconds. 19.51930439121529% error.
UI Enter n
UI ? 10000
UI Estimated time on input 10000 is 0.12448339108290869 microseconds.
UI fib(10000) = Infinity in 0.11238325835986891 microseconds. 10.766846325360355% error.
UI Enter n
UI ? 100000
UI Estimated time on input 100000 is 0.14047907294983614 microseconds.
UI fib(100000) = Infinity in 0.17426493703266388 microseconds. -19.387643124385363% error.
UI Enter n
UI ? null
UI 0:ExponentialFib
UI 1:LinearFib
UI 2:LogFib
UI 3:ConstantFib
UI 4:MysteryFib
UI 5:EXIT
UI command 3
doExperiments prog03.ConstantFib@2acf57e3
UI Enter n
UI ? 100
UI fib(100) = 3.542248481792631E20 in 0.13179278435894834 microseconds.
UI Enter n
UI ? 100
UI Estimated time on input 100 is 0.13179278435894834 microseconds.
UI fib(100) = 3.542248481792631E20 in 0.10043620191556464 microseconds. 31.220398467222758% error.
UI Enter n
UI ? 100
UI Estimated time on input 100 is 0.10043620191556464 microseconds.
UI fib(100) = 3.542248481792631E20 in 0.09902929065720266 microseconds. 1.4207021468346275% error.
UI Enter n
UI ? 1000
UI Estimated time on input 1000 is 0.09902929065720266 microseconds.
UI fib(1000) = 4.3466557686938915E208 in 0.12068541637361203 microseconds. -17.94427725166676% error.
UI Enter n
UI ? 10000
UI Estimated time on input 10000 is 0.12068541637361203 microseconds.
UI fib(10000) = Infinity in 0.099276070458736 microseconds. 21.565464684437533% error.
UI Enter n
UI ? 100000
UI Estimated time on input 100000 is 0.099276070458736 microseconds.
UI fib(100000) = Infinity in 0.08161698066914047 microseconds. 21.636538922190812% error.
UI Enter n
UI ? null
UI 0:ExponentialFib
UI 1:LinearFib
UI 2:LogFib
UI 3:ConstantFib
UI 4:MysteryFib
UI 5:EXIT
UI command 4
doExperiments prog03.MysteryFib@96532d6
UI Enter n
UI ? 100
UI fib(100) = 3.54224848179262E20 in 1.5975494532804166 microseconds.
UI Enter n
UI ? 100
UI Estimated time on input 100 is 1.5975494532804164 microseconds.
UI fib(100) = 3.54224848179262E20 in 1.1799046227732592 microseconds. 35.39649073715134% error.
UI Enter n
UI ? 100
UI Estimated time on input 100 is 1.1799046227732592 microseconds.
UI fib(100) = 3.54224848179262E20 in 0.6885447700469907 microseconds. 71.36207754402595% error.
UI Enter n
UI ? 200
UI Estimated time on input 200 is 1.3770895400939813 microseconds.
UI fib(200) = 2.8057117299251016E41 in 1.3411713915839336 microseconds. 2.6781177063155295% error.
UI Enter n
UI ? 500
UI Estimated time on input 500 is 3.352928478959834 microseconds.
UI fib(500) = 1.394232245616977E104 in 3.1806174231669506 microseconds. 5.417534801193181% error.
UI Enter n
UI ? 1000
UI Estimated time on input 1000 is 6.361234846333901 microseconds.
UI fib(1000) = 4.346655768693743E208 in 8.695107030357567 microseconds. -26.841212832404786% error.
UI Enter n
UI ? null
UI 0:ExponentialFib
UI 1:LinearFib
UI 2:LogFib
UI 3:ConstantFib
UI 4:MysteryFib
UI 5:EXIT
UI command 0
doExperiments prog03.ExponentialFib@3796751b
UI Enter n
UI ? 10
UI fib(10) = 55.0 in 0.4044369127966038 microseconds.
UI Enter n
UI ? 20
UI Estimated time on input 20 is 49.74245195163357 microseconds.
UI fib(20) = 6765.0 in 43.674147280999755 microseconds. 13.894500633499039% error.
UI Enter n
UI ? 30
UI Estimated time on input 30 is 5371.565017721947 microseconds.
UI fib(30) = 832040.0 in 5361.375461988301 microseconds. 0.1900548806157811% error.
UI Enter n
UI ? 40
UI Estimated time on input 40 is 659405.5905246731 microseconds.
UI fib(40) = 1.02334155E8 in 650765.695 microseconds. 1.327650733751902% error.
UI Enter n
UI ? 100
UI Estimated time on input 100 is 2.25259474230912742E18 microseconds.
UI Estimated time is more than an hour.
I will ask you if you really want to run it.
UI 0:yes
UI 1:no
UI command 1
UI Enter n
UI ? null
UI 0:ExponentialFib
UI 1:LinearFib
UI 2:LogFib
UI 3:ConstantFib
UI 4:MysteryFib
UI 5:EXIT
UI command 5
prog06/prog03/TestUI.class
package prog03;
public synchronized class TestUI implements prog02.UserInterface {
int iCase;
int[] cases;
int iInfo;
String[][] info;
public void TestUI();
public void TestUI(String);
public int getCommand(String[]);
public void sendMessage(String);
public String getInfo(String);
void error(int, String);
public static void main(String[]);
}
prog06/prog03/TestUI.java
prog06/prog03/TestUI.java
package prog03;
import javax.swing.*;
import prog02.UserInterface;
/**
*
* @author vjm
*/
public class TestUI implements UserInterface {
/** Creates a new instance of TestUI */
public TestUI() {
}
/** Creates a new instance of TestUI */
public TestUI(String title) {
}
int iCase = -1;
int[] cases = { 0, 1, 2, 3, 4, 0, 5 };
int iInfo = 0;
String[][] info =
{ { "", "abc", "-10", "10", "10", "10", "20", "30", "40", null },
{ "100", "100", "100", "200", "400", "800", null },
{ "100", "100", "100", "1000", "10000", "100000", null },
{ "100", "100", "100", "1000", "10000", "100000", null },
{ "100", "100", "100", "200", "500", "1000", null },
{ "10", "20", "30", "40", "100", null },
{ }, };
/** presents set of commands for user to choose one of
@param commands the commands to choose from
@return the index of the command in the array
*/
public int getCommand (String[] commands) {
System.out.println("UI Main calls getCommand with choices");
for (int i = 0; i < commands.length; i++)
System.out.println("UI " + i + ":" + commands[i]);
if (commands.length == 2) {
if (commands[0].toLowerCase().indexOf("no") != -1) {
System.out.println("UI " + "getCommand returns 0");
return 0;
}
if (commands[1].toLowerCase().indexOf("no") != -1) {
System.out.println("UI " + "getCommand returns 1");
return 1;
}
error(-5, "could not find yes or no");
System.out.println("UI " + "getCommand returns 1");
return 1;
}
String[] choices = { "ExponentialFib", "LinearFib", "LogFib", "ConstantFib", "MysteryFib", "EXIT" };
if (commands.length != choices.length) {
System.out.print("UI Choices should be: ");
for (int i = 0; i < choices.length; i++)
System.out.print(" " + choices[i]);
System.out.println();
System.out.print("UI Instead of: ");
for (int i = 0; i < commands.length; i++)
System.out.print(" " + commands[i]);
System.out.println();
System.out.println("UI " + "getCommand returns " + (commands.length-1));
return commands.length-1;
}
for (int j = 0; j < choices.length; j++)
if (!commands[j].equalsIgnoreCase(choices[j])) {
System.out.print("UI Choices should be: ");
for (int i = 0; i < choices.length; i++)
System.out.print(" " + choices[i]);
System.out.println();
System.out.print("UI Instead of: ");
for (int i = 0; i < commands.length; i++)
System.out.print(" " + commands[i]);
System.out.println();
System.exit(-1);
}
if (iCase >= 0 && iInfo < info[iCase].length)
error(-5, "break too soon");
System.out.println("UI " + "getCommand returns " + cases[++iCase]);
iInfo = 0;
return cases[iCase];
}
/** tell the user something
@param message string to print out to the user
*/
public void sendMessage (String message) {
if (message == null || message.contains("null"))
error(-5, "message contains null");
System.out.println("UI Main calls sendMessage(\"" + message + "\")");
}
/** prompts the user for a string
@param prompt the request
@return what the user enters, null if nothing
*/
public String getInfo (String prompt) {
System.out.println("UI Main calls getInfo(\"" + prompt + "\")");
if (!prompt.equals("Enter n")) {
System.out.println("Prompt was not \"Enter n\"");
System.exit(-1);
}
if (iInfo == info[iCase].length) {
error(-5, "missing break");
return null;
}
String ret = info[iCase][iInfo++];
if (ret != null)
System.out.println("UI getInfo returns \"" + ret + "\"");
else
System.out.println("UI getInfo returns null");
return ret;
}
void error (int off, String mess) {
System.out.println("ERROR (" + off + " points): " + mess + ".");
}
public static void main (String[] args) {
UserInterface ui = new TestUI();
String[] commands = { "hello", "how", "are", "you" };
int choice = ui.getCommand(commands);
ui.sendMessage("You chose " + choice);
String result = ui.getInfo("say something");
ui.sendMessage("You said " + result);
}
}
prog06/prog03/Timing.pdf
Measuring and Predicting Running Time
Victor Milenkovic
Department of Computer Science
University of Miami
CSC220 Programming II – Spring 2020
Outline
Running times of different implementations
I We have two implementations of PhoneDirectory: ArrayBasedPD and
SortedPD.
I Each has implementations of find, add, and remove.
I Can we compare their speeds?
Running times of different implementations
I We have two implementations of PhoneDirectory: ArrayBasedPD and
SortedPD.
I Each has implementations of find, add, and remove.
I Can we compare their speeds?
Running times of different implementations
I We have two implementations of PhoneDirectory: ArrayBasedPD and
SortedPD.
I Each has implementations of find, add, and remove.
I Can we compare their speeds?
Running times of different implementations
I We have two implementations of PhoneDirectory: ArrayBasedPD and
SortedPD.
I Each has implementations of find, add, and remove.
I Can we compare their speeds?
find
I ArrayBasedPD.find
I Jay, Bob, Zoe, Ian, Ann, Eve
I Look for Vic?
I Have to compare Vic with n entries, where n = size, which is 6.
I SortedPD.find
I Only really helpful when n (size) is large.
I Requires log2 n comparisons
find
I ArrayBasedPD.find
I Jay, Bob, Zoe, Ian, Ann, Eve
I Look for Vic?
I Have to compare Vic with n entries, where n = size, which is 6.
I SortedPD.find
I Only really helpful when n (size) is large.
I Requires log2 n comparisons
find
I ArrayBasedPD.find
I Jay, Bob, Zoe, Ian, Ann, Eve
I Look for Vic?
I Have to compare Vic with n entries, where n = size, which is 6.
I SortedPD.find
I Only really helpful when n (size) is large.
I Requires log2 n comparisons
find
I ArrayBasedPD.find
I Jay, Bob, Zoe, Ian, Ann, Eve
I Look for Vic?
I Have to compare Vic with n entries, where n = size, which is 6.
I SortedPD.find
I Only really helpful when n (size) is large.
I Requires log2 n comparisons
find
I ArrayBasedPD.find
I Jay, Bob, Zoe, Ian, Ann, Eve
I Look for Vic?
I Have to compare Vic with n entries, where n = size, which is 6.
I SortedPD.find
I Only really helpful when n (size) is large.
I Requires log2 n comparisons
find
I ArrayBasedPD.find
I Jay, Bob, Zoe, Ian, Ann, Eve
I Look for Vic?
I Have to compare Vic with n entries, where n = size, which is 6.
I SortedPD.find
I Only really helpful when n (size) is large.
I Requires log2 n comparisons
find
I ArrayBasedPD.find
I Jay, Bob, Zoe, Ian, Ann, Eve
I Look for Vic?
I Have to compare Vic with n entries, where n = size, which is 6.
I SortedPD.find
I Only really helpful when n (size) is large.
I Requires log2 n comparisons
find
I ArrayBasedPD.find
I Jay, Bob, Zoe, Ian, Ann, Eve
I Look for Vic?
I Have to compare Vic with n entries, where n = size, which is 6.
I SortedPD.find
I Only really helpful when n (size) is large.
I Requires log2 n comparisons
addOrChangeEntry
I ArrayBasedPD.addOrChangeEntry
I Jay, Bob, Zoe, Ian, Ann, Eve
I Add Vic?
I Has to call find and wait for find to finish (to make sure Vic isn’t there
already).
I If you call addOrChangeEntry, you don’t care how it does it, you just care
how long it takes. No excuses, addOrChangeEntry!
I find uses n comparisons
I Then it calls add, which only takes 1 array access to add Vic to end of array.
I Jay, Bob, Zoe, Ian, Ann, Eve, Vic
I Unless array is full, and then we need to allocate a bigger one, and copy
everything over first.
I So n array access (actually 2n) when array is full, but let’s not worry about
that now.
I Total time is n comparisons to find plus 1 array access to add or change.
I SortedPD.addOrChangeEntry
I Also has to call find and wait for find to finish.
I find uses log2 n comparisons
I Ann, Bob, Eve, Ian, Jay, Zoe
I Let’s add Abe.
I Abe, Ann, Bob, Eve, Ian, Jay, Zoe
I add uses n array accesses. Actually n − 1 reads and n writes, where n is 7.
So 2n − 1.
I Total time is log2 n comparisons (find) plus 2n − 1 array accesses (add).
addOrChangeEntry
I ArrayBasedPD.addOrChangeEntry
I Jay, Bob, Zoe, Ian, Ann, Eve
I Add Vic?
I Has to call find and wait for find to finish (to make sure Vic isn’t there
already).
I If you call addOrChangeEntry, you don’t care how it does it, you just care
how long it takes. No excuses, addOrChangeEntry!
I find uses n comparisons
I Then it calls add, which only takes 1 array access to add Vic to end of array.
I Jay, Bob, Zoe, Ian, Ann, Eve, Vic
I Unless array is full, and then we need to allocate a bigger one, and copy
everything over first.
I So n array access (actually 2n) when array is full, but let’s not worry about
that now.
I Total time is n comparisons to find plus 1 array access to add or change.
I SortedPD.addOrChangeEntry
I Also has to call find and wait for find to finish.
I find uses log2 n comparisons
I Ann, Bob, Eve, Ian, Jay, Zoe
I Let’s add Abe.
I Abe, Ann, Bob, Eve, Ian, Jay, Zoe
I add uses n array accesses. Actually n − 1 reads and n writes, where n is 7.
So 2n − 1.
I Total time is log2 n comparisons (find) plus 2n − 1 array accesses (add).
addOrChangeEntry
I ArrayBasedPD.addOrChangeEntry
I Jay, Bob, Zoe, Ian, Ann, Eve
I Add Vic?
I Has to call find and wait for find to finish (to make sure Vic isn’t there
already).
I If you call addOrChangeEntry, you don’t care how it does it, you just care
how long it takes. No excuses, addOrChangeEntry!
I find uses n comparisons
I Then it calls add, which only takes 1 array access to add Vic to end of array.
I Jay, Bob, Zoe, Ian, Ann, Eve, Vic
I Unless array is full, and then we need to allocate a bigger one, and copy
everything over first.
I So n array access (actually 2n) when array is full, but let’s not worry about
that now.
I Total time is n comparisons to find plus 1 array access to add or change.
I SortedPD.addOrChangeEntry
I Also has to call find and wait for find to finish.
I find uses log2 n comparisons
I Ann, Bob, Eve, Ian, Jay, Zoe
I Let’s add Abe.
I Abe, Ann, Bob, Eve, Ian, Jay, Zoe
I add uses n array accesses. Actually n − 1 reads and n writes, where n is 7.
So 2n − 1.
I Total time is log2 n comparisons (find) plus 2n − 1 array accesses (add).
addOrChangeEntry
I ArrayBasedPD.addOrChangeEntry
I Jay, Bob, Zoe, Ian, Ann, Eve
I Add Vic?
I Has to call find and wait for find to finish (to make sure Vic isn’t there
already).
I If you call addOrChangeEntry, you don’t care how it does it, you just care
how long it takes. No excuses, addOrChangeEntry!
I find uses n comparisons
I Then it calls add, which only takes 1 array access to add Vic to end of array.
I Jay, Bob, Zoe, Ian, Ann, Eve, Vic
I Unless array is full, and then we need to allocate a bigger one, and copy
everything over first.
I So n array access (actually 2n) when array is full, but let’s not worry about
that now.
I Total time is n comparisons to find plus 1 array access to add or change.
I SortedPD.addOrChangeEntry
I Also has to call find and wait for find to finish.
I find uses log2 n comparisons
I Ann, Bob, Eve, Ian, Jay, Zoe
I Let’s add Abe.
I Abe, Ann, Bob, Eve, Ian, Jay, Zoe
I add uses n array accesses. Actually n − 1 reads and n writes, where n is 7.
So 2n − 1.
I Total time is log2 n comparisons (find) plus 2n − 1 array accesses (add).
addOrChangeEntry
I ArrayBasedPD.addOrChangeEntry
I Jay, Bob, Zoe, Ian, Ann, Eve
I Add Vic?
I Has to call find and wait for find to finish (to make sure Vic isn’t there
already).
I If you call addOrChangeEntry, you don’t care how it does it, you just care
how long it takes. No excuses, addOrChangeEntry!
I find uses n comparisons
I Then it calls add, which only takes 1 array access to add Vic to end of array.
I Jay, Bob, Zoe, Ian, Ann, Eve, Vic
I Unless array is full, and then we need to allocate a bigger one, and copy
everything over first.
I So n array access (actually 2n) when array is full, but let’s not worry about
that now.
I Total time is n comparisons to find plus 1 array access to add or change.
I SortedPD.addOrChangeEntry
I Also has to call find and wait for find to finish.
I find uses log2 n comparisons
I Ann, Bob, Eve, Ian, Jay, Zoe
I Let’s add Abe.
I Abe, Ann, Bob, Eve, Ian, Jay, Zoe
I add uses n array accesses. Actually n − 1 reads and n writes, where n is 7.
So 2n − 1.
I Total time is log2 n comparisons (find) plus 2n − 1 array accesses (add).
addOrChangeEntry
I ArrayBasedPD.addOrChangeEntry
I Jay, Bob, Zoe, Ian, Ann, Eve
I Add Vic?
I Has to call find and wait for find to finish (to make sure Vic isn’t there
already).
I If you call addOrChangeEntry, you don’t care how it does it, you just care
how long it takes. No excuses, addOrChangeEntry!
I find uses n comparisons
I Then it calls add, which only takes 1 array access to add Vic to end of array.
I Jay, Bob, Zoe, Ian, Ann, Eve, Vic
I Unless array is full, and then we need to allocate a bigger one, and copy
everything over first.
I So n array access (actually 2n) when array is full, but let’s not worry about
that now.
I Total time is n comparisons to find plus 1 array access to add or change.
I SortedPD.addOrChangeEntry
I Also has to call find and wait for find to finish.
I find uses log2 n comparisons
I Ann, Bob, Eve, Ian, Jay, Zoe
I Let’s add Abe.
I Abe, Ann, Bob, Eve, Ian, Jay, Zoe
I add uses n array accesses. Actually n − 1 reads and n writes, where n is 7.
So 2n − 1.
I Total time is log2 n comparisons (find) plus 2n − 1 array accesses (add).
addOrChangeEntry
I ArrayBasedPD.addOrChangeEntry
I Jay, Bob, Zoe, Ian, Ann, Eve
I Add Vic?
I Has to call find and wait for find to finish (to make sure Vic isn’t there
already).
I If you call addOrChangeEntry, you don’t care how it does it, you just care
how long it takes. No excuses, addOrChangeEntry!
I find uses n comparisons
I Then it calls add, which only takes 1 array access to add Vic to end of array.
I Jay, Bob, Zoe, Ian, Ann, Eve, Vic
I Unless array is full, and then we need to allocate a bigger one, and copy
everything over first.
I So n array access (actually 2n) when array is full, but let’s not worry about
that now.
I Total time is n comparisons to find plus 1 array access to add or change.
I SortedPD.addOrChangeEntry
I Also has to call find and wait for find to finish.
I find uses log2 n comparisons
I Ann, Bob, Eve, Ian, Jay, Zoe
I Let’s add Abe.
I Abe, Ann, Bob, Eve, Ian, Jay, Zoe
I add uses n array accesses. Actually n − 1 reads and n writes, where n is 7.
So 2n − 1.
I Total time is log2 n comparisons (find) plus 2n − 1 array accesses (add).
addOrChangeEntry
I ArrayBasedPD.addOrChangeEntry
I Jay, Bob, Zoe, Ian, Ann, Eve
I Add Vic?
I Has to call find and wait for find to finish (to make sure Vic isn’t there
already).
I If you call addOrChangeEntry, you don’t care how it does it, you just care
how long it takes. No excuses, addOrChangeEntry!
I find uses n comparisons
I Then it calls add, which only takes 1 array access to add Vic to end of array.
I Jay, Bob, Zoe, Ian, Ann, Eve, Vic
I Unless array is full, and then we need to allocate a bigger one, and copy
everything over first.
I So n array access (actually 2n) when array is full, but let’s not worry about
that now.
I Total time is n comparisons to find plus 1 array access to add or change.
I SortedPD.addOrChangeEntry
I Also has to call find and wait for find to finish.
I find uses log2 n comparisons
I Ann, Bob, Eve, Ian, Jay, Zoe
I Let’s add Abe.
I Abe, Ann, Bob, Eve, Ian, Jay, Zoe
I add uses n array accesses. Actually n − 1 reads and n writes, where n is 7.
So 2n − 1.
I Total time is log2 n comparisons (find) plus 2n − 1 array accesses (add).
addOrChangeEntry
I ArrayBasedPD.addOrChangeEntry
I Jay, Bob, Zoe, Ian, Ann, Eve
I Add Vic?
I Has to call find and wait for find to finish (to make sure Vic isn’t there
already).
I If you call addOrChangeEntry, you don’t care how it does it, you just care
how long it takes. No excuses, addOrChangeEntry!
I find uses n comparisons
I Then it calls add, which only takes 1 array access to add Vic to end of array.
I Jay, Bob, Zoe, Ian, Ann, Eve, Vic
I Unless array is full, and then we need to allocate a bigger one, and copy
everything over first.
I So n array access (actually 2n) when array is full, but let’s not worry about
that now.
I Total time is n comparisons to find plus 1 array access to add or change.
I SortedPD.addOrChangeEntry
I Also has to call find and wait for find to finish.
I find uses log2 n comparisons
I Ann, Bob, Eve, Ian, Jay, Zoe
I Let’s add Abe.
I Abe, Ann, Bob, Eve, Ian, Jay, Zoe
I add uses n array accesses. Actually n − 1 reads and n writes, where n is 7.
So 2n − 1.
I Total time is log2 n comparisons (find) plus 2n − 1 array accesses (add).
addOrChangeEntry
I ArrayBasedPD.addOrChangeEntry
I Jay, Bob, Zoe, Ian, Ann, Eve
I Add Vic?
I Has to call find and wait for find to finish (to make sure Vic isn’t there
already).
I If you call addOrChangeEntry, you don’t care how it does it, you just care
how long it takes. No excuses, addOrChangeEntry!
I find uses n comparisons
I Then it calls add, which only takes 1 array access to add Vic to end of array.
I Jay, Bob, Zoe, Ian, Ann, Eve, Vic
I Unless array is full, and then we need to allocate a bigger one, and copy
everything over first.
I So n array access (actually 2n) when array is full, but let’s not worry about
that now.
I Total time is n comparisons to find plus 1 array access to add or change.
I SortedPD.addOrChangeEntry
I Also has to call find and wait for find to finish.
I find uses log2 n comparisons
I Ann, Bob, Eve, Ian, Jay, Zoe
I Let’s add Abe.
I Abe, Ann, Bob, Eve, Ian, Jay, Zoe
I add uses n array accesses. Actually n − 1 reads and n writes, where n is 7.
So 2n − 1.
I Total time is log2 n comparisons (find) plus 2n − 1 array accesses (add).
addOrChangeEntry
I ArrayBasedPD.addOrChangeEntry
I Jay, Bob, Zoe, Ian, Ann, Eve
I Add Vic?
I Has to call find and wait for find to finish (to make sure Vic isn’t there
already).
I If you call addOrChangeEntry, you don’t care how it does it, you just care
how long it takes. No excuses, addOrChangeEntry!
I find uses n comparisons
I Then it calls add, which only takes 1 array access to add Vic to end of array.
I Jay, Bob, Zoe, Ian, Ann, Eve, Vic
I Unless array is full, and then we need to allocate a bigger one, and copy
everything over first.
I So n array access (actually 2n) when array is full, but let’s not worry about
that now.
I Total time is n comparisons to find plus 1 array access to add or change.
I SortedPD.addOrChangeEntry
I Also has to call find and wait for find to finish.
I find uses log2 n comparisons
I Ann, Bob, Eve, Ian, Jay, Zoe
I Let’s add Abe.
I Abe, Ann, Bob, Eve, Ian, Jay, Zoe
I add uses n array accesses. Actually n − 1 reads and n writes, where n is 7.
So 2n − 1.
I Total time is log2 n comparisons (find) plus 2n − 1 array accesses (add).
addOrChangeEntry
I ArrayBasedPD.addOrChangeEntry
I Jay, Bob, Zoe, Ian, Ann, Eve
I Add Vic?
I Has to call find and wait for find to finish (to make sure Vic isn’t there
already).
I If you call addOrChangeEntry, you don’t care how it does it, you just care
how long it takes. No excuses, addOrChangeEntry!
I find uses n comparisons
I Then it calls add, which only takes 1 array access to add Vic to end of array.
I Jay, Bob, Zoe, Ian, Ann, Eve, Vic
I Unless array is full, and then we need to allocate a bigger one, and copy
everything over first.
I So n array access (actually 2n) when array is full, but let’s not worry about
that now.
I Total time is n comparisons to find plus 1 array access to add or change.
I SortedPD.addOrChangeEntry
I Also has to call find and wait for find to finish.
I find uses log2 n comparisons
I Ann, Bob, Eve, Ian, Jay, Zoe
I Let’s add Abe.
I Abe, Ann, Bob, Eve, Ian, Jay, Zoe
I add uses n array accesses. Actually n − 1 reads and n writes, where n is 7.
So 2n − 1.
I Total time is log2 n comparisons (find) plus 2n − 1 array accesses (add).
addOrChangeEntry
I ArrayBasedPD.addOrChangeEntry
I Jay, Bob, Zoe, Ian, Ann, Eve
I Add Vic?
I Has to call find and wait for find to finish (to make sure Vic isn’t there
already).
I If you call addOrChangeEntry, you don’t care how it does it, you just care
how long it takes. No excuses, addOrChangeEntry!
I find uses n comparisons
I Then it calls add, which only takes 1 array access to add Vic to end of array.
I Jay, Bob, Zoe, Ian, Ann, Eve, Vic
I Unless array is full, and then we need to allocate a bigger one, and copy
everything over first.
I So n array access (actually 2n) when array is full, but let’s not worry about
that now.
I Total time is n comparisons to find plus 1 array access to add or change.
I SortedPD.addOrChangeEntry
I Also has to call find and wait for find to finish.
I find uses log2 n comparisons
I Ann, Bob, Eve, Ian, Jay, Zoe
I Let’s add Abe.
I Abe, Ann, Bob, Eve, Ian, Jay, Zoe
I add uses n array accesses. Actually n − 1 reads and n writes, where n is 7.
So 2n − 1.
I Total time is log2 n comparisons (find) plus 2n − 1 array accesses (add).
addOrChangeEntry
I ArrayBasedPD.addOrChangeEntry
I Jay, Bob, Zoe, Ian, Ann, Eve
I Add Vic?
I Has to call find and wait for find to finish (to make sure Vic isn’t there
already).
I If you call addOrChangeEntry, you don’t care how it does it, you just care
how long it takes. No excuses, addOrChangeEntry!
I find uses n comparisons
I Then it calls add, which only takes 1 array access to add Vic to end of array.
I Jay, Bob, Zoe, Ian, Ann, Eve, Vic
I Unless array is full, and then we need to allocate a bigger one, and copy
everything over first.
I So n array access (actually 2n) when array is full, but let’s not worry about
that now.
I Total time is n comparisons to find plus 1 array access to add or change.
I SortedPD.addOrChangeEntry
I Also has to call find and wait for find to finish.
I find uses log2 n comparisons
I Ann, Bob, Eve, Ian, Jay, Zoe
I Let’s add Abe.
I Abe, Ann, Bob, Eve, Ian, Jay, Zoe
I add uses n array accesses. Actually n − 1 reads and n writes, where n is 7.
So 2n − 1.
I Total time is log2 n comparisons (find) plus 2n − 1 array accesses (add).
addOrChangeEntry
I ArrayBasedPD.addOrChangeEntry
I Jay, Bob, Zoe, Ian, Ann, Eve
I Add Vic?
I Has to call find and wait for find to finish (to make sure Vic isn’t there
already).
I If you call addOrChangeEntry, you don’t care how it does it, you just care
how long it takes. No excuses, addOrChangeEntry!
I find uses n comparisons
I Then it calls add, which only takes 1 array access to add Vic to end of array.
I Jay, Bob, Zoe, Ian, Ann, Eve, Vic
I Unless array is full, and then we need to allocate a bigger one, and copy
everything over first.
I So n array access (actually 2n) when array is full, but let’s not worry about
that now.
I Total time is n comparisons to find plus 1 array access to add or change.
I SortedPD.addOrChangeEntry
I Also has to call find and wait for find to finish.
I find uses log2 n comparisons
I Ann, Bob, Eve, Ian, Jay, Zoe
I Let’s add Abe.
I Abe, Ann, Bob, Eve, Ian, Jay, Zoe
I add uses n array accesses. Actually n − 1 reads and n writes, where n is 7.
So 2n − 1.
I Total time is log2 n comparisons (find) plus 2n − 1 array accesses (add).
addOrChangeEntry
I ArrayBasedPD.addOrChangeEntry
I Jay, Bob, Zoe, Ian, Ann, Eve
I Add Vic?
I Has to call find and wait for find to finish (to make sure Vic isn’t there
already).
I If you call addOrChangeEntry, you don’t care how it does it, you just care
how long it takes. No excuses, addOrChangeEntry!
I find uses n comparisons
I Then it calls add, which only takes 1 array access to add Vic to end of array.
I Jay, Bob, Zoe, Ian, Ann, Eve, Vic
I Unless array is full, and then we need to allocate a bigger one, and copy
everything over first.
I So n array access (actually 2n) when array is full, but let’s not worry about
that now.
I Total time is n comparisons to find plus 1 array access to add or change.
I SortedPD.addOrChangeEntry
I Also has to call find and wait for find to finish.
I find uses log2 n comparisons
I Ann, Bob, Eve, Ian, Jay, Zoe
I Let’s add Abe.
I Abe, Ann, Bob, Eve, Ian, Jay, Zoe
I add uses n array accesses. Actually n − 1 reads and n writes, where n is 7.
So 2n − 1.
I Total time is log2 n comparisons (find) plus 2n − 1 array accesses (add).
addOrChangeEntry
I ArrayBasedPD.addOrChangeEntry
I Jay, Bob, Zoe, Ian, Ann, Eve
I Add Vic?
I Has to call find and wait for find to finish (to make sure Vic isn’t there
already).
I If you call addOrChangeEntry, you don’t care how it does it, you just care
how long it takes. No excuses, addOrChangeEntry!
I find uses n comparisons
I Then it calls add, which only takes 1 array access to add Vic to end of array.
I Jay, Bob, Zoe, Ian, Ann, Eve, Vic
I Unless array is full, and then we need to allocate a bigger one, and copy
everything over first.
I So n array access (actually 2n) when array is full, but let’s not worry about
that now.
I Total time is n comparisons to find plus 1 array access to add or change.
I SortedPD.addOrChangeEntry
I Also has to call find and wait for find to finish.
I find uses log2 n comparisons
I Ann, Bob, Eve, Ian, Jay, Zoe
I Let’s add Abe.
I Abe, Ann, Bob, Eve, Ian, Jay, Zoe
I add uses n array accesses. Actually n − 1 reads and n writes, where n is 7.
So 2n − 1.
I Total time is log2 n comparisons (find) plus 2n − 1 array accesses (add).
addOrChangeEntry
I ArrayBasedPD.addOrChangeEntry
I Jay, Bob, Zoe, Ian, Ann, Eve
I Add Vic?
I Has to call find and wait for find to finish (to make sure Vic isn’t there
already).
I If you call addOrChangeEntry, you don’t care how it does it, you just care
how long it takes. No excuses, addOrChangeEntry!
I find uses n comparisons
I Then it calls add, which only takes 1 array access to add Vic to end of array.
I Jay, Bob, Zoe, Ian, Ann, Eve, Vic
I Unless array is full, and then we need to allocate a bigger one, and copy
everything over first.
I So n array access (actually 2n) when array is full, but let’s not worry about
that now.
I Total time is n comparisons to find plus 1 array access to add or change.
I SortedPD.addOrChangeEntry
I Also has to call find and wait for find to finish.
I find uses log2 n comparisons
I Ann, Bob, Eve, Ian, Jay, Zoe
I Let’s add Abe.
I Abe, Ann, Bob, Eve, Ian, Jay, Zoe
I add uses n array accesses. Actually n − 1 reads and n writes, where n is 7.
So 2n − 1.
I Total time is log2 n comparisons (find) plus 2n − 1 array accesses (add).
addOrChangeEntry
I ArrayBasedPD.addOrChangeEntry
I Jay, Bob, Zoe, Ian, Ann, Eve
I Add Vic?
I Has to call find and wait for find to finish (to make sure Vic isn’t there
already).
I If you call addOrChangeEntry, you don’t care how it does it, you just care
how long it takes. No excuses, addOrChangeEntry!
I find uses n comparisons
I Then it calls add, which only takes 1 array access to add Vic to end of array.
I Jay, Bob, Zoe, Ian, Ann, Eve, Vic
I Unless array is full, and then we need to allocate a bigger one, and copy
everything over first.
I So n array access (actually 2n) when array is full, but let’s not worry about
that now.
I Total time is n comparisons to find plus 1 array access to add or change.
I SortedPD.addOrChangeEntry
I Also has to call find and wait for find to finish.
I find uses log2 n comparisons
I Ann, Bob, Eve, Ian, Jay, Zoe
I Let’s add Abe.
I Abe, Ann, Bob, Eve, Ian, Jay, Zoe
I add uses n array accesses. Actually n − 1 reads and n writes, where n is 7.
So 2n − 1.
I Total time is log2 n comparisons (find) plus 2n − 1 array accesses (add).
addOrChangeEntry
I ArrayBasedPD.addOrChangeEntry
I Jay, Bob, Zoe, Ian, Ann, Eve
I Add Vic?
I Has to call find and wait for find to finish (to make sure Vic isn’t there
already).
I If you call addOrChangeEntry, you don’t care how it does it, you just care
how long it takes. No excuses, addOrChangeEntry!
I find uses n comparisons
I Then it calls add, which only takes 1 array access to add Vic to end of array.
I Jay, Bob, Zoe, Ian, Ann, Eve, Vic
I Unless array is full, and then we need to allocate a bigger one, and copy
everything over first.
I So n array access (actually 2n) when array is full, but let’s not worry about
that now.
I Total time is n comparisons to find plus 1 array access to add or change.
I SortedPD.addOrChangeEntry
I Also has to call find and wait for find to finish.
I find uses log2 n comparisons
I Ann, Bob, Eve, Ian, Jay, Zoe
I Let’s add Abe.
I Abe, Ann, Bob, Eve, Ian, Jay, Zoe
I add uses n array accesses. Actually n − 1 reads and n writes, where n is 7.
So 2n − 1.
I Total time is log2 n comparisons (find) plus 2n − 1 array accesses (add).
removeEntry
I ArrayBasedPD.removeEntry
I Jay, Bob, Zoe, Ian, Ann, Eve
I Who takes longest to remove? Jay?
I removeEntry calls find.
I find takes 1 comparison to find Jay.
I removeEntry calls remove.
I Eve, Bob, Zoe, Ian, Ann
I remove takes 2 array accesses to remove Jay.
I Total time for 1 comparison and 2 array accesses.
I What about Eve? (Last entry)
I Call to find takes n comparisons.
I add still uses 2 array accesses to “remove” Eve (but it could be smarter).
I So Eve is worst case, requiring time for n comparisons (find) and 2 array
accesses (remove).
I SortedPD.removeEntry
I Ann, Bob, Eve, Ian, Jay, Zoe
I Who is the worst to remove?
I Did you figure out it was Ann?
I find takes log2 n comparisons to locate Ann.
I add takes n array reads and writes to move everyone else back.
I Bob, Eve, Ian, Jay, Zoe
I Total is log2 n comparisons (find) and 2n array accesses (remove).
removeEntry
I ArrayBasedPD.removeEntry
I Jay, Bob, Zoe, Ian, Ann, Eve
I Who takes longest to remove? Jay?
I removeEntry calls find.
I find takes 1 comparison to find Jay.
I removeEntry calls remove.
I Eve, Bob, Zoe, Ian, Ann
I remove takes 2 array accesses to remove Jay.
I Total time for 1 comparison and 2 array accesses.
I What about Eve? (Last entry)
I Call to find takes n comparisons.
I add still uses 2 array accesses to “remove” Eve (but it could be smarter).
I So Eve is worst case, requiring time for n comparisons (find) and 2 array
accesses (remove).
I SortedPD.removeEntry
I Ann, Bob, Eve, Ian, Jay, Zoe
I Who is the worst to remove?
I Did you figure out it was Ann?
I find takes log2 n comparisons to locate Ann.
I add takes n array reads and writes to move everyone else back.
I Bob, Eve, Ian, Jay, Zoe
I Total is log2 n comparisons (find) and 2n array accesses (remove).
removeEntry
I ArrayBasedPD.removeEntry
I Jay, Bob, Zoe, Ian, Ann, Eve
I Who takes longest to remove? Jay?
I removeEntry calls find.
I find takes 1 comparison to find Jay.
I removeEntry calls remove.
I Eve, Bob, Zoe, Ian, Ann
I remove takes 2 array accesses to remove Jay.
I Total time for 1 comparison and 2 array accesses.
I What about Eve? (Last entry)
I Call to find takes n comparisons.
I add still uses 2 array accesses to “remove” Eve (but it could be smarter).
I So Eve is worst case, requiring time for n comparisons (find) and 2 array
accesses (remove).
I SortedPD.removeEntry
I Ann, Bob, Eve, Ian, Jay, Zoe
I Who is the worst to remove?
I Did you figure out it was Ann?
I find takes log2 n comparisons to locate Ann.
I add takes n array reads and writes to move everyone else back.
I Bob, Eve, Ian, Jay, Zoe
I Total is log2 n comparisons (find) and 2n array accesses (remove).
removeEntry
I ArrayBasedPD.removeEntry
I Jay, Bob, Zoe, Ian, Ann, Eve
I Who takes longest to remove? Jay?
I removeEntry calls find.
I find takes 1 comparison to find Jay.
I removeEntry calls remove.
I Eve, Bob, Zoe, Ian, Ann
I remove takes 2 array accesses to remove Jay.
I Total time for 1 comparison and 2 array accesses.
I What about Eve? (Last entry)
I Call to find takes n comparisons.
I add still uses 2 array accesses to “remove” Eve (but it could be smarter).
I So Eve is worst case, requiring time for n comparisons (find) and 2 array
accesses (remove).
I SortedPD.removeEntry
I Ann, Bob, Eve, Ian, Jay, Zoe
I Who is the worst to remove?
I Did you figure out it was Ann?
I find takes log2 n comparisons to locate Ann.
I add takes n array reads and writes to move everyone else back.
I Bob, Eve, Ian, Jay, Zoe
I Total is log2 n comparisons (find) and 2n array accesses (remove).
removeEntry
I ArrayBasedPD.removeEntry
I Jay, Bob, Zoe, Ian, Ann, Eve
I Who takes longest to remove? Jay?
I removeEntry calls find.
I find takes 1 comparison to find Jay.
I removeEntry calls remove.
I Eve, Bob, Zoe, Ian, Ann
I remove takes 2 array accesses to remove Jay.
I Total time for 1 comparison and 2 array accesses.
I What about Eve? (Last entry)
I Call to find takes n comparisons.
I add still uses 2 array accesses to “remove” Eve (but it could be smarter).
I So Eve is worst case, requiring time for n comparisons (find) and 2 array
accesses (remove).
I SortedPD.removeEntry
I Ann, Bob, Eve, Ian, Jay, Zoe
I Who is the worst to remove?
I Did you figure out it was Ann?
I find takes log2 n comparisons to locate Ann.
I add takes n array reads and writes to move everyone else back.
I Bob, Eve, Ian, Jay, Zoe
I Total is log2 n comparisons (find) and 2n array accesses (remove).
removeEntry
I ArrayBasedPD.removeEntry
I Jay, Bob, Zoe, Ian, Ann, Eve
I Who takes longest to remove? Jay?
I removeEntry calls find.
I find takes 1 comparison to find Jay.
I removeEntry calls remove.
I Eve, Bob, Zoe, Ian, Ann
I remove takes 2 array accesses to remove Jay.
I Total time for 1 comparison and 2 array accesses.
I What about Eve? (Last entry)
I Call to find takes n comparisons.
I add still uses 2 array accesses to “remove” Eve (but it could be smarter).
I So Eve is worst case, requiring time for n comparisons (find) and 2 array
accesses (remove).
I SortedPD.removeEntry
I Ann, Bob, Eve, Ian, Jay, Zoe
I Who is the worst to remove?
I Did you figure out it was Ann?
I find takes log2 n comparisons to locate Ann.
I add takes n array reads and writes to move everyone else back.
I Bob, Eve, Ian, Jay, Zoe
I Total is log2 n comparisons (find) and 2n array accesses (remove).
removeEntry
I ArrayBasedPD.removeEntry
I Jay, Bob, Zoe, Ian, Ann, Eve
I Who takes longest to remove? Jay?
I removeEntry calls find.
I find takes 1 comparison to find Jay.
I removeEntry calls remove.
I Eve, Bob, Zoe, Ian, Ann
I remove takes 2 array accesses to remove Jay.
I Total time for 1 comparison and 2 array accesses.
I What about Eve? (Last entry)
I Call to find takes n comparisons.
I add still uses 2 array accesses to “remove” Eve (but it could be smarter).
I So Eve is worst case, requiring time for n comparisons (find) and 2 array
accesses (remove).
I SortedPD.removeEntry
I Ann, Bob, Eve, Ian, Jay, Zoe
I Who is the worst to remove?
I Did you figure out it was Ann?
I find takes log2 n comparisons to locate Ann.
I add takes n array reads and writes to move everyone else back.
I Bob, Eve, Ian, Jay, Zoe
I Total is log2 n comparisons (find) and 2n array accesses (remove).
removeEntry
I ArrayBasedPD.removeEntry
I Jay, Bob, Zoe, Ian, Ann, Eve
I Who takes longest to remove? Jay?
I removeEntry calls find.
I find takes 1 comparison to find Jay.
I removeEntry calls remove.
I Eve, Bob, Zoe, Ian, Ann
I remove takes 2 array accesses to remove Jay.
I Total time for 1 comparison and 2 array accesses.
I What about Eve? (Last entry)
I Call to find takes n comparisons.
I add still uses 2 array accesses to “remove” Eve (but it could be smarter).
I So Eve is worst case, requiring time for n comparisons (find) and 2 array
accesses (remove).
I SortedPD.removeEntry
I Ann, Bob, Eve, Ian, Jay, Zoe
I Who is the worst to remove?
I Did you figure out it was Ann?
I find takes log2 n comparisons to locate Ann.
I add takes n array reads and writes to move everyone else back.
I Bob, Eve, Ian, Jay, Zoe
I Total is log2 n comparisons (find) and 2n array accesses (remove).
removeEntry
I ArrayBasedPD.removeEntry
I Jay, Bob, Zoe, Ian, Ann, Eve
I Who takes longest to remove? Jay?
I removeEntry calls find.
I find takes 1 comparison to find Jay.
I removeEntry calls remove.
I Eve, Bob, Zoe, Ian, Ann
I remove takes 2 array accesses to remove Jay.
I Total time for 1 comparison and 2 array accesses.
I What about Eve? (Last entry)
I Call to find takes n comparisons.
I add still uses 2 array accesses to “remove” Eve (but it could be smarter).
I So Eve is worst case, requiring time for n comparisons (find) and 2 array
accesses (remove).
I SortedPD.removeEntry
I Ann, Bob, Eve, Ian, Jay, Zoe
I Who is the worst to remove?
I Did you figure out it was Ann?
I find takes log2 n comparisons to locate Ann.
I add takes n array reads and writes to move everyone else back.
I Bob, Eve, Ian, Jay, Zoe
I Total is log2 n comparisons (find) and 2n array accesses (remove).
removeEntry
I ArrayBasedPD.removeEntry
I Jay, Bob, Zoe, Ian, Ann, Eve
I Who takes longest to remove? Jay?
I removeEntry calls find.
I find takes 1 comparison to find Jay.
I removeEntry calls remove.
I Eve, Bob, Zoe, Ian, Ann
I remove takes 2 array accesses to remove Jay.
I Total time for 1 comparison and 2 array accesses.
I What about Eve? (Last entry)
I Call to find takes n comparisons.
I add still uses 2 array accesses to “remove” Eve (but it could be smarter).
I So Eve is worst case, requiring time for n comparisons (find) and 2 array
accesses (remove).
I SortedPD.removeEntry
I Ann, Bob, Eve, Ian, Jay, Zoe
I Who is the worst to remove?
I Did you figure out it was Ann?
I find takes log2 n comparisons to locate Ann.
I add takes n array reads and writes to move everyone else back.
I Bob, Eve, Ian, Jay, Zoe
I Total is log2 n comparisons (find) and 2n array accesses (remove).
removeEntry
I ArrayBasedPD.removeEntry
I Jay, Bob, Zoe, Ian, Ann, Eve
I Who takes longest to remove? Jay?
I removeEntry calls find.
I find takes 1 comparison to find Jay.
I removeEntry calls remove.
I Eve, Bob, Zoe, Ian, Ann
I remove takes 2 array accesses to remove Jay.
I Total time for 1 comparison and 2 array accesses.
I What about Eve? (Last entry)
I Call to find takes n comparisons.
I add still uses 2 array accesses to “remove” Eve (but it could be smarter).
I So Eve is worst case, requiring time for n comparisons (find) and 2 array
accesses (remove).
I SortedPD.removeEntry
I Ann, Bob, Eve, Ian, Jay, Zoe
I Who is the worst to remove?
I Did you figure out it was Ann?
I find takes log2 n comparisons to locate Ann.
I add takes n array reads and writes to move everyone else back.
I Bob, Eve, Ian, Jay, Zoe
I Total is log2 n comparisons (find) and 2n array accesses (remove).
removeEntry
I ArrayBasedPD.removeEntry
I Jay, Bob, Zoe, Ian, Ann, Eve
I Who takes longest to remove? Jay?
I removeEntry calls find.
I find takes 1 comparison to find Jay.
I removeEntry calls remove.
I Eve, Bob, Zoe, Ian, Ann
I remove takes 2 array accesses to remove Jay.
I Total time for 1 comparison and 2 array accesses.
I What about Eve? (Last entry)
I Call to find takes n comparisons.
I add still uses 2 array accesses to “remove” Eve (but it could be smarter).
I So Eve is worst case, requiring time for n comparisons (find) and 2 array
accesses (remove).
I SortedPD.removeEntry
I Ann, Bob, Eve, Ian, Jay, Zoe
I Who is the worst to remove?
I Did you figure out it was Ann?
I find takes log2 n comparisons to locate Ann.
I add takes n array reads and writes to move everyone else back.
I Bob, Eve, Ian, Jay, Zoe
I Total is log2 n comparisons (find) and 2n array accesses (remove).
removeEntry
I ArrayBasedPD.removeEntry
I Jay, Bob, Zoe, Ian, Ann, Eve
I Who takes longest to remove? Jay?
I removeEntry calls find.
I find takes 1 comparison to find Jay.
I removeEntry calls remove.
I Eve, Bob, Zoe, Ian, Ann
I remove takes 2 array accesses to remove Jay.
I Total time for 1 comparison and 2 array accesses.
I What about Eve? (Last entry)
I Call to find takes n comparisons.
I add still uses 2 array accesses to “remove” Eve (but it could be smarter).
I So Eve is worst case, requiring time for n comparisons (find) and 2 array
accesses (remove).
I SortedPD.removeEntry
I Ann, Bob, Eve, Ian, Jay, Zoe
I Who is the worst to remove?
I Did you figure out it was Ann?
I find takes log2 n comparisons to locate Ann.
I add takes n array reads and writes to move everyone else back.
I Bob, Eve, Ian, Jay, Zoe
I Total is log2 n comparisons (find) and 2n array accesses (remove).
removeEntry
I ArrayBasedPD.removeEntry
I Jay, Bob, Zoe, Ian, Ann, Eve
I Who takes longest to remove? Jay?
I removeEntry calls find.
I find takes 1 comparison to find Jay.
I removeEntry calls remove.
I Eve, Bob, Zoe, Ian, Ann
I remove takes 2 array accesses to remove Jay.
I Total time for 1 comparison and 2 array accesses.
I What about Eve? (Last entry)
I Call to find takes n comparisons.
I add still uses 2 array accesses to “remove” Eve (but it could be smarter).
I So Eve is worst case, requiring time for n comparisons (find) and 2 array
accesses (remove).
I SortedPD.removeEntry
I Ann, Bob, Eve, Ian, Jay, Zoe
I Who is the worst to remove?
I Did you figure out it was Ann?
I find takes log2 n comparisons to locate Ann.
I add takes n array reads and writes to move everyone else back.
I Bob, Eve, Ian, Jay, Zoe
I Total is log2 n comparisons (find) and 2n array accesses (remove).
removeEntry
I ArrayBasedPD.removeEntry
I Jay, Bob, Zoe, Ian, Ann, Eve
I Who takes longest to remove? Jay?
I removeEntry calls find.
I find takes 1 comparison to find Jay.
I removeEntry calls remove.
I Eve, Bob, Zoe, Ian, Ann
I remove takes 2 array accesses to remove Jay.
I Total time for 1 comparison and 2 array accesses.
I What about Eve? (Last entry)
I Call to find takes n comparisons.
I add still uses 2 array accesses to “remove” Eve (but it could be smarter).
I So Eve is worst case, requiring time for n comparisons (find) and 2 array
accesses (remove).
I SortedPD.removeEntry
I Ann, Bob, Eve, Ian, Jay, Zoe
I Who is the worst to remove?
I Did you figure out it was Ann?
I find takes log2 n comparisons to locate Ann.
I add takes n array reads and writes to move everyone else back.
I Bob, Eve, Ian, Jay, Zoe
I Total is log2 n comparisons (find) and 2n array accesses (remove).
removeEntry
I ArrayBasedPD.removeEntry
I Jay, Bob, Zoe, Ian, Ann, Eve
I Who takes longest to remove? Jay?
I removeEntry calls find.
I find takes 1 comparison to find Jay.
I removeEntry calls remove.
I Eve, Bob, Zoe, Ian, Ann
I remove takes 2 array accesses to remove Jay.
I Total time for 1 comparison and 2 array accesses.
I What about Eve? (Last entry)
I Call to find takes n comparisons.
I add still uses 2 array accesses to “remove” Eve (but it could be smarter).
I So Eve is worst case, requiring time for n comparisons (find) and 2 array
accesses (remove).
I SortedPD.removeEntry
I Ann, Bob, Eve, Ian, Jay, Zoe
I Who is the worst to remove?
I Did you figure out it was Ann?
I find takes log2 n comparisons to locate Ann.
I add takes n array reads and writes to move everyone else back.
I Bob, Eve, Ian, Jay, Zoe
I Total is log2 n comparisons (find) and 2n array accesses (remove).
removeEntry
I ArrayBasedPD.removeEntry
I Jay, Bob, Zoe, Ian, Ann, Eve
I Who takes longest to remove? Jay?
I removeEntry calls find.
I find takes 1 comparison to find Jay.
I removeEntry calls remove.
I Eve, Bob, Zoe, Ian, Ann
I remove takes 2 array accesses to remove Jay.
I Total time for 1 comparison and 2 array accesses.
I What about Eve? (Last entry)
I Call to find takes n comparisons.
I add still uses 2 array accesses to “remove” Eve (but it could be smarter).
I So Eve is worst case, requiring time for n comparisons (find) and 2 array
accesses (remove).
I SortedPD.removeEntry
I Ann, Bob, Eve, Ian, Jay, Zoe
I Who is the worst to remove?
I Did you figure out it was Ann?
I find takes log2 n comparisons to locate Ann.
I add takes n array reads and writes to move everyone else back.
I Bob, Eve, Ian, Jay, Zoe
I Total is log2 n comparisons (find) and 2n array accesses (remove).
removeEntry
I ArrayBasedPD.removeEntry
I Jay, Bob, Zoe, Ian, Ann, Eve
I Who takes longest to remove? Jay?
I removeEntry calls find.
I find takes 1 comparison to find Jay.
I removeEntry calls remove.
I Eve, Bob, Zoe, Ian, Ann
I remove takes 2 array accesses to remove Jay.
I Total time for 1 comparison and 2 array accesses.
I What about Eve? (Last entry)
I Call to find takes n comparisons.
I add still uses 2 array accesses to “remove” Eve (but it could be smarter).
I So Eve is worst case, requiring time for n comparisons (find) and 2 array
accesses (remove).
I SortedPD.removeEntry
I Ann, Bob, Eve, Ian, Jay, Zoe
I Who is the worst to remove?
I Did you figure out it was Ann?
I find takes log2 n comparisons to locate Ann.
I add takes n array reads and writes to move everyone else back.
I Bob, Eve, Ian, Jay, Zoe
I Total is log2 n comparisons (find) and 2n array accesses (remove).
removeEntry
I ArrayBasedPD.removeEntry
I Jay, Bob, Zoe, Ian, Ann, Eve
I Who takes longest to remove? Jay?
I removeEntry calls find.
I find takes 1 comparison to find Jay.
I removeEntry calls remove.
I Eve, Bob, Zoe, Ian, Ann
I remove takes 2 array accesses to remove Jay.
I Total time for 1 comparison and 2 array accesses.
I What about Eve? (Last entry)
I Call to find takes n comparisons.
I add still uses 2 array accesses to “remove” Eve (but it could be smarter).
I So Eve is worst case, requiring time for n comparisons (find) and 2 array
accesses (remove).
I SortedPD.removeEntry
I Ann, Bob, Eve, Ian, Jay, Zoe
I Who is the worst to remove?
I Did you figure out it was Ann?
I find takes log2 n comparisons to locate Ann.
I add takes n array reads and writes to move everyone else back.
I Bob, Eve, Ian, Jay, Zoe
I Total is log2 n comparisons (find) and 2n array accesses (remove).
removeEntry
I ArrayBasedPD.removeEntry
I Jay, Bob, Zoe, Ian, Ann, Eve
I Who takes longest to remove? Jay?
I removeEntry calls find.
I find takes 1 comparison to find Jay.
I removeEntry calls remove.
I Eve, Bob, Zoe, Ian, Ann
I remove takes 2 array accesses to remove Jay.
I Total time for 1 comparison and 2 array accesses.
I What about Eve? (Last entry)
I Call to find takes n comparisons.
I add still uses 2 array accesses to “remove” Eve (but it could be smarter).
I So Eve is worst case, requiring time for n comparisons (find) and 2 array
accesses (remove).
I SortedPD.removeEntry
I Ann, Bob, Eve, Ian, Jay, Zoe
I Who is the worst to remove?
I Did you figure out it was Ann?
I find takes log2 n comparisons to locate Ann.
I add takes n array reads and writes to move everyone else back.
I Bob, Eve, Ian, Jay, Zoe
I Total is log2 n comparisons (find) and 2n array accesses (remove).
removeEntry
I ArrayBasedPD.removeEntry
I Jay, Bob, Zoe, Ian, Ann, Eve
I Who takes longest to remove? Jay?
I removeEntry calls find.
I find takes 1 comparison to find Jay.
I removeEntry calls remove.
I Eve, Bob, Zoe, Ian, Ann
I remove takes 2 array accesses to remove Jay.
I Total time for 1 comparison and 2 array accesses.
I What about Eve? (Last entry)
I Call to find takes n comparisons.
I add still uses 2 array accesses to “remove” Eve (but it could be smarter).
I So Eve is worst case, requiring time for n comparisons (find) and 2 array
accesses (remove).
I SortedPD.removeEntry
I Ann, Bob, Eve, Ian, Jay, Zoe
I Who is the worst to remove?
I Did you figure out it was Ann?
I find takes log2 n comparisons to locate Ann.
I add takes n array reads and writes to move everyone else back.
I Bob, Eve, Ian, Jay, Zoe
I Total is log2 n comparisons (find) and 2n array accesses (remove).
removeEntry
I ArrayBasedPD.removeEntry
I Jay, Bob, Zoe, Ian, Ann, Eve
I Who takes longest to remove? Jay?
I removeEntry calls find.
I find takes 1 comparison to find Jay.
I removeEntry calls remove.
I Eve, Bob, Zoe, Ian, Ann
I remove takes 2 array accesses to remove Jay.
I Total time for 1 comparison and 2 array accesses.
I What about Eve? (Last entry)
I Call to find takes n comparisons.
I add still uses 2 array accesses to “remove” Eve (but it could be smarter).
I So Eve is worst case, requiring time for n comparisons (find) and 2 array
accesses (remove).
I SortedPD.removeEntry
I Ann, Bob, Eve, Ian, Jay, Zoe
I Who is the worst to remove?
I Did you figure out it was Ann?
I find takes log2 n comparisons to locate Ann.
I add takes n array reads and writes to move everyone else back.
I Bob, Eve, Ian, Jay, Zoe
I Total is log2 n comparisons (find) and 2n array accesses (remove).
Summary
I ArrayBasedPD
I find: n comparisons
I add: 1 array access (usually)
I remove: 2 array accesses
I addOrChangeEntry: n comparisons plus 1 array access (usually)
I removeEntry: n comparisons plus 2 array accesses
I SortedPD
I find: log2 n comparisons
I add: 2n array accesses
I remove: 2n array accesses
I addOrChangeEntry: log2 n comparisons plus 2n array accesses.
I removeEntry: log2 n comparisons plus 2n array accesses.
Summary
I ArrayBasedPD
I find: n comparisons
I add: 1 array access (usually)
I remove: 2 array accesses
I addOrChangeEntry: n comparisons plus 1 array access (usually)
I removeEntry: n comparisons plus 2 array accesses
I SortedPD
I find: log2 n comparisons
I add: 2n array accesses
I remove: 2n array accesses
I addOrChangeEntry: log2 n comparisons plus 2n array accesses.
I removeEntry: log2 n comparisons plus 2n array accesses.
Summary
I ArrayBasedPD
I find: n comparisons
I add: 1 array access (usually)
I remove: 2 array accesses
I addOrChangeEntry: n comparisons plus 1 array access (usually)
I removeEntry: n comparisons plus 2 array accesses
I SortedPD
I find: log2 n comparisons
I add: 2n array accesses
I remove: 2n array accesses
I addOrChangeEntry: log2 n comparisons plus 2n array accesses.
I removeEntry: log2 n comparisons plus 2n array accesses.
Summary
I ArrayBasedPD
I find: n comparisons
I add: 1 array access (usually)
I remove: 2 array accesses
I addOrChangeEntry: n comparisons plus 1 array access (usually)
I removeEntry: n comparisons plus 2 array accesses
I SortedPD
I find: log2 n comparisons
I add: 2n array accesses
I remove: 2n array accesses
I addOrChangeEntry: log2 n comparisons plus 2n array accesses.
I removeEntry: log2 n comparisons plus 2n array accesses.
Summary
I ArrayBasedPD
I find: n comparisons
I add: 1 array access (usually)
I remove: 2 array accesses
I addOrChangeEntry: n comparisons plus 1 array access (usually)
I removeEntry: n comparisons plus 2 array accesses
I SortedPD
I find: log2 n comparisons
I add: 2n array accesses
I remove: 2n array accesses
I addOrChangeEntry: log2 n comparisons plus 2n array accesses.
I removeEntry: log2 n comparisons plus 2n array accesses.
Summary
I ArrayBasedPD
I find: n comparisons
I add: 1 array access (usually)
I remove: 2 array accesses
I addOrChangeEntry: n comparisons plus 1 array access (usually)
I removeEntry: n comparisons plus 2 array accesses
I SortedPD
I find: log2 n comparisons
I add: 2n array accesses
I remove: 2n array accesses
I addOrChangeEntry: log2 n comparisons plus 2n array accesses.
I removeEntry: log2 n comparisons plus 2n array accesses.
Summary
I ArrayBasedPD
I find: n comparisons
I add: 1 array access (usually)
I remove: 2 array accesses
I addOrChangeEntry: n comparisons plus 1 array access (usually)
I removeEntry: n comparisons plus 2 array accesses
I SortedPD
I find: log2 n comparisons
I add: 2n array accesses
I remove: 2n array accesses
I addOrChangeEntry: log2 n comparisons plus 2n array accesses.
I removeEntry: log2 n comparisons plus 2n array accesses.
Summary
I ArrayBasedPD
I find: n comparisons
I add: 1 array access (usually)
I remove: 2 array accesses
I addOrChangeEntry: n comparisons plus 1 array access (usually)
I removeEntry: n comparisons plus 2 array accesses
I SortedPD
I find: log2 n comparisons
I add: 2n array accesses
I remove: 2n array accesses
I addOrChangeEntry: log2 n comparisons plus 2n array accesses.
I removeEntry: log2 n comparisons plus 2n array accesses.
Summary
I ArrayBasedPD
I find: n comparisons
I add: 1 array access (usually)
I remove: 2 array accesses
I addOrChangeEntry: n comparisons plus 1 array access (usually)
I removeEntry: n comparisons plus 2 array accesses
I SortedPD
I find: log2 n comparisons
I add: 2n array accesses
I remove: 2n array accesses
I addOrChangeEntry: log2 n comparisons plus 2n array accesses.
I removeEntry: log2 n comparisons plus 2n array accesses.
Summary
I ArrayBasedPD
I find: n comparisons
I add: 1 array access (usually)
I remove: 2 array accesses
I addOrChangeEntry: n comparisons plus 1 array access (usually)
I removeEntry: n comparisons plus 2 array accesses
I SortedPD
I find: log2 n comparisons
I add: 2n array accesses
I remove: 2n array accesses
I addOrChangeEntry: log2 n comparisons plus 2n array accesses.
I removeEntry: log2 n comparisons plus 2n array accesses.
Summary
I ArrayBasedPD
I find: n comparisons
I add: 1 array access (usually)
I remove: 2 array accesses
I addOrChangeEntry: n comparisons plus 1 array access (usually)
I removeEntry: n comparisons plus 2 array accesses
I SortedPD
I find: log2 n comparisons
I add: 2n array accesses
I remove: 2n array accesses
I addOrChangeEntry: log2 n comparisons plus 2n array accesses.
I removeEntry: log2 n comparisons plus 2n array accesses.
Summary
I ArrayBasedPD
I find: n comparisons
I add: 1 array access (usually)
I remove: 2 array accesses
I addOrChangeEntry: n comparisons plus 1 array access (usually)
I removeEntry: n comparisons plus 2 array accesses
I SortedPD
I find: log2 n comparisons
I add: 2n array accesses
I remove: 2n array accesses
I addOrChangeEntry: log2 n comparisons plus 2n array accesses.
I removeEntry: log2 n comparisons plus 2n array accesses.
Summary
I ArrayBasedPD
I find: n comparisons
I add: 1 array access (usually)
I remove: 2 array accesses
I addOrChangeEntry: n comparisons plus 1 array access (usually)
I removeEntry: n comparisons plus 2 array accesses
I SortedPD
I find: log2 n comparisons
I add: 2n array accesses
I remove: 2n array accesses
I addOrChangeEntry: log2 n comparisons plus 2n array accesses.
I removeEntry: log2 n comparisons plus 2n array accesses.
Order Arithmetic
I O(1), O(log n), or O(n)
I Constants don’t matter.
I log2 n = 3.3219 log10 n, so we just say O(log n)
I Only the dominant term matters.
I Accurate, up to a constant factor, for large n.
Order Arithmetic
I O(1), O(log n), or O(n)
I Constants don’t matter.
I log2 n = 3.3219 log10 n, so we just say O(log n)
I Only the dominant term matters.
I Accurate, up to a constant factor, for large n.
Order Arithmetic
I O(1), O(log n), or O(n)
I Constants don’t matter.
I log2 n = 3.3219 log10 n, so we just say O(log n)
I Only the dominant term matters.
I Accurate, up to a constant factor, for large n.
Order Arithmetic
I O(1), O(log n), or O(n)
I Constants don’t matter.
I log2 n = 3.3219 log10 n, so we just say O(log n)
I Only the dominant term matters.
I Accurate, up to a constant factor, for large n.
Order Arithmetic
I O(1), O(log n), or O(n)
I Constants don’t matter.
I log2 n = 3.3219 log10 n, so we just say O(log n)
I Only the dominant term matters.
I Accurate, up to a constant factor, for large n.
Order Arithmetic
I O(1), O(log n), or O(n)
I Constants don’t matter.
I log2 n = 3.3219 log10 n, so we just say O(log n)
I Only the dominant term matters.
I Accurate, up to a constant factor, for large n.
Summary
I ArrayBasedPD
I find: n comparisons – O(n)
I add: 1 array access (usually) – O(1)
I remove: 2 array accesses – O(1)
I addOrChangeEntry: n comparisons plus 1 array access (usually) –
O(n) + O(1) = O(n)
I removeEntry: n comparisons plus 2 array accesses – O(n) + O(1) = O(n)
I SortedPD
I find: log2 n comparisons – O(log n)
I add: 2n array accesses – O(n)
I remove: 2n array accesses – O(n)
I addOrChangeEntry: log2 n comparisons plus 2n array accesses –
O(log n) + O(n) = O(n)
I removeEntry: log2 n comparisons plus 2n array accesses –
O(log n) + O(n) = O(n)
I SortedPD compared to ArrayBasedPD
I Sorted find is (much) faster.
I Which is good, because that’s probably what you do most.
I Sorted add is (much) slower.
I Sorted remove is (much) slower.
I SortedPD addOrChangeEntry is the same.
I SortedPD removeEntry is the same.
Summary
I ArrayBasedPD
I find: n comparisons – O(n)
I add: 1 array access (usually) – O(1)
I remove: 2 array accesses – O(1)
I addOrChangeEntry: n comparisons plus 1 array access (usually) –
O(n) + O(1) = O(n)
I removeEntry: n comparisons plus 2 array accesses – O(n) + O(1) = O(n)
I SortedPD
I find: log2 n comparisons – O(log n)
I add: 2n array accesses – O(n)
I remove: 2n array accesses – O(n)
I addOrChangeEntry: log2 n comparisons plus 2n array accesses –
O(log n) + O(n) = O(n)
I removeEntry: log2 n comparisons plus 2n array accesses –
O(log n) + O(n) = O(n)
I SortedPD compared to ArrayBasedPD
I Sorted find is (much) faster.
I Which is good, because that’s probably what you do most.
I Sorted add is (much) slower.
I Sorted remove is (much) slower.
I SortedPD addOrChangeEntry is the same.
I SortedPD removeEntry is the same.
Summary
I ArrayBasedPD
I find: n comparisons – O(n)
I add: 1 array access (usually) – O(1)
I remove: 2 array accesses – O(1)
I addOrChangeEntry: n comparisons plus 1 array access (usually) –
O(n) + O(1) = O(n)
I removeEntry: n comparisons plus 2 array accesses – O(n) + O(1) = O(n)
I SortedPD
I find: log2 n comparisons – O(log n)
I add: 2n array accesses – O(n)
I remove: 2n array accesses – O(n)
I addOrChangeEntry: log2 n comparisons plus 2n array accesses –
O(log n) + O(n) = O(n)
I removeEntry: log2 n comparisons plus 2n array accesses –
O(log n) + O(n) = O(n)
I SortedPD compared to ArrayBasedPD
I Sorted find is (much) faster.
I Which is good, because that’s probably what you do most.
I Sorted add is (much) slower.
I Sorted remove is (much) slower.
I SortedPD addOrChangeEntry is the same.
I SortedPD removeEntry is the same.
Summary
I ArrayBasedPD
I find: n comparisons – O(n)
I add: 1 array access (usually) – O(1)
I remove: 2 array accesses – O(1)
I addOrChangeEntry: n comparisons plus 1 array access (usually) –
O(n) + O(1) = O(n)
I removeEntry: n comparisons plus 2 array accesses – O(n) + O(1) = O(n)
I SortedPD
I find: log2 n comparisons – O(log n)
I add: 2n array accesses – O(n)
I remove: 2n array accesses – O(n)
I addOrChangeEntry: log2 n comparisons plus 2n array accesses –
O(log n) + O(n) = O(n)
I removeEntry: log2 n comparisons plus 2n array accesses –
O(log n) + O(n) = O(n)
I SortedPD compared to ArrayBasedPD
I Sorted find is (much) faster.
I Which is good, because that’s probably what you do most.
I Sorted add is (much) slower.
I Sorted remove is (much) slower.
I SortedPD addOrChangeEntry is the same.
I SortedPD removeEntry is the same.
Summary
I ArrayBasedPD
I find: n comparisons – O(n)
I add: 1 array access (usually) – O(1)
I remove: 2 array accesses – O(1)
I addOrChangeEntry: n comparisons plus 1 array access (usually) –
O(n) + O(1) = O(n)
I removeEntry: n comparisons plus 2 array accesses – O(n) + O(1) = O(n)
I SortedPD
I find: log2 n comparisons – O(log n)
I add: 2n array accesses – O(n)
I remove: 2n array accesses – O(n)
I addOrChangeEntry: log2 n comparisons plus 2n array accesses –
O(log n) + O(n) = O(n)
I removeEntry: log2 n comparisons plus 2n array accesses –
O(log n) + O(n) = O(n)
I SortedPD compared to ArrayBasedPD
I Sorted find is (much) faster.
I Which is good, because that’s probably what you do most.
I Sorted add is (much) slower.
I Sorted remove is (much) slower.
I SortedPD addOrChangeEntry is the same.
I SortedPD removeEntry is the same.
Summary
I ArrayBasedPD
I find: n comparisons – O(n)
I add: 1 array access (usually) – O(1)
I remove: 2 array accesses – O(1)
I addOrChangeEntry: n comparisons plus 1 array access (usually) –
O(n) + O(1) = O(n)
I removeEntry: n comparisons plus 2 array accesses – O(n) + O(1) = O(n)
I SortedPD
I find: log2 n comparisons – O(log n)
I add: 2n array accesses – O(n)
I remove: 2n array accesses – O(n)
I addOrChangeEntry: log2 n comparisons plus 2n array accesses –
O(log n) + O(n) = O(n)
I removeEntry: log2 n comparisons plus 2n array accesses –
O(log n) + O(n) = O(n)
I SortedPD compared to ArrayBasedPD
I Sorted find is (much) faster.
I Which is good, because that’s probably what you do most.
I Sorted add is (much) slower.
I Sorted remove is (much) slower.
I SortedPD addOrChangeEntry is the same.
I SortedPD removeEntry is the same.
Summary
I ArrayBasedPD
I find: n comparisons – O(n)
I add: 1 array access (usually) – O(1)
I remove: 2 array accesses – O(1)
I addOrChangeEntry: n comparisons plus 1 array access (usually) –
O(n) + O(1) = O(n)
I removeEntry: n comparisons plus 2 array accesses – O(n) + O(1) = O(n)
I SortedPD
I find: log2 n comparisons – O(log n)
I add: 2n array accesses – O(n)
I remove: 2n array accesses – O(n)
I addOrChangeEntry: log2 n comparisons plus 2n array accesses –
O(log n) + O(n) = O(n)
I removeEntry: log2 n comparisons plus 2n array accesses –
O(log n) + O(n) = O(n)
I SortedPD compared to ArrayBasedPD
I Sorted find is (much) faster.
I Which is good, because that’s probably what you do most.
I Sorted add is (much) slower.
I Sorted remove is (much) slower.
I SortedPD addOrChangeEntry is the same.
I SortedPD removeEntry is the same.
Summary
I ArrayBasedPD
I find: n comparisons – O(n)
I add: 1 array access (usually) – O(1)
I remove: 2 array accesses – O(1)
I addOrChangeEntry: n comparisons plus 1 array access (usually) –
O(n) + O(1) = O(n)
I removeEntry: n comparisons plus 2 array accesses – O(n) + O(1) = O(n)
I SortedPD
I find: log2 n comparisons – O(log n)
I add: 2n array accesses – O(n)
I remove: 2n array accesses – O(n)
I addOrChangeEntry: log2 n comparisons plus 2n array accesses –
O(log n) + O(n) = O(n)
I removeEntry: log2 n comparisons plus 2n array accesses –
O(log n) + O(n) = O(n)
I SortedPD compared to ArrayBasedPD
I Sorted find is (much) faster.
I Which is good, because that’s probably what you do most.
I Sorted add is (much) slower.
I Sorted remove is (much) slower.
I SortedPD addOrChangeEntry is the same.
I SortedPD removeEntry is the same.
Summary
I ArrayBasedPD
I find: n comparisons – O(n)
I add: 1 array access (usually) – O(1)
I remove: 2 array accesses – O(1)
I addOrChangeEntry: n comparisons plus 1 array access (usually) –
O(n) + O(1) = O(n)
I removeEntry: n comparisons plus 2 array accesses – O(n) + O(1) = O(n)
I SortedPD
I find: log2 n comparisons – O(log n)
I add: 2n array accesses – O(n)
I remove: 2n array accesses – O(n)
I addOrChangeEntry: log2 n comparisons plus 2n array accesses –
O(log n) + O(n) = O(n)
I removeEntry: log2 n comparisons plus 2n array accesses –
O(log n) + O(n) = O(n)
I SortedPD compared to ArrayBasedPD
I Sorted find is (much) faster.
I Which is good, because that’s probably what you do most.
I Sorted add is (much) slower.
I Sorted remove is (much) slower.
I SortedPD addOrChangeEntry is the same.
I SortedPD removeEntry is the same.
Summary
I ArrayBasedPD
I find: n comparisons – O(n)
I add: 1 array access (usually) – O(1)
I remove: 2 array accesses – O(1)
I addOrChangeEntry: n comparisons plus 1 array access (usually) –
O(n) + O(1) = O(n)
I removeEntry: n comparisons plus 2 array accesses – O(n) + O(1) = O(n)
I SortedPD
I find: log2 n comparisons – O(log n)
I add: 2n array accesses – O(n)
I remove: 2n array accesses – O(n)
I addOrChangeEntry: log2 n comparisons plus 2n array accesses –
O(log n) + O(n) = O(n)
I removeEntry: log2 n comparisons plus 2n array accesses –
O(log n) + O(n) = O(n)
I SortedPD compared to ArrayBasedPD
I Sorted find is (much) faster.
I Which is good, because that’s probably what you do most.
I Sorted add is (much) slower.
I Sorted remove is (much) slower.
I SortedPD addOrChangeEntry is the same.
I SortedPD removeEntry is the same.
Summary
I ArrayBasedPD
I find: n comparisons – O(n)
I add: 1 array access (usually) – O(1)
I remove: 2 array accesses – O(1)
I addOrChangeEntry: n comparisons plus 1 array access (usually) –
O(n) + O(1) = O(n)
I removeEntry: n comparisons plus 2 array accesses – O(n) + O(1) = O(n)
I SortedPD
I find: log2 n comparisons – O(log n)
I add: 2n array accesses – O(n)
I remove: 2n array accesses – O(n)
I addOrChangeEntry: log2 n comparisons plus 2n array accesses –
O(log n) + O(n) = O(n)
I removeEntry: log2 n comparisons plus 2n array accesses –
O(log n) + O(n) = O(n)
I SortedPD compared to ArrayBasedPD
I Sorted find is (much) faster.
I Which is good, because that’s probably what you do most.
I Sorted add is (much) slower.
I Sorted remove is (much) slower.
I SortedPD addOrChangeEntry is the same.
I SortedPD removeEntry is the same.
Summary
I ArrayBasedPD
I find: n comparisons – O(n)
I add: 1 array access (usually) – O(1)
I remove: 2 array accesses – O(1)
I addOrChangeEntry: n comparisons plus 1 array access (usually) –
O(n) + O(1) = O(n)
I removeEntry: n comparisons plus 2 array accesses – O(n) + O(1) = O(n)
I SortedPD
I find: log2 n comparisons – O(log n)
I add: 2n array accesses – O(n)
I remove: 2n array accesses – O(n)
I addOrChangeEntry: log2 n comparisons plus 2n array accesses –
O(log n) + O(n) = O(n)
I removeEntry: log2 n comparisons plus 2n array accesses –
O(log n) + O(n) = O(n)
I SortedPD compared to ArrayBasedPD
I Sorted find is (much) faster.
I Which is good, because that’s probably what you do most.
I Sorted add is (much) slower.
I Sorted remove is (much) slower.
I SortedPD addOrChangeEntry is the same.
I SortedPD removeEntry is the same.
Summary
I ArrayBasedPD
I find: n comparisons – O(n)
I add: 1 array access (usually) – O(1)
I remove: 2 array accesses – O(1)
I addOrChangeEntry: n comparisons plus 1 array access (usually) –
O(n) + O(1) = O(n)
I removeEntry: n comparisons plus 2 array accesses – O(n) + O(1) = O(n)
I SortedPD
I find: log2 n comparisons – O(log n)
I add: 2n array accesses – O(n)
I remove: 2n array accesses – O(n)
I addOrChangeEntry: log2 n comparisons plus 2n array accesses –
O(log n) + O(n) = O(n)
I removeEntry: log2 n comparisons plus 2n array accesses –
O(log n) + O(n) = O(n)
I SortedPD compared to ArrayBasedPD
I Sorted find is (much) faster.
I Which is good, because that’s probably what you do most.
I Sorted add is (much) slower.
I Sorted remove is (much) slower.
I SortedPD addOrChangeEntry is the same.
I SortedPD removeEntry is the same.
Summary
I ArrayBasedPD
I find: n comparisons – O(n)
I add: 1 array access (usually) – O(1)
I remove: 2 array accesses – O(1)
I addOrChangeEntry: n comparisons plus 1 array access (usually) –
O(n) + O(1) = O(n)
I removeEntry: n comparisons plus 2 array accesses – O(n) + O(1) = O(n)
I SortedPD
I find: log2 n comparisons – O(log n)
I add: 2n array accesses – O(n)
I remove: 2n array accesses – O(n)
I addOrChangeEntry: log2 n comparisons plus 2n array accesses –
O(log n) + O(n) = O(n)
I removeEntry: log2 n comparisons plus 2n array accesses –
O(log n) + O(n) = O(n)
I SortedPD compared to ArrayBasedPD
I Sorted find is (much) faster.
I Which is good, because that’s probably what you do most.
I Sorted add is (much) slower.
I Sorted remove is (much) slower.
I SortedPD addOrChangeEntry is the same.
I SortedPD removeEntry is the same.
Summary
I ArrayBasedPD
I find: n comparisons – O(n)
I add: 1 array access (usually) – O(1)
I remove: 2 array accesses – O(1)
I addOrChangeEntry: n comparisons plus 1 array access (usually) –
O(n) + O(1) = O(n)
I removeEntry: n comparisons plus 2 array accesses – O(n) + O(1) = O(n)
I SortedPD
I find: log2 n comparisons – O(log n)
I add: 2n array accesses – O(n)
I remove: 2n array accesses – O(n)
I addOrChangeEntry: log2 n comparisons plus 2n array accesses –
O(log n) + O(n) = O(n)
I removeEntry: log2 n comparisons plus 2n array accesses –
O(log n) + O(n) = O(n)
I SortedPD compared to ArrayBasedPD
I Sorted find is (much) faster.
I Which is good, because that’s probably what you do most.
I Sorted add is (much) slower.
I Sorted remove is (much) slower.
I SortedPD addOrChangeEntry is the same.
I SortedPD removeEntry is the same.
Summary
I ArrayBasedPD
I find: n comparisons – O(n)
I add: 1 array access (usually) – O(1)
I remove: 2 array accesses – O(1)
I addOrChangeEntry: n comparisons plus 1 array access (usually) –
O(n) + O(1) = O(n)
I removeEntry: n comparisons plus 2 array accesses – O(n) + O(1) = O(n)
I SortedPD
I find: log2 n comparisons – O(log n)
I add: 2n array accesses – O(n)
I remove: 2n array accesses – O(n)
I addOrChangeEntry: log2 n comparisons plus 2n array accesses –
O(log n) + O(n) = O(n)
I removeEntry: log2 n comparisons plus 2n array accesses –
O(log n) + O(n) = O(n)
I SortedPD compared to ArrayBasedPD
I Sorted find is (much) faster.
I Which is good, because that’s probably what you do most.
I Sorted add is (much) slower.
I Sorted remove is (much) slower.
I SortedPD addOrChangeEntry is the same.
I SortedPD removeEntry is the same.
Summary
I ArrayBasedPD
I find: n comparisons – O(n)
I add: 1 array access (usually) – O(1)
I remove: 2 array accesses – O(1)
I addOrChangeEntry: n comparisons plus 1 array access (usually) –
O(n) + O(1) = O(n)
I removeEntry: n comparisons plus 2 array accesses – O(n) + O(1) = O(n)
I SortedPD
I find: log2 n comparisons – O(log n)
I add: 2n array accesses – O(n)
I remove: 2n array accesses – O(n)
I addOrChangeEntry: log2 n comparisons plus 2n array accesses –
O(log n) + O(n) = O(n)
I removeEntry: log2 n comparisons plus 2n array accesses –
O(log n) + O(n) = O(n)
I SortedPD compared to ArrayBasedPD
I Sorted find is (much) faster.
I Which is good, because that’s probably what you do most.
I Sorted add is (much) slower.
I Sorted remove is (much) slower.
I SortedPD addOrChangeEntry is the same.
I SortedPD removeEntry is the same.
Summary
I ArrayBasedPD
I find: n comparisons – O(n)
I add: 1 array access (usually) – O(1)
I remove: 2 array accesses – O(1)
I addOrChangeEntry: n comparisons plus 1 array access (usually) –
O(n) + O(1) = O(n)
I removeEntry: n comparisons plus 2 array accesses – O(n) + O(1) = O(n)
I SortedPD
I find: log2 n comparisons – O(log n)
I add: 2n array accesses – O(n)
I remove: 2n array accesses – O(n)
I addOrChangeEntry: log2 n comparisons plus 2n array accesses –
O(log n) + O(n) = O(n)
I removeEntry: log2 n comparisons plus 2n array accesses –
O(log n) + O(n) = O(n)
I SortedPD compared to ArrayBasedPD
I Sorted find is (much) faster.
I Which is good, because that’s probably what you do most.
I Sorted add is (much) slower.
I Sorted remove is (much) slower.
I SortedPD addOrChangeEntry is the same.
I SortedPD removeEntry is the same.
Summary
I ArrayBasedPD
I find: n comparisons – O(n)
I add: 1 array access (usually) – O(1)
I remove: 2 array accesses – O(1)
I addOrChangeEntry: n comparisons plus 1 array access (usually) –
O(n) + O(1) = O(n)
I removeEntry: n comparisons plus 2 array accesses – O(n) + O(1) = O(n)
I SortedPD
I find: log2 n comparisons – O(log n)
I add: 2n array accesses – O(n)
I remove: 2n array accesses – O(n)
I addOrChangeEntry: log2 n comparisons plus 2n array accesses –
O(log n) + O(n) = O(n)
I removeEntry: log2 n comparisons plus 2n array accesses –
O(log n) + O(n) = O(n)
I SortedPD compared to ArrayBasedPD
I Sorted find is (much) faster.
I Which is good, because that’s probably what you do most.
I Sorted add is (much) slower.
I Sorted remove is (much) slower.
I SortedPD addOrChangeEntry is the same.
I SortedPD removeEntry is the same.
Summary
I ArrayBasedPD
I find: n comparisons – O(n)
I add: 1 array access (usually) – O(1)
I remove: 2 array accesses – O(1)
I addOrChangeEntry: n comparisons plus 1 array access (usually) –
O(n) + O(1) = O(n)
I removeEntry: n comparisons plus 2 array accesses – O(n) + O(1) = O(n)
I SortedPD
I find: log2 n comparisons – O(log n)
I add: 2n array accesses – O(n)
I remove: 2n array accesses – O(n)
I addOrChangeEntry: log2 n comparisons plus 2n array accesses –
O(log n) + O(n) = O(n)
I removeEntry: log2 n comparisons plus 2n array accesses –
O(log n) + O(n) = O(n)
I SortedPD compared to ArrayBasedPD
I Sorted find is (much) faster.
I Which is good, because that’s probably what you do most.
I Sorted add is (much) slower.
I Sorted remove is (much) slower.
I SortedPD addOrChangeEntry is the same.
I SortedPD removeEntry is the same.
How to predict running time.
I So what use is O(1) or O(log n), O(n), or O(n log n) if we don’t know that
constant, especially if it is a different constant in each case?
I We can measure the running time for one value of n and use that to
extrapolate the running time for another value of n. Here is how to do it.
I Suppose ArrayBasedPD.find takes 10 microseconds for n = 100.
I Since the running time t is in O(n), we have
I t = c · n
I 10 = c · 100
I c = 1/10
I How long will it take for n=1000?
I t = c · n
I t = 1/10 · 1000
I t = 100
I So the answer is 100 microseconds.
How to predict running time.
I So what use is O(1) or O(log n), O(n), or O(n log n) if we don’t know that
constant, especially if it is a different constant in each case?
I We can measure the running time for one value of n and use that to
extrapolate the running time for another value of n. Here is how to do it.
I Suppose ArrayBasedPD.find takes 10 microseconds for n = 100.
I Since the running time t is in O(n), we have
I t = c · n
I 10 = c · 100
I c = 1/10
I How long will it take for n=1000?
I t = c · n
I t = 1/10 · 1000
I t = 100
I So the answer is 100 microseconds.
How to predict running time.
I So what use is O(1) or O(log n), O(n), or O(n log n) if we don’t know that
constant, especially if it is a different constant in each case?
I We can measure the running time for one value of n and use that to
extrapolate the running time for another value of n. Here is how to do it.
I Suppose ArrayBasedPD.find takes 10 microseconds for n = 100.
I Since the running time t is in O(n), we have
I t = c · n
I 10 = c · 100
I c = 1/10
I How long will it take for n=1000?
I t = c · n
I t = 1/10 · 1000
I t = 100
I So the answer is 100 microseconds.
How to predict running time.
I So what use is O(1) or O(log n), O(n), or O(n log n) if we don’t know that
constant, especially if it is a different constant in each case?
I We can measure the running time for one value of n and use that to
extrapolate the running time for another value of n. Here is how to do it.
I Suppose ArrayBasedPD.find takes 10 microseconds for n = 100.
I Since the running time t is in O(n), we have
I t = c · n
I 10 = c · 100
I c = 1/10
I How long will it take for n=1000?
I t = c · n
I t = 1/10 · 1000
I t = 100
I So the answer is 100 microseconds.
How to predict running time.
I So what use is O(1) or O(log n), O(n), or O(n log n) if we don’t know that
constant, especially if it is a different constant in each case?
I We can measure the running time for one value of n and use that to
extrapolate the running time for another value of n. Here is how to do it.
I Suppose ArrayBasedPD.find takes 10 microseconds for n = 100.
I Since the running time t is in O(n), we have
I t = c · n
I 10 = c · 100
I c = 1/10
I How long will it take for n=1000?
I t = c · n
I t = 1/10 · 1000
I t = 100
I So the answer is 100 microseconds.
How to predict running time.
I So what use is O(1) or O(log n), O(n), or O(n log n) if we don’t know that
constant, especially if it is a different constant in each case?
I We can measure the running time for one value of n and use that to
extrapolate the running time for another value of n. Here is how to do it.
I Suppose ArrayBasedPD.find takes 10 microseconds for n = 100.
I Since the running time t is in O(n), we have
I t = c · n
I 10 = c · 100
I c = 1/10
I How long will it take for n=1000?
I t = c · n
I t = 1/10 · 1000
I t = 100
I So the answer is 100 microseconds.
How to predict running time.
I So what use is O(1) or O(log n), O(n), or O(n log n) if we don’t know that
constant, especially if it is a different constant in each case?
I We can measure the running time for one value of n and use that to
extrapolate the running time for another value of n. Here is how to do it.
I Suppose ArrayBasedPD.find takes 10 microseconds for n = 100.
I Since the running time t is in O(n), we have
I t = c · n
I 10 = c · 100
I c = 1/10
I How long will it take for n=1000?
I t = c · n
I t = 1/10 · 1000
I t = 100
I So the answer is 100 microseconds.
How to predict running time.
I So what use is O(1) or O(log n), O(n), or O(n log n) if we don’t know that
constant, especially if it is a different constant in each case?
I We can measure the running time for one value of n and use that to
extrapolate the running time for another value of n. Here is how to do it.
I Suppose ArrayBasedPD.find takes 10 microseconds for n = 100.
I Since the running time t is in O(n), we have
I t = c · n
I 10 = c · 100
I c = 1/10
I How long will it take for n=1000?
I t = c · n
I t = 1/10 · 1000
I t = 100
I So the answer is 100 microseconds.
How to predict running time.
I So what use is O(1) or O(log n), O(n), or O(n log n) if we don’t know that
constant, especially if it is a different constant in each case?
I We can measure the running time for one value of n and use that to
extrapolate the running time for another value of n. Here is how to do it.
I Suppose ArrayBasedPD.find takes 10 microseconds for n = 100.
I Since the running time t is in O(n), we have
I t = c · n
I 10 = c · 100
I c = 1/10
I How long will it take for n=1000?
I t = c · n
I t = 1/10 · 1000
I t = 100
I So the answer is 100 microseconds.
How to predict running time.
I So what use is O(1) or O(log n), O(n), or O(n log n) if we don’t know that
constant, especially if it is a different constant in each case?
I We can measure the running time for one value of n and use that to
extrapolate the running time for another value of n. Here is how to do it.
I Suppose ArrayBasedPD.find takes 10 microseconds for n = 100.
I Since the running time t is in O(n), we have
I t = c · n
I 10 = c · 100
I c = 1/10
I How long will it take for n=1000?
I t = c · n
I t = 1/10 · 1000
I t = 100
I So the answer is 100 microseconds.
How to predict running time.
I So what use is O(1) or O(log n), O(n), or O(n log n) if we don’t know that
constant, especially if it is a different constant in each case?
I We can measure the running time for one value of n and use that to
extrapolate the running time for another value of n. Here is how to do it.
I Suppose ArrayBasedPD.find takes 10 microseconds for n = 100.
I Since the running time t is in O(n), we have
I t = c · n
I 10 = c · 100
I c = 1/10
I How long will it take for n=1000?
I t = c · n
I t = 1/10 · 1000
I t = 100
I So the answer is 100 microseconds.
How to predict running time.
I So what use is O(1) or O(log n), O(n), or O(n log n) if we don’t know that
constant, especially if it is a different constant in each case?
I We can measure the running time for one value of n and use that to
extrapolate the running time for another value of n. Here is how to do it.
I Suppose ArrayBasedPD.find takes 10 microseconds for n = 100.
I Since the running time t is in O(n), we have
I t = c · n
I 10 = c · 100
I c = 1/10
I How long will it take for n=1000?
I t = c · n
I t = 1/10 · 1000
I t = 100
I So the answer is 100 microseconds.
How to predict running time.
I So what use is O(1) or O(log n), O(n), or O(n log n) if we don’t know that
constant, especially if it is a different constant in each case?
I We can measure the running time for one value of n and use that to
extrapolate the running time for another value of n. Here is how to do it.
I Suppose ArrayBasedPD.find takes 10 microseconds for n = 100.
I Since the running time t is in O(n), we have
I t = c · n
I 10 = c · 100
I c = 1/10
I How long will it take for n=1000?
I t = c · n
I t = 1/10 · 1000
I t = 100
I So the answer is 100 microseconds.
Another extrapolation
I Now suppose SortedPD.find takes 50 microseconds for n = 100.
I More complicated methods often take longer for small n.
I This is the same reason that you don’t drive your car to go next door.
I By the time you have opened the garage door, got in, started it up, etc.,
you will spend more time than just walking there.
I Since the running time is O(log n), we have
I t = c · log10 n
I 50 = c · log10 100
I 50 = c · 2
I c = 25
I Even though the original analysis of binary search was for log2 n, I can
use any base I want to because all logs differ by a constant factor.
I But you must use the same base for every log in the calculation.
I For n = 1000,
I t = c · log10 n
I t = 25 · log10 1000
I t = 25 · 3
I t = 75
I So 75 microseconds.
I Notice that I used the same log base 10. You can’t switch log bases in
the middle, or you will get a different (and wrong) answer.
Another extrapolation
I Now suppose SortedPD.find takes 50 microseconds for n = 100.
I More complicated methods often take longer for small n.
I This is the same reason that you don’t drive your car to go next door.
I By the time you have opened the garage door, got in, started it up, etc.,
you will spend more time than just walking there.
I Since the running time is O(log n), we have
I t = c · log10 n
I 50 = c · log10 100
I 50 = c · 2
I c = 25
I Even though the original analysis of binary search was for log2 n, I can
use any base I want to because all logs differ by a constant factor.
I But you must use the same base for every log in the calculation.
I For n = 1000,
I t = c · log10 n
I t = 25 · log10 1000
I t = 25 · 3
I t = 75
I So 75 microseconds.
I Notice that I used the same log base 10. You can’t switch log bases in
the middle, or you will get a different (and wrong) answer.
Another extrapolation
I Now suppose SortedPD.find takes 50 microseconds for n = 100.
I More complicated methods often take longer for small n.
I This is the same reason that you don’t drive your car to go next door.
I By the time you have opened the garage door, got in, started it up, etc.,
you will spend more time than just walking there.
I Since the running time is O(log n), we have
I t = c · log10 n
I 50 = c · log10 100
I 50 = c · 2
I c = 25
I Even though the original analysis of binary search was for log2 n, I can
use any base I want to because all logs differ by a constant factor.
I But you must use the same base for every log in the calculation.
I For n = 1000,
I t = c · log10 n
I t = 25 · log10 1000
I t = 25 · 3
I t = 75
I So 75 microseconds.
I Notice that I used the same log base 10. You can’t switch log bases in
the middle, or you will get a different (and wrong) answer.
Another extrapolation
I Now suppose SortedPD.find takes 50 microseconds for n = 100.
I More complicated methods often take longer for small n.
I This is the same reason that you don’t drive your car to go next door.
I By the time you have opened the garage door, got in, started it up, etc.,
you will spend more time than just walking there.
I Since the running time is O(log n), we have
I t = c · log10 n
I 50 = c · log10 100
I 50 = c · 2
I c = 25
I Even though the original analysis of binary search was for log2 n, I can
use any base I want to because all logs differ by a constant factor.
I But you must use the same base for every log in the calculation.
I For n = 1000,
I t = c · log10 n
I t = 25 · log10 1000
I t = 25 · 3
I t = 75
I So 75 microseconds.
I Notice that I used the same log base 10. You can’t switch log bases in
the middle, or you will get a different (and wrong) answer.
Another extrapolation
I Now suppose SortedPD.find takes 50 microseconds for n = 100.
I More complicated methods often take longer for small n.
I This is the same reason that you don’t drive your car to go next door.
I By the time you have opened the garage door, got in, started it up, etc.,
you will spend more time than just walking there.
I Since the running time is O(log n), we have
I t = c · log10 n
I 50 = c · log10 100
I 50 = c · 2
I c = 25
I Even though the original analysis of binary search was for log2 n, I can
use any base I want to because all logs differ by a constant factor.
I But you must use the same base for every log in the calculation.
I For n = 1000,
I t = c · log10 n
I t = 25 · log10 1000
I t = 25 · 3
I t = 75
I So 75 microseconds.
I Notice that I used the same log base 10. You can’t switch log bases in
the middle, or you will get a different (and wrong) answer.
Another extrapolation
I Now suppose SortedPD.find takes 50 microseconds for n = 100.
I More complicated methods often take longer for small n.
I This is the same reason that you don’t drive your car to go next door.
I By the time you have opened the garage door, got in, started it up, etc.,
you will spend more time than just walking there.
I Since the running time is O(log n), we have
I t = c · log10 n
I 50 = c · log10 100
I 50 = c · 2
I c = 25
I Even though the original analysis of binary search was for log2 n, I can
use any base I want to because all logs differ by a constant factor.
I But you must use the same base for every log in the calculation.
I For n = 1000,
I t = c · log10 n
I t = 25 · log10 1000
I t = 25 · 3
I t = 75
I So 75 microseconds.
I Notice that I used the same log base 10. You can’t switch log bases in
the middle, or you will get a different (and wrong) answer.
Another extrapolation
I Now suppose SortedPD.find takes 50 microseconds for n = 100.
I More complicated methods often take longer for small n.
I This is the same reason that you don’t drive your car to go next door.
I By the time you have opened the garage door, got in, started it up, etc.,
you will spend more time than just walking there.
I Since the running time is O(log n), we have
I t = c · log10 n
I 50 = c · log10 100
I 50 = c · 2
I c = 25
I Even though the original analysis of binary search was for log2 n, I can
use any base I want to because all logs differ by a constant factor.
I But you must use the same base for every log in the calculation.
I For n = 1000,
I t = c · log10 n
I t = 25 · log10 1000
I t = 25 · 3
I t = 75
I So 75 microseconds.
I Notice that I used the same log base 10. You can’t switch log bases in
the middle, or you will get a different (and wrong) answer.
Another extrapolation
I Now suppose SortedPD.find takes 50 microseconds for n = 100.
I More complicated methods often take longer for small n.
I This is the same reason that you don’t drive your car to go next door.
I By the time you have opened the garage door, got in, started it up, etc.,
you will spend more time than just walking there.
I Since the running time is O(log n), we have
I t = c · log10 n
I 50 = c · log10 100
I 50 = c · 2
I c = 25
I Even though the original analysis of binary search was for log2 n, I can
use any base I want to because all logs differ by a constant factor.
I But you must use the same base for every log in the calculation.
I For n = 1000,
I t = c · log10 n
I t = 25 · log10 1000
I t = 25 · 3
I t = 75
I So 75 microseconds.
I Notice that I used the same log base 10. You can’t switch log bases in
the middle, or you will get a different (and wrong) answer.
Another extrapolation
I Now suppose SortedPD.find takes 50 microseconds for n = 100.
I More complicated methods often take longer for small n.
I This is the same reason that you don’t drive your car to go next door.
I By the time you have opened the garage door, got in, started it up, etc.,
you will spend more time than just walking there.
I Since the running time is O(log n), we have
I t = c · log10 n
I 50 = c · log10 100
I 50 = c · 2
I c = 25
I Even though the original analysis of binary search was for log2 n, I can
use any base I want to because all logs differ by a constant factor.
I But you must use the same base for every log in the calculation.
I For n = 1000,
I t = c · log10 n
I t = 25 · log10 1000
I t = 25 · 3
I t = 75
I So 75 microseconds.
I Notice that I used the same log base 10. You can’t switch log bases in
the middle, or you will get a different (and wrong) answer.
Another extrapolation
I Now suppose SortedPD.find takes 50 microseconds for n = 100.
I More complicated methods often take longer for small n.
I This is the same reason that you don’t drive your car to go next door.
I By the time you have opened the garage door, got in, started it up, etc.,
you will spend more time than just walking there.
I Since the running time is O(log n), we have
I t = c · log10 n
I 50 = c · log10 100
I 50 = c · 2
I c = 25
I Even though the original analysis of binary search was for log2 n, I can
use any base I want to because all logs differ by a constant factor.
I But you must use the same base for every log in the calculation.
I For n = 1000,
I t = c · log10 n
I t = 25 · log10 1000
I t = 25 · 3
I t = 75
I So 75 microseconds.
I Notice that I used the same log base 10. You can’t switch log bases in
the middle, or you will get a different (and wrong) answer.
Another extrapolation
I Now suppose SortedPD.find takes 50 microseconds for n = 100.
I More complicated methods often take longer for small n.
I This is the same reason that you don’t drive your car to go next door.
I By the time you have opened the garage door, got in, started it up, etc.,
you will spend more time than just walking there.
I Since the running time is O(log n), we have
I t = c · log10 n
I 50 = c · log10 100
I 50 = c · 2
I c = 25
I Even though the original analysis of binary search was for log2 n, I can
use any base I want to because all logs differ by a constant factor.
I But you must use the same base for every log in the calculation.
I For n = 1000,
I t = c · log10 n
I t = 25 · log10 1000
I t = 25 · 3
I t = 75
I So 75 microseconds.
I Notice that I used the same log base 10. You can’t switch log bases in
the middle, or you will get a different (and wrong) answer.
Another extrapolation
I Now suppose SortedPD.find takes 50 microseconds for n = 100.
I More complicated methods often take longer for small n.
I This is the same reason that you don’t drive your car to go next door.
I By the time you have opened the garage door, got in, started it up, etc.,
you will spend more time than just walking there.
I Since the running time is O(log n), we have
I t = c · log10 n
I 50 = c · log10 100
I 50 = c · 2
I c = 25
I Even though the original analysis of binary search was for log2 n, I can
use any base I want to because all logs differ by a constant factor.
I But you must use the same base for every log in the calculation.
I For n = 1000,
I t = c · log10 n
I t = 25 · log10 1000
I t = 25 · 3
I t = 75
I So 75 microseconds.
I Notice that I used the same log base 10. You can’t switch log bases in
the middle, or you will get a different (and wrong) answer.
Another extrapolation
I Now suppose SortedPD.find takes 50 microseconds for n = 100.
I More complicated methods often take longer for small n.
I This is the same reason that you don’t drive your car to go next door.
I By the time you have opened the garage door, got in, started it up, etc.,
you will spend more time than just walking there.
I Since the running time is O(log n), we have
I t = c · log10 n
I 50 = c · log10 100
I 50 = c · 2
I c = 25
I Even though the original analysis of binary search was for log2 n, I can
use any base I want to because all logs differ by a constant factor.
I But you must use the same base for every log in the calculation.
I For n = 1000,
I t = c · log10 n
I t = 25 · log10 1000
I t = 25 · 3
I t = 75
I So 75 microseconds.
I Notice that I used the same log base 10. You can’t switch log bases in
the middle, or you will get a different (and wrong) answer.
Another extrapolation
I Now suppose SortedPD.find takes 50 microseconds for n = 100.
I More complicated methods often take longer for small n.
I This is the same reason that you don’t drive your car to go next door.
I By the time you have opened the garage door, got in, started it up, etc.,
you will spend more time than just walking there.
I Since the running time is O(log n), we have
I t = c · log10 n
I 50 = c · log10 100
I 50 = c · 2
I c = 25
I Even though the original analysis of binary search was for log2 n, I can
use any base I want to because all logs differ by a constant factor.
I But you must use the same base for every log in the calculation.
I For n = 1000,
I t = c · log10 n
I t = 25 · log10 1000
I t = 25 · 3
I t = 75
I So 75 microseconds.
I Notice that I used the same log base 10. You can’t switch log bases in
the middle, or you will get a different (and wrong) answer.
Another extrapolation
I Now suppose SortedPD.find takes 50 microseconds for n = 100.
I More complicated methods often take longer for small n.
I This is the same reason that you don’t drive your car to go next door.
I By the time you have opened the garage door, got in, started it up, etc.,
you will spend more time than just walking there.
I Since the running time is O(log n), we have
I t = c · log10 n
I 50 = c · log10 100
I 50 = c · 2
I c = 25
I Even though the original analysis of binary search was for log2 n, I can
use any base I want to because all logs differ by a constant factor.
I But you must use the same base for every log in the calculation.
I For n = 1000,
I t = c · log10 n
I t = 25 · log10 1000
I t = 25 · 3
I t = 75
I So 75 microseconds.
I Notice that I used the same log base 10. You can’t switch log bases in
the middle, or you will get a different (and wrong) answer.
Another extrapolation
I Now suppose SortedPD.find takes 50 microseconds for n = 100.
I More complicated methods often take longer for small n.
I This is the same reason that you don’t drive your car to go next door.
I By the time you have opened the garage door, got in, started it up, etc.,
you will spend more time than just walking there.
I Since the running time is O(log n), we have
I t = c · log10 n
I 50 = c · log10 100
I 50 = c · 2
I c = 25
I Even though the original analysis of binary search was for log2 n, I can
use any base I want to because all logs differ by a constant factor.
I But you must use the same base for every log in the calculation.
I For n = 1000,
I t = c · log10 n
I t = 25 · log10 1000
I t = 25 · 3
I t = 75
I So 75 microseconds.
I Notice that I used the same log base 10. You can’t switch log bases in
the middle, or you will get a different (and wrong) answer.
Another extrapolation
I Now suppose SortedPD.find takes 50 microseconds for n = 100.
I More complicated methods often take longer for small n.
I This is the same reason that you don’t drive your car to go next door.
I By the time you have opened the garage door, got in, started it up, etc.,
you will spend more time than just walking there.
I Since the running time is O(log n), we have
I t = c · log10 n
I 50 = c · log10 100
I 50 = c · 2
I c = 25
I Even though the original analysis of binary search was for log2 n, I can
use any base I want to because all logs differ by a constant factor.
I But you must use the same base for every log in the calculation.
I For n = 1000,
I t = c · log10 n
I t = 25 · log10 1000
I t = 25 · 3
I t = 75
I So 75 microseconds.
I Notice that I used the same log base 10. You can’t switch log bases in
the middle, or you will get a different (and wrong) answer.
Another extrapolation
I Now suppose SortedPD.find takes 50 microseconds for n = 100.
I More complicated methods often take longer for small n.
I This is the same reason that you don’t drive your car to go next door.
I By the time you have opened the garage door, got in, started it up, etc.,
you will spend more time than just walking there.
I Since the running time is O(log n), we have
I t = c · log10 n
I 50 = c · log10 100
I 50 = c · 2
I c = 25
I Even though the original analysis of binary search was for log2 n, I can
use any base I want to because all logs differ by a constant factor.
I But you must use the same base for every log in the calculation.
I For n = 1000,
I t = c · log10 n
I t = 25 · log10 1000
I t = 25 · 3
I t = 75
I So 75 microseconds.
I Notice that I used the same log base 10. You can’t switch log bases in
the middle, or you will get a different (and wrong) answer.
Another extrapolation
I Now suppose SortedPD.find takes 50 microseconds for n = 100.
I More complicated methods often take longer for small n.
I This is the same reason that you don’t drive your car to go next door.
I By the time you have opened the garage door, got in, started it up, etc.,
you will spend more time than just walking there.
I Since the running time is O(log n), we have
I t = c · log10 n
I 50 = c · log10 100
I 50 = c · 2
I c = 25
I Even though the original analysis of binary search was for log2 n, I can
use any base I want to because all logs differ by a constant factor.
I But you must use the same base for every log in the calculation.
I For n = 1000,
I t = c · log10 n
I t = 25 · log10 1000
I t = 25 · 3
I t = 75
I So 75 microseconds.
I Notice that I used the same log base 10. You can’t switch log bases in
the middle, or you will get a different (and wrong) answer.
I Here is the log base e version.
I Calculate c from first n and t :
I t = c · ln n
I 50 = c · ln 100
I 50 = c · 4.605
I c = 10.857
I Calculate t from second n:
I t = c · ln n
I t = 10.857 · ln 1000
I t = 10.857 · 6.9077
I t = 74.997
I Different log. Same answer!
I Here is the log base e version.
I Calculate c from first n and t :
I t = c · ln n
I 50 = c · ln 100
I 50 = c · 4.605
I c = 10.857
I Calculate t from second n:
I t = c · ln n
I t = 10.857 · ln 1000
I t = 10.857 · 6.9077
I t = 74.997
I Different log. Same answer!
I Here is the log base e version.
I Calculate c from first n and t :
I t = c · ln n
I 50 = c · ln 100
I 50 = c · 4.605
I c = 10.857
I Calculate t from second n:
I t = c · ln n
I t = 10.857 · ln 1000
I t = 10.857 · 6.9077
I t = 74.997
I Different log. Same answer!
I Here is the log base e version.
I Calculate c from first n and t :
I t = c · ln n
I 50 = c · ln 100
I 50 = c · 4.605
I c = 10.857
I Calculate t from second n:
I t = c · ln n
I t = 10.857 · ln 1000
I t = 10.857 · 6.9077
I t = 74.997
I Different log. Same answer!
I Here is the log base e version.
I Calculate c from first n and t :
I t = c · ln n
I 50 = c · ln 100
I 50 = c · 4.605
I c = 10.857
I Calculate t from second n:
I t = c · ln n
I t = 10.857 · ln 1000
I t = 10.857 · 6.9077
I t = 74.997
I Different log. Same answer!
I Here is the log base e version.
I Calculate c from first n and t :
I t = c · ln n
I 50 = c · ln 100
I 50 = c · 4.605
I c = 10.857
I Calculate t from second n:
I t = c · ln n
I t = 10.857 · ln 1000
I t = 10.857 · 6.9077
I t = 74.997
I Different log. Same answer!
I Here is the log base e version.
I Calculate c from first n and t :
I t = c · ln n
I 50 = c · ln 100
I 50 = c · 4.605
I c = 10.857
I Calculate t from second n:
I t = c · ln n
I t = 10.857 · ln 1000
I t = 10.857 · 6.9077
I t = 74.997
I Different log. Same answer!
I Here is the log base e version.
I Calculate c from first n and t :
I t = c · ln n
I 50 = c · ln 100
I 50 = c · 4.605
I c = 10.857
I Calculate t from second n:
I t = c · ln n
I t = 10.857 · ln 1000
I t = 10.857 · 6.9077
I t = 74.997
I Different log. Same answer!
I Here is the log base e version.
I Calculate c from first n and t :
I t = c · ln n
I 50 = c · ln 100
I 50 = c · 4.605
I c = 10.857
I Calculate t from second n:
I t = c · ln n
I t = 10.857 · ln 1000
I t = 10.857 · 6.9077
I t = 74.997
I Different log. Same answer!
I Here is the log base e version.
I Calculate c from first n and t :
I t = c · ln n
I 50 = c · ln 100
I 50 = c · 4.605
I c = 10.857
I Calculate t from second n:
I t = c · ln n
I t = 10.857 · ln 1000
I t = 10.857 · 6.9077
I t = 74.997
I Different log. Same answer!
I Here is the log base e version.
I Calculate c from first n and t :
I t = c · ln n
I 50 = c · ln 100
I 50 = c · 4.605
I c = 10.857
I Calculate t from second n:
I t = c · ln n
I t = 10.857 · ln 1000
I t = 10.857 · 6.9077
I t = 74.997
I Different log. Same answer!
I Here is the log base e version.
I Calculate c from first n and t :
I t = c · ln n
I 50 = c · ln 100
I 50 = c · 4.605
I c = 10.857
I Calculate t from second n:
I t = c · ln n
I t = 10.857 · ln 1000
I t = 10.857 · 6.9077
I t = 74.997
I Different log. Same answer!
I Here is the log base e version.
I Calculate c from first n and t :
I t = c · ln n
I 50 = c · ln 100
I 50 = c · 4.605
I c = 10.857
I Calculate t from second n:
I t = c · ln n
I t = 10.857 · ln 1000
I t = 10.857 · 6.9077
I t = 74.997
I Different log. Same answer!
I Let’s discuss this joke. In general the estimate is terrible and then gets
better and better. Why?
I Let’s say you do an experiment and it generates a number. It could be a
time or a mass or anything. Just something you can measure.
Unfortunately, the result is not very accurate. How can we increase the
accuracy?
I Answer: repeat the experiment many times and take the average.
http://xkcd.com/612/
I Let’s discuss this joke. In general the estimate is terrible and then gets
better and better. Why?
I Let’s say you do an experiment and it generates a number. It could be a
time or a mass or anything. Just something you can measure.
Unfortunately, the result is not very accurate. How can we increase the
accuracy?
I Answer: repeat the experiment many times and take the average.
http://xkcd.com/612/
I Let’s discuss this joke. In general the estimate is terrible and then gets
better and better. Why?
I Let’s say you do an experiment and it generates a number. It could be a
time or a mass or anything. Just something you can measure.
Unfortunately, the result is not very accurate. How can we increase the
accuracy?
I Answer: repeat the experiment many times and take the average.
http://xkcd.com/612/
I Let’s discuss this joke. In general the estimate is terrible and then gets
better and better. Why?
I Let’s say you do an experiment and it generates a number. It could be a
time or a mass or anything. Just something you can measure.
Unfortunately, the result is not very accurate. How can we increase the
accuracy?
I Answer: repeat the experiment many times and take the average.
http://xkcd.com/612/
How many times?
I Suppose I am willing to spend one second timing my program.
I If the time for one run is 50 microseconds, how many times can I run it in
one second?
I Did you figure out 20,000 times?
I What is the general formula?
I Run it for that many times and take the average.
I Let’s say it takes 1,010,203 microseconds seconds to run it 20,000
times.
I The average time 1010203 / 20000 = 50.51015 microseconds.
I Much more accurate. We can trust 5 digits (maybe).
How many times?
I Suppose I am willing to spend one second timing my program.
I If the time for one run is 50 microseconds, how many times can I run it in
one second?
I Did you figure out 20,000 times?
I What is the general formula?
I Run it for that many times and take the average.
I Let’s say it takes 1,010,203 microseconds seconds to run it 20,000
times.
I The average time 1010203 / 20000 = 50.51015 microseconds.
I Much more accurate. We can trust 5 digits (maybe).
How many times?
I Suppose I am willing to spend one second timing my program.
I If the time for one run is 50 microseconds, how many times can I run it in
one second?
I Did you figure out 20,000 times?
I What is the general formula?
I Run it for that many times and take the average.
I Let’s say it takes 1,010,203 microseconds seconds to run it 20,000
times.
I The average time 1010203 / 20000 = 50.51015 microseconds.
I Much more accurate. We can trust 5 digits (maybe).
How many times?
I Suppose I am willing to spend one second timing my program.
I If the time for one run is 50 microseconds, how many times can I run it in
one second?
I Did you figure out 20,000 times?
I What is the general formula?
I Run it for that many times and take the average.
I Let’s say it takes 1,010,203 microseconds seconds to run it 20,000
times.
I The average time 1010203 / 20000 = 50.51015 microseconds.
I Much more accurate. We can trust 5 digits (maybe).
How many times?
I Suppose I am willing to spend one second timing my program.
I If the time for one run is 50 microseconds, how many times can I run it in
one second?
I Did you figure out 20,000 times?
I What is the general formula?
I Run it for that many times and take the average.
I Let’s say it takes 1,010,203 microseconds seconds to run it 20,000
times.
I The average time 1010203 / 20000 = 50.51015 microseconds.
I Much more accurate. We can trust 5 digits (maybe).
How many times?
I Suppose I am willing to spend one second timing my program.
I If the time for one run is 50 microseconds, how many times can I run it in
one second?
I Did you figure out 20,000 times?
I What is the general formula?
I Run it for that many times and take the average.
I Let’s say it takes 1,010,203 microseconds seconds to run it 20,000
times.
I The average time 1010203 / 20000 = 50.51015 microseconds.
I Much more accurate. We can trust 5 digits (maybe).
How many times?
I Suppose I am willing to spend one second timing my program.
I If the time for one run is 50 microseconds, how many times can I run it in
one second?
I Did you figure out 20,000 times?
I What is the general formula?
I Run it for that many times and take the average.
I Let’s say it takes 1,010,203 microseconds seconds to run it 20,000
times.
I The average time 1010203 / 20000 = 50.51015 microseconds.
I Much more accurate. We can trust 5 digits (maybe).
How many times?
I Suppose I am willing to spend one second timing my program.
I If the time for one run is 50 microseconds, how many times can I run it in
one second?
I Did you figure out 20,000 times?
I What is the general formula?
I Run it for that many times and take the average.
I Let’s say it takes 1,010,203 microseconds seconds to run it 20,000
times.
I The average time 1010203 / 20000 = 50.51015 microseconds.
I Much more accurate. We can trust 5 digits (maybe).
How many times?
I Suppose I am willing to spend one second timing my program.
I If the time for one run is 50 microseconds, how many times can I run it in
one second?
I Did you figure out 20,000 times?
I What is the general formula?
I Run it for that many times and take the average.
I Let’s say it takes 1,010,203 microseconds seconds to run it 20,000
times.
I The average time 1010203 / 20000 = 50.51015 microseconds.
I Much more accurate. We can trust 5 digits (maybe).
Summary
I ArrayBasedPD and SortedPD find, addOrChangeEntry, and
removeEntry take different amounts of time,
I such as log2 n comparisons plus 2n array accesses for
SortedPD.removeEntry.
I O() (order) notation simplifies all of these to O(1), O(log n), or O(n).
I The O() running time of a method on one input can be used to predict its
running time on another input.
I Accurate predictions can make or break a business and save millions of
dollars.
I To improve the accuracy of a measurement, repeat it many times and
take an average.
I For example, run it once to get an approximate time. Figure out how
many times you can run it in one second. Run it that many times and
take the average running time.
Summary
I ArrayBasedPD and SortedPD find, addOrChangeEntry, and
removeEntry take different amounts of time,
I such as log2 n comparisons plus 2n array accesses for
SortedPD.removeEntry.
I O() (order) notation simplifies all of these to O(1), O(log n), or O(n).
I The O() running time of a method on one input can be used to predict its
running time on another input.
I Accurate predictions can make or break a business and save millions of
dollars.
I To improve the accuracy of a measurement, repeat it many times and
take an average.
I For example, run it once to get an approximate time. Figure out how
many times you can run it in one second. Run it that many times and
take the average running time.
Summary
I ArrayBasedPD and SortedPD find, addOrChangeEntry, and
removeEntry take different amounts of time,
I such as log2 n comparisons plus 2n array accesses for
SortedPD.removeEntry.
I O() (order) notation simplifies all of these to O(1), O(log n), or O(n).
I The O() running time of a method on one input can be used to predict its
running time on another input.
I Accurate predictions can make or break a business and save millions of
dollars.
I To improve the accuracy of a measurement, repeat it many times and
take an average.
I For example, run it once to get an approximate time. Figure out how
many times you can run it in one second. Run it that many times and
take the average running time.
Summary
I ArrayBasedPD and SortedPD find, addOrChangeEntry, and
removeEntry take different amounts of time,
I such as log2 n comparisons plus 2n array accesses for
SortedPD.removeEntry.
I O() (order) notation simplifies all of these to O(1), O(log n), or O(n).
I The O() running time of a method on one input can be used to predict its
running time on another input.
I Accurate predictions can make or break a business and save millions of
dollars.
I To improve the accuracy of a measurement, repeat it many times and
take an average.
I For example, run it once to get an approximate time. Figure out how
many times you can run it in one second. Run it that many times and
take the average running time.
Summary
I ArrayBasedPD and SortedPD find, addOrChangeEntry, and
removeEntry take different amounts of time,
I such as log2 n comparisons plus 2n array accesses for
SortedPD.removeEntry.
I O() (order) notation simplifies all of these to O(1), O(log n), or O(n).
I The O() running time of a method on one input can be used to predict its
running time on another input.
I Accurate predictions can make or break a business and save millions of
dollars.
I To improve the accuracy of a measurement, repeat it many times and
take an average.
I For example, run it once to get an approximate time. Figure out how
many times you can run it in one second. Run it that many times and
take the average running time.
Summary
I ArrayBasedPD and SortedPD find, addOrChangeEntry, and
removeEntry take different amounts of time,
I such as log2 n comparisons plus 2n array accesses for
SortedPD.removeEntry.
I O() (order) notation simplifies all of these to O(1), O(log n), or O(n).
I The O() running time of a method on one input can be used to predict its
running time on another input.
I Accurate predictions can make or break a business and save millions of
dollars.
I To improve the accuracy of a measurement, repeat it many times and
take an average.
I For example, run it once to get an approximate time. Figure out how
many times you can run it in one second. Run it that many times and
take the average running time.
Summary
I ArrayBasedPD and SortedPD find, addOrChangeEntry, and
removeEntry take different amounts of time,
I such as log2 n comparisons plus 2n array accesses for
SortedPD.removeEntry.
I O() (order) notation simplifies all of these to O(1), O(log n), or O(n).
I The O() running time of a method on one input can be used to predict its
running time on another input.
I Accurate predictions can make or break a business and save millions of
dollars.
I To improve the accuracy of a measurement, repeat it many times and
take an average.
I For example, run it once to get an approximate time. Figure out how
many times you can run it in one second. Run it that many times and
take the average running time.
Summary
I ArrayBasedPD and SortedPD find, addOrChangeEntry, and
removeEntry take different amounts of time,
I such as log2 n comparisons plus 2n array accesses for
SortedPD.removeEntry.
I O() (order) notation simplifies all of these to O(1), O(log n), or O(n).
I The O() running time of a method on one input can be used to predict its
running time on another input.
I Accurate predictions can make or break a business and save millions of
dollars.
I To improve the accuracy of a measurement, repeat it many times and
take an average.
I For example, run it once to get an approximate time. Figure out how
many times you can run it in one second. Run it that many times and
take the average running time.
prog06/prog04/.classpath
prog06/prog04/.project
prog04
org.eclipse.jdt.core.javabuilder
org.eclipse.jdt.core.javanature
prog06/prog04/DLLBasedPD.class
package prog04;
public synchronized class DLLBasedPD implements prog02.PhoneDirectory {
protected DLLEntry first;
protected DLLEntry last;
protected String sourceName;
public void DLLBasedPD();
public void loadData(String);
public void save();
public String addOrChangeEntry(String, String);
protected DLLEntry add(DLLEntry, DLLEntry);
protected DLLEntry find(String);
public String lookupEntry(String);
public String removeEntry(String);
}
prog06/prog04/DLLBasedPD.java
prog06/prog04/DLLBasedPD.java
package prog04;
import prog02.PhoneDirectory;
import java.io.*;
import java.util.Scanner;
/** This is an implementation of the prog02.PhoneDirectory interface
* that uses a doubly linked list to store the data.
* @author vjm
*/
public class DLLBasedPD implements PhoneDirectory {
/** The first entry and last entry of the linked list that stores
* the directory data */
protected DLLEntry first, last;
/** The data file that contains the directory data */
protected String sourceName = null;
/** Method to load the data file.
pre: The directory storage has been created and it is empty.
If the file exists, it consists of name-number pairs
on adjacent lines.
post: The data from the file is loaded into the directory.
@param sourceName The name of the data file
*/
public void loadData (String sourceName) {
// Remember the source name.
this.sourceName = sourceName;
try {
// Create a Scanner for the file.
Scanner in = new Scanner(new File(sourceName));
// Read each name and number and add the entry to the array.
while (in.hasNextLine()) {
String name = in.nextLine();
String number = in.nextLine();
// Add an entry for this name and number.
addOrChangeEntry(name, number);
}
// Close the file.
in.close();
} catch (FileNotFoundException ex) {
// Do nothing: no data to load.
return;
} catch (Exception ex) {
System.err.println("Load of directory failed.");
ex.printStackTrace();
System.exit(1);
}
}
/** Method to save the directory.
pre: The directory has been loaded with data.
post: Contents of directory written back to the file in the
form of name-number pairs on adjacent lines.
*/
public void save () {
try {
// Create PrintStream for the file.
PrintStream out = new PrintStream(new File(sourceName));
// EXERCISE
// Write each directory entry to the file.
for ( DLLEntry entry=first ; entry!=null; entry=entry.getNext() ) {
// Write the name.
out.println(entry.getName());
out.println(entry.getNumber());
// EXERCISE
// Write the number.
}
// Close the file.
out.close();
} catch (Exception ex) {
System.err.println("Save of directory failed");
ex.printStackTrace();
System.exit(1);
}
}
/** Add an entry or change an existing entry.
@param name The name of the person being added or changed
@param number The new number to be assigned
@return The old number or, if a new entry, null
*/
public String addOrChangeEntry (String name, String number) {
DLLEntry entry = find(name);
if (entry != null && entry.getName().equals(name)) {
String oldNumber = entry.getNumber();
entry.setNumber(number);
return oldNumber;
}
else {
add(entry, new DLLEntry(name, number));
return null;
}
}
/** Add a new entry at a location.
@param previousORnext The entry right before or right after
where the new entry should go. null for empty list.
@param newEntry The new entry to be added.
@return the new entry
*/
protected DLLEntry add (DLLEntry previousORnext, DLLEntry newEntry) {
// Add entry to the end of the list. (Ignore previousORnext.)
// What do you do if the list is empty? (Easy!)
// What do you do if the list is not empty? (Tuesday lecture.)
// EXERCISE
if (first==null) {
first=newEntry;
last=newEntry;
}
else {
// add name from previous new entry will equal the place of the new entry
last.setNext(newEntry);
newEntry.setPrevious(last);
last=newEntry;
}
return newEntry;
}
/** Find an entry in the directory.
@param name The name to be found
@return The entry with the same name or the entry right before
or right after where the entry should be. null for an empty
list.
*/
protected DLLEntry find (String name) {
// EXERCISE// For each entry in the directory.
// What is the first? What is the next? How do you know you got them all?
// If this is the entry you want
for(DLLEntry entry=first;entry!=null;entry=entry.getNext()) {
if (entry.getName()==name) {
return entry;
}
else if (entry.getName()!=name) {
return null;
}
// Name not found. It should go at the end.
}
return last;
}
/** Look up an entry.
@param name The name of the person
@return The number. If not in the directory, null is returned
*/
public String lookupEntry (String name) {
DLLEntry entry = find(name);
if (entry != null && entry.getName().equals(name))
return entry.getNumber();
return null;
}
/** Remove an entry from the directory.
@param name The name of the person to be removed
@return The current number. If not in directory, null is
returned
*/
public String removeEntry (String name) {
// Call find to find the entry to remove.
DLLEntry entry = find(name);
// EXERCISE
if (entry==null || entry.getName()==null) {
return null;
}
// If it is not there, return null.
// If there is only one entry (how can you tell?) what do you do?
if (last==first && first==last) {
last=null;
first=null;
}
// If entry is the first entry?
else if (first==entry.getNext()) {
first.setPrevious(null);
first=first.getNext();
first.setPrevious(null);
}
// If entry is the last entry?
else if (last==entry.getPrevious()) {
last.setNext(null);
last= last.getPrevious();
last.setNext(null);
}
else {
DLLEntry previous=entry.getPrevious();
DLLEntry next=entry.getNext();
// Get the previous and next entry.
// Two more lines!
next.setPrevious(previous);
previous.setNext(next);
}
return entry.getNumber();
}
}
prog06/prog04/dllbasedpd.txt
jmin220 Joanna Minott
list is empty and last is null
Calling add(null, Bob:555)
list is Bob:555, and last is Bob:555
list is Ian:412, and last is Ian:412
Calling add(Ian:412, Bob:555)
list is Ian:412, Bob:555, and last is Bob:555
list is Ian:412, and last is Ian:412
Calling add(Ian:412, Vic:777)
list is Ian:412, Vic:777, and last is Vic:777
list is Bob:555, Ian:412, and last is Ian:412
Calling add(Bob:555, Ann:123)
list is Bob:555, Ian:412, Ann:123, and last is Ann:123
list is Bob:555, Ian:412, and last is Ian:412
Calling add(Bob:555, Eve:321)
list is Bob:555, Ian:412, Eve:321, and last is Eve:321
list is Bob:555, Ian:412, and last is Ian:412
Calling add(Ian:412, Eve:321)
list is Bob:555, Ian:412, Eve:321, and last is Eve:321
list is Bob:555, Ian:412, and last is Ian:412
Calling add(Ian:412, Zoe:606)
list is Bob:555, Ian:412, Zoe:606, and last is Zoe:606
list is empty and last is null
find(Bob) returns
null
list is Bob:555, and last is Bob:555
find(Ann) returns
null
java.lang.NullPointerException
find failed: -10
list is empty and last is null
Calling removeEntry(Bob)
removeEntry returns null
list is empty and last is null
list is Bob:555, and last is Bob:555
Calling removeEntry(Bob)
removeEntry returns 555
list is empty and last is null
list is Bob:555, and last is Bob:555
Calling removeEntry(Ann)
removeEntry returns null
list is Bob:555, and last is Bob:555
list is Bob:555, Ian:412, and last is Ian:412
Calling removeEntry(Bob)
java.lang.NullPointerException
removeEntry failed: -20
LAB SCORE: 10
HW SCORE: 0
prog06/prog04/DLLEntry.class
package prog04;
public synchronized class DLLEntry extends prog02.DirectoryEntry {
private DLLEntry next;
private DLLEntry previous;
public void DLLEntry(String, String);
public DLLEntry getNext();
public void setNext(DLLEntry);
public DLLEntry getPrevious();
public void setPrevious(DLLEntry);
}
prog06/prog04/DLLEntry.java
prog06/prog04/DLLEntry.java
package prog04;
import prog02.DirectoryEntry;
/** Entry in doubly linked list
*/
public class DLLEntry extends DirectoryEntry {
/** Creates a new instance of DLLEntry
@param name name of person
@param number number of person
*/
public DLLEntry (String name, String number) {
super(name, number);
}
/** The next entry in the list. */
private DLLEntry next;
/** The previous entry in the list. */
private DLLEntry previous;
/** Gets the next entry in the list.
@return the next entry
*/
public DLLEntry getNext () {
return next;
}
/** Sets the next entry in the list.
@param next the new next entry
*/
public void setNext (DLLEntry next) {
this.next = next;
}
/** Gets the previous entry in the list.
@return the previous entry
*/
public DLLEntry getPrevious () {
return previous;
}
/** Sets the previous entry in the list.
@param previous the new previous entry
*/
public void setPrevious (DLLEntry previous) {
this.previous = previous;
}
}
prog06/prog04/lab.txt
If you are having any problems, draw a diagram for the TA and show him
or her what you are trying to do. You need to figure out as much for
yourself as possible.
0. I put prog04 into your src (Box) folder. In Eclipse, copy and
pasted Main.java from prog02 into prog04. It should automatically put
package prog04;
at the top of Main.java, but if it doesn't, fix it. After that, add the lines
import prog02.UserInterface;
import prog02.GUI;
import prog02.ConsoleUI;
import prog02.PhoneDirectory;
Change the initialization of pd in main to
PhoneDirectory pd = new DLLBasedPD();
1. Read DLLBasedPD.java up to save(). In save(), fill in the missing
parts of the output loop.
2. In add(), add the new entry to the end of the list.
Test your program by modifying and running Main. Add a new entry
and make sure it appears in csc220.txt.
When you think you have it right, run TestDLLBasedPD.javat. find
and remove will fail because you have not done them yet.
3. Finish find(). Test.
HOMEWORK
4. Finish removeEntry(). Remember: if the name is not there, then
find will return null or an entry with a different name. Test.
5. Change Main to use SortedDLLPD. In Eclipse, create a SortedDLLPD
class in package prog04 that extends DLLBasedPD. Copy the
following methods AND THEIR JAVADOC to SortedDLLPD: add and find.
6. Modify add to pay attention to the value of previousORnext.
If it is null, adding is easy.
If it is not null, you have to do a comparison to determine if
previousORnext is previous or next. Set previous or next to
previousORnext and set next or previous using the getNext() or
getPrevious method of DLLEntry.
Add newEntry to the list. Be careful: there are special cases if
previous or next is null meaning it should be added first or last.
Test using TestSortedDLLPD.java. find will fail because you have
not done it yet.
7. Modify find so it returns the entry just before or just after the
name if the name isn't there. Test.
8. Copy and paste TestUI from prog02. Fix any mistakes you still have
in Main.
prog06/prog04/Main.class
package prog04;
public synchronized class Main {
public void Main();
public static void processCommands(String, prog02.UserInterface, prog02.PhoneDirectory);
public static void main(String[]);
}
prog06/prog04/Main.java
prog06/prog04/Main.java
package prog04;
import prog02.GUI;
import prog02.PhoneDirectory;
import prog02.UserInterface;
public class Main {
/** Processes user's commands on a phone directory.
@param fn The file containing the phone directory.
@param ui The UserInterface object to use
to talk to the user.
@param pd The PhoneDirectory object to use
to process the phone directory.
*/
public static void processCommands(String fn, UserInterface ui, PhoneDirectory pd) {
pd.loadData(fn);
String[] commands = {
"Add/Change Entry",
"Look Up Entry",
"Remove Entry",
"Save Directory",
"Exit"};
String name, number;
while (true) {
int c = ui.getCommand(commands);
switch (c) {
case -1:
ui.sendMessage("You shut down the program, restarting. Use Exit to exit.");
break;
case 0:
name = ui.getInfo("Enter name");
number = ui.getInfo("Enter number");
pd.addOrChangeEntry(name, number);
break;
case 1:
name = ui.getInfo("Enter name");
number = pd.lookupEntry(name);
ui.sendMessage("The number for " + name + " is " + number);
break;
case 2:
name = ui.getInfo("Enter name");
number = pd.removeEntry(name);
break;
case 3:
pd.save();
ui.sendMessage("You have saved the directory");
break;
case 4:
String[] options = {"no",
"yes"};
ui.sendMessage("Do you really want to exit? press ok to continue.");
int d=ui.getCommand(options);
switch (d) {
case 0:
break;
case 1:
return;
}
}
}
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
String fn = "csc220.txt";
// PhoneDirectory pd = new SortedPD();
PhoneDirectory pd = new SortedDLLPD();
UserInterface ui = new GUI("Phone Directory");
processCommands(fn, ui, pd);
}
}
prog06/prog04/main.txt
jmin220 Joanna Minott
case 1:
Enter name
? Fred
ERROR (-3 points): message contains null.
The number for Fred is null
case 1:
Enter name
? Victor
The number for Victor is [email protected]
case 2:
Enter name
? Victor
Exception in thread "main" java.lang.NullPointerException
at prog04.DLLBasedPD.removeEntry(DLLBasedPD.java:228)
at prog04.Main.processCommands(Main.java:46)
at prog04.TestUI.main(TestUI.java:82)
pd.loadData(fn);
pd.addOrChangeEntry(name, number);
number = pd.lookupEntry(name);
number = pd.removeEntry(name);
pd.save();
SCORE: 5
prog06/prog04/MainBB.class
package prog04;
public synchronized class MainBB {
public void MainBB();
public static void processCommands(String, prog02.UserInterface, prog02.PhoneDirectory);
public static void main(String[]);
}
prog06/prog04/MainBB.java
prog06/prog04/MainBB.java
package prog04;
import prog02.UserInterface;
import prog02.GUI;
import prog02.ConsoleUI;
import prog02.PhoneDirectory;
/**
* A program to query and modify the phone directory stored in csc220.txt.
* @author vjm
*/
public class MainBB {
/** Processes user's commands on a phone directory.
@param fn The file containing the phone directory.
@param ui The UserInterface object to use
to talk to the user.
@param pd The PhoneDirectory object to use
to process the phone directory.
*/
public static void processCommands(String fn, UserInterface ui, PhoneDirectory pd) {
pd.loadData(fn);
String[] commands = {
"Add/Change Entry",
"Look Up Entry",
"Remove Entry",
"Save Directory",
"Exit"};
String name, number, oldNumber;
while (true) {
int c = ui.getCommand(commands);
switch (c) {
case -1:
ui.sendMessage("You shut down the program, restarting. Use Exit to exit.");
break;
case 0:
name = ui.getInfo("Enter name");
number = ui.getInfo("Enter number");
pd.addOrChangeEntry(name, number);
break;
case 1:
name = ui.getInfo("Enter name");
number = pd.lookupEntry(name);
ui.sendMessage("The number for " + name + " is " + number);
break;
case 2:
name = ui.getInfo("Enter name");
number = pd.removeEntry(name);
break;
case 3:
pd.save();
ui.sendMessage("You have saved the directory");
break;
case 4:
String[] options = {"no",
"yes"};
ui.sendMessage("Do you really want to exit? press ok to continue.");
int d=ui.getCommand(options);
switch (d) {
case 0:
break;
case 1:
return;
}
}
}
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
String fn = "csc220.txt";
// PhoneDirectory pd = new SortedPD();
PhoneDirectory pd = new SortedDLLPD();
UserInterface ui = new GUI("Phone Directory");
processCommands(fn, ui, pd);
}
}
prog06/prog04/SortedDLLPD.class
package prog04;
public synchronized class SortedDLLPD extends DLLBasedPD {
public void SortedDLLPD();
protected DLLEntry add(DLLEntry, DLLEntry);
protected DLLEntry find(String);
}
prog06/prog04/SortedDLLPD.java
prog06/prog04/SortedDLLPD.java
package prog04;
public class SortedDLLPD extends DLLBasedPD {
protected DLLEntry add (DLLEntry previousORnext, DLLEntry newEntry) {
// Add entry to the end of the list. (Ignore previousORnext.)
// What do you do if the list is empty? (Easy!)
if (previousORnext!=null) {
int dd= newEntry.getName().compareTo(previousORnext.getName());
if( dd<0){
newEntry.setNext(previousORnext);
newEntry.setPrevious(previousORnext.getNext());
}
else if (dd>0) {
newEntry.setPrevious(previousORnext);
newEntry.setNext(previousORnext.getPrevious());
}
}
if (first==null&&last==null) {
first=newEntry;
last=newEntry;
}
else if (newEntry.getNext()==null)
{
last.setNext(newEntry);
last=newEntry;
}
else if (newEntry.getPrevious()==null) {
first.setPrevious(newEntry);
first=newEntry;
}
else
{
newEntry.getNext().setPrevious(newEntry);
newEntry.getPrevious().setNext(newEntry);
}
return newEntry;
}
/** Find an entry in the directory.
@param name The name to be found
@return The entry with the same name or the entry right before
or right after where the entry should be. null for an empty
list.
*/
protected DLLEntry find (String name) {
// EXERCISE
for(DLLEntry entry=first;entry!=null;entry=entry.getNext()) {
if (entry.getName()==name) {
return entry;
}
else if (entry.getName()!=name) {
return last;
}
}
// For each entry in the directory.
// What is the first? What is the next? How do you know you got them all?
// If this is the entry you want
// return it.
return last ;
// Name not found. It should go at the end.
}
}
prog06/prog04/sorteddllpd.txt
jmin220 Joanna Minott
list is empty and last is null
Calling add(null, Ann:123)
list is Ann:123, and last is Ann:123
list is Ian:412, and last is Ian:412
Calling add(Ian:412, Ann:123)
list is Ann:123, Ian:412, and last is Ian:412
list is Ian:412, and last is Ian:412
Calling add(Ian:412, Zoe:321)
list is Ian:412, Zoe:321, and last is Zoe:321
list is Sue:555, Ian:412, and last is Ian:412
Calling add(Sue:555, Ann:123)
list is Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123, Sue:555, Ian:412, Ann:123,
CIRCULAR LIST
prog06/prog04/TestDLLBasedPD.class
package prog04;
public synchronized class TestDLLBasedPD extends DLLBasedPD {
String[][][] addIn;
String[] addLoc;
String[][] addEntry;
String[][][] addOut;
String[][][] findIn;
String[] findName;
String[] findOutName;
String[][][] removeIn;
String[] removeName;
String[][][] removeOut;
String[] removeVal;
public void TestDLLBasedPD();
public static void main(String[]);
void test();
boolean testAdd();
boolean testAdd(int);
void setList(String[][]);
DLLEntry getLoc(String);
void printList();
String str(DLLEntry);
boolean checkList(String[][]);
boolean testFind();
boolean testFind(int);
boolean testRemove();
boolean testRemove(int);
}
prog06/prog04/TestDLLBasedPD.java
prog06/prog04/TestDLLBasedPD.java
package prog04;
public class TestDLLBasedPD extends DLLBasedPD {
public static void main (String[] args) {
TestDLLBasedPD test = new TestDLLBasedPD();
test.test();
}
void test () {
int labscore = 20;
if (!testAdd()) {
System.out.println("add failed: -10");
labscore -= 10;
}
if (!testFind()) {
System.out.println("find failed: -10");
labscore -= 10;
}
int hwscore = 20;
if (!testRemove()) {
System.out.println("removeEntry failed: -20");
hwscore -= 20;
}
System.out.println("LAB SCORE: " + labscore);
System.out.println("HW SCORE: " + hwscore);
}
String[][][] addIn = { { },
{ { "Ian", "412" } },
{ { "Ian", "412" } },
{ { "Bob", "555" }, { "Ian", "412" } },
{ { "Bob", "555" }, { "Ian", "412" } },
{ { "Bob", "555" }, { "Ian", "412" } },
{ { "Bob", "555" }, { "Ian", "412" } } };
String[] addLoc = { null, "Ian", "Ian", "Bob", "Bob", "Ian", "Ian" };
String[][] addEntry = { { "Bob", "555" },
{ "Bob", "555" },
{ "Vic", "777" },
{ "Ann", "123" },
{ "Eve", "321" },
{ "Eve", "321" },
{ "Zoe", "606" } };
String[][][] addOut = { { { "Bob", "555" } },
{ { "Ian", "412" }, { "Bob", "555" } },
{ { "Ian", "412" }, { "Vic", "777" } },
{ { "Bob", "555" }, { "Ian", "412" }, { "Ann", "123" } },
{ { "Bob", "555" }, { "Ian", "412" }, { "Eve", "321" } },
{ { "Bob", "555" }, { "Ian", "412" }, { "Eve", "321" } },
{ { "Bob", "555" }, { "Ian", "412" }, { "Zoe", "606" } } };
boolean testAdd () {
for (int i = 0; i < addIn.length; i++) {
try {
if (!testAdd(i))
return false;
} catch (Exception e) {
System.out.println(e);
return false;
}
System.out.println();
}
return true;
}
boolean testAdd (int i) {
setList(addIn[i]);
printList();
DLLEntry location = getLoc(addLoc[i]);
DLLEntry newEntry = new DLLEntry(addEntry[i][0], addEntry[i][1]);
System.out.println("Calling add(" + str(location) + ", " + str(newEntry) + ")");
add(location, newEntry);
printList();
return checkList(addOut[i]);
}
void setList (String[][] list) {
first = last = null;
for (String[] nn : list) {
DLLEntry entry = new DLLEntry(nn[0], nn[1]);
if (first == null) {
first = last = entry;
}
else {
last.setNext(entry);
entry.setPrevious(last);
last = entry;
}
}
}
DLLEntry getLoc (String name) {
if (name == null)
return null;
for (DLLEntry entry = first; entry != null; entry = entry.getNext())
if (entry.getName().equals(name))
return entry;
return null;
}
void printList () {
System.out.print("list is ");
if (first == null)
System.out.print("empty ");
else
for (DLLEntry entry = first; entry != null; entry = entry.getNext())
System.out.print(str(entry) + ", ");
System.out.println("and last is " + str(last));
}
String str (DLLEntry entry) {
if (entry == null)
return "null";
else
return entry.getName() + ":" + entry.getNumber();
}
boolean checkList (String[][] list) {
if (list.length == 0)
return first == null && last == null;
int i = 0;
for (DLLEntry entry = first; entry != null; entry = entry.getNext())
if (!entry.getName().equals(list[i++][0]))
return false;
if (last == null || !last.getName().equals(list[list.length-1][0]))
return false;
return true;
}
String[][][] findIn = { { },
{ { "Bob", "555" } },
{ { "Bob", "555" } },
{ { "Bob", "555" } },
{ { "Ian", "412" }, { "Bob", "555" } },
{ { "Ian", "412" }, { "Bob", "555" } },
{ { "Ian", "412" }, { "Bob", "555" } },
{ { "Ian", "412" }, { "Bob", "555" } },
{ { "Ian", "412" }, { "Bob", "555" } },
{ { "Ian", "412" }, { "Ann", "123" }, { "Bob", "555" } },
{ { "Ian", "412" }, { "Ann", "123" }, { "Bob", "555" } },
{ { "Ian", "412" }, { "Ann", "123" }, { "Bob", "555" } },
{ { "Ian", "412" }, { "Ann", "123" }, { "Bob", "555" } },
{ { "Ian", "412" }, { "Ann", "123" }, { "Bob", "555" } },
{ { "Ian", "412" }, { "Ann", "123" }, { "Bob", "555" } },
{ { "Ian", "412" }, { "Ann", "123" }, { "Bob", "555" } } };
String[] findName = { "Bob", "Ann", "Bob", "Eve", "Ann", "Ian", "Moe", "Bob", "Zoe", "Abe", "Ian", "Joe", "Ann", "Bab", "Bob", "Boo" };
String[] findOutName = { null, "Bob", "Bob", "Bob", "Bob", "Ian", "Bob", "Bob", "Bob", "Bob", "Ian", "Bob", "Ann", "Bob", "Bob", "Bob" };
boolean testFind () {
for (int i = 0; i < findIn.length; i++) {
try {
if (!testFind(i))
return false;
} catch (Exception e) {
System.out.println(e);
return false;
}
System.out.println();
}
return true;
}
boolean testFind (int i) {
setList(findIn[i]);
printList();
String name = findName[i];
System.out.println("find(" + name + ") returns ");
DLLEntry entry = find(name);
System.out.println(str(entry));
if (findOutName[i] == null)
return entry == null;
else
return entry.getName().equals(findOutName[i]);
}
String[][][] removeIn = { { },
{ { "Bob", "555" } },
{ { "Bob", "555" } },
{ { "Bob", "555" }, { "Ian", "412" } },
{ { "Bob", "555" }, { "Ian", "412" } },
{ { "Bob", "555" }, { "Ian", "412" } },
{ { "Ian", "412" }, { "Ann", "123" }, { "Bob", "555" } },
{ { "Ian", "412" }, { "Ann", "123" }, { "Bob", "555" } },
{ { "Ian", "412" }, { "Ann", "123" }, { "Bob", "555" } },
{ { "Ian", "412" }, { "Ann", "123" }, { "Bob", "555" } } };
String[] removeName = { "Bob", "Bob", "Ann", "Bob", "Ian", "Ann", "Ian", "Ann", "Bob", "Joe" };
String[][][] removeOut = { { },
{ },
{ { "Bob", "555" } },
{ { "Ian", "412" } },
{ { "Bob", "555" } },
{ { "Bob", "555" }, { "Ian", "412" } },
{ { "Ann", "123" }, { "Bob", "555" } },
{ { "Ian", "412" }, { "Bob", "555" } },
{ { "Ian", "412" }, { "Ann", "123" } },
{ { "Ian", "412" }, { "Ann", "123" }, { "Bob", "555" } } };
String[] removeVal = { null, "555", null, "555", "412", null, "412", "123", "555", null };
boolean testRemove () {
for (int i = 0; i < removeIn.length; i++) {
try {
if (!testRemove(i))
return false;
} catch (Exception e) {
System.out.println(e);
return false;
}
System.out.println();
}
return true;
}
boolean testRemove (int i) {
setList(removeIn[i]);
printList();
String name = removeName[i];
System.out.println("Calling removeEntry(" + name + ")");
String val = removeEntry(name);
System.out.println("removeEntry returns " + val);
printList();
if (!checkList(removeOut[i]))
return false;
if (removeVal[i] == null)
return val == null;
return val.equals(removeVal[i]);
}
}
prog06/prog04/TestSortedDLLPD.class
package prog04;
public synchronized class TestSortedDLLPD extends SortedDLLPD {
String[][][] addIn;
String[] addLoc;
String[][] addEntry;
String[][][] addOut;
String[][][] findIn;
String[] findName;
String[] findOutName;
public void TestSortedDLLPD();
public static void main(String[]);
void test();
boolean testAdd();
boolean testAdd(int);
void setList(String[][]);
DLLEntry getLoc(String);
void printList();
String str(DLLEntry);
boolean checkList(String[][]);
boolean testFind();
boolean testFind(int);
}
prog06/prog04/TestSortedDLLPD.java
prog06/prog04/TestSortedDLLPD.java
package prog04;
public class TestSortedDLLPD extends SortedDLLPD {
public static void main (String[] args) {
TestSortedDLLPD test = new TestSortedDLLPD();
test.test();
}
void test () {
int score = 40;
if (!testAdd()) {
System.out.println("add failed: -20");
score -= 10;
}
if (!testFind()) {
System.out.println("find failed: -20");
score -= 10;
}
System.out.println("SCORE: " + score);
}
String[][][] addIn = { { },
{ { "Ian", "412" } },
{ { "Ian", "412" } },
{ { "Sue", "555" }, { "Ian", "412" } },
{ { "Sue", "555" }, { "Ian", "412" } },
{ { "Sue", "555" }, { "Ian", "412" } },
{ { "Sue", "555" }, { "Ian", "412" } },
{ { "Sue", "555" }, { "Moe", "848" }, { "Ian", "412" } },
{ { "Sue", "555" }, { "Moe", "848" }, { "Ian", "412" } },
{ { "Sue", "555" }, { "Moe", "848" }, { "Ian", "412" } },
{ { "Sue", "555" }, { "Moe", "848" }, { "Ian", "412" } },
{ { "Sue", "555" }, { "Moe", "848" }, { "Ian", "412" } },
{ { "Sue", "555" }, { "Moe", "848" }, { "Ian", "412" } } };
String[] addLoc = { null, "Ian", "Ian", "Sue", "Sue", "Ian", "Ian", "Sue", "Sue", "Moe", "Moe", "Ian", "Ian" };
String[][] addEntry = { { "Ann", "123" },
{ "Ann", "123" },
{ "Zoe", "321" },
{ "Ann", "123" },
{ "Zoe", "321" },
{ "Ann", "321" },
{ "Zoe", "606" },
{ "Ann", "321" },
{ "Zoe", "606" },
{ "Ann", "321" },
{ "Zoe", "606" },
{ "Ann", "321" },
{ "Zoe", "606" },
{ "Ann", "321" },
{ "Zoe", "606" },
{ "Ann", "321" },
{ "Zoe", "606" },
{ "Ann", "321" },
{ "Zoe", "606" } };
String[][][] addOut = { { { "Ann", "321" } },
{ { "Ann", "321" }, { "Ian", "412" } },
{ { "Ian", "412" }, { "Zoe", "606" } },
{ { "Ann", "321" }, { "Sue", "555" }, { "Ian", "412" } },
{ { "Sue", "555" }, { "Zoe", "606" }, { "Ian", "412" } },
{ { "Sue", "555" }, { "Ann", "321" }, { "Ian", "412" } },
{ { "Sue", "555" }, { "Ian", "412" }, { "Zoe", "606" } },
{ { "Ann", "321" }, { "Sue", "555" }, { "Moe", "848" }, { "Ian", "412" } },
{ { "Sue", "555" }, { "Zoe", "606" }, { "Moe", "848" }, { "Ian", "412" } },
{ { "Sue", "555" }, { "Ann", "321" }, { "Moe", "848" }, { "Ian", "412" } },
{ { "Sue", "555" }, { "Moe", "848" }, { "Zoe", "606" }, { "Ian", "412" } },
{ { "Sue", "555" }, { "Moe", "848" }, { "Ann", "321" }, { "Ian", "412" } },
{ { "Sue", "555" }, { "Moe", "848" }, { "Ian", "412" }, { "Zoe", "606" } } };
boolean testAdd () {
for (int i = 0; i < addIn.length; i++) {
try {
if (!testAdd(i))
return false;
} catch (Exception e) {
System.out.println(e);
return false;
}
System.out.println();
}
return true;
}
boolean testAdd (int i) {
setList(addIn[i]);
printList();
DLLEntry location = getLoc(addLoc[i]);
DLLEntry newEntry = new DLLEntry(addEntry[i][0], addEntry[i][1]);
System.out.println("Calling add(" + str(location) + ", " + str(newEntry) + ")");
add(location, newEntry);
printList();
return checkList(addOut[i]);
}
void setList (String[][] list) {
first = last = null;
for (String[] nn : list) {
DLLEntry entry = new DLLEntry(nn[0], nn[1]);
if (first == null) {
first = last = entry;
}
else {
last.setNext(entry);
entry.setPrevious(last);
last = entry;
}
}
}
DLLEntry getLoc (String name) {
if (name == null)
return null;
for (DLLEntry entry = first; entry != null; entry = entry.getNext())
if (entry.getName().equals(name))
return entry;
return null;
}
void printList () {
System.out.print("list is ");
if (first == null)
System.out.print("empty ");
else
for (DLLEntry entry = first; entry != null; entry = entry.getNext())
System.out.print(str(entry) + ", ");
System.out.println("and last is " + str(last));
}
String str (DLLEntry entry) {
if (entry == null)
return "null";
else
return entry.getName() + ":" + entry.getNumber();
}
boolean checkList (String[][] list) {
if (list.length == 0)
return first == null && last == null;
int i = 0;
for (DLLEntry entry = first; entry != null; entry = entry.getNext())
if (!entry.getName().equals(list[i++][0]))
return false;
if (last == null || !last.getName().equals(list[list.length-1][0]))
return false;
return true;
}
String[][][] findIn = { { },
{ { "Bob", "555" } },
{ { "Bob", "555" } },
{ { "Bob", "555" } },
{ { "Bob", "555" }, { "Ian", "412" } },
{ { "Bob", "555" }, { "Ian", "412" } },
{ { "Bob", "555" }, { "Ian", "412" } },
{ { "Bob", "555" }, { "Ian", "412" } },
{ { "Bob", "555" }, { "Ian", "412" } },
{ { "Bob", "555" }, { "Ian", "412" }, { "Sue", "616" } },
{ { "Bob", "555" }, { "Ian", "412" }, { "Sue", "616" } },
{ { "Bob", "555" }, { "Ian", "412" }, { "Sue", "616" } },
{ { "Bob", "555" }, { "Ian", "412" }, { "Sue", "616" } },
{ { "Bob", "555" }, { "Ian", "412" }, { "Sue", "616" } },
{ { "Bob", "555" }, { "Ian", "412" }, { "Sue", "616" } },
{ { "Bob", "555" }, { "Ian", "412" }, { "Sue", "616" } } };
String[] findName = { "Bob",
"Ann", "Bob", "Eve",
"Ann", "Bob", "Eve", "Ian", "Moe",
"Ann", "Bob", "Eve", "Ian", "Moe", "Sue", "Zoe" };
String[] findOutName = { null,
"Bob", "Bob", "Bob",
"Bob", "Bob", "Ian", "Ian", "Ian",
"Bob", "Bob", "Ian", "Ian", "Sue", "Sue", "Sue" };
boolean testFind () {
for (int i = 0; i < findIn.length; i++) {
try {
if (!testFind(i))
return false;
} catch (Exception e) {
System.out.println(e);
return false;
}
System.out.println();
}
return true;
}
boolean testFind (int i) {
setList(findIn[i]);
printList();
String name = findName[i];
System.out.println("find(" + name + ") returns ");
DLLEntry entry = find(name);
System.out.println(str(entry));
if (findOutName[i] == null)
return entry == null;
else
return entry.getName().equals(findOutName[i]);
}
}
prog06/prog04/TestUI.class
package prog04;
public synchronized class TestUI implements prog02.UserInterface {
int iCase;
int[] cases;
int iInfo;
String[][] info;
public void TestUI();
public void TestUI(String);
public int getCommand(String[]);
public void sendMessage(String);
public String getInfo(String);
public static void main(String[]);
}
prog06/prog04/TestUI.java
prog06/prog04/TestUI.java
package prog04;
import javax.swing.*;
import prog02.UserInterface;
/**
*
* @author vjm
*/
public class TestUI implements UserInterface {
/** Creates a new instance of TestUI */
public TestUI() {
}
/** Creates a new instance of TestUI */
public TestUI(String s) {
}
int iCase = -1;
int[] cases = { 1, 1, 2, 2, 0, 0, 0, 0, 1, 1, 2, 2, 0, 0, 4, 3, 4 };
int iInfo = 0;
String[][] info =
{ { "Fred" }, { "Victor" },
{ "Victor" }, { "Victor" },
{ "Victor", "" },
{ "Fred", "fred" }, { "Fred", "777" },
{ "Victor", null },
{ null }, { "" }, { null }, { "" }, { null }, { "" },
{ },
{ },
{ } };
/** presents set of commands for user to choose one of
@param commands the commands to choose from
@return the index of the command in the array
*/
public int getCommand (String[] commands) {
if (commands.length == 2) {
System.out.println("commands: " + commands[0] + " " + commands[1]);
int i = commands[1].equalsIgnoreCase("yes") ? 0 : 1;
System.out.println("selecting " + commands[i]);
System.out.println("-3 if it does not do a case 3 (save) before exiting");
return i;
}
if (iCase >= 0 && iInfo < info[iCase].length)
System.out.println("ERROR (-3 points): break too soon.");
System.out.println("\t" + "case " + cases[++iCase] + ":");
iInfo = 0;
return cases[iCase];
}
/** tell the user something
@param message string to print out to the user
*/
public void sendMessage (String message) {
if (message == null || message.contains("null"))
System.out.println("ERROR (-3 points): message contains null.");
System.out.println(message);
}
/** prompts the user for a string
@param prompt the request
@return what the user enters, null if nothing
*/
public String getInfo (String prompt) {
System.out.println("\t" + prompt);
if (iInfo == info[iCase].length) {
System.out.println("ERROR (-3 points): missing break.");
return null;
}
String ret = info[iCase][iInfo++];
System.out.println("\t" + "? " + ret);
return ret;
}
public static void main (String[] args) {
UserInterface ui = new TestUI();
String[] commands = { "hello", "how", "are", "you" };
int choice = ui.getCommand(commands);
ui.sendMessage("You chose " + choice);
String result = ui.getInfo("say something");
ui.sendMessage("You said " + result);
}
}
prog06/prog05/ArrayStack.class
package prog05;
public synchronized class ArrayStack implements StackInterface {
Object[] theData;
int size;
private static final int INITIAL_CAPACITY = 4;
public void ArrayStack();
public void reallocate();
public Object push(Object);
public Object pop();
public Object peek();
public boolean...