1 of 28

Immutability and Selecting ADT’s

CS61B Sp18 Discussion 6

2 of 28

Administrivia

  • Midterm scores are out!
  • Regrade requests are Friday the 23rd at noon. No regrades will be accepted later than that.
    • Please format your regrade according to the format specified on Piazza @1520
  • Project 2 final version is out
    • Phase 1 due February 26
    • Phase 2 due March 5th
  • It is highly recommended that you find a partner for this project. Partner forms are linked in the spec. Please email jzeitsoff@berkeley.edu if you fill out the form late!
  • Homework 1 is out and due 2/21

3 of 28

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

4 of 28

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.

5 of 28

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.

6 of 28

Review: Types of Exceptions

There are 2 overarching types of exceptions:

  • Checked
    • You must either wrap them in a try/catch block or pass the buck by using “throws exception” in the method header
  • Unchecked
    • You don’t need to handle these. They are typically an error on a user’s part, which can’t really be helped.

7 of 28

Review: Iterators and Iterables

  • Iterable: Something that can be iterated over
    • Must have .iterator() method which creates an iterator
  • Iterator: actually tool/machine you use to do the iteration.
    • Must have .next() and .hasNext() methods

Each iterable object will need to produce its own one-use iterator object.

8 of 28

Access Control

Access control allows us to restrict the use of methods, classes, and fields.

  • private
  • protected
  • default (no modifier)
  • public

Modifier

Class

Package

Subclass

World

public

Y

Y

Y

Y

protected

Y

Y

Y

N

Y

Y

N

N

private

Y

N

N

N

9 of 28

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>()

  • Although arr is declared as final, you can still call arr.insert(“convfefe”).
  • However, you cannot reassign arr = new LinkedList<String>();

Now, nobody can change the value of x.

10 of 28

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:

  • List: an ordered collection of elements
  • Set: an unordered collection of unique elements (no repeats)
  • Map: a collection of key/value pairs
  • Stacks: has last in first out property (LIFO)
  • Queues: has first in first out property (FIFO)
  • Deques: can be both LIFO and FIFO

11 of 28

  • Rocks pt1

Now, nobody can change the value of x.

12 of 28

  • Rocks pt1

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

13 of 28

  • Rocks pt2

14 of 28

  • Rocks pt2

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.

15 of 28

  • Rocks pt3

16 of 28

  • Rocks pt3

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.

17 of 28

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.

18 of 28

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.

19 of 28

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.

20 of 28

2.) Breaking the System pt2

Exploit another flaw in the stack by completing the main method below so that

the stack appears infinitely tall.

21 of 28

2.) Breaking the System pt2

Exploit another flaw in the stack by completing the main method below so that

the stack appears infinitely tall.

22 of 28

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.

23 of 28

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?

24 of 28

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.

25 of 28

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).

  • Parking spaces can be either regular, compact, or handicapped-only.
  • When a new car arrives, the system should assign a specific space based on the type of car.
  • All cars are allowed to park in regular spots. Thus, compact cars can park in both compact spaces and regular spaces.
  • When a car leaves, the system should record that the space is free.
  • Your package should be designed in a manner that allows different parking lots to have different numbers of spaces for each of the 3 types.
  • Parking spots should have a sense of closeness to the entrance. When parking a car, place it as close to the entrance as possible. Assume these distances are distinct.

26 of 28

Car

27 of 28

Spot

28 of 28

Parking Lot