cs230 Lecture Notes
Week 9 Monday

Quiz today.

Exam 2 next Tuesday 7 November.


Object-oriented design
----------------------

1) objective: re-use code

2) write new code using highest-level constructs
   (because they are the least error prone)

3) compromise with efficiency (in the sense of overhead)


Choices for hw07
----------------

Option: you can use the built-in LinkedList class if you want.

1) Each PriorityQueue contains a List object

   are there List operations that we can use without modification?

   are there changes we might want to make in the List class
   that would make it more useful for implementing PQ?

   does code in PQ have to go in and mess with the internals of
   the List?

2) Each PriorityQueue contains a Node object that is the
   head of a linked list

   are there Node operations that we can use without modification?

   are there changes we might want to make in the Node class
   that would make it more useful for implementing PQ?

   does code in PQ have to go in and mess with the internals of
   the linked list?

3) A PriorityQueue is a kind of List, with modifications.

   Do we have to add any instance variables?

   Do we have to add any new methods?

   Do we have to override any existing methods?

   Do we have to make any changes to the List class to make
   it a better progenitor for PQ?


Design criteria
---------------

1) appropriate encapsulation

2) code that is demonstrably (if not provably) correct

3) minimal changes to existing code

4) reasonable efficiency


Extra special suggestion for the extra ambitious:
You might want to look ahead at Section 10.9


Abstract classes
----------------

Implementation: four pieces

1) definition: we're using a built-in one, so we haven't
   see a definition yet

2) data structure: generic, but you can invoke the methods
   that are guaranteed

3) client: instantiate member classes, typecast when you
   insert, typecast back when you remove

4) member: implement the interface, as promised
   (there are some built-in members of the built-in abstract
   classes)