CS231 lecture notes, Fall 1999
Week 5, Monday


Reading: Standish Chapter 5, start by doing a chapter overview,
then get into the details

5.1 Discussion of modularity, abstraction and ADTs

5.2 Priority queues -- interface definition

5.3 Priority queues -- two implementations

    a) sorted linked list
    b) unsorted arrays

5.4 Using Java interfaces to build generic ADTs

5.5 Summary of information hiding and modularity

-----

Our plan:  Look at priority queues (and both implementations in
the book) and the Java Vector class (implementation unknown), and
then write an implementation of PQ using Vector.

-----

What is an ADT?  A general-purpose data structure (often containing
a collection of Objects) that is defined by the set of operations
that can be performed on it, rather than by its implementation.

Why are there ADTs?

1) because there are a bunch of data structures that have turned
   out to be useful for a variety of applications, but which can
   be implemented in any number of ways

2) someone using one of the data structures doesn't care how it's
   implemented (except possibly for performance reasons)

3) they provide a high-level language for talking about data
   structures and programs.  Every programmer in the world knows
   what a priority queue is.

4) they facilitate the reuse of code and the division of large
   software projects.

5) in many cases they make it easier to demonstrate the correctness
   of a program or detect errors.

-----

Priority queue

Operations:

1) Construct an empty PQ
2) get the size of an existing PQ
3) insert a new item in a PQ
4) remove an item from a PQ

Contrary to what the book implies, this set of definitions is not
a complete definition of the PQ.  In addition we need:

1) every item in a PQ must have a priority that is comparable to
   the priorities of the other items

   (whaddya mean comparable?  integers are comparable, fruits are not)

2) The item removed by the remove operation is the one with the
   highest priority.

General usefulness of PQ

0.5) sorting, the example in the book

1) deadline-driven scheduling.  Add new assignments to notebook.
   Always work on (and remove) the one with the nearest deadline.

2) event-driven simulation.  As we learn about future events, put
   them in the PQ.  Simulation loop looks like

   a) get_next_event
   b) simulate it, adding any resulting future events to the queue


What does the PQ interface look like in Java?

1) PriorityQueue queue = new PriorityQueue ();
2) int n = queue.size();

So far so good, but now we need something to put in the PQ.
(just like we needed ListNodes to put into Lists).  In this
case they are called PQItems.

3) PQItem key = new PQItem (x);
   queue.insert (key);

4) PQItem out = queue.remove ();

By definition, remove returns the item in the queue that has
the highest priority.

Notice that at this stage, we know nothing about how the items
are stored internally.  In a linked structure like a List or
a contiguous structure like an array?  Are they stored in order
or do we go looking for the biggest when asked?

   Not part of the definition!  That's why it's called abstract.

   If the implementation were part of the definition, it would be
   a CDT.


Example: using the Priority Queue to sort 100 keys


   public static void main (String[] args) {

    PriorityQueue pq = new PriorityQueue ();

    // generate 100 items with random keys and put them in the PQ
    PQItem item;
    for (int i = 0; i<100; i++) {
      int x = (int) (Math.random() * 100);
      item = new PQItem (x);
      pq.insert (item);
      System.out.println ("Inserting " + item);
    }

    // remove all the items from the PQ; they should be in order
    while (true) {
      item = pq.remove ();

      // when remove returns null, we're done
      if (item == null) break;
      System.out.println ("Removing " + item);
    }
  }