Data Structures and Algorithms
Chapter 2
Inheritance • Inheritance hierarchy example
ArithmeticProgression # increment: long
# advance()
GeometricProgression # base: long
# advance()
FibonacciProgression # prev: long
# advance()
Inheritance
Progression # current: long
+ nextValue(): long
+ printProgression(n: int) # advance()
Inheritance /* not a complete code */
public class Progression {
}
protected long current;
public Progression( ) { this(0); }
public Progression(long start) { current = start; } public long nextValue( ) {
}
protected void advance( ) {
}
public void printProgression(int n) {
}
Inheritance /* not a complete code */
public class ArithmeticProgression extends Progression {
}
protected long increment;
public ArithmeticProgression( ) { this(1, 0); }
public ArithmeticProgression(long stepsize) {
}
public ArithmeticProgression(long stepsize, long start) { }
protected void advance( ) {
}
Inheritance /* not a complete code */
public class FibonacciProgression extends Progression {
}
protected long prev;
public FibonacciProgression( ) { this(0, 1); }
public FibonacciProgression(long first, long second) { }
protected void advance( ) {
}
Interface
• Usedtospecifya“contract”betweendifferent programs.
• No data
• Methods do not have implementation.
• Cannot be instantiated.
• Can be used for multiple inheritance.
• Aclassimplementinganinterfacemust implements all methods.
3
4
5
6
7
8 9}
/** Returns a description of the object. */ public String description( );
/** Returns the list price in cents. */ public int listPrice( );
Interface
1 /** Interface for objects that can be sold. */
2 public interface Sellable {
/** Returns the lowest price in cents we will accept. */ public int lowestPrice( );
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private String descript;
private int price;
private boolean color;
public Photograph(String desc, int p, boolean c) { // constructor
/** Class for photographs that can be sold. */ public class Photograph implements Sellable {
}
descript = desc; price = p;
color = c;
Interface
}
public String description( ) { return descript; } public int listPrice( ) { return price; }
public int lowestPrice( ) { return price/2; } public boolean isColor( ) { return color; }
// description of this photo // the price we are setting
// true if photo is in color
1
2
3
4
5
6 7}
/** Returns the weight in grams. */
public int weight();
/** Returns whether the object is hazardous. */ public boolean isHazardous();
Interface
/** Interface for objects that can be transported. */ public interface Transportable {
Interface • Multiple inheritance
Interface
1 public class BoxedItem implements Sellable, Transportable {
private String descript; private int price; private int weight; private boolean haz; private int height=0; private int width=0; private int depth=0;
// description of this item // list price in cents
2
3
4
5
6
7
8
9
10
11
12
13
14
/* continue to the next slide */
// weight in grams
// true if object is hazardous // box height in centimeters
// box width in centimeters // box depth in centimeters
public BoxedItem(String desc, int p, int w, boolean h) { descript = desc;
price = p;
weight = w;
haz = h; }
15 public String description() { return descript; }
16 public int listPrice() { return price; }
17 public int lowestPrice() { return price/2; }
18 public int weight() { return weight; }
19 public boolean isHazardous() { return haz; }
20 public int insuredValue() { return price*2; }
21 public void setBox(int h, int w, int d) {
22 height = h;
23 width = w;
24 depth = d;
25 }
26 }
Interface
Abstract Class
• An abstract method: a method without implementation.
• A concrete method: a method with implementation.
• Abstract class:
– Declared with abstract keyword.
– May or may not have abstract method.
– A class with an abstract method must be an abstract class.
– Used when subclasses share many common variables and methods.
– Cannot be instantiated.
Abstract Class
• An example from Oracle documentation (https://docs.oracle.com/javase/tutorial/jav a/IandI/abstract.html)
… }
abstract void draw();
abstract void resize(); }
Abstract Class
abstract class GraphicObject { int x, y;
…
void moveTo(int newX, int newt) {
} }
… }
void resize() {
// implementation …
Abstract Class
class Rectangle extends GraphicObject { void draw() {
// implementation
Interface and Abstract Class
• Consider using interfaces if any of these statements apply to your situation:
– You expect that unrelated classes would implement your interface.
– You want to specify the behavior of a particular data type, but not concerned about who implements its behavior.
– You want to take advantage of multiple inheritance of type.
Interface and Abstract Class
• Consider using abstract classes if any of these statements apply to your situation:
– You want to share code among several closely related classes.
– You expect that classes that extend your abstract class have many common methods or fields.
Exceptions
• Anexception,shorthandforexceptionalevent,is an event that occurs during the execution of a program
• When an exception occurs
– an exception is thrown
– the runtime system finds an exception handler – the code in the handler is executed
Exceptions
• Callstackandexceptionhandlersearchpath
• Try-catch statement try {
Exceptions
guardedBody
} catch (exceptionType1 variable1) {
remedyBody1
} catch (exceptionType2 variable2) {
remedyBody2 }…
…
• Example:ExceptionDemo.java
Exceptions • JavaExceptionHierarchy(part)
Exceptions • Errors (yellow):
– exception objects of the Error class and all of its subclasses.
– external to the application and they are thrown by JVM.
• Exceptions
– RuntimeException (green) – Other exceptions (tan)
Exceptions
• Errors:
– exception objects of the Error class and all of its subclasses. – external to the application and they are thrown by JVM.
• Runtime exceptions (unchecked exceptions):
– exception objects of the RuntimeException class and all of its
subclasses.
– exceptional events internal to the application, and occur due to mistakes in programming logic
• Other exceptions (checked exceptions):
– all other exceptions
– If a code may throw a checked exception, then it must be in a try-catch statement or it must be in a method which is declared with a throws clause.
Generics • Types are declared using generic names:
public class GenericQueue
private java.util.ArrayList
}
public E dequeue(){
}
…
}
• Instantiated using actual types:
GenericQueue
Generics • Generic class definition
public class Pair
1
2
3
4
5
6 7}
8 public A getFirst() { return first; }
9 public B getSecond() { return second;}
10 }
B second;
public Pair(A a, B b) {
// constructor
first = a; second = b;
• Instantiation
Pair
Generics • Generics and arrays
– Case 1: We have a generic class with parameterized types. We want to declare, outside of the generic class, an array storing objects of the generic class with actual type parameters.
– Case 2: We have a generic class with parameterized types. We want to declare, as an instance variable of the class, an array storing objects of one of the formal parameter types.
Generics • Generics and arrays – Case 1
1 Pair
// type parameters are allowed
2 holdings = new Pair
3 holdings = new Pair[25]; // this is allowed
4 holdings[0] = new Pair<>(“ORCL”, 3.14); // this is legal
Generics • Generics and arrays – Case 2
1
2
3
4
5
6 7}
8 public T get(int index) { return data[index]; }
9 public void set(int index, T element) { data[index] = element; }
10 }
public class Portfolio
public Portfolio(int capacity) {
data = new T[capacity]; // illegal; compiler error data = (T[ ]) new Object[capacity]; // legal, but compiler
// warning
Generics • Generic method
1
2
3
4
5
6
7 8} 9}
10 }
public class GenericDemo {
public static
int low = 0, high = data.length – 1;
while (low < high) { // swap data[low] and data[high]
T temp = data[low]; data[low++] = data[high]; data[high--] = temp;
// post-increment of low // post-decrement of high
• Generic method
Generics
String[ ] names = new String[ ]{"john", "susan", "molly"}; GenericDemo.reverse(names);
Integer[ ] integers = new Integer[ ]{10, 20, 30, 40, 50}; GenericDemo.reverse(integers);
Character[ ] chars = new Character[ ]{'a', 'b', 'c', 'd', 'e'}; GenericDemo.reverse(chars);
• Demonstration
– GenericQueue.java – GenericDemo1.java – GenericDemo2.java – GenericDemo3.java
Generics
class OuterClass { ...
} }
class NestedClass { ...
Nested Class
•
We use nested classes for the following reasons:
• •
The code becomes more readable and it is easy to maintain.
Nested Class
– NestedClass is used only for the OuterClass.
– We want to declare members of the OuterClass as private but, at the same time, we want a smaller class to be able to access members of the OuterClass.
– We want to implement a data structure which has another smaller data structure as its member.
Nested classes also help reduce name conflict.
References
• M.T. Goodrich, R. Tamassia, and M.H. Goldwasser, “Data Structures and Algorithms in Java,” Sixth Edition, Wiley, 2014.
• Oracle documentation (https://docs.oracle.com/javase/tutorial/java/IandI/abstrac t.html)