Question

Task 1:

You will modify the add method in the LinkedBag class.Add a second parameter to the method header that will be a boolean variable:

public boolean add(T newEntry, boolean sorted)

The modification to the add method will makeit possible toadd new entriesto the beginning of the list, as it does now, but also to add new entries in sorted order. The sorted parameter if set to false will result in the existing functionality being executed (it will add the new element to the beginning of the list), if set to true the new element will be inserted into the list such that the list isin sorted order.So for example if these are the current entries in the list:

5 -> 8 -> 10 -> 16 -> 25

And the new entry that I want to put into the list is 14, it will put it into the list between 10 and 16:

5 -> 8 -> 10 -> 14 -> 16 -> 25

Remember, this is a generic classso it needs to be able to process any kind of object, just as it does now.

Task 2:

You will need to modify the add method header in the BagInterface class alsoto include the new parameter.

Task 3:

Create a test program to thoroughly test the add method. Name this file LinkedBagTester.java. Part of this assignment is to create test cases that test all possible conditions of adding data into the list to verify that the new entry will get placed into the correct place in the list. Also, you need to test the conditions of adding elements only to the beginning of the list so that youverify that your changes did not break the existing functionality.

================Files==================

* LinkedBag.java ************************************************

public final class LinkedBag<T> implements BagInterface<T>
{
   private Node firstNode; // Reference to first node
   private int numberOfEntries;

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

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

   /** Gets the number of entries currently in this bag.
   @return The integer number of entries currently in this bag. */
   public int getCurrentSize()
   {
       return numberOfEntries;
   } // 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, boolean sorted) // OutOfMemoryError possible
   {
// Add to beginning of chain:
       Node newNode = new Node(newEntry);
       newNode.next = firstNode; // Make new node reference rest of chain
// (firstNode is null if chain is empty)
firstNode = newNode; // New node is at beginning of chain
       numberOfEntries++;

       return true;
   } // end add

   /** Retrieves all entries that are in this bag.
   @return A newly allocated array of all the entries in this bag. */
   public T[] toArray()
   {
// The cast is safe because the new array contains null entries
@SuppressWarnings("unchecked")
T[] result = (T[])new Object[numberOfEntries]; // Unchecked cast

int index = 0;
Node currentNode = firstNode;
while ((index < numberOfEntries) && (currentNode != null))
{
result[index] = currentNode.getData();
index++;
currentNode = currentNode.getNextNode();
} // end while

       return result;
   } // end toArray

   /** 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 this bag. */
   public int getFrequencyOf(T anEntry)
   {
       int frequency = 0;

int counter = 0;
Node currentNode = firstNode;
while ((counter < numberOfEntries) && (currentNode != null))
{
if (anEntry.equals(currentNode.getData()))
{
frequency++;
} // end if

counter++;
currentNode = currentNode.getNextNode();
} // end while

       return frequency;
   } // end getFrequencyOf

   /** Tests whether this bag contains a given entry.
       @param anEntry The entry to locate.
       @return True if the bag contains anEntry, or false otherwise. */
   public boolean contains(T anEntry)
   {
boolean found = false;
Node currentNode = firstNode;

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

return found;
} // end contains

    // 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.getData()))
               found = true;
           else
               currentNode = currentNode.getNextNode();
       } // end while

       return currentNode;
   } // end getReferenceTo

/** Removes all entries from this bag. */
   public void clear()
   {
       while (!isEmpty())
remove();
   } // end clear

   /** Removes one unspecified entry from this bag, if possible.
@return Either the removed entry, if the removal
was successful, or null. */
   public T remove()
   {
       T result = null;
if (firstNode != null)
{
result = firstNode.getData();
firstNode = firstNode.getNextNode(); // Remove first node from chain
numberOfEntries--;
} // end if

       return result;
   } // end remove

   /** Removes one occurrence of a given entry from this bag, if possible.
@param anEntry The entry to be removed.
@return True if the removal was successful, or false otherwise. */
public boolean remove(T anEntry)
   {
       boolean result = false;
Node nodeN = getReferenceTo(anEntry);

if (nodeN != null)
{
nodeN.setData(firstNode.getData()); // Replace located entry with entry in first node

firstNode = firstNode.getNextNode(); // Remove first node
numberOfEntries--;

result = true;
} // end if

       return result;
   } // end remove

   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 constructor

