Problem Set 3: Implementing Abstract Datatypes

Due: Tuesday, 21 September (beginning of class)

Purpose

• Gain experience implementing a data abstraction.
• Develop and carry out a testing strategy for a data abstraction.
• Learn to use abstraction functions and rep invariants to reason about data abstractions.
• Reason about design trade-offs in implementing data abstractions.

Reasoning About Data Abstractions

First, we will consider a implementing the Poly abstraction from Chapter 5 (specified in Figure 5.4). Suppose we implement Poly using a java.util.ArrayList. The ArrayList type allows us to represent an ordered collection of Objects. The objects we will store in our list are records of <term, coefficient>.

Here is the representation:

import java.util.ArrayList;

/**
 * OVERVIEW: A TermRecord is a record type for a power and coefficient.
 */
class TermRecord {
   int power;
   int coeff;
   TermRecord (int p_coeff, int p_power) {
	   power = p_power;
	   coeff = p_coeff;
   }
   public String toString () {
	   return "TermRecord: " + coeff + " x^ " + power;
   }
}

/**
 * OVERVIEW: Polys are immutable polynomials with integer coefficients. A typical Poly is:
 *    c_0 + c_1*x + c_2 * x^2 + ... + c_n * x^n
 */
public class Poly {
	// Rep:
	private ArrayList<TermRecord> terms;
        ...

Suppose this is the implementation of degree:

   /**
     *  EFFECTS: Returns the degree of this, i.e., the largest exponent
     * 	with a non-zero coefficient.  Returns 0 if this is the zero Poly.
     */
	public int degree () {
		return terms.get(terms.size() - 1).power;
	}

In an alternate implementation with the same rep (that is, the abstraction function and rep invariant may be different), suppose this is the implementation of coeff:

   /**
     * EFFECTS: Returns the coefficient of the term of this whose exponent is d.
     */
   public int coeff (int d) {
      int res = 0;
      for (TermRecord r : terms) {
	 if (r.power == d) { res += r.coeff; }
      }

      return res;
   }

Implementing StringGraph

Here is the specification of a StringGraph datatype. It is similar to the LabeledGraph datatype from PS2, except it does not have labels on the edges.

public class StringGraph
  OVERVIEW: A StringGraph is a directed graph  where
      V is a set of Strings, and E is a set of edges.
      Each edge is a pair (v1, v2), representing an edge
      from v1 to v2 in G.  A typical StringGraph is
       < {v1, v2, ..., vn} , { (v_a1, v_b1), (v_a2, v_b2), ... } >
    where each ai and bi is in [1, n].

  public StringGraph()
    EFFECTS: Creates a new, empty StringGraph: < {}, {} >

  public void addNode(String s) throws DuplicateException
     MODIFIES: this
     EFFECTS: If s is the name of a node in this, throws
       DuplicateException. Otherwise, adds
       s to the nodes in this, with no adjacent nodes:
           Gpost = < Vpre U { s }, Epre >

  public void addEdge(String s, String t) throws NoNodeException, DuplicateException
     MODIFIES: this
     EFFECTS: If s and t are not nodes in
        this, throws NoNodeException.  If there is already an edge
        between s and t, throws DuplicateEdgeException.
        Otherwise, adds an edge between s and t to this:
           Gpost = < Vpre, Epre U { (s, t) } >

  public Set<String> getAdjacent(String s) throws NoNodeException
     EFFECTS: If s is not a node in this, throws NoNodeException.
        Otherwise, returns a set containing the nodes adjacent to s

        That is, returns the set of nodes
            { e | <s, e> is in E }

  public String toString()
     EFFECTS: Returns a human-readable string representation of this.

There are many possible representations for the StringGraph. Here are three possibilities:

ArrayList<String> nodes;
boolean [][] edges;

Set<String> nodes;
Set<Edge> edges;

class Edge {
   String a, b;
   ... // constructors and toString
}

Set<NodeRecord> rep;

class NodeRecord {
   String key;
   Set<String> values;
   ... // constructors and toString
}

The next two questions ask you to implement the StringGraph datatype. The first question asks to develop a testing strategy, and the second question asks for the datatype implementation. You will probably want to revise your answers to question 7 as you develop your implementation, but we strongly recommend thinking about and developing your tests before the implementation, and refining them as you develop the implementation and are actually able to run the test cases.

Note that the specification requires the NoNodeException and DuplicateException datatypes. These should be defined in separate files as subtypes of Exception. For example, NoNodeException should be defined as:

package ps3;

public class NoNodeException extends Exception {
	private static final long serialVersionUID = 1L; // Avoids compiler warning
}

Print PDF