DS 230: Object Oriented Programming

Algorithms and pseudocode

• An algorithm is a procedure for solving a problem in terms of the actions to execute and the order in which they execute.
• Pseudocode is an informal language for developing algorithms without worrying about Java syntax. It does not execute on computers.

// Algorithm: add two numbers
Step 1: Start
Step 2: Declare variables num1, num2 and sum
Step 3: Read values num1 and num2
Step 4: sum = num1 + num2
Step 5: Display sum
Step 6: Stop

The three control structures

Each of these words is a Java keyword. Control statements are single-entry/single-exit.

if and if…else

if performs an action only when the condition is true. if…else also performs a different action when it is false.

int grade = 75;
if (grade >= 60)
    System.out.println("Passed");
else
    System.out.println("Failed");

int number = 13;
if (number % 2 == 0)
    System.out.println("even number");
else
    System.out.println("odd number");

Passed
odd number

Blocks

The body of an if normally holds one statement. To include several, enclose them in braces to make a block.

if (grade >= 60)
    System.out.println("Passed");
else {
    System.out.println("Failed");
    System.out.println("You must take this course again.");
}

Nested if…else (else if)

if (studentGrade >= 90)
    System.out.println("A");
else if (studentGrade >= 80)
    System.out.println("B");
else if (studentGrade >= 70)
    System.out.println("C");
else if (studentGrade >= 60)
    System.out.println("D");
else
    System.out.println("F");

switch…case

Performs different actions based on the possible values of a constant integral expression.

• Switch expression types: byte, short, int, long, enums and String.
• Case values must be unique.
• break is optional but it jumps out of the switch. Without it, execution falls through and runs the next case too.
• default is optional and runs when no case matches.

int number = 20;
switch (number) {
    case 10: System.out.println("10"); break;
    case 20: System.out.println("20"); break;
    case 30: System.out.println("30"); break;
    default: System.out.println("Not in 10, 20 or 30");
}

char grade = 'C';
switch (grade) {
    case 'A': System.out.println("Excellent!"); break;
    case 'B':
    case 'C': System.out.println("Well done"); break;   // B and C share this
    case 'D': System.out.println("You passed");
    case 'F': System.out.println("Better try again"); break;
    default:  System.out.println("Invalid grade");
}

20
Well done

The conditional operator ?:

Java’s only ternary operator (three operands). A shorter replacement for simple if…else: condition ? valueIfTrue : valueIfFalse.

int a = 6, b = 12;
String out = (a == b) ? "Yes" : "No";            // "No"
int x = 69, y = 89, z = 79;
int largest = (x > y) ? (x > z ? x : z) : (y > z ? y : z);   // 89

What every loop needs

1. A control variable (loop counter)
2. The initial value of the control variable
3. The increment applied each time through the loop (each iteration)
4. The loop-continuation condition that decides if looping continues

while, for and do…while

// while: test first
int counter = 1;
while (counter <= 10) {
    System.out.printf("%d ", counter);
    ++counter;
}

// for: all counter details in one line
for (int i = 1; i <= 10; i++)
    System.out.printf("%d ", i);

// sum of even numbers from 2 to 20
int total = 0;
for (int number = 2; number <= 20; number += 2)
    total += number;     // 110

// do...while: test after
int n = 1;
do {
    System.out.printf("%d ", n);
    n++;
} while (n <= 10);

1 2 3 4 5 6 7 8 9 10 

Each of the counting loops above prints this line. The even-sum loop leaves total = 110.

In a for header, the increment expression acts like a standalone statement at the end of the loop body. You may use arithmetic expressions in the header.

Nested loops

A loop inside another loop. The inner loop finishes all its iterations for each iteration of the outer loop.

for (int i = 1; i <= 3; i++) {        // outer loop
    for (int j = 1; j <= 2; j++) {    // inner loop
        System.out.print("(" + i + "," + j + ") ");
    }
    System.out.println();
}

(1,1) (1,2) 
(2,1) (2,2) 
(3,1) (3,2) 

break and continue

for (int i = 1; i <= 5; i++) {
    if (i == 3) continue;   // skip 3
    if (i == 5) break;      // stop at 5
    System.out.print(i + " ");
}

1 2 4 

Logical operators

Precedence and associativity so far (high to low)

Primitive vs reference types

Creating, initializing and using arrays

