Algorithms and Abstract Data Types Programming Assignment 1 Solution

Our goal in this project is to build an Integer List ADT and use it to alphabetize the lines in a file. This ADT module will also be used (with some modifications) in future programming assignments, so you should test it thoroughly, even though not all of its features will be used here. Begin by reading the handout ADT.pdf posted on the class webpage for a thorough explanation of the programming practices and conventions required in this class for implementing ADTs in Java and C.




Program Operation




The main program for this project will be called Lex.java. Your List ADT module will be contained in a file called List.java, and will export its services to the client module Lex.java. Each file will define one top level class, List and Lex respectively. The required List operations are specified in detail below. Lex.java will take two command line arguments giving the names of an input file and an output file. The input can be any text file. The output file will contain the same lines as the input arranged in lexicographic (i.e. alphabetical) order. For example:




Input file:


Output file:
one


five
two


four
three


one
four


three
five


two



Lex.java will follow the sketch given below.




Check that there are two command line arguments. Quit with a usage message to stderr if more than or less than two strings are given on the command line.



Count the number of lines n in the file named by args[0]. Create a String array of length n and read in the lines of the file as Strings, placing them into the array.



Create a List whose elements are the indices of the above String array. These indices should be arranged in an order that effectively sorts the array. Using the above input file as an example we would have.



Indices: 0 1 2 3 4

Array: one two three four five
















List:
4
3
0
2
1



To build the integer List in the correct order, begin with an initially empty List, then insert the indices of the array one by one into the appropriate positions of the List. Use the InsertionSort algorithm as a guide to your thinking on how to accomplish this. (Please read the preceding two sentences several times so that you understand what is required. You are not being asked to sort the input array using InsertionSort.) You may use only the List ADT operations defined below to manipulate the List. Note that the String class provides a method called compareTo() that determines the lexicographic ordering of two Strings. If s1 and s2 are strings then:




s1.compareTo(s2)<0 is true if and only if s1 comes before s2

s1.compareTo(s2)0 is true if and only if s1 comes after s2




1
s1.compareTo(s2)==0 is true if and only if s1 is identical to s2




Use the List constructed in (3) to print the array in alphabetical order to the file named by args[1]. Note



that at no time is the array ever sorted. Instead you are indirectly sorting the array by building a List of indices in a certain order.




See the example FileIO.java to learn about file input-output operations in Java if you are not already familiar with them. I will place a number of matched pairs of input-output files in the examples section, along with a python script that creates random input files along with their matched output files. Use these tools to test your program once it is up and running.




List ADT Specifications




Your list module for this project will be a bi-directional queue that includes a “cursor” to be used for iteration. Think of the cursor as highlighting or underscoring a distinguished element in the list. Note that it is a valid state for this ADT to have no distinguished element, i.e. the cursor may be undefined or “off the list”, which is in fact its default state. Thus the set of “mathematical structures” for this ADT consists of all finite sequences of integers in which at most one element is underscored. A list has two ends referred to as “front” and “back” respectively. The cursor will be used by the client to traverse the list in either direction. Each list element is associated with an index ranging from 0 (front) to n-1 (back), where n is the length of the list. Your list module will define the following operations.




// Constructor






List() // Creates a
new empty list.


// Access functions




int length()
// Returns the number of
elements in this List.
int index()
// If
cursor is defined,
returns the index of the cursor element,


// otherwise returns -1.


int front()
// Returns front element. Pre: length()0
int back()
// Returns back element. Pre: length()0
int get()
// Returns cursor element. Pre: length()0, index()=0
boolean equals(List
L) // Returns true
if and only if this List and L are the same
integer sequence. The states of the cursors in the two Lists
are not used in determining equality.



Manipulation procedures
void clear()
// Resets this List to its original
empty state.
void moveFront() // If List is non-empty, places
the
cursor under the front element,


// otherwise
does nothing.




void moveBack()
// If List is non-empty, places
the
cursor under the back element,


// otherwise
does nothing.




void movePrev()
// If cursor
is defined and not
at front, moves cursor one step toward
front of this List, if cursor is defined and at front, cursor becomes
undefined, if cursor is undefined does nothing.
void moveNext() // If cursor is defined and not at back, moves cursor one step toward




