CMSC 341 Spring 2011
Project 1

Assigned	Monday, Feb 7, 2011
Due	11:59pm, Wednesday Feb 23, 2011
Update	Thursday, Feb 10, 2011 1. Correction: in the first line of the description, “unordered” is changed to “unsorted”. 2. Clarification: in Command File section, for commands UNION, INTERSECTION, DIFFERENCE, when an exception occurs due to violation of uniqueness of keys, stop the current command without changing the Alist in <result index> (remains the same as before the command is executed), and proceed to the next command.
Update	Tuesday, Feb 15, 2011 1. For simplicity string (either as value or key) in each command will NOT contain spaces and will NOT be enclosed within quotation markers, for example GeorgeWBush, YunPeng. Here is an example of INSERT command assuming the command line gives string-int for the key/value types INSERT 0 DellD630 1377

Objectives

To exercise and refresh your Java programming and in particular the concept of generic class
To start work with LIST, one of the simplest but also the widely used data structures, and
To warm up you for more complex data structures and more elaborated project assignments later in this course.

Description

In this project you will implement a data structure called an association list, or alist. Alists are used to store ~~unordered~~ unsorted collections of values. A unique key is associated with each value in an AList and the key must be used to access the value. The term AList is borrowed from the Lisp language in which ALists are implemented using lists as the underlying data structure. In this project, you should use an ArrayList or LinkedList (your choice) as the underlying data structure, any other Java Collection classes are not allowed.

One way to understand an AList is to compare it with a simple array. Arrays are used to store values, and the values are accessed by specifying an integer, namely an array index, that gives the location of the desired value. The array index can be thought of as a key. In contrast, there is no notion of location or index with ALists, and both keys and values can be any class type, not necessarily integers.

For example, in one Alist you want the age of a person (integer) to be associated to and accessed by that person’s name (string), and you may find an element in that Alist containing key = “George W. Bush” and value = 64. For another Alist, you may want the instructor of a class (string) to be associated to and accessed by the class number (integer), and you may find an element in that Alist containing key = “1072” and value = “Yun Peng”. In the latter case, the fact that the key is 1072 does not mean that the value "Yun Peng" is stored at location 1072. It just means that there's a value (i.e. the string "Yun Peng") in the AList that was stored with the key 1072 and that this key must be used to retrieve the value.

Each element of AList, called AListElement, contains a value and a key. Both AList class and AListElement class shall be generic classes so that different types of keys and values can be accommodated. All elements in an Alist shall have the same key/value types.

In addition to the value-key pair, each AListElement also has an indicator of whether the element has been deleted. The purpose of the deleted member allows us to use a technique known as lazy deletion when removing elements from an AList. That is, rather than actually removing the element from the list, we will simply mark it as deleted.

Both AList class and AListElement class should have methods to support the commands specified shortly in this document. All of these methods must observe and preserve the uniqueness of keys, i.e., no two elements in the same AList shall contain the same key. If this is violated, you should throw an exception and print a proper error message.

You should also write a main( ). Among other things, your main( ) should construct an array of ALists which will be used to store all ALists created by the commands you read in from the command file. Each cell of this array stores one AList. The types of key/value, the size of the array, and the full path of the command file will be read in from the command line, so your main( ) should also provide methods to read and parse these command line parameters.

Command Line

Project 1 will be invoked with a command line that consists of three arguments. The first argument specifies the types of the keys and values. Although AList can have any value and key types, in this project we restrict to only two pairs of types. Specifically, the first argument will be either "int-string" (without the quotes), in which case the keys are integers and the values are strings; or "string-int" (without the quotes), in which case the keys are strings and the values are integers. The second argument will be an integer for the size of the array where ALists will be stored. The third argument will be the name of the full path of a file that contains a set of operations that must be performed on ALists of the appropriate type. All ALists created by the operations in a single command file will have the same key-value types as given in the first argument. Following is an example of the command line:

  ant -Dargs="int-string 20 /afs/umbc.edu/users/y/p/ypeng/pub/cs341s11/Proj1/test1.txt" run

Note that you must check command line arguments to ensure that they are valid, e.g. there are three arguments and the command file can be opened, and throw an exception if an error is found.

Command File

Commands in the file specify a sequence of operations to be performed on ALists. Each line in the file represents one command. Blank lines may appear anywhere in the file and should be ignored. Lines whose first character is '#' are comments and should also be ignored. Otherwise, you can assume that any line containing a command is syntactically well-formed. We make this assumption so you don't have to spend lots of time making the command file parser bullet proof.

All commands and their parameters must be echoed as part of your program output.

All ALists created by the operations shall be stored in an array. The commands described below all have as their first argument a number that is the index in this array of the AList on which the command is to be performed. You can assume that the array index is valid. You can also assume that other parameters in each command are with correct types consistent with the types given in the first command line argument.

The command file format follows:

INSERT <AList-array-index> <key> <value> -- Insert the given value with the given key into the AList whose array index is specified. If the key already exists in the AList throw an exception and print an appropriate message.
FIND <AList-array-index> <key> -- Retrieve and print the value associated with the given key in the AList whose array index is specified. If the key does not exist in the AList, throw an exception and print an appropriate message.
REMOVE <AList-array-index> <key> -- Remove the value associated with the given key in the AList whose array index is specified. If the key does not exist in the AList, throw an exception and print an appropriate message.
UNION <result index> <first operand index> <second operand index> -- Create an AList that contains the union of the key/value pairs of the ALists specified by the two array operand indices. Put the resulting AList in the location specified by the "result index", overwriting any AList that might already be there. Recall that all keys in an AList must be unique. If both operand ALists contain values with the same key, then there are two special cases. If the values are the same, put only one copy in the result AList. If the values are different, throw an exception and do not modify the AList in the "result index".
INTERSECTION <result index> <first operand index> <second operand index> -- Create an AList that contains only those key/value pairs that occur in both the AList at the first operand index and the second operand index. Put the resulting AList in the location specified by the "result index", overwriting any AList that might already be there. If both operand ALists contain the same key but the values differ, throw an exception and do not modify the AList in the "result index".
DIFFERENCE <result index> <first operand index> <second operand index> -- Create an AList that contains only those key/value pairs that occur in the AList at the first operand index but not the AList at the second operand index. Put the resulting AList in the location specified by the "result index", overwriting whatever AList might already be there. Again, if the operand ALists both contain the same key but the values differ, throw an exception and do not modify the AList in the "result index".
PRINT <AList-array-index> -- Print all of the key/value pairs stored in the AList whose array index is specified in a proper and readable format.

Project 1 Questions (10 points)

In a file named proj1_questions.txt answer the following:

What is the worst can time complexity of each of the following operation:

Insert
Remove
intersection

To get full credit, you must justify each of your answers with an analysis of your code, creating a time equation and the resulting Big-Oh analysis.

Files to Be Submitted

Submit the following files:

build.xml
all your source code (including Proj1.java), your source code must be organized in the way that is consistent with your build file, otherwise it won’t compile and run
proj1_questions.txt containing your answers to the project question
README (optional)

You must use CVS to check out your module in the Proj1 repository and to check in your code. That must include an ant build.xml file and javadoc. See the projects page for more information on all of these topics. The repository location for this project is:

      /afs/umbc.edu/users/y/p/ypeng/pub/cs341s11/Proj1

If you don't submit a project correctly, you will not get credit for it. Why throw away all that hard work you did to write the project? Check your submittals. Make sure they work. Do this before the due date.