• An array is a data structure. Each element is accessed by an index (subscript) in square brackets. The index must be a non-negative integer or integer expression.
• The first element is at index 0. An array of 12 elements uses c[0] to c[11]. c.length gives the number of elements.
• Arrays are created with the keyword new.

int[] c = new int[12];            // 12 elements, all start at 0
int[] d = {10, 20, 30, 40, 50};     // array initializer
String[] b = new String[100], x = new String[27];

c[0] = -45;
int sum = c[0] + c[1] + c[2];
int total = 0;
for (int i = 0; i < d.length; i++)
    total += d[i];                  // 150
c[5 + 6] += 2;                      // adds 2 to c[11]

Exception handling: try-catch

An exception is a problem that occurs while the program executes. Put code that might throw one in a try block and the handling code in a catch block. The finally block runs regardless of the result.

try {
    int[] myNumbers = {1, 2, 3};
    System.out.println(myNumbers[10]);   // error!
} catch (Exception e) {
    System.out.println("Something went wrong.");
} finally {
    System.out.println("The try catch is finished.");
}

Something went wrong.
The try catch is finished.

Without the try-catch, Java stops with ArrayIndexOutOfBoundsException: 10.

Enhanced for statement

Iterates through the elements of an array without a counter, so you cannot “step outside” the array. The header has a type and an identifier for the current element, then : and the array name.

int[] array = {87, 68, 94, 100, 83};
int total = 0;
for (int number : array)
    total += number;
System.out.println(total);

432

Passing arrays to methods

Specify the array name without brackets. The call is modifyArray(hourlyTemperatures); and the header is void modifyArray(double[] b).

Pass-by-value vs pass-by-reference

Multidimensional arrays

A two-dimensional array is a table with rows and columns. Rows can have different lengths.

int[][] b = { {1, 2}, {3, 4} };       // b[0][0]=1, b[0][1]=2, b[1][0]=3, b[1][1]=4
int[][] jag = { {1, 2}, {3, 4, 5} };   // row 0 has 2 elements, row 1 has 3
System.out.println(jag[1][2]);

5

Classes and objects

• Instance variable: declared inside the class but outside any method. It gets memory at runtime, when an object is created.
• Method: represents a behavior of an object.
• new creates an object. The parentheses after the class name are required.

public class Account {
    private String name;                    // instance variable

    public void setName(String name) {      // setter
        this.name = name;                   // this refers to the instance variable
    }
    public String getName() {               // getter
        return name;
    }
}

public class AccountTest {
    public static void main(String[] args) {
        Account myAccount = new Account();  // instantiate
        myAccount.setName("Jane Green");
        System.out.println("Name is: " + myAccount.getName());
    }
}

Name is: Jane Green

Each object statement has three parts: declaration (variable of an object type), instantiation (the new operator), and initialization (the call to a constructor).

Access modifiers

Default and explicit initialization

• Local variables are not initialized by default.
• Primitive instance variables are: numeric types (byte, char, short, int, long, float, double) start at 0, and boolean starts at false.
• You can also initialize an instance variable explicitly in its declaration.

Constructors

A constructor initializes an object when it is created. It has the same name as its class and looks like a method, but has no return type.

class MyClass {
    int x;
    MyClass(int i) { x = i; }          // parameterized constructor
}
MyClass t1 = new MyClass(10);
MyClass t2 = new MyClass(20);
System.out.println(t1.x + " " + t2.x);

10 20

static members

• A static variable belongs to the class as a whole. All objects share it. It gets memory only once, when the class is loaded.
• A static method relates to the class, not to a specific object. Instance methods work on one object’s instance variables.

class Counter {
    static int count = 0;
    Counter() { count++; System.out.println(count); }
}
new Counter(); new Counter(); new Counter();   // prints 1, 2, 3

Implementing a test class

A class with main that creates objects of your class and calls their methods is a test class. Example: a bank Account with insert, deposit, withdraw (printing “Insufficient Balance” if amount < amt) and checkBalance. Starting at 1000, deposit 40000 gives 41000; withdraw 15000 gives 26000.

The this reference

When a local variable or parameter has the same name as an instance variable, it shadows it. Use this.name to refer to the instance variable.

class Student {
    int rollno; String name; float fee;
    Student(int rollno, String name, float fee) {
        this.rollno = rollno;
        this.name = name;
        this.fee = fee;
    }
}
class A {
    A()      { System.out.println("hello a"); }
    A(int x) { this();                       // calls the no-arg constructor
               System.out.println(x); }
}
new A(10);

hello a
10

