Concerning the Appointment ADT

An appointment is just an entry for a calendar: it has a period of time and a description of the activity. We define this immutable ADT for you. In particular we make it comparable so that we can order the appointments in an appointment book. As is recommended in Java, the compare function returns 0 only if the two appointments are equal.

Concerning the ApptBook ADT

The ApptBook ADT is a distant variant of the Sequence ADT from the textbook (Section 3.3 on pages 145-158 (142-155, 3rd ed.)). The data structure is used in the same way, but the elements are kept in order, and we have a new method setCurrent (described below).

The sequence maintains a location within it, and uses this to define a current element. If the location is after all the elements, there is no current element.

The textbook uses two method addBefore and addAfter to add an element before or after the current element. Since we keep the elements in order, there is no need for two methods, so we have a single one insert. Similarly, addAll is renamed insertAll, and unlike the textbook, simply inserts the elements of the argument into this sequence in the correct order. If there is already an appointment equal to the one we are adding, we put the new one after the existing one.

We also add a new public method:

setCurrent(appt)

The cursor is reset to point to the first appointment in the appointment book which is equal or greater to the argument.

You are encouraged (but not required) to write your own toString method which may be useful when debugging the ADT.

In this homework null appointment values are not permitted, partly because it's not clear where they go (the compareTo method may crash).

Unlike the textbook, we recommend that you do not use System.arrayCopy. While it does indeed run faster than doing a loop, it's not very clear what it is doing. Use a for loop for clarity.

Concerning Invariants and Assertions

The sequence-specific data structure makes use of two integer fields, and an array field. There are certain configurations that make no sense. In situations like this, programmers are recommended to define and check object invariants. For CompSci 351, this recommendation is converted to a requirement. See page 126 (3rd ed. p. 123) in the textbook.

There are conventions and Java language features to help you codify and test the invariant. For this homework, you will implement the class invariant as a private boolean method named wellFormed(). Then the beginning of every public method must have code as follows:

assert wellFormed() : "Invariant failed at start"; 

and at the end of any public method that changes any field, there must be the following line:

assert wellFormed() : "Invariant failed at end"; 

We have placed these lines in the code in the skeleton file for your convenience.

Public methods assert the invariant in this way, so they should not be called by other methods that are in the process of breaking and (one assumes) eventually restoring the invariant. Neither should they be called by code that is checking the invariant!

An invariant may be expensive to check. Therefore in Java, assertions are turned off by default. For that reason, an assertion should not include some side-effect that needs to happen. Don't rely on an assertion to check (say) that a parameter is good.

