Csci 1933: Introduction to

Algorithms and Data Structures

Spring 2022
 Overview
• Last time:
– Loops in Java, variable scope, strings/string
operations, started arrays

• Today:
• Finish arrays, Wrapper classes, Object-oriented
programming: composition, inheritance

• Announcements:
• Project 1 due tomorrow (Friday, 2/11, 7pm)
• Lab 3 due this Friday (last office hours)
• Midterm #1: February 24 (two weeks from
today)
 Midterm 1
• Thursday, February 24, 6:30-8:30pm
• Closed book, closed computer
• You are allowed 1 page (8.5” x 11”)
(2 sides) of handwritten notes

• Time limit: 2 hrs

• Example midterm + list of topics is posted

on Canvas (see “Week 4” module)
https://canvas.umn.edu/courses/290814
Brief review of defining Java classes/writing
main programs
Brief review of key concepts covered last time
Loop implementation of the
factorial operation

public static double loopFactorial(int x) {

double result=1;

for(int i=1; i <= x; i++) {

result *= i;
}

return result;
}
Reminders about solving problems
with recursion
Recursive solution: an operation that can be defined in
terms of itself
– Solving a problem using recursion depends on solving
smaller occurrences of the same problem

Two necessary components:

– base case: a simple occurrence that can be answered
directly

– recursive case: a more complex occurrence of the problem

that cannot be directly answered, but can be described in
terms of smaller occurrences of the same problem
Two implementations of the
factorial operation
public static double loopFactorial(int x) {
double result=1;

for(int i=1; i <= x; i++) {

result *= i;
}

return result;
}

public static double recurseFactorial(int x) {

double result;
if(x <= 1) { result=1;}
else {
result = x*recurseFactorial(x-1);
}
return result;
}
 Review of variable scope

• Variables declared in methods are visible inside the

current code block or any blocks nested within the
current block

• Parameter variables are visible only inside the

associated method

• Class member variables are visible throughout the

entire class
• if there’s a local variable with the same name, the
local variable has precedence— use
“this.<variable name>” to refer to the class
data member
 Class data member example
public class MyMath {
private double count=0;

public double factorial(double x) {

double result=1;

for(double i=1; i <= x; i++) {

result *= I; }
count++;
return result;
}

public double linearFunction(double m, double b, double x) {

double result=0;
result = m*x+b;

count++;
return result;
Code in main program:
} MyMath calculator = new MyMath();

calculator.linearFunction(10,0,1);
public double getNumCalls() { double sum=0;
return count; for(int i=1; i < 100; i++) {
} sum += calculator.factorial(i);
}
} System.out.println("NumCalls="+calculator.get
NumCalls());
 Strings in Java
• Strings are another built-in class (java.lang
package)
• Strings are immutable—once they’re created,
they can’t be modified
• Otherwise, they’re just objects, like everything
else we’ve talked about

String className = "UMN:CSCI:1933:Sec010";

//this also works but the top one is preferred
String className2 = new String("UMN:CSCI:1933:Sec010");

System.out.println(className);
 What’s the right way to compare Strings?
• Strings are objects just like most other things we’ve covered
• They have a defined set of methods for interacting with them, e.g.
char charAt(int index)
Returns the char value at the specified index.
String concat(String str)
Concatenates the specified string to the end of this string.
boolean equals(Object anObject)
Compares this string to the specified object.
boolean equalsIgnoreCase(String anotherString)
Compares this String to another String, ignoring case considerations.
int indexOf(int ch)
Returns the index within this string of the first occurrence of the specified character.
int indexOf(int ch, int fromIndex)
Returns the index within this string of the first occurrence of the specified character,
starting the search at the specified index.
int indexOf(String str)
Returns the index within this string of the first occurrence of the specified substring.
int indexOf(String str, int fromIndex)
Returns the index within this string of the first occurrence of the specified substring,
starting at the specified index.
int length()
Returns the length of this string.
String replaceAll(String regex, String replacement)
Replaces each substring of this string that matches the given regular expression with
the given replacement.
String[] split(String regex)
Splits this string around matches of the given regular expression.

See https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/lang/String.html for many more

 Comparing strings (2)
• compareTo method
• compares two Strings to see which is alphabetically first
• returns an integer
• negative  string you’re comparing is alphabetically before the
string passed
• positive  string you’re comparing is alphabetically after the
string passed
• 0  the two Strings are equal

• case-sensitive— with lower-case letters considered to be after upper-

case ones
String letterA = "A";
String lettera = "a"; Output:
String letterb = "b"; -33
32
System.out.println(letterA.compareTo(letterb));
System.out.println(lettera.compareTo(letterA));

(Also compareToIgnoreCase() method – treats upper and lower case the same)
 Searching within strings
• int indexOf(char c): finds first occurrence of character c

• int indexOf(char c, int p): finds the first occurrence of

character c at or beyond position p.

• int indexOf(String s): finds the first occurrence of String s, and

returns the position of the first character of s, if any.

