Your task is to implement the three new methods in the LinkedBag class so that they work as described. The interface is available in file BagInterface.java. The LinkedBag class (without the new methods) is available in file LinkedBag.java. Test your implementation with the main program CS445Rec2.java. The output contents should match that shown in Rec2Out.txt. Note, however, that within any bag the order of the data does not matter so if you bags show the contents in a different order that does not necessarily mean that they are incorrect.

Hints:

You will need to iterate through the contents of one or perhaps both of your LinkedBag objects to implement these methods. This can be done by accessing the underlying linked lists in a loop.

The argument bag for each of these methods will be passed in via a BagInterface parameter. This parameter type will restrict access to the methods in BagInterface and will not allow direct access of the underlying linked list. To get this access (if you need it) you will need to cast the parameter to type (LinkedBag) .

BagInterface.java

CS445Rec2.java

LinkedBag.java

Output:

Bag 1 contains: Inigo Buttercup Fezzik Westley

Bag 2 contains: Inigo Fezzik Vizzini Humperdinck Rugen

Bag 3 contains: Rugen Humperdinck Vizzini Fezzik Inigo Westley Fezzik Buttercup Inigo

Bag 4 contains: Fezzik Inigo

Bag 5 contains: Buttercup Westley

Bag 6 contains: Vizzini Humperdinck Rugen

Bag 7 contains: Westley Fezzik Buttercup Inigo Inigo Buttercup Fezzik Westley Inigo Fezzik Vizzini Humperdinck Rugen

Bag 8 contains: Fezzik Inigo Westley Fezzik Buttercup Inigo Inigo Buttercup Fezzik Westley

Bag 9 contains: Westley Fezzik Buttercup Inigo

import java.util.*; public class CS445Rec2 public static void addItems (BagInterface void showItems (BagInterface bag! BagInterface bag2 addItems (bag1, datal) addIterms (bag2, data2) = new LinkedBag() ; new LinkedBag): System.out.println "Bag 1 contains:") showItems (bagl); System.out.printin ) System.out.println("Bag 2 contains:"); showItems (bag2) System.out.println) BagInterface bag3bagl.union (bag2) BagInterface bag4 - bagl.intersection (bag2); BagInterface bag5-bag1.difference (bag2) BagInterface bag6bag2.difference (bagl) System.out.printin ("Bag 3 contains:") showItems (bag3) System.out.printin; System.out.println("Bag 4 contains:"); showItems (bag4) System.out.println) System.out.println("Bag 5 contains:") showItems (bag5) System.out.println ); System.out.printin ("Bag 6 contains:") showItems (bag6); System.out.println ); Bad InterfaceString> bag? -bag3. union (bag!) ; System.out.println ("Bag 7 contains:") showItems (bag7) System.out.println) BagInterface bag8bag7.intersection (bag1); System.out.println "Bag 8 contains:") showItems (bag8) System.out.printin ); BagInterface bag9 - bag1.intersection (bag7) System.out.println("Bag 9 contains:"); showItems (bag9); System.out.println public final class LinkedBag implements BagInterface private Node firstNode: private int numberofEntries; // Reference to first node public LinkedBag ) firstNodenull; numberofEntries0; end default constructor / Sees whether this bag is empty return True if this bag is empty, or false if not. / public boolean isEmpty return numberofEntries0 end isEmpty /* Gets the capacity of this bag return The integer number of entries that this bag can hold. */ public int getCapacity) return Integer.MAX VALUE // end getCapacity * Gets the number of entries currently in this bag @return The integer number of entries currently in this bag. */ public int getcurrentsize () return numberofEntries; /7 end getcurrentsize / Adds a new entry to this bag. param newEntry The object to be added as a new entry @return True if the addition is successful, or false if not. */ public boolean add (T newEntry) / OutofMemoryError possible // Add to beginning of chain: Node newNodenew Node (newEntry) newNode.next = firstNode ; // Make new node reference rest of chain I (tirstNode is null if chain is empty) /New node is at beginning of chain firstNodenewNode; numberofEntries++ return true // end add / Retrieves all entries that are in this bag public T toArray ) @return A newly allocated array of all the entries in this bag. / // The cast is safe because the new array contains null entries Suppresswarnings ("unchecked") Tl result -(T[1) new Object [numberOfEntries]; 1/ Unchecked cast int index0; Node currentNodefirstNode; while ((index