Rice University - Comp 212 - Intermediate Programming

Spring 2005

Lecture #14 - Examples of LRStruct Visitors - OOT vs. NOOT


Recall last lecture's exercise: Write an algorithm to remove the last element from an LRStruct.  Throw an exception if the LRStruct is empty.

Below are two different ways of thinking that lead to two different ways of solving the above problem.

Non Object-Oriented Thinking (NOOT)

Object-Oriented Thinking (OOT)

Any LRStruct algorithm must consider the case when the LRStruct is empty  and the case when the LRStruct is not empty. As dictated by the framework, any algorithm on LRStruct is a concrete IAlgo visitor with two methods: one to deal with the empty case and one to take care of the non-empty case.

 

If the LRStruct is empty, then throw an exception as specified. When the LRStruct host is empty, throw an exception as specified.

 

If the LRStruct is not empty, traverse the LRStruct until the empty LRStruct is reached, at which point ask the preceding LRStruct to remove its first. 

The above algorithm seems straightforward and simple enough. It involves imposing an external control structure to traverse an LRStruct and stop at some appropriate point.  As illustrated in a subsequent section, such an algorithm is usually implemented in terms of a loop whose exit condition involves checking an LRStruct for emptiness!

When the LRStruct host is not empty, it has a first and a rest, which is itself an LRStruct.  In order to remove the last element from such a host, we need to answer two questions:
  1. which object should be  responsible for determining whether or not the host's first is the last element?
  2. which object should be responsible for removing the last element?  

The host's rest knows whether or not itself is empty, and thus can determine whether or not the host's first is actually the last element.  Therefore the responsibility for determining whether or not the host is holding the last element should be delegated to the host's rest.

Though the host's rest knows whether or not the host holds the last element, it cannot remove that element.  The only object capable of removing this element is the host itself.

So knowing when to remove does not necessarily mean capable of the task of removal.  In general, knowing when some action must take place does not mean that the same object is capable of carrying out that action.  These are two distinct responsibilities that need to be distributed between two cooperating objects.

The above OO thought process leads to the idea of decomposing the task of removing the last element into two subtasks.

  1. Ask the host's rest for help in determining whether or not the host is holding the last element.  When asking for help, the host will need to pass itself as a parameter to the helper task so that once the last element is discovered, it can then be removed.
  2. Help the preceding LRStruct remove its last element.  When helping the preceding (non-empty) LRStruct to remove an element, an empty LStruct simply tells the given LRStruct to remove its first, while a non-empty LRStruct will ask its rest for help to remove its last element passing itself as a parameter.

Note that the above algorithm involves no notion of list traversal at all.  It entails decomposing the original task into smaller subtasks ("divide-and-conquer") and is only expressed in terms of which objects should be doing what and what pieces of information must be passed to each object's method in order to carry out each of the subtasks.

  OOP calls for thinking in terms of  problem abstraction, task decomposition, and delegation of responsibilities.  It is a paradigm shift that emphasizes design and promotes a different way of thinking about formulating and solving problems.

 

Below is an implementation of the procedural non-oo algorithm.

Non Object-Oriented Algorithm (NOOA)

Non Object-Oriented Coding (NOOC)

Algorithm to check for emptiness
public class IsEmpty implements IAlgo {
  // Singleton
  public Object emptyCase(LRStruct host, Object... inp) {
    return Boolean.TRUE;
  }

  public Object nonEmptyCase(LRStruct host, Object... inp) {
    return Boolean.FALSE;
  }
}
If the LRStruct is empty, throw an exception.

If the LRStruct is not empty, traverse the LRStruct until the empty LRStruct is reached, at which point ask the preceding LRStruct to remove its first. 

/**
* Static method of some class.
*/
public static void removeLast(LRStruct list) {
  if ((Boolean)list.execute(IsEmpty.Singleton)) {
    throw new java.util.NoSuchElementException("Empty list has no data.");
  }
  LRStruct next = list.getRest();  
  while (!((Boolean)next.execute(IsEmpty.Singleton))) {
    list = next;
    next = list.getRest();
  }
  list.removeFront();
}
   
Comment

Though the high level description of the algorithm seems simple enough, its translation into code is not that simple.

It is not apparent that the code is a faithful (and correct) translation of the algorithm statement because it involves a lot of tedious book-keeping and flow control.

 

 

Now consider how the OO algorithm is implemented.

Object-Oriented Algorithm (OOA)

Object-Oriented Coding (OOC)

An algorithm to remove the last element from an LRStruct is a concrete IAlgo visitor.
public class RemLast implements IAlgo {
  // Singleton
When the LRStruct host is empty, throw an exception as specified.  The code on the right simply expresses such an action.
  public Object emptyCase(LRStruct host, Object... inp) {
    throw new java.util.NoSuchElementException("Empty list has no data.");
  }

When the LRStruct host is not empty, ask the host's rest for help in determining whether or not the host is holding the last element, passing the host as a parameter just in case this is true and the last element needs to be removed.

  public Object nonEmptyCase(LRStruct host, Object... inp) {
    return host.getRest().execute(RemLastHelp.Singleton, host);
  }
}
The algorithm for a host LRStruct to help remove the last element from the preceding LRStruct, p, is a concrete IAlgo visitor whose input parameter is p.
public class RemLastHelp implements IAlgo {
  // Singleton
The empty LRStruct tells the preceding LRStruct to remove its first, because the preceding LRStruct is the one that holds the last element.
  /**
  * @param inp inp[0] is the LRStruct preceding host.
  */  
  public Object emptyCase(LRStruct host, Object... inp) {
    return ((LRStruct)inp[0]).removeFront();
  }
A  non-empty LRStruct asks its rest for help to remove its last element passing itself as a parameter.
  /**
  * The last element of the (non-empty) host is the
  * last element of inp[0], the LRStruct preceding host.
  */
  public Object nonEmptyCase(LRStruct host, Object... inp) {
    return host.getRest().execute(this, host);
  }
}
   
Comment:

The implementation code for the OO algorithm directly maps to the abstract high-level description of the algorithm and can be easily proved to be correct.

It is "declarative" in nature.  It does not involve any conditional to specify when to perform certain task.  It simply states what needs to be done for each state of the host LRStruct.  Polymorphism is put to use to direct all control flow reducing code complexity.

 

The RemLastHelp defined in the above will only perform correctly if it is passed the appropriate parameter: the LRStruct  that precedes the host.  Though it is called once, inside of RemLast.nonEmptyCase(...), by the original LRStruct to "help" it determine whether or not it is holding the last element and remove that element if this is the case, we have to go through the standard process of defining a class for it.  We can (and should) rewrite RemLastHelp as a local anonymous inner class that is instantiated "on-the-fly" inside of the RemLast.nonEmtpyCase(...) as follows.

public class RemLast implements IAlgo {
  // other methods elided...
    public Object nonEmptyCase(LRStruct host, Object... inp) {
        return host.getRest().execute(new IAlgo() { // Anonymous inner class!

            public Object emptyCase(LRStruct h, Object... p) {
                return ((LRStruct)p[0]).removeFront();
            }

            public Object nonEmptyCase(LRStruct h, Object... p) {
                return h.getRest().execute(this, h);
            }
        }, host);
    }
}

In the above, note how the parameters of the anonymous inner class are renamed in order to avoid masking the parameter names in the outer object.

In-class exercise 1: 

Remove the minimum element from a list of Integers.

Click here to see a solution.

In-class exercise 2: 

Reverse a list.

Click here to see a solution.

 


dxnguyen at rice.edu
Copyright 2005, Dung X. Nguyen - All rights reserved.