Programming Assignment 1

Due Date

See the assignment turn-in page (last modified on 23 February 2010) for instructions on turning in your assignment.

The absolute deadline for turning-in Assignment 1 is Saturday, 23 October at 11:30 p.m.. It is not possible to turn-in Assignment 1 after the absolute deadline.

Background

A linked sequence ADT is a family of data structures representing value sequences. Adjacent values in a linked sequence are directly linked; non-adjacent values are not linked.

The links in a sequence are numbered sequentially starting from zero at one end of the sequence; the end values in a sequence are assumed to have links on both sides.

An empty sequence is assumed to have one link.

A value v in a linked sequence is referred to by the index associated with v's left link (or, if you prefer, the smaller of the two index values directly associated with v). Operations on values in a linked sequence are specified relative to link indices.

The stack, queue, and linked list ADTs are members of the linked-sequence ADT family. They differ in the range of indices their operations can accept:

• Stack operations can only accept index 0.
• Queue put operations can accept only index n, where n is the number of elements in the queue, and the other operations can accept index 0.
• All linked-list operations can accept any of the indices 0 through n-1, where n is the number of elements in the linked list; only the put operation can accept the index n.

The Assignment

Part 1: Implement the stack, queue and linked list ADTs. Each ADT should be a separate class implementing the linked-sequence interface given in

/export/home/class/cs-305/pa1/LinkedSequence.java

The implemented ADTs should dynamic, capable of storing arbitrarily many values. The implementations should be from scratch, without using classes from the Java Collection library.

Part 2: Implement a class implementing the LinkedSequenceByExample interface given in

/export/home/class/cs-305/pa1/LinkedSequenceByExample.java

Implementation

The classes created for the first assignment should be placed in the default package. Classes are placed in the default package when the Java source code does not use package declarations. Using package declarations in Java source code places class files in non-default packages, and the turn-in software, expecting the class files to be in the default package, won't be able to find them.

/export/home/class/cs-305/pa1/pa1.jar

$ java -classpath jar-path/pa1.jar:. main class-name

where jar-path is the path to pa1.jar and class-name is the name of the class implementing the LinkedSequenceByExample interface. For example, if the class ADTs implements LinkedSequenceByExample and you’re using pa1.jar in the public class directory, you would type

$ java -classpath /export/home/class/cs-305/pa1/pa1.jar:. main ADTs 

Make sure you give the class name (ADTs in this example) on the command line, not the name of file containing ADTs (ADTs.class).

You can simplify your typing a bit by copying pa1.jar to your working directory ( . ):

$ cp /export/home/class/cs-305/pa1/pa1.jar .

$ java -classpath ./pa1.jar:. main Queue

If you do copy pa1.jar, make sure you keep it up to date with version in the class directory. You can check jar file j’s version by typing

jar tf j | grep 2010

For example,

$ jar tf /export/home/class/cs-305/pa1/pa1.jar | grep 2010
2010.Sep.29

$ 

The recognized optional command-line options are:

• -v: print informative message to std-err while running tests.

$ java -ea -cp pa1.jar:. main LinkedADTs
Test failed:  requested a queue, got a stack.

$ java -ea -cp pa1.jar:. main -v LinkedADTs
Request a queue.
Test ADT as a linked list.
  (put, 0, 1, true, undefined) : passed.
  (put, 1, 3, true, undefined) : ADT failed on this action.
Test ADT as a queue.
  (put, 0, 1, true, undefined) : passed.
  (put, 1, 3, true, undefined) : ADT failed on this action.
Test ADT as a stack.
  (put, 0, 1, true, undefined) : passed.
  (put, 1, 2, false, undefined) : passed.
Test failed:  requested a queue, got a stack.

$