Here is my code and it is not working can you please help fix it. these are the
ID: 3798034 • Letter: H
Question
Here is my code and it is not working can you please help fix it. these are the output 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 109nanos 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.
import java.util.Random;
import java.util.Scanner;
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
/**
*
* @author Scott
*/
public class Fox_Project1 {
public static void main(String[] args) {
long squares;
long occurrances;
long size = 100000;
long time;
long time1;
long time2;
long time3;
long time4;
long time5;
Node<String> head = new Node<String>("Paul", null);
Node<String> tail = head.addNodeAfter("saul");
tail = tail.addNodeAfter("mauls");
tail = tail.addNodeAfter("sauls");
Node<String> head1 = new Node<String>("john", null);
Node<String> tail1 = head1.addNodeAfter("nathan");
tail = head.addNodeAfter("bill");
tail = head.addNodeAfter("ryan");
LinkedSequence list1 = new LinkedSequence<String>(head);
LinkedSequence list2 = new LinkedSequence<String>(head1);
LinkedSequence list3;
//cloning list2 to a blank list.
list3 = list2.clone();
tail1 = tail1.addNodeAfter("nick");
tail1 = tail1.addNodeAfter("aaron");
//displaying the lists
list1.displayList();
System.out.println(" ");
list1.addNodeAfter("bill");
list1.displayList();
System.out.println(" ");
list1.addNodeAfter("bob");
System.out.println(" ");
list1.displayList();
System.out.println(" ");
list1.addAll(list2);
System.out.println(" ");
list1.displayList();
System.out.println(" ");
list3.displayList();
System.out.println(" ");
//concatenating the lists.
LinkedSequence.concatanate(list3, list1).displayList();
long l1;
l1 = System.nanoTime();
time = l1;
//creating large linked lists with rectangle objects
Random ran = new Random();
Rectangle rec = new Rectangle(ran.nextInt(30) + 1, ran.nextInt(30) + 1);
Node<Rectangle> rhead = new Node<Rectangle>(rec, null);
LinkedSequence<Rectangle> seq = new LinkedSequence<Rectangle>(rhead);
seq.setCursor(rhead);
Node<Rectangle> rtail = new Node<Rectangle>(null, null);
seq.setTail(rtail);
for (int i = 0; i < size; i++) {
Rectangle rec1 = new Rectangle(ran.nextInt(30) + 1, ran.nextInt(30) + 1);
rtail = rhead.addNodeAfter(rec1);
seq.advance();
}
//completing step 5 with 10000 size list
time1 = System.nanoTime();
System.out.println("Step 5 took " + (time1 - time) / Math.pow(10, 9));
System.out.println(Node.listPosition(rhead, size).toString());
size = 1000000;
time2 = System.nanoTime();
for (int i = 0; i < size; i++) {
Rectangle rec1 = new Rectangle(ran.nextInt(30) + 1, ran.nextInt(30) + 1);
rtail = rhead.addNodeAfter(rec1);
seq.advance();
}
//completeing step 6 with 1000000 size list
time3 = System.nanoTime();
System.out.println("Step 6 took " + (time3 - time2) / Math.pow(10, 9));
System.out.println(Node.listPosition(rhead, size).toString());
time4 = System.nanoTime();
size = 10000000;
for (int i = 0; i < size; i++) {
Rectangle rec1 = new Rectangle(ran.nextInt(30) + 1, ran.nextInt(30) + 1);
rtail = rhead.addNodeAfter(rec1);
seq.advance();
}
//completeing final step.
time5 = System.nanoTime();
System.out.println("Step 7 took " + (time5 - time4) / Math.pow(10, 9));
System.out.println(Node.listPosition(head, size).toString());
int s = 10000000;
Rectangle[] rect = new Rectangle[s];
for (int i =0;i < size;i++){
rect[i] = seq.getCurrent();
seq.advance();
}
Rectangle target = new Rectangle(17,17);
System.out.println(seq.getCurrent());
System.out.println(counting(rect,target));
}
public static String counting(Rectangle[] boxes, Rectangle target) {
long count = 0;
long occur = 0;
for (int i = 1; i < boxes.length; i++) {
if (boxes[i].getLength() == boxes[i].getWidth()) {
count++;
}
}
for (int g = 0; g < boxes.length; g++) {
if (boxes[g] == target) {
occur++;
}
}
return count + " " + occur;
}
}
public class Node <T>
{
private T data;
private Node<T> link;
Node(T initialData, Node<T> initialLink){
this.data = initialData;
this.link = initialLink;
}
public Node<T> addNodeAfter(T element){
link = new Node<T>(element,link);
return link;
}
public void removeNodeAfter(Node head){
int x =0;
Node cursor;
cursor = head;
for (x = 1; x < listLength(head); x++) {
cursor = cursor.link;
}
cursor.data = null;
}
/*
*/
public String toString(int dum) {
String s1 = "";
String s2 = "";
if (data == null) {
s1 = "data: dummy";
} else {
s1 = "data: " + data.toString();
}
if (link == null) {
s2 = "link: null in tail";
} else {
s2 = "link: " + link.toString();
}
return s1 + " " + s2;
}
public String toString(){
String message = data.toString();
return message;
}
public static Node listCopy(Node source){
Node copyHead;
Node copyTail;
if(source == null){
return null;
}
copyHead = new Node(source.getData(), null);
copyTail = copyHead;
while(source.link != null){
source = source.link;
copyTail.addNodeAfter(source.data);
copyTail = copyTail.link;
}
return source;
}
public static Object listPosition(Node head, long position){
Node cursor;
int i = 1;
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.getData();
}
public static int listLength(Node head){
Node cursor;
int answer = 0;
for(cursor = head; cursor != null; cursor = cursor.link){
answer++;
}
return answer;
}
public static Node getTail(Node source){
int i;
Node cursor;
cursor = source;
for(i=1; i < listLength(source); i++){
cursor = cursor.link;
}
return cursor;
}
public void setLink(Node newLink){
link = newLink;
}
public void setData(T newData){
data = newData;
}
public T getData() {
return data;
}
public Node getLink() {
return link;
}
}
public class LinkedSequence<T> implements Cloneable{
private Node<T> head, tail, cursor, precursor;
private Node<T> dummy = new Node<T>(null,null);
private int manyNodes = 0;
public Node<T> getHead() {
return head;
}
public void setHead(Node<T> head) {
this.head = head;
}
public Node<T> getTail() {
return tail;
}
public void setTail(Node<T> tail) {
this.tail = tail;
}
public Node<T> getCursor() {
return cursor;
}
public void setCursor(Node<T> cursor) {
this.cursor = cursor;
}
public Node<T> getPrecursor() {
return precursor;
}
public void setPrecursor(Node<T> precursor) {
this.precursor = precursor;
}
public Node<T> getDummy() {
return dummy;
}
public void setDummy(Node<T> dummy) {
this.dummy = dummy;
}
public int getManyNodes() {
return manyNodes;
}
public void setManyNodes(int manyNodes) {
this.manyNodes = manyNodes;
}
public LinkedSequence(Node<T> h){
this.head = h;
head = tail;
dummy.setLink(head);
}
public Node<T> addNodeAfter(T data){
if (head == null) {
precursor = dummy;
head = dummy.addNodeAfter(data);
return cursor = head;
} else if (cursor == null) {
precursor = tail;
cursor = tail.addNodeAfter(data);
return cursor = tail;
} else {
precursor = cursor;
return cursor = cursor.addNodeAfter(data);
}
}
public Node<T> addBefore(T data)
{
if (precursor == null) {
head = new Node<T>(data, head);
return head = cursor;
} else {
precursor.setLink(dummy.addNodeAfter(data));
return cursor = precursor.getLink();
}
}//end addBefore method
public void addAll(LinkedSequence added)
{
if (added == null || added.head == null) {
return;
}
if (head == null) {
this.head = added.head;
this.tail = added.tail;
} else {
this.tail.setLink(added.head);
this.tail = added.tail;
}
}//end addAll method
public void advance()
{
if (isCurrent() && cursor != tail) {
precursor = cursor;
cursor = cursor.getLink();
} else if (!isCurrent()) {
precursor = dummy;
cursor = head;
} else {
precursor = tail;
cursor = null;
}
}//end else statement
public Node start()
{
cursor = head;
return null;
}
@Override
public LinkedSequence<T> clone()
{
LinkedSequence<T> copy = null;
try {
copy = (LinkedSequence<T>) super.clone();
} catch (CloneNotSupportedException ex) {
System.out.println("CloneNotSupportedException");
}
copy.head = Node.listCopy(head);
copy.tail = Node.getTail(head);
return copy;
}
public static <T> LinkedSequence<T> concatanate(LinkedSequence<T> s1, LinkedSequence<T> s2)
{
LinkedSequence<T> s3 = new LinkedSequence(null);
if((s1 == null)||(s2 == null))
{
throw new NullPointerException("Can not have an empty list.");
}
else
{
s3.head = Node.listCopy(s1.head);
s3.tail = Node.getTail(s2.head);
return s3;
}
}
public Node<T> removeCurrent(Node head)
{
if (!isCurrent()){
return null;
}
if (cursor == null);
{
cursor.setLink(cursor.getLink().getLink());
}
return head;
}
public void displayList(){
System.out.println(head.toString());
}
public String displayList(int count){
String indentation = "";
for (int i = 1;i<count;i++){
indentation += " ";
}
return "data: " + head + " " + indentation +"link: " + cursor; // Final value of toString method
}
// added methid to help with the advance method and remove current, checks current value
public boolean isCurrent() {
if (cursor != null) {
return false;
} else {
return true;
}
}
public T getCurrent(){
if (!isCurrent()|| cursor == null){
return cursor.getData();
}
else {
return cursor.getData();
}
}
}
public class Rectangle {
private int width;
private int length;
public Rectangle(int w, int l){
this.length = l;
this.width = w;
}
/**
*
* @param Rect1
* @param Rect2
* @return
*/
public boolean equals(Rectangle Rect1,Rectangle Rect2){
if (Rect1.length == Rect2.length){
if (Rect1.width==Rect2.width){
return true;
}
}
return false;
}
@Override
public String toString(){
String message = "";
message = "width = " + width + " Length = " + length;
return message;
}
public int getWidth() {
return width;
}
public void setWidth(int width) {
this.width = width;
}
public int getLength() {
return length;
}
public void setLength(int length) {
this.length = length;
}
}
Explanation / Answer
Hello... Fixed the bugs in your code to get it to work. By the way , step 4 above only tells you need to count all squares of size 15 and not a matching object instance. So we need to just need to compare the rectangle dimensions (as imlemented in Rectangle.equals()) and count if matched. But just in case you need a function to count no. of object instances (matching the exact object itself and not the dimensions), I have implemented a function getOccurences() which can be used.
Also since the size 10000000 is too large, the program goes out of memory for that size. So to increase heap size in java , you may want to follow http://www.wikihow.com/Increase-Java-Memory-in-Windows-7
A sample run of the program is attached. Please do rate the answer if it helped you. Thanks.
=========
Node.java
----------
public class Node<T> {
private T data;
private Node<T> link;
public Node(T initialData, Node<T> initialLink) {
this.data = initialData;
this.link = initialLink;
}
public Node<T> addNodeAfter(T element) {
link = new Node<T>(element, null);
return link;
}
/*
*/
public String toString(int dum) {
String s1 = "";
String s2 = "";
if (data == null) {
s1 = "data: dummy";
} else {
s1 = "data: " + data.toString();
}
if (link == null) {
s2 = "link: null in tail";
} else {
s2 = "link: " + link.toString(dum);
}
return s1 + " " + s2;
}
public String toString() {
String message = data.toString();
return message;
}
public static Node listCopy(Node source) {
Node copyHead;
Node copyTail;
if (source == null) {
return null;
}
copyHead = new Node(source.getData(), null);
copyTail = copyHead;
while (source.link != null) {
source = source.link;
copyTail=copyTail.addNodeAfter(source.data);
}
return source;
}
public static Object listPosition(Node head, long position) {
Node cursor;
int i = 1;
if (position <= 0) {
throw new IllegalArgumentException("position is not positive.");
}
if(head==null)
return null;
cursor = head;
for (i = 1; (i < position) && (cursor != null); i++) {
cursor = cursor.link;
}
if(cursor!=null)
return cursor.getData();
else
return null;
}
public static int listLength(Node head) {
Node cursor;
int answer = 0;
if(head==null) return 0;
for (cursor = head; cursor != null; cursor = cursor.link) {
answer++;
}
return answer;
}
public static Node getTail(Node source) {
Node cursor=source;
while(cursor.link!=null)
cursor=cursor.link;
return cursor;
}
public void setLink(Node newLink) {
link = newLink;
}
public void setData(T newData) {
data = newData;
}
public T getData() {
return data;
}
public Node getLink() {
return link;
}
}
----------------
LinkedSequence.java
---------
public class LinkedSequence<T> implements Cloneable {
private Node<T> head, tail, cursor, precursor;
private Node<T> dummy = new Node<T>(null, null);
private int manyNodes = 0;
public Node<T> getHead() {
return head;
}
public void setHead(Node<T> head) {
this.head = head;
}
public Node<T> getTail() {
return tail;
}
public void setTail(Node<T> tail) {
this.tail = tail;
}
public Node<T> getCursor() {
return cursor;
}
public void setCursor(Node<T> cursor) {
this.cursor = cursor;
}
public Node<T> getPrecursor() {
return precursor;
}
public void setPrecursor(Node<T> precursor) {
this.precursor = precursor;
}
public Node<T> getDummy() {
return dummy;
}
public void setDummy(Node<T> dummy) {
this.dummy = dummy;
}
public int getManyNodes() {
return manyNodes;
}
public LinkedSequence(Node<T> h) {
this.head = h;
tail = head;
cursor=tail;
dummy.setLink(head);
precursor=dummy;
}
// add a node to the end of list
public Node<T> addNode(T data) {
if (head == null) {
head = tail = new Node<T>(data, null);
dummy.setLink(head);
precursor=dummy;
} else {
tail = tail.addNodeAfter(data);
precursor=cursor;
}
manyNodes++;
cursor = tail;
return tail;
}
public void addAll(LinkedSequence<T> added) {
if (added == null || added.head == null) {
return;
}
for (Node<T> h = added.head; h != null; h = h.getLink()) {
addNode(h.getData());
}
}// end addAll method
public Node advance() {
if(cursor!=null)
{
precursor=cursor;
cursor=cursor.getLink();
}
return cursor;
}// end else statement
public Node start() {
precursor = dummy;
cursor = head;
return cursor;
}
@Override
public LinkedSequence<T> clone() {
LinkedSequence<T> copy = new LinkedSequence<T>(null);
copy.addAll(this);
return copy;
}
public static <T> LinkedSequence<T> concatanate(LinkedSequence<T> s1, LinkedSequence<T> s2) {
LinkedSequence<T> s3 = new LinkedSequence(null);
if ((s1 == null) || (s2 == null)) {
throw new NullPointerException("Can not have an empty list.");
} else {
s3.addAll(s1);
s3.addAll(s2);
return s3;
}
}
public void displayList() {
System.out.println(head.toString(0));
}
public String displayList(int count) {
String indentation = "";
for (int i = 1; i < count; i++) {
indentation += " ";
}
return "data: " + head + " " + indentation + "link: " + cursor; // Final
// value
// of
// toString
// method
}
// added methid to help with the advance method and remove current, checks
// current value
public boolean isCurrent() {
if (cursor != null) {
return false;
} else {
return true;
}
}
public Node<T> listPostion() {
return cursor;
}
}
--------------
Rectangle.java
----------
public class Rectangle {
private int width;
private int length;
public Rectangle(int w, int l) {
this.length = l;
this.width = w;
}
/**
*
* @param Rect1
* @param Rect2
* @return
*/
public boolean equals( Rectangle Rect2) {
if(Rect2==null) return false;
if ( length == Rect2.length) {
if (width == Rect2.width) {
return true;
}
}
return false;
}
@Override
public String toString() {
String message = "";
message = "width = " + width + " , length = " + length;
return message;
}
public int getWidth() {
return width;
}
public void setWidth(int width) {
this.width = width;
}
public int getLength() {
return length;
}
public void setLength(int length) {
this.length = length;
}
}
---------------
Fox_Project1.java
--------------
import java.util.Random;
import java.util.Scanner;
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
/**
*
* @author Scott
*/
public class Fox_Project1 {
public static void main(String[] args) {
long squares;
long occurrances;
int size[] = {10000,1000000,10000000};
double time1, time2;
String names1[]={"Paul","saul","mauls","sauls"};
LinkedSequence<String> list1=new LinkedSequence<>(null);
for(int i=0;i<names1.length;i++)
list1.addNode(names1[i]);
String names2[]={"john","nathan","bill","ryan"};
LinkedSequence<String> list2=new LinkedSequence<>(null);
for(int i=0;i<names2.length;i++)
list2.addNode(names2[i]);
System.out.println("list1 contains");
list1.displayList();
System.out.println("list2 contains");
list2.displayList();
LinkedSequence list3;
// cloning list2 to a blank list.
list3 = list2.clone();
System.out.println("Adding nick aaron to list1");
list1.addNode("nick");
list1.addNode("aaron");
// displaying the lists
list1.displayList();
System.out.println(" Adding bill to list1");
list1.addNode("bill");
list1.displayList();
System.out.println(" Adding bob to list1");
list1.addNode("bob");
System.out.println(" List1 contains");
list1.displayList();
System.out.println(" Adding list2 to list1");
list1.addAll(list2);
System.out.println(" list1 contains");
list1.displayList();
System.out.println(" the clone list3 contains");
list3.displayList();
System.out.println(" Concatenating list3 and list1");
// concatenating the lists.
LinkedSequence.concatanate(list3, list1).displayList();
Random ran = new Random();
double totalTime,elapsed;
//create and record times for sequence of different sizes , repeat steps in for loop for different sizes
for(int j=0;j<size.length;j++)
{
totalTime=0;
System.out.println("Creating sequence with size="+size[j]);
time1= System.nanoTime();
// creating large linked lists with rectangle objects
LinkedSequence<Rectangle> seq = new LinkedSequence<Rectangle>(null);
for (int i = 0; i < size[j]; i++) {
Rectangle rec1 = new Rectangle(ran.nextInt(30) + 1, ran.nextInt(30) + 1);
seq.addNode(rec1);
}
// completing step 1
time2 = System.nanoTime();
elapsed=(time2 - time1) / Math.pow(10, 9);
totalTime+=elapsed;
System.out.println("Step 1 creating list with (size="+size[j]+") took " +elapsed +"seconds");
System.out.println("listPosition()="+seq.listPostion().toString());
System.err.println("tail = "+seq.getTail().toString());
time1 = System.nanoTime();
//step 3 instantiate a rectangle array and load it from list
Rectangle rectArray[]=new Rectangle[size[j]];
Node<Rectangle> r=seq.getHead();
for(int k=0;r!=null;r=r.getLink(),k++)
rectArray[k]=r.getData();
time2 = System.nanoTime();
elapsed=(time2 - time1) / Math.pow(10, 9);
totalTime+=elapsed;
System.out.println("Step 3 Loading rectangle array (size="+size[j]+") took " + elapsed+"seconds");
//step4 creating a rectangle with size 15,15 and call count to count them in the array
time1=System.nanoTime();
Rectangle square=new Rectangle(15,15);
int c=count(rectArray,square);
time2=System.nanoTime();
elapsed=(time2 - time1) / Math.pow(10, 9);
totalTime+=elapsed;
System.out.println("Step 4 Counting squares of size 15 took " + elapsed+"seconds");
System.out.println("There are "+c+" recantagles matching"+square.toString());
System.out.println(" Total time for all steps ="+totalTime+"seconds");
for(int i=0;i<rectArray.length;i++)
rectArray[i]=null;
}
}
//counts how many times the rectangles matching the target rectangle dimensions exist in the array
public static int count(Rectangle[] boxes, Rectangle target) {
int count = 0;
for (int i = 0; i < boxes.length; i++) {
if (boxes[i].equals(target)) {
//matched both length and width of current rectangle with target rectangle
count++;
}
}
return count;
}
//get all occurences of the target
public static int getOccurences(Rectangle[] boxes, Rectangle target) {
int count = 0;
for (int i = 0; i < boxes.length; i++) {
if (boxes[i]==target) { //compare object ids i.e. hashcode
count++;
}
}
return count;
}
}
-------------
sample output
-----------
list1 contains
data: Paul
link: data: saul
link: data: mauls
link: data: sauls
link: null in tail
list2 contains
data: john
link: data: nathan
link: data: bill
link: data: ryan
link: null in tail
Adding nick aaron to list1
data: Paul
link: data: saul
link: data: mauls
link: data: sauls
link: data: nick
link: data: aaron
link: null in tail
Adding bill to list1
data: Paul
link: data: saul
link: data: mauls
link: data: sauls
link: data: nick
link: data: aaron
link: data: bill
link: null in tail
Adding bob to list1
List1 contains
data: Paul
link: data: saul
link: data: mauls
link: data: sauls
link: data: nick
link: data: aaron
link: data: bill
link: data: bob
link: null in tail
Adding list2 to list1
list1 contains
data: Paul
link: data: saul
link: data: mauls
link: data: sauls
link: data: nick
link: data: aaron
link: data: bill
link: data: bob
link: data: john
link: data: nathan
link: data: bill
link: data: ryan
link: null in tail
the clone list3 contains
data: john
link: data: nathan
link: data: bill
link: data: ryan
link: null in tail
Concatenating list3 and list1
data: john
link: data: nathan
link: data: bill
link: data: ryan
link: data: Paul
link: data: saul
link: data: mauls
link: data: sauls
link: data: nick
link: data: aaron
link: data: bill
link: data: bob
link: data: john
link: data: nathan
link: data: bill
link: data: ryan
link: null in tail
Creating sequence with size=10000
Step 1 creating list with (size=10000) took 0.011248945seconds
listPosition()=width = 3,length = 5
tail = width = 3,length = 5
Step 3 Loading rectangle array (size=10000) took 0.016091779seconds
Step 4 Counting squares of size 15 took 7.00982E-4seconds
There are 14 recantagles matchingwidth = 15,length = 15
Total time for all steps =0.028041706seconds
Creating sequence with size=1000000
Step 1 creating list with (size=1000000) took 0.719080433seconds
tail = width = 27,length = 14listPosition()=width = 27,length = 14
Step 3 Loading rectangle array (size=1000000) took 0.020177905seconds
Step 4 Counting squares of size 15 took 0.016526348seconds
There are 1160 recantagles matchingwidth = 15,length = 15
Total time for all steps =0.755784686seconds
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.