• int indexOf(String s, int p): finds the first occurrence of

String s at or beyond position p.

String className = "UMN:CSCI:1933:Sec001";

System.out.println(className.indexOf("CSCI"));
Output:
System.out.println(className.indexOf(":",4));
4
8
 Another useful string class
StringTokenizer
• StringTokenizer is a class that’s built for splitting up
strings
Typical use:
StringTokenizer st = new StringTokenizer(<string>,<delimiter>);
(default delimiter– space)

• Example:
String className = "UMN:CSCI:1933:Sec001";
StringTokenizer st = new Output:
StringTokenizer(className,":"); 1:UMN
2:CSCI
int count=1; 3:1933
while(st.hasMoreTokens()) {
4:Sec001
System.out.println(count+":"+st.nextToken());
count++;
}
 Array declarations
• Declaration/initialization of arrays:

Primitives Arrays

Declaration int myInt; int[] myArray;

myArray = new int[7];

myInt = 5;
OR
Initialization OR
int[] myArray = new
int myInt=5;
int[7];
 Looping over arrays

Standard loop structure:

for(int i = 0; i < myArray.length; i++){
if(i == 0){
myArray[i] = 0;
}else if(i == 1){
myArray[i] = 1;
}else{
myArray[i] = myArray[i-1]
}
}

• What kind of thing is length?

 Arrays exercise
Linear search

int[] myArray = {30, 50, 40, 33, 12};

public static int linearSearch(int[] a, int key)

Find max element

int[] a = new int[]{23, 565, 21, 56, 22,1000,675, 123, 676, 87};
New material
 Overview of today’s material

• More Java programming basics:

- Finish arrays
- Wrapper classes

• Object-oriented programming:
- Composition
- inheritance
Arrays
 Assignment operators
For array elements, "=" is a copy operation:

temperatures[monday] = temperatures[sunday];

For array references, "=" is an alias operation:

int[] b = new int[10];

int[] a = b;
a[0] = 5;
b[0] = 3;
System.out.println(“a[0] = “ + a[0]);
 More looping on arrays
• One useful type of loop that can help you avoid out
of range indexing
• For-each loop
for(<local var. declaration> : <array>) {
<block of code>
}

Output:
Ashlee
Austin
String[] TAs ={“Ashlee",“Austin",“Alice",“Isaac"}; Alice
for (String curr : TAs) { Isaac
System.out.println(curr);
}
Output:
int[] intArray = {1,2,3,4}; 1
for(int curr : intArray) { 2
System.out.println(curr); 3
} 4
 Passing arrays to functions
public static double calcMean(int[] a) {
double result=0;

for(int i=0; i < a.length; i++) {

result += a[i];
}

return(result/a.length);
}

In main program:
int arr[] = {10, 90, 49, 2, 1, 5, 23};
System.out.println("Mean: "+calcMean(arr));
 Passing arrays to functions (2)
