Held: Tuesday, 11 November 2014

Back to Outline 38 - Implementing Queues with Arrays. On to Outline 40 - Designing a Dictionary API.

Summary

We consider priority queues, one of the important linear structures.

Related Pages

• Reading: Linear Structures
• Reading: Priority Queues
• Lab: Priority Queues
• Repository: https://github.com/Grinnell-CSC207/linear
• EBoard 39 (Source 39) (HTML 39)

Overview

• Wrappers, adapters, and delagates.
• Design patterns.
• A short introduction to priority queues.
• Array-based implementations.
• Running times.
• Sorting with priority queues.

Administrivia

• New lab partners.
• Extended office hours continue this week.
• My favorite comment about yesterday's class: "Sam, it was really nice to be able to work on lab and discussion simultaneously - when we hit a question, you were just covering it in the discussion."
  • But we'll go back to lab anyway.

Upcoming Work

• Homework 9: Skip Lists due Wednesday.
• No reading for Wednesday. We're doing another design exercise.

Extra Credit

Academic

• Convocation Wednesday at noon: Dean Latham.
• Wednesday at 7:30 p.m. Internship panel with Nelson, Mira, and Lea.

Peer Support

• Ajuna's Radio show Mondays at 8pm. Listen to African music.
  • Of course, this assumes that KDIC actually works.
• Ezra's Radio show Thursdays at midnight. Radio melodrama.
• Charlie's Friday Night "War in Animated Film" ExCo.
• All of Ajuna's various activities this week (each to be announced as appropriate).

Wrappers, adapters, and delegation

What interesting (or not so interesting) design ideas did you get from ReportingLinearStructure.java?

Here are some of the things I see as important ideas:

• We already know that we can add functionality to a particular class by subclassing.
• ReportingLinearStructure.java shows another mechanism for adding functionality, one that works for an arbitrary class that implements an interface.
• The basic strategy:
  • Our wrapper/adapter has a field that contains an object that implements the interface. I call this the "wrapped object" or "wrapped class".
  • Our wrapper/adapter also implements the interface.
  • Most of the methods are implemented by delegating the actual work to the wrapped object.
  • But the wrapper can add functionality or modify the behavior.

Here's my really bad ASCII art diagram.

          Wrapper
         +-------------------+
Client ---> fun: wrapped.fun |
         |                   |
         |  wrapped          |
         |    +---------+    |
         |    | fun     |    |
         |    +---------+    |
         +-------------------+

Uses

• As you saw, one use of this pattern is to provide some automatic logging of your program. When you want to log everything an object does, you wrap that object with something that logs each call. Once you're satisfied, you remove the wrapper.
• It's also useful to add some analysis capabilities, such as a count of the number of times each method is called.
• Or we can change some of the behavior. For example, we might have something that calls put twice each time it is called. (I have no idea why you would want such behavior.)
• A talented Java programmer can probably write a generic logging or counting wrapper. I don't have the time, and it's been long enough since I've used Java's introspection to write such a wrapper.

Terminology and design patterns

• As object-oriented (and other) programmers have found common approaches to problems, they've worked to find common names for these approaches to make it easier to talk to others about the approach.
• Often, people use the term "design patterns" to refer to this approach.
  • Design patterns are a bit more specific, in the sense that a good design pattern also tells you a lot about when to use the pattern.
  • Most of the members of this department like design patterns primarily as a use of common terminology.
• I've had trouble finding the right term for this approach, which is a common pattern.
• I call these "wrappers", but I use "wrapper" for a lot of things.
• They use delegation (or the Delegate Pattern).
• They are kind of like the Adapter Pattern, although Adapters are usually used to make objects meet new interfaces. (You've seen me use Adapters to get built-in Java classes meet my interfaces.)

A quick introduction to priority queues

• Linear structures.
• But with the policy "highest priority first".
• Priority represented with a Comparator.
• Probably easier to implement than queues, particularly if you've already studied sorting.

Implementation with arrays

• Two options:
  • Stored in order (put is slow)
  • Stored unordered (get is slow)

Run-time analysis

• Put or get is O(n).
• That's kind of disappointing. For queues and stacks, put and get were both O(1).
• Can we do better? Yes, but it requires that we learn some new concepts. So we'll return to a better implementation toward the end of the semester.

Sorting with priority queues

• Can you guess an obvious sorting algorithm?

Lab

Back to our favorite repository. (And we're not done with it yet!)