SUNY Geneseo Department of Computer Science

Creating Subclasses of List

Previous Lecture

Misc

Dept. talk on spoken language interfaces

• Thurs. April 1, 12:45
• Place TBA

Making appointments

• Some of you probably still need them
• Please don't use blocks with something else in them, even if it's "office hours", etc.

Exam 2 will be Thursday (April 1)

• Mainly lists, design and analysis of list algorithms
• Rules and format similar to first exam

Practice Exam on Web

Questions?

Final comprehensive but biased to material since last hour exam, designed for 2 hours, same rules as hour exams

For hour exam, know roughly what messages you can send to lists

List of integers, all have to be wrapped

• To use them as ints, you have to unwrap them

    someList.addItem( new Integer( i ) );
    ....
    ...x + ((Integer)someList.getFirst()).intValue()...

• or

    int y = ((Integer)someList.getFirst()).intValue();
    ... x + y ... 

Proof for red tiles

• Two recursions - one for left, one right
• Strong induction
  • Assume "hunt()" correct for all treasure hunts of <= k-1 tiles
• Left and right each have at most k-1 tiles
• Innduction hypothesis applies

List Subclasses

Section 11.5.1

• Creating new methods in subclass of List
• Problem: messages return Lists, not instances of subclass
  • Solution: cast sublists as instances of subclass so messages return right type
• Constructing new lists
  • Make constructor in two parts
  • Basic constructor that makes empty list
  • Second part does ... ?

The makeNewList factory method

• Factory design pattern
  • Pattern = generic way of solving some programming problem
  • e.g., problem of creating a new object without knowing what kind

• SquareBoxyList inherits addItem method from List

    addItem ( n )
        temp = this.makeNewList()
            // vs temp = new List()
        temp.head = this.head;
        temp.tail = this.tail
        this.head = n
        this.tail = temp

• Adding items to lists requires creating new lists
• Solution? override addItem in every subclass
  • ... and copy
  • .. and others?
• Better solution: isolate the part that changes with subclasses so that programmmers can override just that part.
  • makeNewList

        public List makeNewList() {
            return new ...this subclass...
        }

• For example

        // In class SquareBoxyList:
        public List makeNewList() {
            return new SquareBoxylist();
        }
        public SquareBoxyList() {
            super();
        }

• Constructors initialize data, but messages depend on class used in "new ..."

Why casts?

• See Appendix section 1.5.2
• Cast lets programmer promise the compiler that an expression will produce a result of a certain type even if the compiler can't deduce that for itself.
• See Code Example illustrating use of cast in recursive method within a subclass.

Next

Stacks - a list-like class

Read

• Intro to chapter 12
• Section 12.2 through 12.2.4

Next Lecture