Use the given codes below ArrayBag,LinkedBag,Bag and SinglyLinkedList to complete these tasks. Create a client class that fulfills the instructions below and uses the codes given. If any codes need to be changed you may alter them. Please provide an output and updated answers to all the codes when completed. (Follow instructions below) ====

ArrayBag.java

public class ArrayBag implements Bag { private E[] list; private int numberOfEntries; private static final int DEFAULT_CAPACITY = 25; public ArrayBag() { this(DEFAULT_CAPACITY); }

@SuppressWarnings("unchecked") public ArrayBag(int initialCapacity) { numberOfEntries = 0; list = (E[]) new Object[initialCapacity]; } public int getCurrentSize() { return numberOfEntries; }

@Override public boolean isEmpty() { return numberOfEntries == 0; }

@Override public void add(E newEntry) { if (numberOfEntries == list.length) { list = Arrays.copyOf(list, 2 * list.length); } list[numberOfEntries++] = newEntry; }

@Override public E remove() { return removeTest(); }

@Override public E remove(E anEntry) { int index = getIndexOf(anEntry); E removed = removeEntry(index); return removed; }

private int getIndexOf(E anEntry) { int where = -1; boolean stillLooking = true; int index = 0; while (stillLooking && (index

private E removeEntry(int givenIndex) { E result = null; if (!isEmpty() && (givenIndex >= 0)) { result = list[givenIndex]; numberOfEntries--; list[givenIndex] = list[numberOfEntries]; list[numberOfEntries] = null; } return result; } public void addTest(E newEntry) { if (numberOfEntries == list.length) { list = Arrays.copyOf(list, 2 * list.length); } list[numberOfEntries] = newEntry; numberOfEntries++; }

public E removeTest() { if (numberOfEntries == 0) { return null; } numberOfEntries--; E removed = list[numberOfEntries]; list[numberOfEntries] = null; return removed; } } =======

LinkedBag.java

public class LinkedBag implements Bag { private Node head; private int numberOfEntries;

public LinkedBag() { head = null; numberOfEntries = 0; }

public int getCurrentSize() { return numberOfEntries; }

public boolean isEmpty() { return numberOfEntries == 0; }

public void add(E newEntry) { Node newNode = new Node(newEntry); newNode.next = head; head = newNode; numberOfEntries++; }

public E remove() { E result = null; if (head != null) { result = head.data; head = head.next; numberOfEntries--; } return result; }

public E remove(E anEntry) { Node currentNode = head; E result = null; int index = 0; while (currentNode != null) { if (currentNode.data.equals(anEntry)) { result = currentNode.data; removeNode(index); break; } currentNode = currentNode.next; index++; } return result; }

private void removeNode(int index) { if (index == 0) { head = head.next; } else { Node nodeBefore = getNodeAt(index - 1); Node nodeToRemove = nodeBefore.next; nodeBefore.next = nodeToRemove.next; } numberOfEntries--; }

private Node getNodeAt(int index) { Node currentNode = head; for (int i = 0; i

public void addTest(E newEntry) { Node newNode = new Node(newEntry); if (head == null) { head = newNode; } else { Node currentNode = head; while (currentNode.next != null) { currentNode = currentNode.next; } currentNode.next = newNode; } numberOfEntries++; }

public E removeTest() { E result = null; if (head != null) { Node currentNode = head; Node previousNode = null; while (currentNode.next != null) { previousNode = currentNode; currentNode = currentNode.next; } result = currentNode.data; if (previousNode == null) { head = null; } else { previousNode.next = null; } numberOfEntries--; } return result; }

private static class Node { private E data; private Node next;

private Node(E data) { this.data = data; next = null; } } } =======

Bag.Java

=======

SinglyLinkedList.java

Restrictions: You cannot use any predefined Java classes in writing this lab. You CAN import the java.util.Random class. All output in this assignment must use the printf method. System.out.print and System.out.println cannot be used. You must use the System.out.printf method for all output. Create a NetBeans project using the standard naming convention, i.e. Lab04- LastFM and save it to a location like the desktop or your flash drive. In the project you will do the following: Copy the following classes from your Lab103 assignment into the source code directory for this assignment: - Bag - ArrayBag - LinkedBag - SinglyLinkedList If your Lab103 assignment is incomplete and/or incorrect you need to, at a minimum, correctly complete the methods needed for this this assignment. In this assignment you are going to try and measure the speed differences between an array-based structure and a linked-based structure. You will use your ArrayBag and LinkedBag for these measurements. You want to be careful that features like the ArrayBag automatically expanding when it needs more space or the ArrayBag shifting items to the left to fill in empty gaps do not impact the measurements. You also do not want to traverse the LinkedBag looking for an item to remove. To avoid these problems, add the following methods to your ArrayBag and/or LinkedBag classes: To the ArrayBag class add: public void addTest( E e ) this method adds to the end of the array. public E removeTest() this method removes the last item at the end of the array. Note that by adding and removing from the end of the array no left-shifting of values will be needed. To the LinkedBag class add: public void addTest( E e ) this method adds to the head of the linkedList public E removeTest( ) this method removes from the head of the linkedList Note by adding and removing from the head of the linkedList it will not be necessary to traverse the list. If you implement the above methods correctly they should all have O(1) performance. Note that these are methods for your ArrayBag and LinkedBag classes. You should not make any changes to the SinglyLinkedList class. Of course, the methods for the LinkedBag class will still need to call the corresponding methods in the SinglyLinkedList class. Write a Client program that does that tests the ArrayBag and LinkedBag as following: - For each structure: - Perform a timing test for each of these data structures. - Each timing test should measure how long it takes to add N Integers to the structure and then remove N integers from the structure. - Time measurements should be made in milliseconds. - A time measurement should include how long it takes to both add all N values to the structure and then remove all N values from the structure. - N should vary from 10 to 100,000,000 increasing N by a factor of 10 for each test. - Depending on your system you may run out of memory before you reach the maximum value of N. - If you run out of memory, just drop the maximum value of N by a factor of 10 until your program runs successfully. - For each timing test start with a new, empty data structure. - The overload constructor should be called when creating the ArrayBag instance and passed a value of N for that test. This will keep the ArrayBag from having to expand the size of its array during the test. - You must store your test results in a two-dimensional array. - Test results must be displayed in a nicely formatted ASCIl table similar to the examples provided at the end of the assignment. - For the ASCII table: - You must create a method that prints the ASCIl table. - This method should be passed a two-dimensional array that holds the values to be printed. - Each cell is delimited by the vertical pipe symbol 'l' - Values in each cell are padded by 2 blank spaces - Numerical values use the comma thousand separator, e.g. 1,234,567 - Each column is just wide enough to display the widest entry in that column including the cell padding. - There is a separator line between each row of values. - This separator line is also printed at the top and the bottom of the table. - Note that the ' + ' plus symbols in the separator line, align with the vertical pipe symbols in the value rows. - This table can be a static table, i.e. the column widths do not have to automatically adjust to the values being printed. - Future assignments may require that you make the ASCII table dynamic. - An example of the ASCII table for this assignment is given at the end of this assignment. Example of the ASCII table. - Note that the values line up in a tabular format. - You will need to change your font in your windows document to a non-proportional font, e.g. Courier New. ablic interface Bag { int size (); boolean isEmpty (); void clear(); int getFrequencyof (E e); boolean contains (E e); void add (E e); E remove (E e); E remove (); E get (int i); String tostring (); boolean equals(Object o); Source History size=0; \}