First Exercise: Pair-programming

By Thursday class next week (2/2/2006), do the following:

1. get paired

2. download JUnit, get it installed on a PC, and figure out how to run it... try the examples, get familiar with how a JUnit test class is written for a target Java class. Also get familiar with how test classes are aggregated in test suites with the alternate form of the JUnit test class.

3. Write, as a pair (using JUnit testing) a Java class to implement the DES specified below. You may wish to try test-first, but this is not a requirement, as we will do the next exercise as test-first. Test-first means you write your test class first, using it to define the means by which you will convince yourself your target code works... then you write the target class.

   In any event, JUnit will be the "driver" for this program/class.

DES: Double-Ended Stack of Elt (bounded)

new(n) :            --> DES
pushE  :  DES x Elt --> DES
pushW  :  DES x Elt --> DES
popE   :  DES       --> DES
popW   :  DES       --> DES
topE   :  DES       --> Elt
topW   :  DES       --> Elt
max    :  DES       --> int
size   :  DES       --> int
isEmpty:  DES       --> bool
isFull :  DES       --> bool

I now define my semantics based on these canonical constructors, using ML as my definition language (these specs are executable... try them with an ML interpreter):

(*

  DES: double ended stack of E (bounded)

  stack is created with max size.
  push on a full stack is a noop.

  New(n) :            --> DES
  pushE  :  DES x Elt --> DES
  pushW  :  DES x Elt --> DES
  popE   :  DES       --> DES
  popW   :  DES       --> DES
  topE   :  DES       --> Elt
  topW   :  DES       --> Elt
  max    :  DES       --> int
  size   :  DES       --> int
  isEmpty:  DES       --> bool
  isFull :  DES       --> bool

*)

datatype ('E) DES =
   New of int
   | pushE of ('E) DES * int
   ;

fun max(New(n)) = if n>=0 then n else 0
  | max(pushE(D,e)) = max(D)
  ;

fun isEmpty(New(n)) = true
  | isEmpty(pushE(D,e)) = ( max(D)=0 )
  ;

fun size(New(n)) = 0
  | size(pushE(D,e)) = if size(D)=max(D) then max(D) else size(D)+1
  ;

fun isFull(New(n)) = ( n <= 0 )
  | isFull(pushE(D,e)) = if size(D)<max(D)-1 then false else true
  ;


fun pushW(New(n),e) = pushE(New(n),e)
  | pushW(pushE(D,e1),e2) = if isFull(D)
                            then D
                            else if isFull(pushE(D,e1))
                                 then pushE(D,e1)
                                 else pushE(pushW(D,e2),e1)
  ;

fun popE(New(n)) = New(n)
  | popE(pushE(D,e)) = if isFull(D) then popE(D) else D
  ;

fun popW(New(n)) = New(n)
  | popW(pushE(D,e)) = if isEmpty(D)
                       then D
                       else if isFull(D)
                            then popW(D)
                            else pushE(popW(D),e)
  ;

exception topEmptyStack;

fun topE(New(n)) = raise topEmptyStack
  | topE(pushE(D,e)) = if isFull(D) then topE(D) else e
  ;

fun topW(New(n)) = raise topEmptyStack
  | topW(pushE(D,e)) = if isEmpty(D) then e else topW(D)
  ;

(* sample data points *)


val d0 = New(8);
val d1 = pushE(d0,11);
val d2 = pushE(d1,12);
val d3 = pushE(d2,13);

val dd0 = New(100);
val dd1 = pushW(dd0,21);
val dd2 = pushE(dd1,22);
val dd3 = pushW(dd2,23);
val dd4 = pushW(dd3,24);

val tb0 = New(3);
val tb1 = pushW(tb0,31);
val tb2 = pushW(tb1,32);
val tb3 = pushW(tb2,33);
val tb4 = pushW(tb3,34);
val tb5 = pushW(tb4,35);
val tb6 = pushW(tb5,36);