Question

SimpleLinkedBag

We need to implement and test all of SimpleLinkedBag’s methods before we can use them in our game. These method implementations are similar to the examples in the course materials. When using the Node class, import it from the bag package. Refer to your text, class notes and examples to see examples of how to use a Node that holds a generic type. Remember the UML lists the return type for each method.

SimpleLinkedBag()

In SimpleLinkedBag, initialize the instance variables in the constructor. firstNode needs to be null and numberOfEntries needs to be 0.

getCurrentSize() && isEmpty()

Implement these yourself.

add(T anEntry)

Build a new Node containing the T entry as a parameter.

Prepend your node to the SimpleLinkedBag by setting the new Node’s next to be the firstNode. Set your new Node to be the firstNode field. Increment the numberOfEntriesfield by one, and finally return true, since adding is always successful. Here too think about the case if anEntry is null! In this case it should not add anything and return false.

pick()

If isEmpty() returns true, return null. This means there is nothing to draw from the bag.

Otherwise, we need to randomly select from the list. To do this, generate a random number named index using numberOfEntries as the bound. Refer back to the pick() section underSimpleArrayBag to see how the TestableRandom class works.

Starting with the firstNode, call getNext() repeatedly for index’s number, to arrive at your randomly selected Node. Return its getData().

getReferenceTo(T anEntry)

We need to search for the entry specified. To start, make a local boolean named found and set it to false. Also, make a local Node named currentNode and set it equal to firstNode.

Next, create a while loop which continues while the entry is not found and there is still more of the bag to search.

Check to see if every Node contains the entry by checking if anEntry equals that node’s contents. Use anEntry’s equals() method and currentNode’s getData() method.

If found, set your boolean to true. Otherwise, move your local Node by setting it to its getNext() value.

Once out of the while loop, return currentNode. This will be null if it was not found, or not null if we successfully found the entry specified.

remove(T anEntry)

Call getReferenceTo with your entry parameter to check if this LinkedBag contains the entry to remove.

If getReferenceTo() returns null, return false. This means we failed to remove the entry.

Otherwise, we need to remove the Node given. However, we can’t simply take it out. In a singly linked list, the only easily removed Node is the first one.

Instead, we will copy the value in the firstNode to our localNode. That way the data we want to remove will be contained in the first node, then we can simply update the firstNode pointer to be firstNode’s getNext().

Decrement the numberOfEntries, and return true since we successfully found and removed our entry.

In JAVA

Answer 1

SimpleLinkedBagTest.java

import student.TestableRandom;

public class SimpleLinkedBagTest extends student.TestCase
{
    private SimpleLinkedBag<String> bag1 = new SimpleLinkedBag<String>();
    private SimpleLinkedBag<String> bag2 = new SimpleLinkedBag<String>();

    /**
     * set up method for a LinkedBag test
     */
    public void setUp()
   {
        bag1.add("apples");
        bag1.add("bananas");
    }
  
    /**
     * test method for add
     */
    public void testAdd()
   {
        assertTrue(bag1.add("apples"));
        assertFalse(bag1.add(null));
    }
  
    /**
     * test method for getCurrentSize
     */
    public void testGetCurrentSize()
   {
        assertEquals(2, bag1.getCurrentSize());
    }
  
    /**
     * test method for isEmpty
     */
    public void testIsEmpty()
   {
        assertTrue(bag2.isEmpty());
        assertFalse(bag1.isEmpty());
    }

    /**
     * test method for pick
     */
    public void testPick()
   {
        TestableRandom.setNextInts(1);
        assertEquals("apples", bag1.pick());
        assertNull(bag2.pick());
    }
  
    /**
     * test method for pick
     */
    public void testRemove()
   {
        bag1.remove("apples");
        assertTrue(bag1.remove("bananas"));
        assertFalse(bag1.remove("apples"));
    }

}

=============================================================================================

SimpleLinkedBag.java

public class SimpleLinkedBag<T> implements SimpleBagInterface<T>
{
    private Node<T> firstNode;
    private int numberOfEntries;

    /**
     * default constructor for SimpleLinkedBag
     */
    public SimpleLinkedBag()
   {
        firstNode = null;
        numberOfEntries = 0;
    }
  
    /**
     * Add method for SimpleLinkedBag
     */
    @Override
    public boolean add(T anEntry)
   {

        if (anEntry == null)
       {
            return false;
        }
        Node<T> newNode = new Node<>(anEntry);
        newNode.setNext(firstNode);
        firstNode = newNode;
        numberOfEntries++;
        return true;

    }

    /**
     * getCurrentSize method for SimpleLinkedBag
     */
    @Override
    public int getCurrentSize()
   {

        return numberOfEntries;
    }

    /**
     * isEmpty method for SimpleLinkedBag
     */
    @Override
    public boolean isEmpty()
   {

        return numberOfEntries == 0;
    }

   /**
    * Pick method for SimpleLinkedBag
    */
    @Override
    public T pick()
   {
        if (isEmpty())
       {
            return null;
        }
        else
       {
            TestableRandom generator = new TestableRandom();
            int index = generator.nextInt(numberOfEntries);
            Node<T> temporary = firstNode;
            for (int i = 0; i < index; i++)
           {
                temporary = temporary.next();
            }
            return temporary.data();
        }
    }

    /**
     * Remove method for SimpleLinkedBag
     */
    @Override
    public boolean remove(T anEntry)
   {
        if (getReferenceTo(anEntry) == null)
       {
            return false;
        }
        else
       {
            Node<T> node = getReferenceTo(anEntry);
            node.setData(firstNode.data());
            firstNode = firstNode.next();
            numberOfEntries--;
        }
        return true;
    }

    /**
     * getReference method for SimpleLinkedBag
     * @param anEntry entry for which we need to find the reference
     * @return the node of an entry
     */
    private Node<T> getReferenceTo(T anEntry)
   {
        boolean found = false;
        Node<T> currentNode = firstNode;
        while (!found && currentNode != null)
       {
            if (anEntry.equals(currentNode.data()))
           {
                found = true;
            }
            else
           {
                currentNode = currentNode.next();
            }
        }
        return currentNode;

    }

}