private T getData()
{
return data;
} // end getData

private void setData(T newData)
{
data = newData;
} // end setData

private Node getNextNode()
{
return next;
} // end getNextNode

private void setNextNode(Node nextNode)
{
next = nextNode;
} // end setNextNode
   } // end Node
} // end LinkedBag

* BagInterface.java ************************************************

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 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. */
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 contents of 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

* 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 LinkedBagDemo

Answer 1

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

{ private Node firstNode; // Reference to first node

private int numberOfEntries;
public LinkedBag() { firstNode = null; numberOfEntries = 0; } // end default constructor
/** Sees whether this bag is empty. @return True if this bag is empty, or false if not. */

public boolean isEmpty()

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

{ return numberOfEntries; } // 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 newNode = new Node(newEntry);
       newNode.next = firstNode; // Make new node reference rest of chain
// (firstNode is null if chain is empty)
firstNode = newNode; // New node is at beginning of chain
       numberOfEntries++;
  
}
void insertAfter(struct node* prev_node, int new_data)
{
if (prev_node == NULL)
{
printf("the given previous node cannot be NULL");   
return;
}
  
/*
struct node* new_node =(struct node*) malloc(sizeof(struct node));
new_node->data = new_data;
new_node->next = prev_
prev_node->next = new_node;
}
   } // end add
/** Retrieves all entries that are in this bag. @return A newly allocated array of all the entries in this bag. */ public T[] toArray() { // The cast is safe because the new array contains null entries @SuppressWarnings("unchecked") T[] result = (T[])new Object[numberOfEntries]; // Unchecked cast
int index = 0; Node currentNode = firstNode; while ((index < numberOfEntries) && (currentNode != null)) { result[index] = currentNode.getData(); index++; currentNode = currentNode.getNextNode(); } // end while
return result; } // end toArray
/** 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 this bag. */ public int getFrequencyOf(T anEntry) { int frequency = 0;
int counter = 0; Node currentNode = firstNode; while ((counter < numberOfEntries) && (currentNode != null)) { if (anEntry.equals(currentNode.getData())) { frequency++; } // end if
counter++; currentNode = currentNode.getNextNode(); } // end while
return frequency; } // end getFrequencyOf
/** Tests whether this bag contains a given entry. @param anEntry The entry to locate. @return True if the bag contains anEntry, or false otherwise. */ public boolean contains(T anEntry) { boolean found = false; Node currentNode = firstNode;
while (!found && (currentNode != null)) { if (anEntry.equals(currentNode.getData())) found = true; else currentNode = currentNode.getNextNode(); } // end while
return found; } // end contains
// 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.getData())) found = true; else currentNode = currentNode.getNextNode(); } // end while
return currentNode; } // end getReferenceTo
/** Removes all entries from this bag. */ public void clear() { while (!isEmpty()) remove(); } // end clear
/** Removes one unspecified entry from this bag, if possible. @return Either the removed entry, if the removal was successful, or null. */ public T remove() { T result = null; if (firstNode != null) { result = firstNode.getData(); firstNode = firstNode.getNextNode(); // Remove first node from chain numberOfEntries--; } // end if
return result; } // end remove
/** Removes one occurrence of a given entry from this bag, if possible. @param anEntry The entry to be removed. @return True if the removal was successful, or false otherwise. */ public boolean remove(T anEntry) { boolean result = false; Node nodeN = getReferenceTo(anEntry);
if (nodeN != null) { nodeN.setData(firstNode.getData()); // Replace located entry with entry in first node
firstNode = firstNode.getNextNode(); // Remove first node numberOfEntries--;
result = true; } // end if
return result; } // end remove
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 constructor
private T getData() { return data; } // end getData
private void setData(T newData) { data = newData; } // end setData
private Node getNextNode() { return next; } // end getNextNode
private void setNextNode(Node nextNode) { next = nextNode; } // end setNextNode } // end Node } // end LinkedBag

* BagInterface.java ************************************************
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 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. */ 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 contents of 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

* 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 LinkedBagDemo