CSE 2221

@requires

Precondition; The caller must ensure this is true.

@ensures

Postcondition

@updates

The method changes (updates) this parameter. The final value may depend on the initial value.

@replaces

The method gives this parameter a completely new value. It does NOT depend on its old value.

@restores

The method leaves this parameter unchanged.

@clears

The parameter is set to its “cleared” or empty state.

#x

Original Value before the method starts

|s|

number of characters in string s

rev(s)

s written backwards

entries(s)

set of characters in s (no duplicates)

{a, b, c}

a set (order doesn’t matter, duplicates removed)

s * n

s repeated n times

x x x * x

x concatenated with itself 4 times

P ∧ Q

both P and Q are true (AND)

P ∨ Q

at least one is true (OR)

¬P

NOT P

P ⇒ Q

if P is true, Q must be true

P ⇔ Q

P and Q mean the same thing (equivalent)

isZero()

NaturalNumber Kernal; checks if is zero

divideBy10()

NaturalNumber(); removes last digit and returns it

multiplyBy10(d)

NaturalNumber(); appends digit d

increment()

NaturalNumber(); adds 1

decrement()

NaturalNumber(); -1

copyFrom(other)

NaturalNumber(); copyFrom

Static Methods

No this parameter; Called without a receiver

Instance Methods

without static; Called with a receiver; Has this parameter

Overriding

new body for same method signature.

Overloading

same name, different parameters

Declared Type (Static Type):

type in variable declaration

Object Type (Dynamic Type)

type from constructor (new)

@Override

Implementing interface method

Overriding superclass method

Polymorphism

Method body used is determined by object type of receiver, NOT declared type.

Primitive

boolean, char, int, double

Reference

String, XMLTree, NaturalNumber, etc.

Assignment with primitives

copies VALUE

Assignment with references

copies REFERENCE VALUE (memory address) (ALIASES)

Aliasing

When two references point to same object:

NaturalNumber n = z;

n.increment(); // Changes BOTH n and z! (same object)

Immutable

(safe to reason like primitive): String, XMLTree

Mutable

(danger with aliases): NaturalNumber, SimpleReader, SimpleWriter

Pass by Value/Call-by-Copy/Call-by-Value

a copy of the actual value is passed to the function.

Pass by Reference

Gives the function access to the memory address of the original variable.

Design-by-Contract

If precondition true → method terminates with postcondition true

Monte Carlo Estimation

Throw darts randomly at known region

Count hits inside shape vs total

Estimated area = (hits / total) × known_area

Java's % is NOT true modulo for negative numbers!

(-67) % 24 = -19 ⚠ DIFFERENT from mod!

transferFrom

NaturalNumber is a reference type! The method receives a reference and can modify the object.

private static void foo(NaturalNumber x, NaturalNumber y) {

// Ensures: x = #x + 1 and y = #y + 2

}

NaturalNumber a = new NaturalNumber2(10);

foo(a, a);

// ⚠ REPEATED ARGUMENT!

Height

int maxSubtreeHeight = 0;

if (t.isTag()) {

for (int i = 0; i < t.numberOfChildren(); i++) {

int h = height(t.child(i));

if (h > maxSubtreeHeight) {

maxSubtreeHeight = h;

}

}

}

return maxSubtreeHeight + 1;

Unit Testing

Test individual components (one method/class at a time)

Integration Testing

Test multiple components together

System Testing

Test entire end-user system

Goal of Testing

Show that code has DEFECTS (not prove correctness!)

Testing can show presence of bugs, never their absence"

Test Case Design

Three types:

1. Boundary cases: smallest, largest, special values

2. Routine cases: typical/normal inputs

3. Challenging cases: difficult/error-prone situations

Invalid Test Cases

Don't test with inputs that violate precondition - these reveal nothing!

Queue

FIFO: First-In-First-Out (like a line at a store)

Wrapper Types

Java automatically converts between them

Boolean

Character

Integer

Double

Generics

Generic arguments must be reference types (not primitives)

List<**Integer**> myList = new ArrayList<>();

How does program know when user clicks button, types key, etc.?

1. Polling(bad ): Program constantly checks each widget: "event? event? event?"

2. Callbacks(Good):

   1. Observer registers interest with subject

   2. Subject keeps list of observers

   3. When event occurs, subject calls back each observer

Threads

Initial thread: runs main() until complete
Event dispatch thread: runs Swing code and callbacks

Model

Data and business logic (no GUI knowledge)

View

GUI widgets and display (extends JFrame, implements ActionListener)

1. Create JFrame

2. Set up widgets

3. Register observers

4. Start window

Controller

Mediates between Model and View

Loop Invariant

Property that is true every time you reach the loop condition test.

Loop Invariants to Trace

Don't trace loop body! Use invariant + condition:

Before loop: this = <1,2,3>, q = <4,5,6>

After loop (when test false):

- Invariant says: this * q = <1,2,3,4,5,6>

- Condition false says: |q| = 0, so q = < >

- Therefore: this = <1,2,3,4,5,6>

perms()

perms(s1, s2) checks if strings are permutations (reorderings):

javaperms(<1,2,3>, <3,1,2>) // true

perms(<2,2,1>, <2,1>) // false (different lengths)

entries()

Converts string to set (removes duplicates, ignores order):

javaentries(<2,2,2,1>) = {1, 2}

Class

is a blueprint for creating objects

Interface

contract—a formal declaration of a set of related methods that any implementing class must provide