Question

• Write a class "LinkedBag" which implements this interface.
• The LinkedBag class has two instance variables firstNode and numberOfEntries.
• It has an inner class Node.

BagInterface.java

/** An interface that describes the operations of a bag of objects. @author Frank M. Carrano @author Timothy M. Henry @version 4.1*/public interface BagInterface<T>{ /** Gets the current number of entries in this bag. @return The integer number of entries currently in the bag. */ public int getCurrentSize(); /** Sees whether this bag is empty. @return True if the bag is empty, or false if not. */ public boolean isEmpty(); /** 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); /** Removes one unspecified entry from this bag, if possible. @return Either the removed entry, if the removal. was successful, or null. */ public T remove(); /** Removes one occurrence ofa given entry from this bag. @param anEntry The entry to be removed. @return True if the removal was successful, or false if not. */ public boolean remove(T anEntry); /** Removes all entries from this bag. */ public void clear(); /** Counts the number of times a given entry appears in this bag. @param anEntry The entry to be counted. @return The number of times anEntry appears in the bag. */ public int getFrequencyOf(T anEntry);/** Tests whether this bag contains a given entry. @param anEntry The entry to locate. @return True if the bag contains anEntry, or false if not. */ public boolean contains(T anEntry); /** Retrieves all entries that are in this bag. @return A newly allocated array of all the entries in the bag. Note: If the bag is empty, the returned array is empty. */ public T[] toArray();// public <T> T[] toArray(); // Alternate// public Object[] toArray(); // Alternate /** Creates a new bag that combines the contentsof this bag and anotherBag. @param anotherBag The bag that is to be added. @return A combined bag. */ // public BagInterface<T> union(BagInterface<T> anotherBag); /** Creates a new bag that contains those objects that occur in both this bag and anotherBag. @param anotherBag The bag that is to be compared. @return A combined bag. */ // public BagInterface<T> intersection(BagInterface<T> anotherBag); /** Creates a new bag of objects that would be left in this bag after removing those that also occur in anotherBag. @param anotherBag The bag that is to be removed. @return A combined bag. */ // public BagInterface<T> difference(BagInterface<T> anotherBag);} // end BagInterface

public class LinkedBag <T> implements BagInterface<T>

{

private Node firstNode; // Reference to first node of chain
private int numberOfEntries;

...

//default constructor
public LinkedBag()
{
firstNode = null;
numberOfEntries = 0;
} // end default constructor

// Implement the unimplemented methods

// Locates a given entry within this bag.
// Returns a reference to the node containing the entry, if located,
// or null otherwise.
private Node getReferenceTo(T anEntry)
{
boolean found = false;
Node currentNode = firstNode;

while (!found && (currentNode != null))
{
if (anEntry.equals(currentNode.data))
found = true;
else
currentNode = currentNode.next;
} // end while

return currentNode;
} // end getReferenceTo

private class Node
{

...

}// end Node

}// end LinkedBag

• Test your code with the Diver class: LinkedBagDemo.java
• Required files:

  • BagInterface.java

  • LinkedBag.java  <= You need to write it!

  • LinkedBagDemo.java

LinkedBagDemo.java

/** A demonstration of the class LinkedBag.

@author Frank M. Carrano

@author Timothy M. Henry

@version 4.0

*/

public class LinkedBagDemo

{

public static void main(String[] args)

{

// Tests on a bag that is empty

System.out.println("Creating an empty bag.");

BagInterface<String> aBag = new LinkedBag<>();

displayBag(aBag);

testIsEmpty(aBag, true);

String[] testStrings1 = {"", "B"};

testFrequency(aBag, testStrings1);

testContains(aBag, testStrings1);

testRemove(aBag, testStrings1);

// Adding strings

String[] contentsOfBag = {"A", "D", "B", "A", "C", "A", "D"};

testAdd(aBag, contentsOfBag);

// Tests on a bag that is not empty

testIsEmpty(aBag, false);

String[] testStrings2 = {"A", "B", "C", "D", "Z"};

testFrequency(aBag, testStrings2);

testContains(aBag, testStrings2);

// Removing strings

String[] testStrings3 = {"", "B", "A", "C", "Z"};

testRemove(aBag, testStrings3);

System.out.println("\nClearing the bag:");

aBag.clear();

testIsEmpty(aBag, true);

displayBag(aBag);

} // end main

   // Tests the method add.

private static void testAdd(BagInterface<String> aBag, String[] content)

{

System.out.print("Adding to the bag: ");

for (int index = 0; index < content.length; index++)

{

aBag.add(content[index]);

   System.out.print(content[index] + " ");

} // end for

System.out.println();

displayBag(aBag);

} // end testAdd

   // Tests the two remove methods.

private static void testRemove(BagInterface<String> aBag, String[] tests)

{

for (int index = 0; index < tests.length; index++)

{

   String aString = tests[index];

   if (aString.equals("") || (aString == null))

   {

// test remove()

System.out.println("\nRemoving a string from the bag:");

String removedString = aBag.remove();

System.out.println("remove() returns " + removedString);

   }

   else

   {

// test remove(aString)

System.out.println("\nRemoving \"" + aString + "\" from the bag:");

boolean result = aBag.remove(aString);

System.out.println("remove(\"" + aString + "\") returns " + result);

   } // end if

   displayBag(aBag);

} // end for

} // end testRemove

   // Tests the method isEmpty.

   // correctResult indicates what isEmpty should return.

private static void testIsEmpty(BagInterface<String> aBag, boolean

correctResult)

{

System.out.print("Testing isEmpty with ");

if (correctResult)

   System.out.println("an empty bag:");

else

   System.out.println("a bag that is not empty:");

System.out.print("isEmpty finds the bag ");

if (correctResult && aBag.isEmpty())

System.out.println("empty: OK.");

else if (correctResult)

System.out.println("not empty, but it is empty: ERROR.");

else if (!correctResult && aBag.isEmpty())

System.out.println("empty, but it is not empty: ERROR.");

else

System.out.println("not empty: OK.");

System.out.println();

} // end testIsEmpty

   // Tests the method getFrequencyOf.

private static void testFrequency(BagInterface<String> aBag, String[] tests)

{

System.out.println("\nTesting the method getFrequencyOf:");

for (int index = 0; index < tests.length; index++)

   System.out.println("In this bag, the count of " + tests[index] +

" is " + aBag.getFrequencyOf(tests[index]));

   } // end testFrequency

   // Tests the method contains.

private static void testContains(BagInterface<String> aBag, String[] tests)

{

System.out.println("\nTesting the method contains:");

for (int index = 0; index < tests.length; index++)

   System.out.println("Does this bag contain " + tests[index] +

"? " + aBag.contains(tests[index]));

   } // end testContains

   // Tests the method toArray while displaying the bag.

private static void displayBag(BagInterface<String> aBag)

{

System.out.println("The bag contains " + aBag.getCurrentSize() +

   " string(s), as follows:");

Object[] bagArray = aBag.toArray();

for (int index = 0; index < bagArray.length; index++)

{

System.out.print(bagArray[index] + " ");

} // end for

System.out.println();

} // end displayBag

} // end LinkedBagDemo

/*

Creating an empty bag.

The bag contains 0 string(s), as follows:

Testing isEmpty with an empty bag:

isEmpty finds the bag empty: OK.

Testing the method getFrequencyOf:

In this bag, the count of is 0

In this bag, the count of B is 0

Testing the method contains:

Does this bag contain ? false

Does this bag contain B? false

Removing a string from the bag:

remove() returns null

The bag contains 0 string(s), as follows:

Removing "B" from the bag:

remove("B") returns false

The bag contains 0 string(s), as follows:

Adding to the bag: A D B A C A D

The bag contains 7 string(s), as follows:

D A C A B D A

Testing isEmpty with a bag that is not empty:

isEmpty finds the bag not empty: OK.

Testing the method getFrequencyOf:

In this bag, the count of A is 3

In this bag, the count of B is 1

In this bag, the count of C is 1

In this bag, the count of D is 2

In this bag, the count of Z is 0

Testing the method contains:

Does this bag contain A? true

Does this bag contain B? true

Does this bag contain C? true

Does this bag contain D? true

Does this bag contain Z? false

Removing a string from the bag:

remove() returns D

The bag contains 6 string(s), as follows:

A C A B D A

Removing "B" from the bag:

remove("B") returns true

The bag contains 5 string(s), as follows:

C A A D A

Removing "A" from the bag:

remove("A") returns true

The bag contains 4 string(s), as follows:

C A D A

Removing "C" from the bag:

remove("C") returns true

The bag contains 3 string(s), as follows:

A D A

Removing "Z" from the bag:

remove("Z") returns false

The bag contains 3 string(s), as follows:

A D A

Clearing the bag:

Testing isEmpty with an empty bag:

isEmpty finds the bag empty: OK.

The bag contains 0 string(s), as follows:

*/

WRITE LinkedBag.java

Answer 1

// BagInterface.java

/** An interface that describes the operations of a bag of objects.
* @author Frank M. Carrano @author Timothy M. Henry
* @version 4.1*/

public interface BagInterface<T>{
   /** Gets the current number of entries in this bag.
   @return The integer number of entries currently in the bag.
   */
   public int getCurrentSize();
  
   /** Sees whether this bag is empty.
   @return True if the bag is empty, or false if not.
   */
   public boolean isEmpty();
  
   /** 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);
  
   /** Removes one unspecified entry from this bag, if possible.
   @return Either the removed entry, if the removal. was successful, or null.
   */
   public T remove();
  
   /** Removes one occurrence ofa given entry from this bag.
   @param anEntry The entry to be removed.
   @return True if the removal was successful, or false if not.
   */
   public boolean remove(T anEntry);
  
   /** Removes all entries from this bag. */
   public void clear();
  
   /** Counts the number of times a given entry appears in this bag.
   @param anEntry The entry to be counted.
   @return The number of times anEntry appears in the bag.
   */
   public int getFrequencyOf(T anEntry);
  
   /** Tests whether this bag contains a given entry.
   @param anEntry The entry to locate.
   @return True if the bag contains anEntry, or false if not.
   */
   public boolean contains(T anEntry);
  
   /** Retrieves all entries that are in this bag.
   @return A newly allocated array of all the entries in the bag.
   Note: If the bag is empty, the returned array is empty.
   */
   public T[] toArray();
  
   // public <T> T[] toArray(); // Alternate
   // public Object[] toArray(); // Alternate
  
   /** Creates a new bag that combines the contentsof this bag and anotherBag.
   @param anotherBag The bag that is to be added.
   @return A combined bag.
   */
   //public BagInterface<T> union(BagInterface<T> anotherBag);
  
   /** Creates a new bag that contains those objects that occur in both this bag and anotherBag.
   @param anotherBag The bag that is to be compared. @return A combined bag.
   */
   // public BagInterface<T> intersection(BagInterface<T> anotherBag);
  
   /** Creates a new bag of objects that would be left in this bag after removing those that also occur in anotherBag.
   @param anotherBag The bag that is to be removed.
   @return A combined bag.
   */
   // public BagInterface<T> difference(BagInterface<T> anotherBag);
  
} // end BagInterface

//end of BagInterface.java

// LinkedBag.java

public class LinkedBag<T> implements BagInterface<T> {
  

   private Node firstNode; // Reference to first node of chain
   private int numberOfEntries;
  
   //default constructor
   public LinkedBag()
   {
       firstNode = null;
       numberOfEntries = 0;
   } // end default constructor
  
  
   // Implement the unimplemented methods

   // Locates a given entry within this bag.
   // Returns a reference to the node containing the entry, if located,
   // or null otherwise.
   private Node getReferenceTo(T anEntry)
   {
       boolean found = false;
       Node currentNode = firstNode;
  
       while (!found && (currentNode != null))
       {
       if (anEntry.equals(currentNode.data))
       found = true;
       else
       currentNode = currentNode.next;
       } // end while
  
       return currentNode;
   } // end getReferenceTo

   /** Gets the current number of entries in this bag.
   @return The integer number of entries currently in the bag.
   */
   @Override
   public int getCurrentSize() {
       return numberOfEntries ;
   }

   /** Sees whether this bag is empty.
   @return True if the bag is empty, or false if not.
   */
   @Override
   public boolean isEmpty() {
       return numberOfEntries == 0;
   }

   /** 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.
   */
   @Override
   public boolean add(T newEntry) {
       // create a new node to contain newEntry
       Node node = new Node(newEntry);
       // insert node at the start
       node.next = firstNode;
       firstNode = node;
       numberOfEntries++;
       return true;
   }

   /** Removes one unspecified entry from this bag, if possible.
   @return Either the removed entry, if the removal. was successful, or null.
   */
   @Override
   public T remove() {
       if(isEmpty()) // empty bag
           return null;
       else
       {
           // get the data of the first node
           T data = firstNode.data;
           // remove the first node
           firstNode = firstNode.next;
           numberOfEntries--;
           return data;
       }
   }

   /** Removes one occurrence of a given entry from this bag.
   @param anEntry The entry to be removed.
   @return True if the removal was successful, or false if not.
   */
   @Override
   public boolean remove(T anEntry) {
       Node curr = firstNode;
       Node prev = null;
      
       // loop to get the first occurrence of anEntry in curr and node previous to curr in prev
       while(curr != null)
       {
           if(curr.data.equals(anEntry))
               break;
           prev = curr;
           curr = curr.next;
       }
      
       if(curr == null) // anEntry not in bag
           return false;
       else
       {
           if(prev == null) // firstNode contains anEntry
               firstNode = firstNode.next;
           else
               prev.next = curr.next;
           numberOfEntries--;
           return true;
       }
   }

   /** Removes all entries from this bag. */
   @Override
   public void clear() {
       firstNode = null;
       numberOfEntries = 0;  
   }

   /** Counts the number of times a given entry appears in this bag.
   @param anEntry The entry to be counted.
   @return The number of times anEntry appears in the bag.
   */
   @Override
   public int getFrequencyOf(T anEntry) {
      
       int count = 0;
       Node curr = firstNode;
      
       // loop to count the number of times anEntry is present in the bag
       while(curr != null)
       {
           if(curr.data.equals(anEntry))
               count++;
           curr = curr.next;
       }
      
       return count;
   }

   /** Tests whether this bag contains a given entry.
   @param anEntry The entry to locate.
   @return True if the bag contains anEntry, or false if not.
   */
   @Override
   public boolean contains(T anEntry) {
       return getReferenceTo(anEntry) != null;
   }

   /** Retrieves all entries that are in this bag.
   @return A newly allocated array of all the entries in the bag.
   Note: If the bag is empty, the returned array is empty.
   */
   @Override
   public T[] toArray() {
      
       // create an array of size numberOfEntries
       T[] result = (T[])new Object[numberOfEntries];
      
       int index = 0;
       Node current = firstNode;
  
       // loop to insert the items of the bag in the array
       while((index < numberOfEntries) && (current != null))
       {
           result[index] = current.data;
           index++;
           current = current.next;
       }

   return result;
   }
     
  
   // A class of nodes for a chain of linked nodes.
   private class Node
   {
       private T data;
   // Entry in bag
   private Node next;
   // Link to next node
   private Node(T dataPortion)
   {
       this(dataPortion, null);
   }
   // end constructor
   private Node(T dataPortion, Node nextNode)
   {
       data = dataPortion;
       next = nextNode;
   }
  
   } // end Node
}

//end of LinkedBag.java

// LinkedBagDemo.java

public class LinkedBagDemo {
         
   public static void main(String[] args)
   {

       // Tests on a bag that is empty
  
       System.out.println("Creating an empty bag.");
  
       BagInterface<String> aBag = new LinkedBag<>();
  
       displayBag(aBag);
  
       testIsEmpty(aBag, true);
  
       String[] testStrings1 = {"", "B"};
  
       testFrequency(aBag, testStrings1);
  
       testContains(aBag, testStrings1);
  
       testRemove(aBag, testStrings1);
  
       // Adding strings
  
       String[] contentsOfBag = {"A", "D", "B", "A", "C", "A", "D"};
  
       testAdd(aBag, contentsOfBag);
  
       // Tests on a bag that is not empty
  
       testIsEmpty(aBag, false);
  
       String[] testStrings2 = {"A", "B", "C", "D", "Z"};
  
       testFrequency(aBag, testStrings2);
  
       testContains(aBag, testStrings2);
  
       // Removing strings
  
       String[] testStrings3 = {"", "B", "A", "C", "Z"};
  
       testRemove(aBag, testStrings3);
  
       System.out.println("\nClearing the bag:");
  
       aBag.clear();
  
       testIsEmpty(aBag, true);
  
       displayBag(aBag);

   } // end main

   // Tests the method add.

   private static void testAdd(BagInterface<String> aBag, String[] content)
   {

       System.out.print("Adding to the bag: ");
  
       for (int index = 0; index < content.length; index++)
       {
           aBag.add(content[index]);
           System.out.print(content[index] + " ");
      
       } // end for
  
       System.out.println();
  
       displayBag(aBag);

   } // end testAdd
     
   // Tests the two remove methods.
   private static void testRemove(BagInterface<String> aBag, String[] tests)
   {

       for (int index = 0; index < tests.length; index++)
       {
  
       String aString = tests[index];
  
       if (aString.equals("") || (aString == null))
       {
  
               // test remove()
              
               System.out.println("\nRemoving a string from the bag:");
              
               String removedString = aBag.remove();
              
               System.out.println("remove() returns " + removedString);
       }
       else
       {
  
               // test remove(aString)
          
               System.out.println("\nRemoving \"" + aString + "\" from the bag:");
          
               boolean result = aBag.remove(aString);
          
               System.out.println("remove(\"" + aString + "\") returns " + result);
  
       } // end if
  
       displayBag(aBag);
  
       } // end for

   } // end testRemove

     
   // Tests the method isEmpty.
   // correctResult indicates what isEmpty should return.
   private static void testIsEmpty(BagInterface<String> aBag, boolean correctResult)
   {

       System.out.print("Testing isEmpty with ");

       if (correctResult)
           System.out.println("an empty bag:");
       else
           System.out.println("a bag that is not empty:");
         
       System.out.print("isEmpty finds the bag ");
       if (correctResult && aBag.isEmpty())
           System.out.println("empty: OK.");
       else if (correctResult)
           System.out.println("not empty, but it is empty: ERROR.");
       else if (!correctResult && aBag.isEmpty())
           System.out.println("empty, but it is not empty: ERROR.");
       else
           System.out.println("not empty: OK.");
       System.out.println();
   } // end testIsEmpty
     
   // Tests the method getFrequencyOf.
   private static void testFrequency(BagInterface<String> aBag, String[] tests)
   {

       System.out.println("\nTesting the method getFrequencyOf:");
  
       for (int index = 0; index < tests.length; index++)
       System.out.println("In this bag, the count of " + tests[index] +
               " is " + aBag.getFrequencyOf(tests[index]));

   } // end testFrequency

   // Tests the method contains.

   private static void testContains(BagInterface<String> aBag, String[] tests)
   {

       System.out.println("\nTesting the method contains:");
       for (int index = 0; index < tests.length; index++)
           System.out.println("Does this bag contain " + tests[index] +
                   "? " + aBag.contains(tests[index]));

   } // end testContains
     
   // Tests the method toArray while displaying the bag.
   private static void displayBag(BagInterface<String> aBag)
   {

       System.out.println("The bag contains " + aBag.getCurrentSize() +
               " string(s), as follows:");
  
       Object[] bagArray = aBag.toArray();
  
       for (int index = 0; index < bagArray.length; index++)
       {
  
           System.out.print(bagArray[index] + " ");
  
       } // end for
  
       System.out.println();

   } // end displayBag
}

//end of LinkedBagDemo.java

Output: