Princeton University Computer Science Dept.

Computer Science 441 Programming Languages Fall 1998 Assignment 9 Due 12/15/98

A. GJ

The following are interfaces for singly and doubly-linked nodes and a linked list:

// Interface for node objects w/ values of type String

public interface NodeIfc<T>{

   // Returns following node.
   T getNext();

   // Hook up newNext to the right of this
   void setNext(T newNext);

   // Returns value stored in node
   String getValue();

   // Sets value stored in node to newVal
   void setValue(String newVal);
}
-----------------------------------------

// Interface for doubly-linked node objects w/ values of type String

public interface DbleNodeIfc<T> extends NodeIfc<T>{

   // Returns preceding node.
   T getPrevious();

   // Set node bfore this to be newPrevious
   void setPrevious(T newPrevious);
}

-----------------------------------------
// Interface for Ordered List of Strings, parameterized by the type of node.
import java.util.Enumeration;

public interface OrdListIfcN< implements NodeIfc<N>>{

   // Return true iff val is in list
   boolean inList(String val);

   // Add newNode to list (in proper order).  Duplicates are OK.
   void add(N newNode);

   // Return an Enumeration which will go through all elements of list in order.
   Enumeration getEnumerator();

   // If val is in list, delete first copy and return true, else return false.
   boolean delete(String val);
}   

1. Please write GJ classes:
   1. SNode for singly-linked nodes (that implements NodeIfc<SNode>).

   2. DNode for doubly-linked nodes (that implements DbleNodeIfc<DNode>).
      Warning: The methods setNext and setPrevious in DNode must each set two links so the new elements are hooked up properly. You may find it easiest to add protected auxiliary methods to just set single links in order to get these to work properly.

   3. OrdList<N implements NodeIfc<N>> for linked lists (that implements OrdListIfc<N>).

   The class OrdList should result in a singly linked list if it is instantiated with SNode, and a doubly-linked list if instantiated with DNode. (Note: SNode and DNode cannot be subclasses.)

2. Depending on the instantiation, OrdList can represent either singly or doubly-linked lists, but doubly-linked lists usually provide more specialized implementations and methods. Write class DOrdList<N implements DbleNodeIfc<N>> which extends OrdList and adds a tail instance variable and method

      // Return Enumeration which goes through elements of list in reverse order.
      public Enumeration getRevEnumerator();
   

   You will also have to override methods add and delete to ensure that the tail instance variable gets overridden properly. See if you can write them so that you call the inherited method from the superclass and then simply execute a few extra instructions to make sure that tail has the proper value.

A. Object Encodings

For the following problems, please refer to CellClass from the lecture notes as well as the following subclass:

   class ColorCellClass inherit CellClass{
      color: ColorType;
      getColor(): ColorType {return self.color}
      set(nuVal:int): void {x := nuVal;
                            self.color := red;}
}

1. Let cell hold the result of evaluating new CellClass. In particular, its x instance variable has value 0. Please explain in terms of our encoding what happens when the following expression is evaluated:

      cell.bump();
   

   Your answer should include a description of the use of existentials, the suite of methods (meth and meth'), and the detailed definition of the bump translation given in the lecture notes.

2. With the translation given in class, please show that if we send the bump method to an object instantiated from ColorCellClass, then the result will be a cell with color red. Show this by arguing from the translation, not from intuition about how object-oriented languages work. That is, I want you to convince me that the translation properly handles dynamic method invocation.