Assignment #2: ADTs and Linked Lists

This assignment is to be done individually and handed in electronically (using submit) before 12:00pm on Tuesday, February 8.

Problem

You are to write a Java program to maintain an inventory of sales of popular books, grouped by author.

Scenario

You are given a file of book sales, each entry of which includes the name of the author, the title of the book, and the number of copies sold by one store. You must track total sales for each book, and be prepared to report these totals as well as calculating the total sales for each author.

Specifications

Your employer has dictated that you are to store the sales information using a list structure that keeps its entries in the order in which they were most recently changed. Using such a list, whenever an entry is to be modified, it must first be moved to the head of the list, so the most recently changed entry appears first, the entry that was second most recently changed appears second, and the entry that was least recently changed appears last on the list.

A list organized in this fashion can be described using two interfaces: one describes a key-value pair and the other describes the list itself, which is accessed based on matching the key.

public interface Pair {

/* object pairing a key and some value */

public Object getKey();

//pre: returns the key for this

public Object getValue();

//pre: returns the value for this

public void setKey(Object newKey);

//pre: newKey is not null

//post: the key field contains newKey

public void setValue(Object newValue);

//pre: newValue is not null

//post: the value field contains newValue

}

public interface FrontList {

/* finite (possibly empty) collection of Pair objects, ordered by most recent use

public boolean isEmpty();

//post: returns true iff this is empty

public void add(Pair newItem);

//pre: newItem is not null

//post: inserts newItem at the head of the list

// (before any Pairs that may already be present)

public boolean moveToFront(Object key);

//pre: key is not null

//post: if a Pair matching the key is an element of this,

// that Pair is moved to the head of this and the method returns true;

// otherwise the method returns false (and the list is unchanged)

public Pair getFirst();

//pre: this is not empty

//post: returns the Pair at the head of this

public void replaceFirst(Pair newItem);

//pre: key is not null

// this is not empty

//post: replaces the Pair at the head of the this by newItem

public Object[] dump();

//post: returns an array holding the Pairs from this in the same order

}

The information for a particular book title can then be stored as a pair for which the key is the book title and the associated value is the total number of sales for that book. The information for an author can be stored as a pair for which the key is the author’s name and the associated value is the list of books (title-sales pairs) written by that author. Finally, the sales inventory is a list of authors (each of which is then associated with a list of title-sales pairs). For simplicity, we’ll assume that each book has only one author and that the author is uniquely identified by his or her last name.

A sample file of sales records can be found in sales.txt, resulting in an inventory structure illustrated in inventory.txt, where lists are shown with their heads towards the top of the page. Notice that the ordering of each list from head to tail is determined by how recently each item in the list was last updated.

The input to your program will be a file of sales records, one per line, arbitrarily interspersed with a “report” line consisting of a single question mark (“?”) only. Each time you read a sales record, you are to update the inventory (updating one of the book lists as well as the author list). Each time you read a report line, you are to append a complete sales report to report.txt, one line per book as well as a totals line for each author, in the order that the books and authors appear in the inventory. For the inventory shown in inventory.txt, a corresponding report can be found in report.txt.

As part of your solution, you must design and implement classes to represent both interfaces described above. The class implementing FrontList must use singly-linked lists, which means the methods manipulate objects from the Node class as defined in the notes and text. This Node class should not be changed. We will provide the exact same Node class used when executing your code upon submission, so you need not submit or change this class.

Input and Output Files

• For file input and output, we strongly recommend that you use the CS 123 TextInput and TextOutput classes.
• You should hard-code the file names sales.txt and report.txt as constants in your code. Do not prefix the names with path names; otherwise, your code will not compile properly when we test your assignment and you will lose marks.

Design

• We expect you to spend much of your time away from the computer. It is not unreasonable to expect that at least one-third of the time you spend on this assignment will be at the design stage. Questions to consider include the role of each class and method (e.g., which class should be responsible for reading sales records from the file? which should be responsible for parsing the records? are there any helper methods that will simplify your implementation?).
• Be sure that you separate components that use an interface from the components that implement that interface. Use a data factory to create instances of your abstract data types:

public class DataFactory {

/* generator of instances for each abstract data type */

public static Pair makePair(){

//post: returns an instance of the ADT Pair

return (Pair) new PairClass(); /* use the name of your class here */

}

public static FrontList makeFrontList(){

//post: returns an instance of the ADT FrontList

return (FrontList) new FrontListUsingLinks (); /* use your class name */

}

}

• Write a brief text file named design.txt that explains the approach you have taken to solve the problem. Highlight any assumptions or clarifications that you have made. At a minimum, design.txt must include descriptions of the classes used, the relationships between classes and how the data is stored. If you create this file using Microsoft Word or Wordpad, be sure to save it as a text-only document. You will be penalized if your document is not just text.

Implementation and Documentation

• Use test compile to make sure your assignment works when we test it. Remember that some files will compile in JBuilder but not on other platforms.
• Since we will be performing some automated testing of your submission, you must include a Main class which contains the main() method for your program.
• If you make any assumptions other than the ones listed below, ensure that you document them in design.txt.
• sales.txt will exist.
• All specified output files can be created with the names specified.
• There is enough memory to hold the complete inventory.
• Input files may be empty but input strings are non-empty.
• Each sales record is on one line, and has the three required fields: a string with no quotation marks and no intervening blanks, a string in quotation marks, and an integer.

Important Notes!

You may only use the becker, java.lang and java.util packages. Contact the tutor before using any other packages. Not doing so may cause your program to fail compilation.

For this and all subsequent programming assignments in CS124 you are not allowed to use package names. That is, your  files cannot begin with something like 

package Assign02;

This causes marking scripts to fail. If you make package names in this way and the marking scripts fail, you will be penalized. 

Documentation

• Preconditions and postconditions are required for all methods that you implement. This includes trivial accessor methods. Also ensure that the purpose of each method is clear to the marker.
• Choose meaningful identifiers. This together with appropriate inline documentation should mean your code is easy to understand. In particular, each non-trivial block of code should be explained with a comment.

Testing

• Create an input file that shows that your program works as expected. Be sure to include a variety of different system test cases that exercise your program. In a separate document, named testing.txt, identify for each of the six methods defined for the FrontList class, 2 different black box tests (with respect to that method) that are covered by your input. This is best shown by a chart with entries including the condition being tested, the specific inputs (and contexts) that demonstrate that your program works correctly in that situation, the expected results, and an explanation (using knowledge of the code’s structure) of why the input checks that condition for that method. For example, your file might look like this:

method: isEmpty()

condition: the FrontList is empty

input: The first sales record processed is ‘Brown "The Da Vinci Code" 12’ followed by ‘?’

output: The output shows ‘Brown "The Da Vinci Code" 12’ followed by ‘Brown 12’

explanation: Before recording the first author record and first title record for that author, the system checks for the empty list.

method isEmpty()

condition: the FrontList is not empty

….

Grading

Design	15%
Documentation (including pre- and post-conditions)	28%
Correctness	45%
Testing	12%

You can also view the marking scheme for Assignment 2.

Electronic Submission

For every file you submit, include your name and ID number. Submit:

• Main.java that contains the main method to run your program (necessary since we will be marking part of the assignment by script)
• all *.java files used by your program - EXCEPT your Node.java class. This will be provided.
• testing.txt
• design.txt

Note: Late assignments will NOT be accepted.