this() invokes another constructor of the current class.

Overloaded constructors

A class can have any number of constructors that differ in the number or types of parameters. The compiler tells them apart by their parameter lists, e.g. Account(int a), Account(int a, int b), Account(String a, int b).

Default and no-argument constructors

• Every class must have at least one constructor.
• If you provide none, the compiler creates a default constructor with no arguments. It sets instance variables to their declared initial values or their default values.

Composition (has-a)

A class can have references to objects of other classes as members. This is composition, the has-a relationship. Example: an AlarmClock has two Time objects; a car has a steering wheel, a brake pedal and an accelerator.

enum types

A special class that defines a set of constants as unique identifiers.

public enum Season { WINTER, SPRING, SUMMER, FALL }

for (Season s : Season.values())
    System.out.println(s);
System.out.println(Season.valueOf("SUMMER").ordinal());

WINTER
SPRING
SUMMER
FALL
2

Garbage collection

Objects use system resources, such as memory. Java returns memory automatically through garbage collection: an object is marked for collection when no references to it exist. The finalize method (defined in java.lang.Object, no parameters, returns void) lets an object release other resources.

static class members and static import

• static class variable: class-wide information, shared by all objects.
• Access a public static member by qualifying it with the class name and a dot: Math.PI.
• A static import lets you use static members by their unqualified names. Two forms: import one static member, or all static members of a class.

import static java.lang.Math.*;
double r = sqrt(16) + abs(-3);   // no "Math." needed

final instance variables

final means the variable cannot be modified. Any attempt is a compile-time error. It enforces the principle of least privilege.

private final int INCREMENT = 5;     // a constant

Creating packages

A package is a group of related classes and interfaces. It helps manage complexity, supports reuse and gives unique class names. The convention is the reverse of your Internet domain name, e.g. com.deitel.

package pack;                 // file A.java
public class A { public void msg() { System.out.println("Hello"); } }

package mypack;               // file B.java
import pack.*;
class B { public static void main(String[] args) { new A().msg(); } }

Hello

Superclasses and subclasses

Inheritance is a mechanism in which one class acquires the properties and behaviors of another. It represents the IS-A relationship (parent-child) and gives software reusability.

• A subclass is a more specialized group of objects. It inherits the superclass behaviors, can customize them, and can add its own fields and methods.
• Direct superclass: inherited explicitly, one level up. Indirect superclass: two or more levels up.
• Single inheritance: one superclass. Multiple inheritance: several superclasses. Java does not support multiple inheritance for classes.

Types of inheritance

class Animal { void eat() { System.out.println("eating..."); } }
class Dog extends Animal { void bark() { System.out.println("barking..."); } }

Dog d = new Dog();
d.bark();
d.eat();      // inherited from Animal

barking...
eating...

protected members and super

protected is an intermediate level between public and private. A subclass reaches a superclass member with the keyword super and a dot.

class Superclass {
    int i = 20;
    void display() { System.out.println("Superclass display method"); }
}
class Subclass extends Superclass {
    int i = 100;
    void display() {
        super.display();                              // call parent version
        System.out.println("i value = " + i);
        System.out.println("superclass i value = " + super.i);
    }
}
new Subclass().display();

Superclass display method
i value = 100
superclass i value = 20

final class: if you do not want other classes to inherit from a class, declare it final. class Main extends Vehicle then gives “cannot inherit from final Vehicle”.

Polymorphism

Polymorphism means “many forms”. It occurs when many classes are related by inheritance and each performs the same action in its own way. You can treat objects in the same hierarchy as objects of the superclass. New classes can be added easily and still be processed.

In overriding, which method runs is decided by the object being referred to, not the reference type. Using a superclass reference for a subclass object is upcasting.

class Animal       { void eat() { System.out.println("Animals Eat"); } }
class Herbivores extends Animal { void eat() { System.out.println("Herbivores Eat Plants"); } }
class Carnivores extends Animal { void eat() { System.out.println("Carnivores Eat Meat"); } }

Animal h = new Herbivores();   // upcasting
Animal c = new Carnivores();   // upcasting
h.eat();
c.eat();

Herbivores Eat Plants
Carnivores Eat Meat

Abstract classes and interfaces

abstract class Animal {
    public abstract void animalSound();     // no body
    public void sleep() { System.out.println("Zzz"); }
}
class Pig extends Animal {
    public void animalSound() { System.out.println("The pig says: wee wee"); }
}
// Animal a = new Animal();   // ERROR: cannot instantiate an abstract class
Pig myPig = new Pig();
myPig.animalSound();
myPig.sleep();

