Data Structures & Algorithms Lecture Notes

1 October 2010 • List Traversal

---

Outline

• Why traversals?
• Traversing with references.
• Iterators
• Traversals

Why Traversals?

• ADTs are commonly used to store and retreive values.
• ADTs can also treat the collected values as a group.
  • Give everybody a 10% pay cut.
  • Which students are on the Dean’s list?
  • Move the more seriously injured ahead of the less seriously injured.
• What group-value operations should an ADT support? And how?

Group Operations

• Group operations should
  • cover a wide range of uses (whatever you can do to an individual you can do to a group, and more)
  • and be simple to use (groups are more complex than individuals, and so are group operations).
• These requirements conflict.
  • Simple group operations are not capable,
    capable group operations are not simple.

Simple Group Operations

• High-level (or simple) group operations operate on the data as a group.

  List<patients> triage = 
    er.criticallyOrdered(10);
  

• Simple, but I want all patients in critical order.

  List<patients> roster = 
    er.criticallyOrdered(er.size());
  

• Not so simple, and I want only patients with flu-like symptoms.

Capable Group Operations

• Low-level (or capable) group operations operate on individual values and the ADT’s adjacency relationship.

  List<patients> roster;
  for (p = er.first(); 
       p.hasMore() && triage.size() < 11; 
       p.next())
    if (p.value().fluLike())
      roster.add(p.value())
  

• Capable, but not so simple.

Simple vs Capable

• Practically, a general-purpose ADT should provide both simple and capable group operations.
  • Less general ADTs should favor simple group operations.
  • More general ADTs should favor capable group operations.
• Progress starts with capable group operations and adds simplicity without losing capability.
• We’re interested in general ADTs and capable group operators.

References

• References provide the simplest approach to capable group operations.
• Group operations need to
  • access, and perhaps manipulate, values in an ADT, and
  • move among the values in an ADT.
• References have both these abilities.
• ADT clients use references to move through and manipulate values as needed.

Example

• Order the emergency-room patients in decreasing critical state.

for (i = er.first(); i.hasMore(); i.next())
  List<Patient>.reference sickest = i;
  for (j = i.next(); j.hasMore(); j.next())
    if j.value().sicker(sickest.value())
      sickest = j
  er.swap(i, sickest)

• Compare to

  triage = er.decreasingCriticality();
  

Traversals

• References access and move among ADT values.
• Value access and manipulation depends on the group operation.
• Moving is independent (more or less) of group operations.
• Focusing on simpler forms of moving through values is one way of creating simpler group operations.
  • A traversal is a simpler, more organized form of moving through ADT values.

But First...

• References may be too powerful when restricted to just traversing data.
  • Depending on how references are defined.
• Manipulating’s not so important for traversals, neither are fancy relative reference operators.
  • Simplified references are easier to use and more efficient in execution.
• Simplified, traversal-specific references are called iterators.

Creating Iterators

• There are numerous ways to return iterators.

  class List<T> {
    Iterator find(T value) { ... } 
    Iterator firstValue() { ... } 
    Iterator LastValue() { ... } 
    Iterator next(Iterator i) { ... } 
    Iterator previous(Iterator i) { ... } 
    }
  

• Other iterator-creating operations can build on these.

Iterator References

• To what does an iterator refer?
  • The choices are to the value itself or to the link containing the value.
• Well designed iterators should hide the implementation.
  • That is, refer to values, not links.
  • Hiding the links makes it easy to change the list implementation.

Implementing Iterators

• Inner-class iterators have access to the list implementation.
  • List manipulations are simple and secure.
• A separate iterator class requires special data and operators.
  • There’s no protection against unauthorized operator use.

Iterator Methods

• There are a number of other useful iterator methods:

    boolean atBeginning() { ... }
    boolean atEnd() { ... }
    boolean equals(Iterator i) { ... }
    T getValue() { ... }
  

• Be careful to distinguish between operations on iterators and operations on the list.
  • Maintain separation of concerns.

Iterator Under Change

• What should happen to an iterator if the associated value changes?
  • Deleting an value, or inserting a new value before or after.
• With deleting, should the iterator become useless, or move to another value?
• With inserting, should the iterator move to the new value, or stay with the original one?
  • Or maybe something else.

List Extremes

• What does it mean to be at one end of the list?
  • It could mean being at the actual end, or
  • being one past the end on a phantom value.

  

• Actual ends are simple and safe, but could lead to difficult manipulations.
• Phantom ends lead to simple and regular manipulations, but are dangerous.

List Traversal

• Iterators enable arbitrary traversal patterns through values.

  void drunkardsWalk(List<V> l, int steps)
  
    int n = l.size()
    List.Iterator here = l.begin()
  
    while steps-- > 0
      int m = random(2n) - n
      while m < 0 ∧ here ≠ l.begin()
        here = here.previous()
        ++m
      while m > 0 ∧ here ≠ l.end()
        here = here.next()
        --m
      f(here.value())

External Traversals

• Client-directed traversals are external traversals.
  • Implemented externally to the data structure.
• External traversals are
  • complicated: what methods are needed?
  • clumsy: client-visible details.
  • dangerous: invalid operations.

Internal Traversals

• Internal traversals are an alternative to external traversals.
• Internal traversals are implemented within the data structure.

  class list<T>
    void forEach(UnaryFunction<T> f)
      // call f on every value in the list.
  
  UnaryFunction<String> printer = 
    new UnaryFunction<String>(System.out)
  stringList.forEach(printer)
  

Comparison

• Internal traversals are
  • simpler: one method per traversal type.
  • straightforward: a minimum of details.
  • safer: the fiddly bits are hidden.
• However, internal traversals are limited to what the data structure provides.
  • A random walk using forEach()?

InEx Traversals

• InEx traversals are a happy medium (?) between internal and external traversals.
  • Some of the details are implemented in the data structure.
  • Other details are implemented elsewhere (in the language, usually).

  List<String> stringList = new ...
  for (String s: stringList)
    // operate on s
  

Summary

• Data structures should provide abstract access to contained values.
  • Access through iterators.
• Iterators should not be leak the internal details of the associated data structure.
• Methods for internal traversals can be simpler and, with the right language, more powerful than external traversals.

References

• Iterators: Signs of Weakness in Object-Oriented Languages by Henry Baker, ACM OOPS Messenger, pages 18-25, July, 1993.
• Iterators Must Go by Andrei Alexandrescu, BoostCon, 2009.

---

This page last modified on 4 February 2010.