Outline

Testing

unless the code is written correctly from the start, the errors must be found by testing the code
writing correct code is a lot of work, so most programmers use testing to make their code as close to correct as possible
test routines can (and probably should) be included in the main method of any class that doesn't already have one. This is a unit test. This main method is a driver program. The driver program can also be defined separately.
the unit test should call all the methods of the class, with as many combinations of parameters as possible
if the writer of the test code doesn't study the code under test, this is black box testing
at the very least, the goal of testing is full coverage: making sure that every path through the code has been used at least once, and has produced an acceptable result
to produce full coverage, the programmer of the test program must study the code being tested: this is white box testing

off-by-one (fencepost): how many fence posts are needed for a fence that is 20 feet long and has a post every 2 feet?
not initializing data correctly. Sometimes this causes null pointer access
using different variables as if they were one, or using one variable as if it were two variables
assumptions that don't turn out to be true (misconceptions), not establishing and maintaining invariants
not checking things that should be checked, e.g. if (x == null)

print/show all method invocations and their parameters and return values
write code to check that the invariants are established and maintained
write test cases to not only provide full coverage, but also check all boundary conditions, where the result should change (make sure it changes where it should)
some common special cases:
- < 0, 0, 1, > 1
- first and last elements of an array, collection, linked list
- elements and values that are null
- desired element is not in the collection, or is in the collection more than once
- collection has size 0, 1, or larger
for example, when testing inserting on a linked list, can test inserting at the beginning of a linked list, at the end, in the middle, and inserting into an empty linked list. Also, inserting an element that has the value null (is the behavior of your program defined in that case? Should it be?)
if code to be tested needs to call a method that is not yet implemented, a stub of that method can do only what is needed for the test

a precondition must be true before a method is called
the code in the method may (and usually will) assume that the precondition is true
the caller of a method must guarantee (be sure) that the precondition holds
a postcondition will be true after a method is called
the code in the method must guarantee that the postcondition is true
preconditions and postconditions are a little bit like a contract or any other agreement: if the caller provides the preconditions, the method will provide the postconditions
preconditions and postconditions are documented in Javadoc
invariants are postconditions of every method, including the constructors
invariants are preconditions of every method except the constructors
invariants are usually documented for the entire class rather than for each method

stacks of dishes or trays in a cafeteria
on a spring-loaded mechanism so only the top one is accessible
adding more dishes pushes down the stack, so only the new top is still accessible
Last In First Out discipline (LIFO -- FIFO will be discussed at a later lecture)

a data structure to hold a variable number of elements
of which only the top one is accessible at any given time
the stack may be empty if it holds no elements
the stack keeps track of the number of elements it has, as well as the individual elements
some stack implementations set a fixed maximum size for the stack, so the stack overflows if more data is added to a full stack

consider a stack to store objects of some type E:
void push(E item) adds the value to the top of the stack
E pop() throws EmptyStackException removes the value on top of the stack and returns it (or throws the exception)
E peek() throws EmptyStackException is like pop, except it doesn't remove the element
boolean empty() reports whether the stack is empty
only the topmost element of the stack is accessible
as in every ADT, we have specified only what the stack does, and not how that is accomplished. The how part belongs in the implementation

can the same name be reused for different methods?
Java: yes
programmers: yes, if they do the same thing
Java uses a signature for each method that includes the method's name, and the type/class and order (sequence) of its parameters
each method's signature must be unique within a class
example:
push(E) is the signature for the push method (above)
in an interface, this is written with the method prototype:
```
void push (E item);
```

in a class implementation, the signature is taken from the method header:

    /* @param	value to push onto the stack */
    public void push(E value) {
         ...

even though arrays and stacks are very different, we can use an array in implementing our stack
implementing a stack using an array is similar to implementing a list using an array
instead of the size of the list, we keep track of where the top of the stack is: an integer we call top
the code outside the class does not know and does not need to know that the stack is implemented using an array

given ArrayStack.java:
in-class exercise (everyone together): what is the runtime (big O) of empty(), push(), and pop()?

even though linked lists and stacks are very different, we can use a linked list in implementing our stack
implementing a stack using a linked list is similar to implementing a list using an array
all operations occur at the head of the list

given ArrayStack.java:
in-class exercise (everyone together): what is the runtime (big O) of empty(), push(), and pop()?
given LinkedStack.java:
in-class exercise (everyone together): what is the runtime (big O) of empty(), push(), and pop()?

any extensible data structure that has access at one end can be used to implement a stack
this includes java Vectors and java Lists
new data is added to or removed from the end of the Vector or ArrayList in O(1) time (when the array doesn't have to grow)
in the code in the book (p. 164/272), note that the data is stored in an object of type List<E>, that is created as an ArrayList<E>: this is an example of polymorphism, and makes it easy to switch to a different kind of list
new data is added to or removed from the front of the Linked List, in O(1) time