Overview
Assignment 1 Report
I used two top level data structures. One is to store all the appoints and another is to store locations and their associated appointments. I use TreeSet to store the appointments collection. Because it supports add, remove and search operation all in O(log(n)) time.
TreeSet
I used it to store all the appointments. In the method getNextAppointment(Date when), I use this data structure to find the next appoint. Because TreeSet is implemented using Red-Black binary search tree, we can add and remove elements in log(n) time. Moreover we can use higher method of it to find the next appoint which is also in log(n) time.
HashMap
I used it to map each location name to the appointments. So I can find the appointments in one location conveniently, using the value type TreeSet is the same reason described above. I use HashMap because HashMap supports O(1) lookup and add operation.
public List
Run time: O(n), n is the number of appointments at this location
Analysis: Use the HashMap to look up corresponding TreeSet is O (1), construct an array list from the tree set is O(n). Because in general the number of appointments at 1 location is less than the total number of appointments, this is still in sub-linear time.
public Appointment getNextAppointment(Date when)
Run time: O(log(n)) n is the number of all appointments
Analysis: Use method higher in TreeSet to find the next appoint, this method runs in O(log(n)). The higher method uses search algorithm in balance binary search tree, the worst time is the height of tree which is log(n).
public Appointment getNextAppointment(Date when, String location)
Run time: O(log(n)) n is the number of all appointments
Analysis: Use the HashMap to look up corresponding TreeSet is O(1), then use the TreeSet to find the next point using higher method is O(log(n)), so the overall time is O(log(n)).
public void add(String description, Date when, String location)
Run time: O(log(n)) n is the number of all appointments
Analysis: Because add element to balance binary search tree is O(log(n)), add the appointment to TreeSet containing all appointments is O(log(n)), look up corresponding TreeSet in the location using HashMap is O(1), add to this TreeSet is also O(log(n)), so the overall time is O(log(n)).
public void remove(Appointment appointment)
Run time: O(log(n)) n is the number of all appointments
Analysis: Because remove element from balance binary search tree is O(log(n)), remove the appointment from TreeSet containing all appointments is O(log(n)), look up corresponding TreeSet in the location using HashMap is O(1), remove from this TreeSet is also O(log(n)), so the overall time is O(log(n)).
Test
I write a Junit test program for the assignment and test the 5 methods respectively.
All test method will test the illegal argument case, so I will omit these cases in the following.
testGetAppointments
case 1: test empty case assertTrue(calendar.getAppointments(¡°F”).isEmpty());
case 2: test the normal case
assertAppoinmentsDescription(Arrays.asList(“A1”, “A2”, “A3”, “A4”, “A5″),
calendar.getAppointments(¡°A”));
testGetNextAppointment
case 1: test no such appointment case assertNull(calendar.getNextAppointment(df.parse(“2017/09/03 09:00:00¡±)));
case 2: test case where there is one possible answer. assertTrue(“A1”.equals(calendar.getNextAppointment(df.parse(“2016/09/02 09:00:00¡±)).getDescription()));
case 3: test case that have more than 1 possible answer. assertTrue(Arrays.asList(“A3″,”A4”).contains(calendar.getNextAppointment(df.parse(“2016/09/05 09:00:00¡±)).getDescription()));
testGetNextAppointmentLocation
case 1: Test no such appointment because of not satisfying the location requirement. assertNull(calendar.getNextAppointment(df.parse(“2017/09/03 09:00:00″), ¡°D”));
case 2: Test no such appointment because of not satisfying the date requirement. assertNull(calendar.getNextAppointment(df.parse(“2016/09/10 09:00:01″), ¡°A”));
case 3: test case where there is one possible answer. assertTrue(Arrays.asList(¡°C4″).contains(calendar.getNextAppointment
df.parse(“2016/10/06 10:00:00”), ¡°C¡±).getDescription()));
case 4: test case where there is more than one possible answer. assertTrue(Arrays.asList(“B1″,”B2”).contains(calendar.getNextAppointment(df.parse(“2016/10/03 09:00:00″), ¡°B”).getDescription()));
testRemove
case 1: remove 1 existing appointment
Appointment appointment = calendar.getNextAppointment(df.parse(“2016/09/02 09:00:00”)); assertEquals(“A1”, appointment.getDescription());
calendar.remove(appointment);
assertAppoinmentsDescription(Arrays.asList(“A2”, “A3”, “A4”, “A5”), calendar.getAppointments(“A”));
case 2: remove non-existing appointment
calendar.remove(new MyAppoint(“A10”, “A”, df.parse(“2016/09/02 09:00:00”))); assertAppoinmentsDescription(Arrays.asList(“A2”, “A3”, “A4”, “A5”), calendar.getAppointments(“A”));
testAdd
case 1: Test case that adds appointment to an existing location name calendar.add(“A100”, date, “A”); assertAppoinmentsDescription(Arrays.asList(“A1”, “A2”, “A3”, “A4”, “A5”, “A100”), calendar.getAppointments(“A”));
case 2: Test case that adds appointment to non-existing location name calendar.add(“F100”, date, “F”);
assertAppoinmentsDescription(Arrays.asList(“F100”), calendar.getAppointments(“F”));