Immutability and Selecting ADT’s
CS61B Sp18 Discussion 6
Administrivia
Review: Generics
Generics is a way to allow your data structures to work with any type.
public class List<T>{...}
List<String> = new ArrayList<String>();
public static <K, V> V get(Map61B<K, V> map, K key){}
public static <K extends Comparable<K>, V> V get(Map61B<K, V> map, K key){}
This is a generic class
Instantiation
Generic method
Type upper bound
Review: Autoboxing
Every primitive in Java has an Object counterpart. Many data structures cannot hold primitives, so we wrap the primitive in an object.
Java is smart and often converts primitive types to their Object counterparts or Objects to their primitive counterparts automatically. This is called autoboxing.
Review: Exceptions
try{
risky code
} catch (Exception e) {
fix it hurry
} finally {
shut it down
}
Will catch the exception if it is thrown in the try block
Run some code that may throw an exception
Will run no matter what.
Review: Types of Exceptions
There are 2 overarching types of exceptions:
Review: Iterators and Iterables
Each iterable object will need to produce its own one-use iterator object.
Access Control
Access control allows us to restrict the use of methods, classes, and fields.
Modifier | Class | Package | Subclass | World |
public | Y | Y | Y | Y |
protected | Y | Y | Y | N |
| Y | Y | N | N |
private | Y | N | N | N |
Immutability
Immutable: A class or object is immutable if you cannot change anything about it after you instantiate it.
public static final int x = 5;
Caveat: If you instantiate a reference as final, then you are making the reference immutable, but not what is inside the object.
public static final List<String> arr = new ArrayList<String>()
Now, nobody can change the value of x.
Abstract Data Types (Review from disc5)
Abstract data types are defined by their behavior, not by their implementations. AKA, they’re about what, not how.
Some examples are:
Now, nobody can change the value of x.
Now, nobody can change the value of x.
Everything in the pebble class is public and non-final. It is mutable.
The Rock class has one int weight and it is declared as final, so it is immutable
There may be a reference to rocks somewhere outside of the class, so it is mutable.
The rock variable is static, but you can still modify the contents of rocks, thus it is mutable.
This class is mutable since Pebble has public variables that can be changed. For
instance, given a MommaRock mr, you could mutate mr with mr.baby.weight = 5.
It is possible to access and modify the contents of PunkRock’s private array through its public myBand() method, so this class is mutable.
2.) Breaking the System pt1
Exploit the flaw by filling in the main method below so that it prints “Success” by causing BadIntegerStack to produce a NullPointerException.
2.) Breaking the System pt1
Exploit the flaw by filling in the main method below so that it prints “Success” by causing BadIntegerStack to produce a NullPointerException.
2.) Breaking the System pt1
Exploit the flaw by filling in the main method below so that it prints “Success” by causing BadIntegerStack to produce a NullPointerException.
The issue is, the bad stack is initialized as empty with top being null. So, if you pop from a newly initialized stack, you will have no “top” variable with which to extract top.value.
2.) Breaking the System pt2
Exploit another flaw in the stack by completing the main method below so that
the stack appears infinitely tall.
2.) Breaking the System pt2
Exploit another flaw in the stack by completing the main method below so that
the stack appears infinitely tall.
2.) Breaking the System pt2
Exploit another flaw in the stack by completing the main method below so that
the stack appears infinitely tall.
If you set top.prev to itself, then every time you pop you will set top back to itself! This means you can keep popping but top will remain in the list.
2.) Breaking the System pt3
How can we change the BadIntegerStack class so that it won’t throw NullPointerExceptions or allow ne’er-do-wells to produce endless stacks?
2.) Breaking the System pt3
How can we change the BadIntegerStack class so that it won’t throw NullPointerExceptions or allow ne’er-do-wells to produce endless stacks?
Check that top is not null before popping and make top private.
3.) Design a parking lot
Design a ParkingLot package that allocates specific parking spaces to cars in a smart way. Decide what classes you’ll need, and design the API for each. Time permitting, select data structures to implement the API for each class. Try to deal with annoying cases (like disobedient humans).
Car
Spot
Parking Lot