The pig says: wee wee
Zzz

Fundamentals

• Characters are the fundamental building blocks of Java source programs. A character literal is written in single quotes, and its value is the integer Unicode value of the character.
• String represents strings. A String is an object, and String objects are immutable: they cannot be changed after creation.
• The String class has constructors that initialize String objects in several ways (empty, from another String, from a char array).

char[] charArray = {'b','i','r','t','h',' ','d','a','y'};
String s1 = "hello";
String s2 = new String(charArray);
System.out.println(s1.length());      // 5
System.out.println(s1.charAt(1));     // e

5
e

Comparing strings

String s1 = new String("hello");
System.out.println(s1 == "hello");        // false (different objects)
System.out.println(s1.equals("hello"));   // true
String s2 = "hello";
System.out.println(s2 == "hello");        // true (string literal)
System.out.println("hello".equals("Hello"));            // false
System.out.println("hello".equalsIgnoreCase("Hello"));  // true

compareTo() compares two strings lexicographically. It returns a positive number if the first is greater, a negative number if it is smaller, and 0 if they are equal.

System.out.println("Hello".compareTo("Hello"));   // 0
System.out.println("cargo".compareTo("cathode")); // -2  ('r' is 2 before 't')

Other String methods (see the book)

Tokenizing strings

A tokenizer partitions a string into individual substrings (tokens) using a delimiter. “His Name is Ali” becomes His, Name, is, Ali. Java offers java.util.StringTokenizer (and String.split).

Regular expressions

A regular expression is a sequence of characters and symbols that describes a search pattern. It is useful for validating input and ensuring data has a particular format. In Java, Pattern is an immutable compiled regular expression and Matcher performs the matching.

import java.util.regex.*;

Pattern p = Pattern.compile(".s");        // . = any single character
Matcher m = p.matcher("as");
boolean b1 = m.matches();                              // true
boolean b2 = Pattern.compile(".s").matcher("as").matches();  // true
boolean b3 = Pattern.matches(".s", "as");              // true

System.out.println(Pattern.matches(".s", "mk"));   // false (2nd char is not s)
System.out.println(Pattern.matches(".s", "mst"));  // false (more than 2 chars)
System.out.println(Pattern.matches("\\d", "1"));   // true (one digit)
System.out.println(Pattern.matches("\\d", "abc")); // false

Character classes

Quantifiers

Pattern.matches("[amn]", "a");              // true
Pattern.matches("[amn]", "ammmna");         // false (more than one char)
Pattern.matches("A+", "AAA");               // true
Pattern.matches("[a-zA-Z0-9]{6}", "arun32");   // true
Pattern.matches("[a-zA-Z0-9]{6}", "arun$2");   // false ($ not allowed)

Recursion concepts

A recursive method calls itself directly or indirectly through another method (A calls B, B calls A). It always has two parts:

Factorial

n! = n × (n − 1)!, and 1! = 1 is the base case. For example 5! = 5 × 4!, 4! = 4 × 3!, …, 1! = 1.

public static long factorial(long number) {
    if (number <= 1)                 // base case
        return 1;
    else                             // recursive step
        return number * factorial(number - 1);
}
System.out.println(factorial(3));

6

Trace of factorial(3): 3 * factorial(2) → 3 * (2 * factorial(1)) → 3 * (2 * 1) = 6. Each call waits for the next to return. Debugging with a breakpoint shows the chain of method calls in the call stack.

Fibonacci series

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … Each number is the sum of the previous two. Two base cases: fibonacci(0) = 0 and fibonacci(1) = 1.

public static long fibonacci(long n) {
    if (n == 0 || n == 1)            // base cases
        return n;
    else
        return fibonacci(n - 1) + fibonacci(n - 2);
}
System.out.println(fibonacci(2));    // fibonacci(1) + fibonacci(0) = 1 + 0

1

Recursion vs iteration

Anything that can be solved recursively can also be solved iteratively.

long result = 1;                         // factorial using iteration
for (int i = 2; i <= 5; i++)
    result *= i;                         // 120

Towers of Hanoi

Move all the disks to Tower 3. You cannot place a larger disk onto a smaller disk. The problem is naturally recursive: move the top n−1 disks to the spare tower, move the largest disk to the target, then move the n−1 disks onto it. With 3 disks you need 2³ − 1 = 7 moves.