// File: LinkedBag.java from the package edu.colorado.linked
// Complete documentation is available from the LinkedBag link in:
// http://www.cs.colorado.edu/~main/docs/
package edu.colorado.collections;
import edu.colorado.nodes.Node;
import edu.colorado.nodes.Lister;
/******************************************************************************
* A LinkedBag is a collection of references to E objects.
*
* @note
* (1) Beyond Int.MAX_VALUE elements, countOccurrences,
* size, and grab are wrong.
*
* (2) Because of the slow linear algorithms of this class, large bags will have
* poor performance.
*
* @see
*
* Java Source Code for this class
* (www.cs.colorado.edu/~main/edu/colorado/collections/LinkedBag.java)
*
*
* @author Michael Main
* (main@colorado.edu)
*
* @version Feb 10, 2016
*
* @see ArrayBag
* @see IntLinkedBag
******************************************************************************/
public class LinkedBag implements Cloneable
{
// Invariant of the LinkedBag class:
// 1. The elements in the bag are stored on a linked list.
// 2. The head reference of the list is in the instance variable
// head.
// 3. The total number of elements in the list is in the instance
// variable manyNodes.
private Node head;
private int manyNodes;
/**
* Initialize an empty bag.
* @postcondition
* This bag is empty.
**/
public LinkedBag( )
{
head = null;
manyNodes = 0;
}
/**
* Put a reference to an object into this bag. The new element may be the
* null reference.
* @param element
* the new element to be added to this bag
* @postcondition
* The element has been added to this bag.
* @exception OutOfMemoryError
* Indicates insufficient memory a new Node.
**/
public void add(E element)
{
head = new Node(element, head);
manyNodes++;
}
/**
* Add the contents of another bag to this bag.
* @param addend
* a bag whose contents will be added to this bag
* @precondition
* The parameter, addend, is not null.
* @postcondition
* The elements from addend have been added to this bag.
* @exception NullPointerException
* Indicates that addend is null.
* @exception OutOfMemoryError
* Indicates insufficient memory to increase the size of the bag.
**/
public void addAll(LinkedBag addend)
{
Node[ ] copyInfo;
// The precondition indicates that addend is not null. If it is null,
// then a NullPointerException is thrown here.
if (addend.manyNodes > 0)
{
copyInfo = Node.listCopyWithTail(addend.head);
copyInfo[1].setLink(head); // Link the tail of copy to my own head...
head = copyInfo[0]; // and set my own head to the head of the copy.
manyNodes += addend.manyNodes;
}
}
/**
* Generate a copy of this bag.
* @return
* The return value is a copy of this bag. Subsequent changes to the
* copy will not affect the original, nor vice versa. Note that the return
* value must be type cast to an LinkedBag before it can be used.
* @exception OutOfMemoryError
* Indicates insufficient memory for creating the clone.
**/
@SuppressWarnings("unchecked")
public LinkedBag clone( )
{ // Clone a LinkedBag object.
LinkedBag answer;
try
{
answer = (LinkedBag) super.clone( );
}
catch (CloneNotSupportedException e)
{ // This exception should not occur. But if it does, it would probably
// indicate a programming error that made super.clone unavailable.
// The most common error would be forgetting the "Implements Cloneable"
// clause at the start of this class.
throw new RuntimeException
("This class does not implement Cloneable");
}
answer.head = Node.listCopy(head);
return answer;
}
/**
* Accessor method to count the number of occurrences of a particular element
* in this bag.
* @param target
* the element that needs to be counted
* @return
* The return value is the number of times that target occurs
* in this bag. If target is non-null, then the occurrences
* are found using the target.equals method.
**/
public int countOccurrences(E target)
{
int answer;
Node cursor;
// Implementation note: listSearch will use == when target is null.
// listSearch will use target.equals(...) when target is not null.
answer = 0;
cursor = Node.listSearch(head, target);
while (cursor != null)
{ // Each time that cursor is not null, we have another occurrence of
// target, so we add one to answer and then move cursor to the next
// occurrence of the target.
answer++;
cursor = cursor.getLink( );
cursor = Node.listSearch(cursor, target);
}
return answer;
}
/**
* Accessor method to retrieve a random element from this bag.
* @precondition
* This bag is not empty.
* @return
* a randomly selected element from this bag
* @exception IllegalStateException
* Indicates that the bag is empty.
**/
public E grab( )
{
int i;
Node cursor;
if (manyNodes == 0)
throw new IllegalStateException("Bag size is zero");
i = (int)(Math.random( ) * manyNodes) + 1;
cursor = Node.listPosition(head, i);
return cursor.getData( );
}
/**
* Create an Iterator containing the elements of this bag.
* @return
* an Iterator containing the elements of
* this bag.
* Note
* If changes are made to this bag before the Iterator
* returns all of its elements, then the subsequent behavior of the
* Iterator is unspecified.
**/
public Lister iterator( )
{
return new Lister(head);
}
/**
* Remove one copy of a specified element from this bag.
* @param target
* the element to remove from the bag
* @return
* If target was found in the bag, then one copy of
* target has been removed and the method returns true.
* Otherwise the bag remains unchanged and the method returns false.
**/
public boolean remove(E target)
{
Node targetNode; // The node that contains the target
// Implementation note: listSearch will use == when target is null.
// listSearch will use target.equals(...) when target is not null.
targetNode = Node.listSearch(head, target);
if (targetNode == null)
// The target was not found, so nothing is removed.
return false;
else
{ // The target was found at targetNode. So copy the head data to targetNode
// and then remove the extra copy of the head data.
targetNode.setData(head.getData( ));
head = head.getLink( );
manyNodes--;
return true;
}
}
/**
* Determine the number of elements in this bag.
* @return
* the number of elements in this bag
**/
public int size( )
{
return manyNodes;
}
/**
* Create a new bag that contains all the elements from two other bags.
* @param b1
* the first of two bags
* @param b2
* the second of two bags
* @param
* the type of the elements in this bag
* @precondition
* Neither b1 nor b2 is null.
* @return
* the union of b1 and b2
* @exception IllegalArgumentException
* Indicates that one of the arguments is null.
* @exception OutOfMemoryError
* Indicates insufficient memory for the new bag.
**/
public static LinkedBag union(LinkedBag b1, LinkedBag b2)
{
// The precondition requires that neither b1 nor b2 is null.
// If one of them is null, then addAll will throw a NullPointerException.
LinkedBag answer = new LinkedBag( );
answer.addAll(b1);
answer.addAll(b2);
return answer;
}
}