Transcript February 5, 2009

CS305/503, Spring 2009
Advanced OOP, Boundary Cases.
Michael Barnathan
Assignment 1 Review
• Distribution: Most grades around 92, 3 100s.
Assignment 1 Review
• This will be the easiest assignment given.
• Primary Purpose:
– To get comfortable with the Java environment.
• Some of you had problems with the IDE. An IDE is overkill and will slow you
down on a project of this size. IDE issues are never an acceptable excuse.
– To get you thinking about boundary cases.
• Cases that occur at extreme or unexpected parameter values (100, the empty
string, NaN, null, etc.).
• Primary issues:
–
–
–
–
Programs froze when secret = 100.
Counter was off by one (make sure you count the last guess!)
Repeated code, magic numbers.
Some of you broke encapsulation of the Guesser class.
• No points were taken off for this, but they will be in the future.
Boundary Cases
• These have an impact on the stability and
security of your software.
– Stability: things may randomly fail (for instance, your
programs would freeze up 1% of the time).
– Security: attackers very frequently exploit boundary
cases and will look for those first.
• What are they?
– Extreme values: in a range from 1 to 100, 1 and 100
are both boundary cases to test.
– Permitted but unexpected: what if I passed in 0,
Integer.MAX_VALUE, or -20?
Case Study: The Zune
• Does anyone have one?
• Did anyone use one on December 31?
– Did it freeze?
– “30GB Zunes Failing Everywhere, All At Once”
• …What’s so special about December 31, 2008?
– It’s the last day of the year, but so was 12/31/07…
– Ah, but 2008 was a leap year!
Microsoft’s Official Fix:
Wait until January 1.
The Source:
• What makes this really interesting is that the
offending source code is available.
• Let’s take a look.
– Line 259 starts the troublesome block.
– (Note the use of the ternary operator on line 170)
• See it?
– 263: Days will never be greater than 366.
– The code inside of that if will never execute!
– And the loop will never terminate!
• This will happen again in 2012 if not patched.
Other Issues
• So we just fix it there and we’re set, right?
– Not quite.
• Here’s why repeating code is bad:
– Look on line 557. There it is again!
– Now we need to change that too!
– If you repeat code, fixing these issues becomes a
wild goose chase.
• DRY Principle: “Don’t Repeat Yourself”.
– If you can write it once, don’t write it twice.
Your Code
•
So if the secret is 100…
A typical solution looked something like this:
public class Guesser {
//…My code…
public static void main(String[] args) {
int low=1;
int high=Guesser.MAXNUM;
int counter=0;
Guesser guess = new Guesser();
while (high > low) {
int mid = (low + high) / 2;
char ans = guess.guessNumber(mid);
if (ans == '>') {
low = mid;
counter++;
DRY
}
else if (ans == '<') {
high = mid;
counter++;
}
else {
System.out.println(counter);
counter++;
break;
}
}
}
}
Off-by-one
• Low = 0, High = 100, Mid = 50
• Low = 50, High = 100, Mid = 75
• Low = 75, High = 100, Mid = 87
• Low = 87, High = 100, Mid = 93
• Low = 93, High = 100, Mid = 96
• Low = 96, High = 100, Mid = 98
• Low = 98, High = 100, Mid = 99
• Low = 99, High = 100, Mid = 99
• Low = 99, High = 100, Mid = 99
• Low = 99, High = 100, Mid = 99
• Low = 99, High = 100, Mid = 99
• Low = 99, High = 100, Mid = 99
• Low = 99, High = 100, Mid = 99
• Low = 99, High = 100, Mid = 99
• Low = 99, High = 100, Mid = 99
•… Ad infinitum
Infinite loop in
boundary case.
Solution: Exclude the guess.
Breaking Encapsulation
• By putting your code directly into the Guesser class,
you were allowing it to read the secret number,
breaking the encapsulation of the class.
• A better way would be to define a GuessingGame class
which uses the Guesser.
• This would also separate the details of how the secret
number is being generated from the algorithm used to
guess it (separation of concerns). This helps make code
modular and maintainable.
• I will take style points off for this in the future.
• Any other questions about the assignment?
Review Questions
• What is the efficiency of the three sorting algorithms
we discussed previously?
• What are their primary advantages and disadvantages?
• Is there any reason you’d want to use one over
another?
• What does it mean for a sort to be “stable”?
• What does “CRUD” stand for and why are these
algorithms important?
• What is the tradeoff involved with using sorted arrays
vs. unsorted arrays?
Here’s what we’ll be learning:
• Object Oriented Programming:
–
–
–
–
–
–
Inheritance.
Polymorphism.
Interfaces and implementations.
Upcasting and downcasting.
Abstract and final classes.
Use of generics.
• We’ll have a lab on sorting and the Vector class next time.
Inheritance
• Classes can “inherit” from each other.
• The “derived” (child) class automatically starts out with all
of the “base class”’s (parent’s) properties and methods.
• You can then “override” methods by redefining them in the
derived class.
• Inheritance is properly used when one class “is a” ‘nother
(“is a” is standard terminology).
– For example, a Truck “is a” Vehicle.
• Every class in Java inherits automatically from the Object
class. This is the only example of multiple inheritance
permissible in Java.
– Object defines methods such as equals() and toString().
Inheritance Hierarchy
• Inheritance defines a hierarchy, with base
classes above derived classes:
Inheritance in Java
public class Vehicle {
//Base class.
public void go() { System.out.println(“Vroom!”); }
public void honk() { System.out.println(“Beep!”); }
}
public class Truck extends Vehicle {
//Derived class.
public void honk() { System.out.println(“HONK!”); }
}
Truck t = new Truck();
t.go();
System.out.println(t.honk());
//Valid. Trucks inherit go().
//“HONK!”, not “Beep!”
Polymorphism
• The primary use of inheritance is for
“polymorphism” (poly = many, morphos = forms).
• This is the practice of using a reference to the
base class with an object of a derived class.
• Any overridden methods called on the reference
will exhibit the behavior of the derived class:
Vehicle v = new Truck();
//Valid!
v.honk();
//“HONK!”
Polymorphism
• The real power of this is apparent when you use it in an
array or other data structure.
• That’s because you can automatically exhibit different
behaviors depending on what each object is:
Vehicle[] cars = new Vehicle[2];
cars[0] = new Vehicle();
cars[1] = new Truck();
for (int i = 0; i < cars.length; i++)
cars[i].honk();
//“Beep! HONK!”
Wait!
• “Ah, but arrays are homogenous!”, you say.
• Yes, and we’re perfectly fine.
• They all contain Vehicle references.
– You’re storing references in the array, not objects.
• Everything inherits from Object…
– So yeah, you can store Objects in arrays.
– And thereby store any combination of classes!
• There’s a catch to this:
– You can only call base class methods through a base class reference.
– The behavior will be that of the derived class.
– But the choice of methods is that of the base class.
• Bummer, but it makes sense:
– You have no idea what those Objects really are, so all you can do is call things
common to every Object: equals(), clone(), toString(), etc.
– Otherwise you might call a function that doesn’t exist.
Downcasting
• “But I do know what I just put into that array!”, you say.
• “Yeah, yeah, tell it to the compiler”, I respond.
• So you did:
Object[] arr = new Object[2];
arr[0] = new Truck();
arr[1] = new Hovercraft();
arr[0].honk();
//Error, arr[0] is an Object.
((Truck) arr[0]).honk(); //Now it works; we told Java it was really a Truck.
• This is called a downcast, because you are casting down the inheritance
hierarchy.
– Object is at the top, of course.
– Vehicle is right below it (along with every other base class).
– Truck is below Vehicle because it inherits from Vehicle.
• Make sure that you downcast into a type that the variable is compatible
with (either the derived type or a base class above it), or Java will throw
an exception. You can’t cast that Hovercraft to a Truck.
Upcasting
• And you can go the other way too.
• This is usually done implicitly by Java.
– e.g. Object o = new Truck();
• But you can also do it explicitly if you wish:
– Object o = (Object) new Truck();
• You can’t access overridden base class
methods this way, though:
– ((Vehicle) new Truck()).honk(); //”HONK!”
– The object is still a truck, so you’re still getting a
truck honk. (Polymorphism at work!)
“Super”
• There is only one way to access overridden base
class methods in Java: “super”.
• “super” refers to the class you inherit from.
• Inside of the Truck class, super() refers to
vehicle…
• And if you were to call super.honk() somewhere
inside of Truck, it would “Beep!”
• This is commonly used to call a base class’
constructor in the derived class’ constructor.
– If you do this, make sure it’s the first statement.
Interfaces and Implementations
• Let’s say you’re more interested in what a class can do
rather than what it is.
• Inheritance is not appropriate here.
• What you need is an interface.
– In Java, an interface is a “contract”.
– It defines some methods.
– In exchange for implementing those methods, Java will let
you call your object using a reference to the interface type.
– That’s because it knows that the methods in the interface
are implemented and it can safely call them.
• It made you write them. But now it knows they exist for sure.
– This has the same benefits as polymorphism.
Defining an Interface
• Interfaces in Java are defined like this:
interface Honkable {
public void honk();
//Other functions can go here too.
//But you just define them; you don’t
//implement them here.
}
Implementing an Interface
• Vehicle could then implement Honkable:
public class Vehicle implements Honkable {
//honk() must be implemented now to compile.
public void honk() { … }
}
• Unlike inheritance, you can implement more than one
interface in Java. Just separate the interface names
with commas.
– You’ll need to write the methods for each, of course.
The Reward
• You can now do this:
Honkable[] h = new Honkable[2];
h[0] = new Vehicle();
h[1] = new FrenchHorn();
for (int i = 0; i < h.length; i++)
h[i].honk(); //All things Honkable have this.
Abstract Classes
• A class is abstract if it defers implementing one or more methods to
a derived class.
• The unimplemented methods must be preceded by the keyword
abstract.
• You can also precede the class definition itself with the abstract
keyword.
• Either way, the end result is that people cannot create objects of
your abstract class. They must create objects of non-abstract
derived classes.
– This doesn’t mean they can’t call the abstract method, however.
Through polymorphism, they can (the method in the derived class,
which is no longer abstract, will execute)
– Also, not every method in the class needs to be abstract. Some could
have base class implementations, which are carried down to the
derived classes.
Abstract Classes
•
•
•
So why are they useful, then?
Because you can define common behavior to a category of things even if there’s no common
implementation of that behavior.
Example:
public abstract class Shape {
//There’s no area of a “shape”, but it makes sense to talk about shapes having areas.
public abstract double area();
}
public class Square extends Shape {
private double sidelen;
public double area() { return sidelen * sidelen; }
}
public class Triangle extends Shape {
private double base;
private double height;
public double area() { return .(base * height) / 2; }
}
//Squares have an area.
//Triangles have an area.
Abstract Classes: Why not use an
interface instead?
• Why not use a hasArea interface in the previous
example?
• Because then your Squares, Circles, and Triangles
wouldn’t be Shapes!
– There might be useful properties or non-abstract methods
carried over from the Shape class that you want to use.
– Having one abstract method doesn’t mean the others all
have to be abstract. The non-abstract methods will be
inherited by the derived classes.
• You can’t do this with interfaces.
– More philosophically, it fails to model the “is a shape”
relationship between classes.
Final Classes
• Inheritance is great, but sometimes you don’t
want people deriving from your classes.
• No problem; just declare the class final.
public final class Planet { … }
//Error, Planet is final - sorry, Pluto.
public class Planetoid extends Planet { … }
Using Generics
• Generic classes are sort of complex to define in
Java, though not beyond your current knowledge.
• We’ll get to them some other time.
• But using them is simple:
Vector<String> vstr = new Vector<String>();
vstr.add(new String(“Foobar”));
//Works.
vstr.add(new Truck());
//Nope.
Abstractions
• The lesson:
– Abstraction is the root of intuitive understanding
of complex systems. Your ability to use the
Internet without understanding everything down
to how the glass in the fiber optic cables was
made is a testament to this. Abstraction is the
only way to build a complex system of any sort.
• Next class: Sorting Lab.