public static void negateArray(int[] arr) {
for(int i=0; i < arr.length; i++) {
arr[i]=-arr[i];
}

In main program:
int arr[] = {10, 90, 49, 2, 1, 5, 23};
negateArray(arr);
System.out.println("Negated element: "+arr[0]);

The variable arr is a reference that points to an array!

 Returning arrays from functions
public static int[] getZeros(int length) {
int[] newarr = new int[length];

for(int i=0; i < newarr.length; i++) {

newarr[i]=0;
}

return(newarr);
}

In main method:
int[] zeroArray = getZeros(10);
System.out.println("Length: "+zeroArray.length+",
first element: "+zeroArray[0]);

Note zeroArray is only declared, we don’t need to allocate memory

because we are getting a reference to an already constructed array
Practice with arrays
 What’s wrong with this code?

Circle[] circleArray = new Circle[10];

int count=0;
Scanner keyboard = new Scanner(System.in);
while(true) {
System.out.println("Enter radius or ‘N’ to quit:");

if(keyboard.hasNextInt()) {
circleArray[count++] = new Circle(0,0,keyboard.nextInt());
} else { break; }
}
 What’s wrong with this code?

Circle[] circleArray = new Circle[10];

int count=0;
Scanner keyboard = new Scanner(System.in);
while(true) {
System.out.println("Enter radius or ‘N’ to quit:");

if(keyboard.hasNextInt()) {
circleArray[count++] = new Circle(0,0,keyboard.nextInt());
} else { break; }
}

Throws ArrayIndexOutOfBoundsException!

We’re trying to index beyond the end of circleArray

Important: Java arrays are of fixed size
 Indexing out of bounds
• Java throws an exception: tells you that
something unexpected happened your
program is stopped
• Lesson: design your code to avoid out of
bounds indexes
• Sometimes this means anticipating
“dangerous” user input— this can be a major
issue!
(More about exceptions later)
 A little history: the Morris worm
• Robert Morris (grad. student Cornell), 1988
• One of the first computer worms
– Purpose: count how many computers were connected
to the internet
– Check if computer was infected, if not, replicate; 1 in 7
times replicate anyway
– Buffer overflow exploit:
• Extra data goes somewhere in memory beyond the end of
an array
• If you design the overflow data right, you can take control of
the computer (data interpreted as binary instruction)
 Morris worm

• Infected ~10% of the internet (~60k total

computers at the time)
• Sentence: 3 yrs probation, 400 hrs community
service, $10k fine
• Now: a professor at MIT
• Moral of the story
– Be careful with indexing arrays (check bounds, etc.)!
(not: it’s ok to write worms that take down the internet)
 Back to the Circle array example
Circle[] circleArray = new Circle[100];
int count=0;
Scanner keyboard = new Scanner(System.in);
while(count < 100) {
System.out.println("Enter radius or ‘N’ to quit:");

if(keyboard.hasNextInt()) {
circleArray[count++] = new
Circle(0,0,keyboard.nextInt());
} else { break; }
}

• I’ve fixed the out of bound indexing problem, but

• How can we resize this array to remove wasted space if the user
doesn’t take it all?
• Remember: arrays are technically fixed size

Exercise: Write a function called resize that can compact our array
Exercise
 Resize function

public static Circle[] resize(Circle[] array, int count) {

Circle[] newArray = new Circle[count];
for(int i=0; i < count; i++) {
newArray[i] = array[i];
}
return newArray;
}
 Multi-dimensional arrays
• Data is often structured in multi-dimensional
tables, e.g.
– a grade spreadsheet with students on the rows
and homework assignments on the columns
– an gray-scale image (a matrix of pixels, e.g.
500x1700 pixels)
– a color image (500x1700x3, 3 color values/pixel)
• Java also allows multi-dimensional arrays
double[][] grades = new double[120][6];
for(int i=0; i < 120; i++) {
for(int j=0; j < 6; j++) {
grades[i][j]=100;
}
}
 Multidimensional arrays
double[][] grades = new double[120][6];

for(int i=0; i < grades.length; i++) {

for(int j=0; j < grades[i].length; j++) {
grades[i][j]=100;
}
}

• What is grades.length?
• How about grades[0].length?

Don’t have to stop at 2 dimensions– can go as

far as we want
 Operations on arrays

• Useful functions for arrays:

– Built-in class Array (java.util.Arrays)
– Useful (static) methods:
• equals(int[] a, int[] b), equals(double[] a, double[] b), …
• fill(int[] a, int val), fill(double[] a, double val), …
• sort(int[] a)…toString(int[] a), …
• binarySearch(int[] a, int key), …
• toString(int[] a), …
• copyOf(int[] a, int length), ....

(https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Arrays.html )
 Example: array operations

int[] numArray = new int[100];

Random randomNumGenerator = new Random();

for(int i=0; i < numArray.length; i++) {
numArray[i] = randomNumGenerator.nextInt(100);
}

System.out.println("Original:");
System.out.println(Arrays.toString(numArray));

System.out.println("Sorted:");
Arrays.sort(numArray);
System.out.println(Arrays.toString(numArray));
 Example 2: array operations
int[] numArray = new int[100];

Random randomNumGenerator = new Random();

for(int i=0; i < numArray.length; i++) {
numArray[i] = randomNumGenerator.nextInt(100);
}

System.out.println("Original:");
System.out.println(Arrays.toString(numArray));

System.out.println("Sorted:");
Arrays.sort(numArray);
System.out.println(Arrays.toString(numArray));

int result = Arrays.binarySearch(numArray,5);

//Must be sorted first!!

if(result > 0) {
System.out.println("Found! Index:"+result);
} else {
System.out.println("Not found! Index:"+result);
}
 Overview of today’s material

• More Java programming basics:

- Finish arrays
- Wrapper classes

• Object-oriented programming:
- Composition
- inheritance
Wrappers
 Wrappers
• By now, you should be familiar with the
distinction between primitive types and class
types
– Primitives: int, double, char
– Class (reference) types: everything else in Java
(e.g. String, Scanner, Circle, …)

• Wrappers for primitives: a class version that

stores the primitive type
e.g. integers now become Java objects
 Primitive wrappers in Java
Primitive Wrapper class (built-in)
boolean java.lang.Boolean
byte java.lang.Byte
char java.lang.Character
double java.lang.Double
float java.lang.Float
int java.lang.Integer
long java.lang.Long
short java.lang.Short

Why might these be useful?

• Answer: there are many built-in classes for storing data (data structures), and
they can only store object references
• In general: “cleaner” if everything is an object

• Caution: this is not usually the most efficient, so if efficiency is important—

wrapper types are probably a bad idea!
Example where wrappers might be
useful
• Built-in Vector class (see Java API)

• Very similar to array, but more flexible:

designed to grow or shrink as needed—no
need to worry about resizing or wasting
memory
• Can only store object references (need class
type, not primitive type)
 Wrapper example

double num = 5.0;

Double objectD = Double.valueOf(num);

• What’s going on? We’re creating a Double

wrapper object by passing the double value
into the valueOf method
• You can always get back to the primitive type
by calling the right method

double r = objectD.doubleValue();
Example for doubles:
double num = 5.0;
Double objectD = Double.valueOf(num);
double r = objectD.doubleValue();

Example for integers:

int i = 5;
Integer objectI = Integer.valueOf(i); Boxing
int j = objectI.intValue();
Un-boxing

•“Boxing”—the process of wrapping up a primitive into an object

•“Un-boxing” – the process of retrieving a primitive from the object type
The Integer wrapper class API

https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/lang/Integer.html
 Auto-boxing/un-boxing
• Auto-boxing and auto-unboxing:
Integer wrapper_integer = 5; Integer wrapper_integer = Integer.valueof(5);

(Note: Java is smart-- don’t need to use valueOf method here to get Integer object)

int primitive_int = wrapper_integer;

int primitive_int = wrapper_integer.intValue();

(Note: again, Java is smart—don’t need to use intValue method here)

• For example, you could also do this if you wanted:

Integer sum = 0;
for(Integer counter=1; counter < 100; counter++) {
sum += counter;
}
Careful—this should only be used when necessary! Unboxing and boxing is inefficient!
An example where it makes sense to use
wrappers

Vector<Integer> intValues = new Vector<Integer>();

Integer intObject = 3;
intValues.add(intObject);
Integer intObject2 = 4;
intValues.add(intObject2);

The built-in Vector class will only store objects (not primitive types)
 Overview of today’s material

• More Java programming basics:

- Finish arrays
- Wrapper classes

• Object-oriented programming:
- Composition
- inheritance
More on object-oriented programming
Back to object-oriented programming: two important
concepts for today

• Composition:
Using classes as data members of other classes
– Generic Types
– Adapters

• Inheritance
Designing hierarchically organized classes that
“inherit” data members and methods
– Access to fields/methods of the base class
– Protected Access
– Overriding, Overloading Methods
 Composition

• When a class has a data field that is an instance of

another class
• Example – an object of type Student.

A "has a"
relationship

fig 2-1

A Student object composed of other objects

Carrano and Henry, Data Structures and Abstractions with Java.
 Reminder: the Name class
public class Name {
private String first; // first name
private String last; // last name

public Name () {
first = ""; last = "";
} // end default constructor

public Name (String firstName, String lastName) {

first = firstName;
last = lastName;
} // end constructor

public void setName (String firstName, String

lastName) {
setFirst (firstName);
setLast (lastName); } // end setName

public String getName () {

return toString (); } // end getName

//other get/set methods...

}
 Example: the Student class
public class Student {
private Name fullName;
private String id; // identification number

public Student () {
fullName = new Name (); id = ""; } // end default constructor

public Student (Name studentName, String studentId) {

fullName = studentName; id = studentId; } // end constructor

public void setStudent (Name studentName, String studentId) {

setName (studentName); // or fullName = studentName;
setId (studentId); // or id = studentId;
} // end setStudent

public void setName (Name studentName) {

fullName = studentName; } // end setName

public Name getName () { return fullName; }

public void setId (String studentId) {

id = studentId; } // end setId

public String getId () {

return id; } // end getId
}
 Exercise: how would you implement a toString()
method?
public class Student {
private Name fullName;
private String id; // identification number

public Student () {
fullName = new Name (); id = ""; } // end default constructor

public Student (Name studentName, String studentId) {

fullName = studentName; id = studentId; } // end constructor

public void setStudent (Name studentName, String studentId) {

setName (studentName); // or fullName = studentName;
setId (studentId); // or id = studentId;
} // end setStudent

public void setName (Name studentName) {

fullName = studentName; } // end setName

public Name getName () { return fullName; }

public void setId (String studentId) {

id = studentId; } // end setId

public String getId () {

return id; } // end getId
}
 A toString() method for the Student class

public String toString() { Which of these will

return (id+first+last);
} work? If not, why not?
public String toString() {
return (id+fullName.first+fullName.last);
}

public String toString() {

return (id+fullName.getFirst()+fullName.getLast());
}

public String toString() {

return (id+fullName.toString());
}
 A toString() method for the Student class

public String toString() { Which of these will

return (id+first+last);
} work? If not, why not?
public String toString() {
return (id+fullName.first+fullName.last);
}

public String toString() {

return (id+fullName.getFirst()+fullName.getLast());
}

public String toString() {

return (id+fullName.toString());
}

Take-home message: for classes that are member

variables, you must respect the standard rules of
method/variable access
Where are you using composition in Project #1?
 Project #1 composition example
import java.awt.*;
public class Triangle {
double x,y,h,w;
Color color;

public Triangle(double x, double y, double h, double w){

...

public double calculatePerimeter(){

...
} Composition is very
public double calculateArea(){ common– you will
}
...
use it in some form
public void setColor(Color c){
...
in most applications
}
public void setPos(double x,double y){
...
}

...
}
 Two special cases of composition

• Generic types
– Class contains a member variable, but its type can
vary
– Example: we might have a data container that
could be used for multiple types, it would be nice
if we could pass the type as a “parameter”

• Adapters
– Using composition to customize an existing class–
remove/add methods or modify the names of
some of its existing methods
 Generic Types
• Consider a class with fields that can be of any class type
• Use a generic type
– Follow class name with an identifier enclosed in angle
brackets
public class MyClass <T>
• T is a placeholder for the type, which you specify
when you instantiate an object from this class
• Rule: T can only be specified as a reference (class
type), doesn’t work with primitives

(type naming convention: single, uppercase letters, e.g. T, E, V, K)

Carrano and Henry, Data Structures and Abstractions with Java.

 An example of generic types: the Point class
public class Point<T> {
private T x;
private T y; Note: T is used as
public Point() { a placeholder
} throughout the
class definition
public Point(T inX, T inY) {
x = inX;
y = inY;
}

public void setPoint(T inX, T inY) {

x = inX;
y = inY;
}
public String toString() {
return "(" + x + ", " + y + ")";
}

In a main method:
Point<Integer> start = new Point<Integer>(5, 7);
Point<Double> end = new Point<Double>(0.5,0.7);
 Generics examples

Point<Integer> start = new Point<Integer>(5, 7);

Point<Double> end = new Point<Double>(0.5,0.7);

start.setPoint(0.5,0.5);
end.setPoint(0.5,0.5);

What’s wrong with this code?

 Generics examples

Point<Integer> start = new Point<Integer>(5, 7);

Point<Double> end = new Point<Double>(0.5,0.7);

start.setPoint(0.5,0.5);
end.setPoint(0.5,0.5);

What’s wrong with this code?

Point<float> start = new Point<float>(0.5, 0.7);

What about this code?

 A more sophisticated use of Generics
public class OrderedPair < T > {
private T first, second;

public OrderedPair () { } // end default constructor

public void setPair (T firstItem, T secondItem) {
first = firstItem;
second = secondItem;
} // end setPair

public void changeOrder () {

T temp = first;
first = second;
second = temp;
} // end changeOrder

public String toString () {

return "(" + first + ", " + second + ")";
} // end toString

} // end OrderedPair

In a main method:
OrderedPair<String> fruit = new OrderedPair<String>();
fruit.setPair("apples", "oranges"); Output:
System.out.println(fruit); (apples, oranges)
fruit.changeOrder(); (oranges, apples)
System.out.println(fruit);
 A Generic type with multiple types

public class OrderedPair<K, V> {

private K key;
private V value;

public OrderedPair(K key, V value) {

this.key = key;
this.value = value;
}
public K getKey() {
return key; }
public V getValue() {
return value; }
}
 Adapters

• General approach of using composition to

customize an existing class
• Implementation:
– Use composition to include existing class as a
member variable
– Implement “custom” methods that rely on
member’s classes where necessary

Carrano and Henry, Data Structures and Abstractions with Java.

 Adapter example
public class NickName {
private Name nick;

public NickName () {
nick = new Name ();
} // end default constructor

public void setNickName (String nickName) {

nick.setFirst (nickName);
} // end setNickName

public String getNickName () { Note: the NickName class actually

return nick.getFirst (); loses some functionality even
} // end getNickName though it is based on Name
-- this can be useful though
} // end NickName

In a main method: Name name = new Name(“Charles”,”Norris”);

System.out.println(name.getLast());

NickName nick = new NickName(“Chuck”);

System.out.println(nick.getNickName());
System.out.println(nick.getLast());
 Composition: summary

• Composition: Using classes as data members of other

classes
– Special cases:
• Generic classes: Class contains a member
variable, but its type can vary
• Adapter classes: Using composition to
customize an existing class
 Overview of today’s material

• More Java programming basics:

- Finish arrays
- Wrapper classes

• Object-oriented programming:
- Composition
- Inheritance
 Inheritance
Basic idea: objects are sometimes hierarchically related to
each other (abstractly) in that they “inherit” data or
methods from more general classes

This principle can be used to organize classes so that

some common properties/behaviors can be defined only
once
An "is a" relationship
(contrast with
Composition– “has a”)

Carrano and Henry, Data Structures and Abstractions with Java.

 Inheritance example: the Student class

• Assume your first job is at a software company that’s

been asked to write a student record management
system
• We’ve identified the classes (objects) we’ll need
• How should we go about implementing them?
Carrano and Henry, Data Structures and Abstractions with Java.
 Bad solution
public class Student {
private Name fullName;
private String id; // identification number

public class
public UndergradStudent
Student () { {
private Name
fullName = fullName;
new Name (); id = ""; } // end default constructor
private String id; // identification number
public Student (Name studentName, String studentId) {
public
public Student
fullName
class () {
=HighSchoolStudent
studentName; id ={ studentId; } // end constructor
fullName
private = new
Name Name (); id = ""; } // end default constructo
fullName;
public void setStudent (Name id;
private String studentName, String studentId)
// identification number {
public Student
setName (Name studentName,
(studentName); String =studentId)
// or fullName {
studentName;
fullName
setIdpublic = studentName;
(studentId);
Student //
()or id = studentId; } // end constructor
{ id = studentId;
} // end setStudent fullName = new Name (); id = ""; } // end default con
public void setStudent (Name studentName, String studentId) {
setName
public void setName
public (studentName);
(Name studentName)
Student //
{ or fullName
(Name studentName, String= studentId)
studentName;
{
setId (studentId);
fullName = studentName; // or id
fullName = }studentName;= studentId;
// end setName
id = studentId; } // end con
} // end setStudent
public Name getName
public () { return
void fullName;
setStudent (Name }studentName, String studentId) {
public void setName (Name
setName studentName) //
(studentName); { or fullName = studentName;
public void setIdfullName
(String= studentId)
studentName;
setId { } //
(studentId); // end setName
or id = studentId;
id = studentId; } // end setId
} // end setStudent
public Name getName () { return fullName; }
public String public
getId () { setName (Name studentName) {
void
public void
return id;setId
} // (String = studentId)
end getId
fullName studentName;{ } // end setName
} id = studentId; } // end setId
public Name getName () { return fullName; }
public String getId () {
 A better solution
• Use inheritance!
• Let’s define a general base (ancestor) class, Student, which
contains all the basic data/methods associated with any type
of student
• Then we can define several derived classes (descendants) that
inherit and extend the functionality of Student
 The CollegeStudent derived class
public class CollegeStudent extends Student {
private int year; // year of graduation
private String degree; // degree sought

public CollegeStudent()
{
super();
year = 0;
degree = "";
} // end default constructor

public CollegeStudent(Name studentName, String studentId,

int graduationYear, String degreeSought)
{
super(studentName, studentId); // must be first
year = graduationYear;
degree = degreeSought;
} // end constructor

public void setStudent(Name studentName, String studentId,

int graduationYear, String degreeSought)
{
setName(studentName);
setId(studentId);

year = graduationYear;
degree = degreeSought;
} // end setStudent

// < The methods setYear, getYear, setDegree, to String, and getDegree go here.>
// . . .
} // end CollegeStudent
 Reminder: the Student class
public class Student {
private Name fullName;
private String id; // identification number

public Student () {
fullName = new Name (); id = ""; } // end default constructor

public Student (Name studentName, String studentId) {

fullName = studentName; id = studentId; } // end constructor

public void setStudent (Name studentName, String studentId) {

setName (studentName); // or fullName = studentName;
setId (studentId); // or id = studentId;
} // end setStudent

public void setName (Name studentName) {

fullName = studentName; } // end setName

public Name getName () { return fullName; }

public void setId (String studentId) {

id = studentId; } // end setId

public String getId () {

return id; } // end getId
}
 Important notes about CollegeStudent derived
class
• the class CollegeStudent has all the data fields and methods of
Student, but notice that we don’t write them in the class definition
(i.e. they’re automatically “inherited”)
• Example:
CollegeStudent student = new
CollegeStudent(“John”,”Doe”,”1234”,2024,”Basketweaving”);
student.setName(new Name(“Jane”,”Doe”));

Note: setName method is not explicitly defined in CollegeStudent, but we

can still use it
Why?
– It’s defined in base class
– It’s public in the base class
 Important notes about CollegeStudent derived
class
• We have added more member variables and methods (behaviors,
example: year, degree, setStudent that takes in extra parameters) (i.e.
we have “extended” or specialized the student class to match what
data we need to store about a college student)
• Example:
CollegeStudent student = new CollegeStudent(“John”,”Doe”,”1234”,2024,”Basketweaving”);

System.out.println(“John’s major is: “+ student.getDegree());

Note: degree is a new member variable and getDegree is a new (public)

method of the CollegeStudent class
 Important notes about CollegeStudent derived
class
• Example: setStudent method definition in CollegeStudent class
public void setStudent(Name studentName, String studentId,
int graduationYear, String degreeSought)
{
setName(studentName);
setId(studentId);

year = graduationYear;
degree = degreeSought;
} // end setStudent

For the boxed section, can we do this instead? Why or why not?

fullName = studentName;
id = studentId;

No-- fullName and id are private members of the Student class!

IMPORTANT– even though the data members exist, we need to respect
access modifiers!
 Private fields methods access summary

• Accessing inherited data fields

– Not accessible by name within definition of a method from
another class – including a derived class
– Still they are inherited by the derived class
• Derived classes must use public methods of the base
class
• Note that private methods in a base class are also
unavailable to derived classes

Carrano and Henry, Data Structures and Abstractions with Java.

 Protected Access summary

• A method or data field modified by protected can

be accessed by name only within
– Its own class definition
– Any class derived from that base class
– Any class within the same package

Carrano and Henry, Data Structures and Abstractions with Java.

 Protected Access

• Note accessibility of elements of a class C

determined by the access modifiers

(default- no
modifier)

Carrano and Henry, Data Structures and Abstractions with Java.

 Important detail: Invoking Constructors
from Within Constructors

• Constructors usually initialize data fields

• Question: how can we initialize member variables in
the base class when using the derived class?
• Answer:
– We need to define a constructor for the derived
class
– That constructor should call the base class
constructor

Carrano and Henry, Data Structures and Abstractions with Java.

 Important detail: Invoking Constructors from
Within Constructors
• In the derived class, we use the reserved word super as a
name for the constructor of the base class
– When super is used, it must be the first action in the
derived constructor definition
– Must not use the name of the constructor
public CollegeStudent()
{
super(); //must be first if called (super() is called implicitly)
year = 0;
degree = "";
} // end default constructor

public CollegeStudent(Name studentName, String studentId,

int graduationYear, String degreeSought)
{
super(studentName, studentId); // must be first
year = graduationYear;
degree = degreeSought;
} // end constructor
 Important detail: Invoking Constructors from
Within Constructors
• If you don’t call super Java will do it for you before
executing any code in your derived class’s constructor
• Example:
public CollegeStudent(Name studentName, String studentId,
int graduationYear, String degreeSought)
{
year = graduationYear;
degree = degreeSought;
} // end constructor

Is equivalent to:
Good practice: always be
explicitstudentId,
public CollegeStudent(Name studentName, String about which base
int graduationYear, String you
class constructor degreeSought)
want
{ to call
super();
year = graduationYear;
degree = degreeSought;
} // end constructor

Why is this probably a bad idea?

 New concepts: overriding and overloading

• Overriding a method: when a derived class defines a

method with exactly the same signature as in base
class

• Overloading a method: defining a new method with

the same name, but different signatures
 Overriding Methods

• When a derived class defines a method with the

same signature as in base class
– Same name
– Same return type
– Same number, types of parameters
• Objects of the derived class that invoke the method
will use the definition from the derived class
• It is possible to use super in the derived class to call
an overridden method of the base class

Carrano and Henry, Data Structures and Abstractions with Java.

 An example from the CollegeStudent class
In Student class:
public String toString ()
{
return id + " " + fullName.toString ();
} // end toString

In CollegeStudent class:

public String toString()

{
return super.toString() + ", " + degree + ", " + year;
} // end toString

Why is this useful?

• derived classes often have specialized data/functions but
we’d like to be able to interact with objects in the same way
 Overriding Methods

The method toString in CollegeStudent

overrides the method toString in Student

Note: you cannot override a private method from the base class

Carrano and Henry, Data Structures and Abstractions with Java.

 Stopping methods from being overridden

• A programmer may wish to specify that a method

definition cannot be overridden
– So that the behavior of the constructor will not be
changed
• This is accomplished by use of the modifier final

Carrano and Henry, Data Structures and Abstractions with Java.

 Overloading a Method

• When the derived class method has

– The same name
– The same return type … but …
– Different number or type of parameters
• Then the derived class has available
– The derived class method … and
– The base class method with the same name
• Java distinguishes between the two methods due to
the different parameters

Carrano and Henry, Data Structures and Abstractions with Java.

 Overloading example
In Student class:
public void setStudent(Name studentName, String studentId)
{
setName(studentName); // or fullName = studentName;
setId(studentId); // or id = studentId;
} // end setStudent

In CollegeStudent class:
public void setStudent(Name studentName, String studentId,
int graduationYear, String degreeSought)
{
setName(studentName);
setId(studentId);
// or setStudent(studentName, studentId);

year = graduationYear;
degree = degreeSought;
} // end setStudent
 Example question
In Student class:
public void setStudent(Name studentName, String studentId)
{
setName(studentName); // or fullName = studentName;
setId(studentId); // or id = studentId;
} // end setStudent

In CollegeStudent class:
public void setStudent(Name studentName, String studentId)
{
setName(studentName);
setId(studentId);
// or setStudent(studentName, studentId);

year = 2022;
degree = “Not declared”;
} // end setStudent

Overriding or overloading?
 Example question
public class Student
{
private Name fullName;
private String id; // identification number

public Student()
{
fullName = new Name();
id = "";
} // end default constructor

public Student(Name studentName, String studentId)

{
fullName = studentName;
id = studentId;
} // end constructor
}

Overriding or overloading?
 Inheritance: summary

• Inheritance: defining new classes that are derived

from existing classes– they then inherit the data and
methods from the base class
– “base” class
– “derived” class
• Public methods from the base class can be used for
instances of the derived class
• Methods/member variables can be added to extend
functionality
– Overriding vs. overloading methods
 Object-oriented design exercise

Think about Project #1:

Triangle, Rectangle, Circle
• How might we design these classes better now that
we know more about object-oriented programming?
• Composition or inheritance?
• What methods should be implemented, and where?
• Remember:
– get/set x,y position
– get/set color
– Calculate perimeter
– Calculate area
– Get/set radius/height/width
 Abstract Classes and Methods
• Some base classes are not intended to have objects
of that type
– The objects will be of the derived classes
• Declare that base class to be abstract
public abstract class Whatever
{ . . . }
• The designer often specifies methods of the abstract
class without a body
public abstract void doSomething();
– This requires all derived classes to implement this method
• Note: we can’t create instances of abstract class types–
they’re only used as “guidelines” for what methods must be
implemented in derived classes
Carrano and Henry, Data Structures and Abstractions with Java.
 Example: an abstract Student class
public abstract class Student {
private Name fullName;
private String id; // identification number

public Student () {
fullName = new Name (); id = ""; } // end default constructor

public Student (Name studentName, String studentId) {

fullName = studentName; id = studentId; } // end constructor

public void setStudent (Name studentName, String studentId) {

setName (studentName); // or fullName = studentName;
setId (studentId); // or id = studentId;
} // end setStudent

public void setName (Name studentName) {

fullName = studentName; } // end setName

public Name getName () { return fullName; }

public void setId (String studentId) {

id = studentId; } // end setId

public String getId () {

return id; } // end getId

public abstract void display();

}
Interfaces
 Interfaces

• Interface: A program component that contains

– Public constants
– Signatures for public methods
– Comments that describe them
• Begins like a class definition
– Use the word interface instead of class

Carrano and Henry, Data Structures and Abstractions with Java.

 Writing an Interface
• Consider geometric figures which have both a
perimeter and an area
• We want classes of these objects to have such
methods
– And we want standardization signatures
• Example:
public interface Measurable {
/** Task: Gets the perimeter. * @return the perimeter */
public double getPerimeter();

/** Task: Gets the area. * @return the area */

public double getArea();
} // end Measurable

Carrano and Henry, Data Structures and Abstractions with Java.

 Java Interface Example
public interface Measurable {
/** Task: Gets the perimeter. * @return the perimeter */
public double getPerimeter();

/** Task: Gets the area. * @return the area */

public double getArea();
} // end Measurable

• Note
– Comments of method purpose, parameters, pre-
and post-conditions
– Any data fields should be public, final, and static
– Interface methods cannot be final

Carrano and Henry, Data Structures and Abstractions with Java.

 Implementing an Interface

• A class that implements an interface must state so at

start of definition with implements clause

• The class must implement every method declared in

the interface
• Multiple classes can implement the same interface
• A class can implement more than one interface

Carrano and Henry, Data Structures and Abstractions with Java.

 Implementing an Interface

The files for an interface, a class that implements the

interface, and the client.
Carrano and Henry, Data Structures and Abstractions with Java.
 An Interface as a Data Type

• An interface can be used as a data type

or …

Carrano and Henry, Data Structures and Abstractions with Java.

 Generic Types Within an Interface

• Recall OrderedPair class we discussed before

• Note the setPair method
• Consider an interface Pairable that declares this
method

A class that implements this interface could begin with the statement

Carrano and Henry, Data Structures and Abstractions with Java.

 The Interface Comparable
• Built-in Java interface– used in many data structures
(sorting, etc.)
• Method compareTo compares two objects, say x
and y
– Returns signed integer
– Returns negative if x < y
– Returns zero if x == y
– Returns positive if x > y

Carrano and Henry, Data Structures and Abstractions with Java.

 Comparable interface example

public class Circle implements Comparable < Circle > {

private double radius, xPos, yPos;
Color circColor;

// Definitions of constructors and methods here

public int compareTo (Circle other) {

int result;
if (Math.abs(this.radius – other.radius) < .001) {
result = 0; }
else if (radius < other.radius) result = -1;
else result = 1;
return result;
} // compareTo

}
 Comparable interface example
public class Circle implements Comparable < Circle > {
private double radius, xPos, yPos;
Color circColor;

// Definitions of constructors and methods here

public int compareTo (Circle other) {

int result;
if (Math.abs(this.radius – other.radius) < .001) {
result = 0; }
else if (radius < other.radius) result = -1;
else result = 1;
return result;
} // compareTo

Implementing the Comparable interface enables us to make use of

some useful built-in classes, e.g. remember Arrays?
Circle[] circleArray = new Circle[100];
//initialize circleArray objects...

Arrays.sort(circleArray);

Arrays class’s static method sort knows how to handle any

object that implements the Comparable interface
 Interfaces Versus Abstract Classes
• Purpose of interface similar to purpose of abstract
class
• But … an interface is not a base class
– It is not a class of any kind
• Use an abstract base class when
– You need a method or private data field that
classes will have in common
• Otherwise use an interface

Carrano and Henry, Data Structures and Abstractions with Java.

 Important reminders
• Project 1 due tomorrow (Friday, 2/11) by 7pm!

• Lab 3: Check off milestones with TA by last office

hours on Friday (tomorrow)

• Midterm Exam #1: February 24 (two weeks from

today)