Please complete the steps to finish the project. Classes ArrayBag and LinkedBag have been completed. Please follow the outline and add the updated codes in the answer along with the output, thanks. (All code has been provided below and if possible please add comments in the client class along with the others) Sorry I couldn't paste all the code as text into this question.

====

ArrayBag.java

===========

LinkedBag.java

=========

Bag.Java

public 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); } =========

SinglyLinkedList.java

public class SinglyLinkedList { private static class Node{ private E element; private Node next;

public Node(E element, Node next) { this.element = element; this.next = next; }

public E getElement() { return element; }

public Node getNext() { return next; }

public void setNext(Node next) { this.next = next; } } private Node head=null; private Node tail=null; private int size=0; public SinglyLinkedList(){} public int size(){ return size; } public boolean isEmpty(){ return size==0; } public E first(){ if(isEmpty()) return null; return head.getElement(); } public E last(){ if(isEmpty())return null; return tail.getElement(); } public void addFirst(E e){ head=new Node(e,head); if(size==0) tail=head; size++; } public void addLast(E e){ Node newest=new Node(e,null); if(isEmpty()) head=newest; else tail.setNext(newest); tail=newest; size++; } public E removeFirst(){ if(isEmpty()) return null; E answer=head.getElement(); size--; if(size==0) tail=null; return answer; } public E remove(E e) { if (isEmpty()) return null;

if (head.getElement().equals(e)) { return removeFirst(); }

Node current = head; while (current.next != null) { if (current.next.getElement().equals(e)) { E result = current.next.getElement(); current.setNext(current.next.getNext()); size--; if (current.next == null) tail = current; return result; } current = current.getNext(); } return null; } public void clear() { head = null; tail = null; size = 0; }

public boolean contains(E e) { Node current = head; while (current != null) { if (current.getElement().equals(e)) return true; current = current.getNext(); } return false; } public E get(int i) { if (i = size) throw new IndexOutOfBoundsException("Index: " + i + ", Size: " + size);

Node current = head; for (int index = 0; index current = head; current != null; current = current.getNext()) { result[i++] = current.getElement(); } return result; }

}

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. Lab04LastFM 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