Overview: IN JAVA

For this project you will be designing a new data structure called an Array2D. This is a linked type data structure version of a 2D array. The Array2D can support any combination of dimensions (n x n, n x m, or m x n, where n > m) This data structure has a singly linked system which allows you to traverse the array in multiple directions in addition to allowing you to retrieve specific rows and columns. The following diagram gives a rough visual of what this data structure looks like:

Array2DNode ADT:

This is a generic class and must be implemented accordingly.

Data Fields:

item: store the data here. This data field is private and should have an appropriate getter and setter.

down and right: these are your directional pointers to traverse your data structure. These pointers each point to the next node in sequence. If there is no node in a direction, the value of that pointer should benull. These data fields should be protected in order to make accessing them from the Array2D class easier. These data fields should NOT have a getter or setter.

No other data fields are allowed.

Constructor:

Array2DNode(): Default constructor which takes no parameters.

Array2DNode(item): Constructor which takes an item of any type and initializes the item data field.

No other constructors are allowed.

Array2D ADT:

This is a generic class and must be implemented accordingly.

Data Fields (All data fields are private):

rows: the number of rows.

cols: the number of columns.

head: this is a Array2DNode pointer, which points to the node at position (0,0) in the array.

No other data fields are allowed.

Constructors:

Array2D(): Default constructor which has 0 rows and 0 cols.

Array2D(int rows, int cols): a constructor which takes the initial number of rows and columns of the Array2D. This constructor needs to initialize the Array2D with linked nodes (which are initially empty).

Example if I invoked the constructor with new Array2D(2, 3), then I would have to initialize my Array2D with something that would have a structure like the picture above but with no values stored in the nodes.

Array2D(array[][]): Constructor which takes a normal 2D array as an argument. This is the ONLY place you can use an 2D array and this 2D array is only used to initialize the values of your Array2D object. The parameter 2D array must remain as a local variable and is not allowed to be stored as a data field. NOTE: You may pass the parameter 2D array to another helper function, but the 2D array cannot be stored as a data field in the Array2D Class.

No other constructors are allowed.

Public Functions:

NOTE 1: For any function which requires the use of an input row or col, you must check to make sure the values are in bounds. If not, your program must throw an IndexOutOfBounds exception.

NOTE 2: Functions in green are for the 5 point version and are optional for the 4 point version.

NOTE 3: All of the following functions should be public.

addFirstCol(): Adds a new column to the beginning of the list.

addFirstRow(): Adds a new row to the beginning of the list.

addLastCol(): Adds a new column to the end of the list.

addLastRow(): Adds a new column to the end of the list.

addCol(index): Inserts a column at the given index. (Insert here means the columns shift over by 1 from the insertion point onward).

addRow(index): Inserts a row at the given index. (Insert here means the rows shift over by 1 from the insertion point onward).

deleteFirstCol(): Removes the first column.

deleteFirstRow(): Removes the first row.

deleteLastCol(): Removes the last column.

deleteLastRow(): Removes the last row.

deleteCol(index): Removes the column at the given index.

deleteRow(index): Removes the row at the given index.

get(row, col): Returns the item at the given (row, col). NOTE: You must return the item stored in the Array2DNode, NOT the Array2DNode itself.

getCol(col): Returns the Array2DNode that starts the beginning of the requested column.

getRow(row): Returns the Array2DNode that starts the beginning of the requested row.

set(row, col, item): Assigns the given item to the Array2DNode at position (row, col).

colSize(): Returns the number of columns.

rowSize(): Returns the number of rows.

No other public functions are allowed.

Private Functions:

You may implement any other private functions you feel are necessary to help you implement the above constructors / public functions.

If you are unsure whether a private function will violate the requirements for this assignment, be sure to ask me.

Additional Requirements:

This data structure is zero-indexed.

Your classes should be written in a package called array2d.

Your data structure must be designed with generics.

Your data structure must include the required functionality and names cannot be changed.

When I test your data structure, I will have my own main method. If you change the names of the public interface then your code will not compile with mine.

You are NOT allowed to use any other data structures in the implementation of your Array2D. This includes but is not limited to arrays, 2D arrays, arraylists, and so on. The point is to create a new data structure. If you are unsure of something feel free to ask. NOTE: The only place you may use a 2D Array is in the methods where it is specifically required. You will receive no credit for the assignment for not following this requirement.

You may not use a tail pointer for this assignment. I want you to practice traversing the 2D array using pointer hopping.

You must use pointer hopping to traverse your data structure.

Deliverables:

The source code for your Array2DNode and Array2D classes. Do not zip these files, upload them separately.

The source code for your Tester class which demonstrates ALL functionality of your code.