Outline of Class 35: Filters

Miscellaneous

• Don't forget to start reading chapter 11.
• Does anyone think I should continue using Java in a Nutshell when I next teach 152? Has anyone found anything they really like?
• For those interested in the student programmer position, I'll have an exercise available next week.
• Once again, today's class notes include more than I expect to cover.
• Class is cancelled for next Tuesday so that I can drive Michelle to Des Moines for her flight and spend a few more hours with her before she leaves for five weeks! :-(
• Any questions on the current homework assignments?

Filters

• Iterators can do more than return the elements in an object. An iterator can be extended to filter or otherwise modify the elements returned.
  • Sort the elements before returning them
  • Do some form of "pattern matching" on the elements and only return elements that match the pattern.
  • Modify objects as they are returned (or, more appropriately, return modified copies).
• By using multiple filters we can perform some fairly complicated tasks. For example, to produce a list of misspelled words in a document we might
  • Translate all words to lower case
  • Filter out punctuation
  • Filter out duplicate words
  • Filter out any words that appear in the dictionary
  • Sort the result for convenience
• Unix permits filtering through some standard programs (e.g., grep, sort, tr, and uniq).
• In Unix (or at least the HP-UX variant), we could get a sorted list of all the words in a document with

  cat document |
    tr -cs a-zA-Z '[\n*]' |
    tr A-Z a-z |
    sort |
    uniq
  

  (Provided we put it all on the same line.)
• There's a slightly different order because of the way some programs work.
  • tr -cs a-zA-Z '[\n*]' indicates "translate any character that is not a letter to a carriage return, collapsing sequences".
    • tr is "translate"
    • -c is "complement" ("is not")
    • -s is "collapse sequence"
    • \n is "carriage return"
  • tr A-Z a-z indicates "translate uppercase to lowercase"
  • uniq is "print only the first line of lines that repeat" (note that in order to get only one copy, the other copies must be on subsequent lines)
• We might write a similar Java program (provided we'd defined the appropriate filter classes) with

  Iterator doc = new DocumentIterator(document);
  Iterator words = new TranslateIterator(doc,cs,"a-zA-Z","\n");
  Iterator lcwords = new TranslateIterator(words,"A-Z","a-z");
  Iterator sorted = new SortIterator(lcwords);
  Iterator unique = new UniqueIterator(sorted);
  Iterator misspelled = new FilterOut(unique,DICTIONARY);
  

• Or simply

  Iterator misspelled =
    new FilterOut(
      new UniqueIterator(
        new SortIterator(
          new TranslateIterator(
            new TranslateIterator(
              new DocumentIterator(document)
              , cs, "a-zA-Z", "\n"
            ) // words only
            , "A-Z", "a-z"
          ) // lowercase only
        ) // sorted
      ) // unique
      , DICTONARY
    ) // filtered out dictonary
  

Predicate-based Filters

• One of the most common types of filter is the predicate-based filter. This filter only allows objects that meet some criteria to pass through the filter.
• In an object-oriented language, a predicate is most likely an object that implements the Predicate interface. We'll pretend that means that the predicate supports okay(Object o).
• Our constructor, PredicateFilter(), will take two parameters: an iterator to filter and a predicate to use for the filtering.
• We'll need at least two fields.
  • One to store this base iterator (call it base).
  • One to store the predicate (call it pred).
• How do we implement the four key methods (reset(), hasMoreElements(), value(), and nextElement())?
• reset() simply requires us to reset the base iterator.
• value(), nextElement(), and hasMoreElements() require us to advance the base iterator until we find an element that the predicate accepts. We'll use a helper function to do this.
• Here's a sketch

  /** An iterator that filters out unwanted items. */
  public class PredicateFilter implements Iterator {
    /** The base iterator. */
    protected Iterator base;
    /** The predicate used for filtering. */
    protected Predicate pred;
   
    /**
       Construct a new filter.
       pre: The base iterator is defined.
       pre: The predicate is defined.
       post: A new filter iterator is returned.
       post: The base iterator may be affected by uses of this
             filter.
     */
    public PredicateFilter(Iterator base, Predicate pred) {
      this.base = base;
      this.pred = pred;
    } // PredicateFilter(Iterator,Predicate)
   
    /**
       Reset the filter.
       post: The filter is reset to the beginning (all elements
             are marked as unseen).
       post: The base iterator may also be affected.
     */
    public void reset() {
      base.reset();
    } // reset
   
    /**
       Peek at the next element.
       pre: There are unseen elements remaining.
       post: The next unseen element is returned.
       post: That element is not marked as seen.
       post: The base iterator may be advanced.
       @throws IteratorException if no unseen elements remain
     */
    public Object value() throws IteratorException {
      // Advance the base iterator until acceptable element found
      if (!advance()) {
        throw new IteratorException("No acceptable elements remain");
      }
      return base.value();
    } // value
   
    /**
       Get the next element.
       pre: There are unseen elements remaining.
       post: The next unseen element is returned.
       post: That element is not marked as seen.
       post: The base iterator may be advanced.
       @throws IteratorException if no unseen elements remain
      */
    public Object nextElement() throws IteratorException {
      // Advance the base iterator until acceptable element found
      if (!advance()) {
        throw new IteratorException("No acceptable elements remain");
      }
      return base.nextElement();
    } // nextElement()
   
    /**
       Are there acceptable elements remaining?
       pre: (none)
       post: True is returned if there are acceptable elements
             remaining.  False is returned o/w.
       post: The base iterator may be advanced.
     */
    public boolean hasMoreElements() {
      return advance();
    } // advance()
   
    /**
       Advance the base iterator until an acceptable element is
       found (one that matches the base predicate).  Returns a
       boolean value that indicates whether or not such an element
       is found.
       pre: (none)
       post: If acceptable unseen elements remain, the current
             value of the base iterator is one such element.
       post: If no acceptable unseen elements remain, the current
             value of the bsae iterator is undefined.
       post: The base iterator may be advanced.
     */
    private boolean advance() {
      while ( (base.hasMoreElements()) && (!pred.okay(base.value())) ) {
        base.nextElement();
      } // while
      // Are there elements remaining in the base predicate.  If so,
      // the advance was successful.
      return base.hasMoreElements();
    } // advance()
  } // PredicateFilter
  

• There are some questions involved here. For example, should we clone the base iterator, so that changes to it don't affect other uses? I've made the choice to document that our filter affects the base predicate.

Transform-based Filters

• Another kind of filter modifies each object as it passes. These filters might be called Transform-based filters.
• The constructor for such a filter would take two parameters:
  • a base iterator
  • a tranformation that maps objects to objects.
• For this type of filter, the methods are all trivial, so we won't write them. Basically,
  • To reset the filter, reset the base iterator
  • There are elements remaining in the filter if there are elements remaining in the base iterator
  • To return an object, grab it from the base iterator and transform it.