You should always turn assertions on while running the main test suite. With the command line, this is done by passing the flag -ea to the java executor. In Eclipse, assertions are enabled by adding -ea (don't forget the hyphen!) as a VM argument on the Arguments tab of the run configuration.

Concerning Random Testing

It's hard (and tedious) to provide exhaustive tests for an ADT. Sometimes, the best way forward is to use random testing where the ADT implementation is tested against a (perhaps inefficient) reference implementation. By doing a lot of random tests, we can increase confidence that the implementation isn't using conditionals to work around our existing tests.

For this assignment, we provide a random test system. If your code is free of compiler errors (no red X'es), you can run it. In the Referenced Libraries, open up homework2.jar. In the default package, find RandomTest, right-click it, and Run As a Java Application.

It will carry out millions of tests. It may either find no errors and give you a congratulatory message, or it outputs a specialized JUnit test that your implementation fails. The output can be copied into a new file and executed so that you can perform debugging. Do not attempt to debug the RandomTest executable itself--it does a different sequence of tests each time.

// This is an assignment for students to complete after reading Chapter 3 of

// "Data Structures and Other Objects Using Java" by Michael Main.

package edu.uwm.cs351;

import junit.framework.TestCase;

/******************************************************************************

* This class is a homework assignment;

* A ApptBook ("book" for short) is a sequence of Appointment objects in sorted order.

* The book can have a special "current element," which is specified and

* accessed through four methods that are available in the this class

* (start, getCurrent, advance and isCurrent).

*

* @note

* (1) The capacity of a book can change after it's created, but

* the maximum capacity is limited by the amount of free memory on the

* machine. The constructor, add, addAll, clone,

* and catenation methods will result in an

* OutOfMemoryError when free memory is exhausted.

*

* (2) A book's capacity cannot exceed the maximum integer 2,147,483,647

* (Integer.MAX_VALUE). Any attempt to create a larger capacity

* results in a failure due to an arithmetic overflow.

*

* NB: Neither of these conditions require any work for the implementors (students).

*

*

******************************************************************************/

public class ApptBook implements Cloneable {

/** Static Constants */

private static final int INITIAL_CAPACITY = 1;

/** Fields */

private Appointment[ ] _data;

private int _manyItems;

private int _currentIndex;

// Invariant of the ApptBook class:

// 1. The number of elements in the books is in the instance variable

// manyItems.

// 2. For an empty book (with no elements), we do not care what is

// stored in any of data; for a non-empty book, the elements of the

// book are stored in data[0] through data[manyItems-1] and we

// don't care what's in the rest of data.

// 3. None of the elemts are null and they are ordered according to their

// natural ordering (Comparable); duplicates *are* allowed.

// 4. If there is a current element, then it lies in data[currentIndex];

// if there is no current element, then currentIndex equals manyItems.

private static boolean doReport = true; // change onluy in invariant tests

private boolean report(String error) {

if (doReport) {

System.out.println("Invariant error: " + error);

}

return false;

}

private boolean wellFormed() {

// Check the invariant.

// 1. data array is never null

// TODO

// 2. The data array has at least as many items in it as manyItems

// claims the book has

// TODO

// 3. None of the elemts are null and all are in natural order

// 4. currentIndex is never negative and never more than the number of

// items in the book.

// TODO

// If no problems discovered, return true

return true;

}

// This is only for testing the invariant. Do not change!

private ApptBook(boolean testInvariant) { }

/**

* Initialize an empty book with

* an initial capacity of INITIAL_CAPACITY. The {@link #insert(Appointment)} method works

* efficiently (without needing more memory) until this capacity is reached.

* @param - none

* @postcondition

* This book is empty and has an initial capacity of INITIAL_CAPACITY

* @exception OutOfMemoryError

* Indicates insufficient memory for initial array.

**/

public ApptBook( )

{

// TODO: Implemented by student.

assert wellFormed() : "invariant failed at end of constructor";

}

/**

* Initialize an empty book with a specified initial capacity.

* The {@link #insert(Appointment)} method works

* efficiently (without needing more memory) until this capacity is reached.

* @param initialCapacity

* the initial capacity of this book, must not be negative

* @exception IllegalArgumentException

* Indicates that name, bpm or initialCapacity are invalid

* @exception OutOfMemoryError

* Indicates insufficient memory for an array with this many elements.

* new Appointment[initialCapacity].

**/

public ApptBook(int initialCapacity)

{

// TODO: Implemented by student.

assert wellFormed() : "invariant failed at end of constructor";

}

/**

* Determine the number of elements in this book.

* @param - none

* @return

* the number of elements in this book

**/

public int size( )

{

assert wellFormed() : "invariant failed at start of size";

// TODO: Implemented by student.

}

/**

* Add a new element to this book, in order.

* If the new element would take this book beyond its current capacity,

* then the capacity is increased before adding the new element.

* The current element (if any) is not affected.

* @param element

* the new element that is being added, must not be null

* @postcondition

* A new copy of the element has been added to this book. The current

* element (whether or not is exists) is not changed.

* @exception IllegalArgumentException

* indicates the parameter is null

* @exception OutOfMemoryError

* Indicates insufficient memory for increasing the book's capacity.

**/

public void insert(Appointment element)

{

assert wellFormed() : "invariant failed at start of insert";

// TODO: Implemented by student.

assert wellFormed() : "invariant failed at end of insert";

}

/**

* Place all the appointments of another book (which may be the

* same book as this!) into this book in order.

* The elements are probably not going to be placed in a single block.

* @param addend

* a book whose contents will be placed into this book

* @precondition

* The parameter, addend, is not null.

* @postcondition

* The elements from addend have been placed into

* this book. The current el;ement (if any) is

* unchanged.

* @exception NullPointerException

* Indicates that addend is null.

* @exception OutOfMemoryError

* Indicates insufficient memory to increase the size of this book.

**/

public void insertAll(ApptBook addend)

{

assert wellFormed() : "invariant failed at start of insertAll";

// TODO: Implemented by student.

// Watch out for the this==addend case!

// Cloning the addend is an easy way to avoid problems.

assert wellFormed() : "invariant failed at end of insertAll";

assert addend.wellFormed() : "invariant of addend broken in insertAll";

}

/**

* Change the current capacity of this book as needed so that

* the capacity is at least as big as the parameter.

* This code must work correctly and efficiently if the minimum

* capacity is (1) smaller or equal to the current capacity (do nothing)

* (2) at most double the current capacity (double the capacity)

* or (3) more than double the current capacity (new capacity is the

* minimum passed).

* @param minimumCapacity

* the new capacity for this book

* @postcondition

* This book's capacity has been changed to at least minimumCapacity.

* If the capacity was already at or greater than minimumCapacity,

* then the capacity is left unchanged.

* @exception OutOfMemoryError

* Indicates insufficient memory for: new array of minimumCapacity elements.

**/

private void ensureCapacity(int minimumCapacity)

{

// TODO: Implemented by student.

// NB: do not check invariant

}

/**

* Set the current element at the front of this book.

* @param - none

* @postcondition

* The front element of this book is now the current element (but

* if this book has no elements at all, then there is no current

* element).

**/

public void start( )

{

assert wellFormed() : "invariant failed at start of start";

// TODO: Implemented by student.

assert wellFormed() : "invariant failed at end of start";

}

/**

* Accessor method to determine whether this book has a specified

* current element that can be retrieved with the

* getCurrent method.

* @param - none

* @return

* true (there is a current element) or false (there is no current element at the moment)

**/

public boolean isCurrent( )

{

assert wellFormed() : "invariant failed at start of isCurrent";

// TODO: Implemented by student.

}

/**

* Accessor method to get the current element of this book.

* @param - none

* @precondition

* isCurrent() returns true.

* @return

* the current element of this book

* @exception IllegalStateException

* Indicates that there is no current element, so

* getCurrent may not be called.

**/

public Appointment getCurrent( )

{

assert wellFormed() : "invariant failed at start of getCurrent";

// TODO: Implemented by student.

// Don't change "this" object!

}

/**

* Move forward, so that the current element will be the next element in

* this book.

* @param - none

* @precondition

* isCurrent() returns true.

* @postcondition

* If the current element was already the end element of this book

* (with nothing after it), then there is no longer any current element.

* Otherwise, the new element is the element immediately after the

* original current element.

* @exception IllegalStateException

* Indicates that there is no current element, so

* advance may not be called.

**/

public void advance( )

{

assert wellFormed() : "invariant failed at start of advance";

// TODO: Implemented by student.

assert wellFormed() : "invariant failed at end of advance";

}

/**

* Remove the current element from this book.

* @param - none

* @precondition

* isCurrent() returns true.

* @postcondition

* The current element has been removed from this book, and the

* following element (if there is one) is now the new current element.

* If there was no following element, then there is now no current

* element.

* @exception IllegalStateException

* Indicates that there is no current element, so

* removeCurrent may not be called.

**/

public void removeCurrent( )

{

assert wellFormed() : "invariant failed at start of removeCurrent";

// TODO: Implemented by student.

assert wellFormed() : "invariant failed at end of removeCurrent";

}

/**

* Set the current element to the first element that is equal

* or greater than the guide.

* @param guide element to compare against, must not be null.

*/

public void setCurrent(Appointment guide) {

// TODO: can be done entirely with other methods.

// (Binary would be much faster for a large book.

// but don't worry about efficiency yet.)

}

/**

* Generate a copy of this book.

* @param - none

* @return

* The return value is a copy of this book. Subsequent changes to the

* copy will not affect the original, nor vice versa.

* @exception OutOfMemoryError

* Indicates insufficient memory for creating the clone.

**/

public ApptBook clone( ) {

assert wellFormed() : "invariant failed at start of clone";

ApptBook answer;

try

{

answer = (ApptBook) super.clone( );

}

catch (CloneNotSupportedException e)

{ // This exception should not occur. But if it does, it would probably

// indicate a programming error that made super.clone unavailable.

// The most common error would be forgetting the "Implements Cloneable"

// clause at the start of this class.

throw new RuntimeException

("This class does not implement Cloneable");

}

// all that is needed is to clone the data array.

// (Exercise: Why is this needed?)

answer._data = _data.clone( );

assert wellFormed() : "invariant failed at end of clone";

assert answer.wellFormed() : "invariant on answer failed at end of clone";

return answer;

}

// don't change this nested class:

public static class TestInvariantChecker extends TestCase {

Time now = new Time();

Appointment e1 = new Appointment(new Period(now,Duration.HOUR),"1: think");

Appointment e2 = new Appointment(new Period(now,Duration.DAY),"2: current");

Appointment e3 = new Appointment(new Period(now.add(Duration.HOUR),Duration.HOUR),"3: eat");

Appointment e4 = new Appointment(new Period(now.add(Duration.HOUR.scale(2)),Duration.HOUR.scale(8)),"4: sleep");

Appointment e5 = new Appointment(new Period(now.add(Duration.DAY),Duration.DAY),"5: tomorrow");

ApptBook hs;

protected void setUp() {

hs = new ApptBook(false);

ApptBook.doReport = false;

}

public void test0() {

assertFalse(hs.wellFormed());

}

public void test1() {

hs._data = new Appointment[0];

hs._manyItems = -1;

assertFalse(hs.wellFormed());

hs._manyItems = 1;

assertFalse(hs.wellFormed());

doReport = true;

hs._manyItems = 0;

assertTrue(hs.wellFormed());

}

public void test2() {

hs._data = new Appointment[1];

hs._manyItems = 1;

assertFalse(hs.wellFormed());

hs._manyItems = 2;

assertFalse(hs.wellFormed());

hs._data[0] = e1;

doReport = true;

hs._manyItems = 0;

assertTrue(hs.wellFormed());

hs._manyItems = 1;

hs._data[0] = e1;

assertTrue(hs.wellFormed());

}

public void test3() {

hs._data = new Appointment[3];

hs._manyItems = 2;

hs._data[0] = e2;

hs._data[1] = e1;

assertFalse(hs.wellFormed());

doReport = true;

hs._data[0] = e1;

assertTrue(hs.wellFormed());

hs._data[1] = e2;

assertTrue(hs.wellFormed());

}

public void test4() {

hs._data = new Appointment[10];

hs._manyItems = 3;

hs._data[0] = e2;

hs._data[1] = e4;

hs._data[2] = e3;

assertFalse(hs.wellFormed());

doReport = true;

hs._data[2] = e5;

assertTrue(hs.wellFormed());

hs._data[0] = e4;

assertTrue(hs.wellFormed());

hs._data[1] = e5;

assertTrue(hs.wellFormed());

}

public void test5() {

hs._data = new Appointment[10];

hs._manyItems = 4;

hs._data[0] = e1;

hs._data[1] = e3;

hs._data[2] = e2;

hs._data[3] = e5;

assertFalse(hs.wellFormed());

doReport = true;

hs._data[2] = e4;

assertTrue(hs.wellFormed());

hs._data[2] = e5;

assertTrue(hs.wellFormed());

hs._data[2] = e3;

assertTrue(hs.wellFormed());

}

public void test6() {

hs._data = new Appointment[3];

hs._manyItems = -2;

assertFalse(hs.wellFormed());

hs._manyItems = -1;

assertFalse(hs.wellFormed());

hs._manyItems = 1;

assertFalse(hs.wellFormed());

doReport = true;

hs._manyItems = 0;

assertTrue(hs.wellFormed());

}

public void test7() {

hs._data = new Appointment[3];

hs._data[0] = e1;

hs._data[1] = e2;

hs._data[2] = e4;

hs._manyItems = 4;

assertFalse(hs.wellFormed());

doReport = true;

hs._manyItems = 3;

assertTrue(hs.wellFormed());

}

public void test8() {

hs._data = new Appointment[3];

hs._data[0] = e2;

hs._data[1] = e3;

hs._data[2] = e1;

hs._manyItems = 2;

hs._currentIndex = -1;

assertFalse(hs.wellFormed());

hs._currentIndex = 3;

assertFalse(hs.wellFormed());

doReport = true;

hs._currentIndex = 0;

assertTrue(hs.wellFormed());

hs._currentIndex = 1;

assertTrue(hs.wellFormed());

hs._currentIndex = 2;

assertTrue(hs.wellFormed());

}

}

}

package edu.uwm.cs351;

/**

* A simple class representing an appointment:

* a period of time and a description.

*/

public class Appointment implements Comparable {

private final Period time;

private final String description;

public Appointment(Period p, String t) {

time = p;

description = t;

}

public Period getTime() { return time; }

public String getDescription() { return description; }

@Override

public int hashCode() {

return time.hashCode() ^ description.hashCode();

}

@Override

public boolean equals(Object obj) {

if (!(obj instanceof Appointment)) return false;

Appointment other = (Appointment)obj;

return time.equals(other.time) && description.equals(other.description);

}

@Override

public String toString() {

return time.toString() + description;

}

@Override

public int compareTo(Appointment o) {

int c = time.getStart().compareTo(o.time.getStart());

if (c != 0) return c;

c = time.getLength().compareTo(o.time.getLength());

if (c != 0) return c;

return description.compareTo(o.description);

}

}