Please help me with this project!!! It is due tomorrow :(

I am using the book Data structures & other objects using Java.

I provide the name of the book in case if you need it, but I provide all the methods that as in the book.

Please help me, I get trouble with doing it.

Introduction - The Problem

In this project, your program demonstrates two applications of the linked list based sequence ADT. The first stores Rectangle objects, the second stores String objects. Your program must test all the sequence operations at least in one of the two data structures created. The rectangle objects are created and added to the list with random field values, the string objects (names) you choose directly or read them from a file you create for input, or you may generate names randomly, too. Must document your choice. Design, Implementation The implementation of the data structure ADT will be based on two user defined classes: Node and LinkedSequence, both generic. A Rectangle class must also be added to project, since in one of the applications the stored data are Rectangle objects. The other application utilizes the String class from the Java library. For testing purposes two more classes will be needed: TestNode to test the Node class methods, and LinkedApplications to use the data structure. 1. The Rectangle class (not generic) has two fields named width and length, both of type int. You may use package access to the fields. The class has:

a constructor taking two parameters to initialize the fields

a toString( ) method which returns a String message that specifies the data field values an equals( ) method which returns true if each of the corresponding field values are equal in two given rectangles

2. Node

This class is generic, yet as for a template, you are advised to study the IntNodeClass specifications (pp 208-211, Figure 4.11 in Ch 4) in the book, as well as the implementations in the previous sections and on pages 212-214. As for a generic Node class there are some hints in the book on pages 283-285 (Sec 5.4 in Ch 5). Our Node class is similar but not identical to the template. We may discard or modify some methods and we may include new methods which are practical in our applications. Partial class documentation: Fields: as usual, but with the generic type parameter

Constructor: takes two parameters to initialize the fields Instance methods

addNodeAfter() as in the book, but not void, returns the link it creates.

public addNodeAfter(int element){

link= new Node (element, link);

return link;

}

removeNodeAfter() as in the book, but returns the link it creates (that is, the node after the removed element) :

public void removeNodeAfter(){

link= link.link;

return link;

}

toString() creates and returns a string message which reveals the stored value (data) but not the link (this method is not recursive)

toString(int dum) creates and returns a string message which reveals the stored value (data) and the links (recursive). This method is applicable for shorter lists only. Static methods

listCopy() as in the book, but, since our addNodeAfter( ) returns the link, you should assign the return value directly to copyTail . That is, combine the two copyTail statements of the while loop in one statement, see the slide from the lecture.

public static Node listCopy(Node source){

Node copyHead;

Node copyTail;

if ( source == null )

return null;

copyHead = new IntNode( source.data, null );

copyTail = copyHead;

while ( source.link != null ) {

source = source.link;

copyTail = copyTail.addNodeAfter( source.data );

}

return copyHead;

}

listPosition() as in the book

public static Node listPosition(Node head, int position){

Node cursor;

int i;

if ( position <= 0 )

throw new IllegalArgumentException( "position is not positive");

cursor = head;

for ( i = 1; ( i < position ) && ( cursor != null ); i++ )

cursor = cursor.link;

return cursor;

}

listLength()as in the book

public static int listLength(Node head){

Node cursor;

int answer;

answer= 0;

for(cursor= head; cursor != null; cursor = cursor.link){

answer++;

return answer;

}

}

getTail() This is a new method! Starting at a node given as the parameter, the method iterates through the list until arrives at the tail, then it returns the tail. The iteration is the same as in the listCopy method. This method helps to maintain the tail reference, and combined with the listCopy method, the listCopyWithTail becomes superfluous

listCopyWithTail() omitted listPart() omitted

listSearch()omitted

3. LinkedSequence

This class is also implemented as a generic class. The specification of a nongeneric DoubleLinkedSeq class is fairly well detailed in your reading, pp 232 238, it helps to design the generic class. It is a marked difference that the book does not apply a dummy node. Also, the LinkedBag implementation in the book can be helpful, but the analogy is rather weak. Fields

The field manyNodes is optional. It can be convenient to have direct access to the size of the sequence, but this variable needs careful update in each method that manipulates the size, and this can be a source of errors. For instance, the removeNodeAfter() method changes the size most of the time, but there is no change when tail is the reference. The listLength() method of the Node class makes the field dispensable, but the length algorithm is O(n). There are five private variables of type Node:

head

tail

cursor

precursor

dummy The LinkedSequence invariant

For your convenience the invariant as part of the class documentation is supplied. When you design and implement the methods, it is important that you pay attention to the invariant. 1. manyNodes is the number of nodes in the sequence; in particular the value is 0 for an empty sequence

2. For a non-empty sequence head is the reference to the first, and tail is a reference to the last node of the sequence; for an empty sequence head and tail are null

3. For a non-empty sequence cursor can be a reference to any of the nodes of the sequence, it cannot reference dummy. The cursor can be null; for an empty sequence cursor is null

4. If cursor is not null, precursor is a reference to a node such that cursor is precursor.link. If cursor is null, precursor is null; in particular precursor does not reference tail 5. dummy is a node reference and it is never null (dummy is not an element of the sequence); dummy.link is always head (null or not). If cursor is the head, then precursor is dummy Methods and Constructors All the fields except dummy require accessor and mutator methods. You should instantiate dummy at the declaration with two null parameters. Constructor

Takes one node parameter to initialize the head. To initialize tail, head is assigned. Assigns dummys link the head (setLink() must be used). Note that dummy does not store any info data but null, and it is not part of the data structure. Its link is always the head, see that ADT invariant.

Instance Methods addAfter( ) Takes a parameter for the new data value to be added to the structure and returns the currently added node. Cursor reference is always updated to the added node. A call to the addNodeAfter method of the Node class shall add the new node to the list

(i) after dummy if head is null

(ii) after tail if cursor is null but head is not

(iii) after cursor if cursor is not null Build the selection logic carefully and update the relevant fields as necessary addBefore( ) Takes a parameter for the new data value to be stored in the structure and returns the currently added node. Cursor reference is always updated to the added node. A call to the addNodeAfter method of the Node class shall add the new node to the list

(i) after dummy if precursor is null

(ii)after precursor if precursor is not null addAll( )Takes another linked sequence for parameter (other) and joins the parameter list to this list after this tail. If the parameter is null or empty, the method returns. Otherwise, if the calling list is empty (head is null) this head assigned other head and this tail assigned other tail; else tail link assigned other head and tail assigned other tail. advance() advances the cursor forward one step, if the cursor is not null and not the tail; precursor is updated accordingly. Null cursor is advanced to head, tail cursor advanced to null. start() if the sequence is empty, the method returns; otherwise assigns cursor the head and precursor the dummy clone( ) Returns a copy of the calling sequence. See the specifications in the book. concatenate( ) static method; takes two linked sequence parameters and creates a third sequence by adding the second after the first. You have to use the listCopy( ) and getTail( ) static methods from Node. Do not use listCopyWithTail( ).

removeCurrent() removes the cursor if cursor is not null and returns the removed node. The new cursor is the following node if there is one, and precursor updated accordingly. If tail was removed, the new new cursor is head if there is head, if so precursor is dummy. If cursor is null, the method returns null.

displayList( ) convenience method. Prints all the nodes to the console; use the toString( ) call with respect to head for the recursive version and run a loop for the non-recursive version. 4. TestNode Create three-node long list(s) of String type and test all the Node methods. This part of the Project is an extension of HW 4, you may use your code from that assignment.

5. LinkedApplications Requirements

Create short (three to five long) String type linked list to test all the methods.

The displayList( ) method must be tested on Rectangle type list

Add two static fields of type long to the application class named squares and occurrences

Add a static void method named counting to the applications class. The method takes a Rectangle array named boxes and a Rectangle object named target for parameters.

The method counts the number of squares among the array element, and stores the value in the squares field, and it also counts the number of array elements that are equal to the target and stores the result in the occurrences field.

Step 1: Create a LinkedSequence of 100 000 Rectangle objects each having integer dimensions randomly selected between 1 and 30. Step 2: Verify that the listPosition() method returns the tail reference for position number 100 000.

Step 3: instantiate a Rectangle array to the list length (do not use literals) and load the Rectangles from the list to the array.

Step 4: Create a target Rectangle with side 15, 15 and call the counting method passing your array and target as parameters.

Step 5: Measure the running time of each step above as well as the combined time and record the results. Hint: use the method call System.nanoTime() to record the current real time in nanoseconds (the return type of the method is long); note that 109 nanos make one second.

Step 6: Repeat Steps 1- 5 for 1 000 000 Rectangle objects

Step 7: Repeat Steps 1 5. 10 000 000 Rectangle objects.

Step 8: Repeat Step 7 by adding the non-random target rectangle of step 4 to the empty list 10 000 000 times. Check out if the random selection in step 7 is a significant overhead for the running time of the algorithm or not. Analyze your running time observations, deduce Big-Oh estimates and advise about the expected time for the case of 100 000 000 rectangles. Attach your report as a comment to the source code following the application class.

Documentation:

Each method in Node and LinkedSequence must be fully documented (specification). You may use the assignment description itself as a help to compile the specifications.