back of this List, if cursor is defined and at back, cursor becomes
undefined, if cursor is undefined does nothing.



void prepend(int data) // Insert new element into this List. If List is non-empty, // insertion takes place before front element.

void append(int data) // Insert new element into this List. If List is non-empty,




insertion takes place after back element.
void insertBefore(int data) // Insert new element before cursor.

Pre: length()0, index()=0
void insertAfter(int data) // Inserts new element after cursor.

// Pre: length()0, index()=0

void deleteFront() // Deletes the front element. Pre: length()0

void deleteBack() // Deletes the back element. Pre: length()0







2
void delete() // Deletes cursor element, making cursor undefined.

// Pre: length()0, index()=0




// Other methods




public String toString() // Overrides Object's toString method. Returns a String

representation of this List consisting of a space
separated sequence of integers, with front on left.
List copy() // Returns a new List representing the same integer sequence as this

List. The cursor in the new list is undefined, regardless of the
state of the cursor in this List. This List is unchanged.



The above operations are required for full credit, though it is not expected that all will be used by the client module in this project. The following operation is optional, and may come in handy in some future assignment:




List concat(List L) // Returns a new List which is the concatenation of

this list followed by L. The cursor in the new List
is undefined, regardless of the states of the cursors



in this List and L. The states of this List and L are
unchanged.



Notice that the above operations offer a standard method for the client to iterate in either direction over the elements in a List. A typical loop in the client might appear as follows.




L.moveFront();

while(L.index()=0){

x = L.get();




do something with x L.moveNext();



}




To iterate back to front, simply replace moveFront() by moveBack() and moveNext() by movePrev(). One could just as well set this up as a for loop in either direction. Observe that in the special case where L is empty, the cursor is necessarily undefined so that L.index() returns -1, making the loop repetition condition initially false, and the loop executes zero times, as it should on an empty List. It is required that function index() be implemented efficiently.




The underlying data structure for the List ADT will be a doubly linked list. The List class should therefore contain a private inner Node class which itself contains fields for an int (the data), and two Node references (the previous and next Nodes, respectively) which may be null. The Node class should also define an appropriate constructor as well as a toString() method. The List class should contain three private fields of type Node referring to the front, back, and cursor elements, respectively. The List class should also contain private int fields storing the length of the List and the index of the cursor element. When the cursor is undefined, an appropriate value the index field is -1, since that is what is returned by index() in such a case.




All of the above classes, fields and methods will be placed in List.java. Create a separate file called ListTest.java to serve as a test client for your ADT. Do not submit this file, just use it for your own tests. I will place another test client on the webpage called ListClient.java. Place this file in the directory containing your completed List.java, then compile and run it. The correct output is included in ListClient.java as a comment. You will submit this file unchanged with your project.




You are required to submit a Makefile that creates an executable jar file called Lex, which is the main program for this project. Include a clean target in your Makefile that removes Lex and any associated .class files to aid the grader in cleaning the submit directory. One possible Makefile will be included on the course webpage under Examples/pa1. You may alter this Makefile as you see fit to perform other tasks such as submit. See my CMPS




3
12B website (https://classes.soe.ucsc.edu/cmps012b/Winter18/lab1.pdf) to learn basic information about Makefiles.




You must also submit a README file for this (and every) assignment. README should list each file submitted, together with a brief description of its role in the project, and any special notes to myself and the grader. README is essentially a table of contents for the project, and nothing more. You will therefore submit five files in all:




List.java written by you

ListClient.java provided on webpage, do not alter

Lex.java written by you

Makefile provided on webpage, you may alter

README written by you




Points will be deducted if you misspell these file names, or if you submit jar files, .class files, input-output files, or any other extra files not specified above. Each source file you submit must begin with a comment block containing your name, CruzID, and the assignment name.




Advice




The examples Queue.java and Stack.java on the website are good starting points for the List module in this project. You are welcome to simply start with one of those files, rename things, then add functionality until the specifications for the List ADT are met. You should first design and build your List ADT, test it thoroughly, and only then start coding Lex.java. Start early and ask questions if anything is unclear. Information on how to turn in your project is posted on the class webpage.



















































































































4