CSCI 146: Lab 6 Materials

BRING YOUR TEXTBOOK TO THIS LAB!

The main goal of Lab 6 is for the students to further their understanding of the linked list data structure by writing some methods for the IntLinkedBag class. You will also need the IntNode class.

Modify the IntLinkedBag class by adding a method for removing all entries with even numbers in them. Before writing any code, write pre- and post-conditions for this method.
Implement a subtract method for the IntLinkedBag, as described in programming project 8 on p.239.

Test the class using the test program provided. In order to use the test program provided, you need to write a method (getBagData) that prints every item in a bag. You should be able to compile and run the program successfully by the end of the lab.

Here is the IntLinkedBag class:


// File: IntLinkedBag.java from the package edu.colorado.linked
// Complete documentation is available from the IntLinkedBag link in:
//   http://www.cs.colorado.edu/~main/docs

package edu.colorado.collections;
import edu.colorado.nodes.IntNode; 

/******************************************************************************
* An IntLinkedBag is a collection of int numbers.
*
* Limitations: 

*   (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.
*
* 
Java Source Code for this class:

*   
*   http://www.cs.colorado.edu/~main/edu/colorado/collections/IntLinkedBag.java
*   
*
* @author Michael Main 
*    (main@colorado.edu) 
*
* @version
*   Jun 12, 1998
*
* @see IntArrayBag
******************************************************************************/
public class IntLinkedBag implements Cloneable
{
   // Invariant of the IntLinkedBag 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 IntNode head;
   private int manyNodes;   


   /**
   * Initialize an empty bag.
   * @param - none
   * 
Postcondition:

   *   This bag is empty.
   **/
   public IntLinkedBag( )
   {
      head = null;
      manyNodes = 0;
   }
        
 
   /**
   * Add a new element to this bag.
   * @param element
   *   the new element that is being added
   * 
Postcondition:

   *   A new copy of the element has been added to this bag.
   * @exception OutOfMemoryError
   *   Indicates insufficient memory a new IntNode.
   **/
   public void add(int element)
   {      
      head = new IntNode(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(IntLinkedBag addend)
   {
      IntNode[ ] copyInfo;
      
      // The precondition indicates that addend is not null. If it is null,
      // then a NullPointerException is thrown here.
      if (addend.manyNodes > 0)
      {
         copyInfo = IntNode.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.
   * @param - none
   * @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 IntLinkedBag before it can be used.
   * @exception OutOfMemoryError
   *   Indicates insufficient memory for creating the clone.
   **/ 
   public Object clone( )
   {  // Clone a nIntLinkedBag object.
      IntLinkedBag answer;
      
      try
      {
         answer = (IntLinkedBag) 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 = IntNode.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 number of times that target occurs in this bag
   **/
   public int countOccurrences(int target)
   {
      int answer;
      IntNode cursor;

      answer = 0;
      cursor = IntNode.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 = IntNode.listSearch(cursor, target);
      }
      return answer;
   }

    
   /**
   * Accessor method to retrieve a random element from this bag.
   * @param - none
   * 
Precondition:

   *   This bag is not empty.
   * @return
   *   a randomly selected element from this bag
   * @exception IllegalStateException
   *   Indicates that the bag is empty.
   **/
   public int grab( )
   {
      int i;
      IntNode cursor;
      
      if (manyNodes == 0)
         throw new IllegalStateException("Bag size is zero");
         
      i =  (int)(Math.random( ) * manyNodes) + 1;
      cursor = IntNode.listPosition(head, i);
      return cursor.getData( );
   }
   
             
   /**
   * Remove one copy of a specified element from this bag.
   * @param target
   *   the element to remove from the bag
   * 
Postcondition:

   *   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(int target)
   {
      IntNode targetNode; // The node that contains the target

      targetNode = IntNode.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.
   * @param - none
   * @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
   * 
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 IntLinkedBag union(IntLinkedBag b1, IntLinkedBag b2)
   {       
      // The precondition requires that neither b1 nor b2 is null.
      // If one of them is null, then addAll will throw a NullPointerException.  
      IntLinkedBag answer = new IntLinkedBag( );
      
      answer.addAll(b1);
      answer.addAll(b2);     
      return answer;
   }
      
}


public class IntLinkedBagTest {
	
	public static void main(String args[])
	{
		IntLinkedBag b1 =  new IntLinkedBag();
		IntLinkedBag b2 = new IntLinkedBag();
		
	
		b1.add(3);
		b1.add(3);
		b1.add(3);
		b1.add(5);
		b1.add(3);
		b1.add(3);
		b1.add(3);
		b1.add(3);
		System.out.println("b1 = \n");
		IntLinkedBag.getBagData( b1);
		
		
		b2.add(4);
		b2.add(3);
		b2.add(3);
		System.out.println("\nb2 = \n");
		IntLinkedBag.getBagData(b2);
		
		
		b1.subtract(b2);
		System.out.println("\nsubtract b2 from b1\n");
		IntLinkedBag.getBagData(b1);

		b2.add(6);
		b2.removeEven();
		System.out.println("\nremove even numbers from b2\n");
		IntLinkedBag.getBagData(b2);
	}
		
	}


public class IntNode
{
    private int data;
    private IntNode link;
    
    public IntNode(int initialData, IntNode initialLink) {
	data = initialData;
	link = initialLink;
    }

    public void addNodeAfter(int element) {
	link = new IntNode(element, link);
    }

    public int getData() {
	return data;
    }

    public IntNode getLink() {
	return link;
    }

    public static IntNode listCopy(IntNode source) {
	IntNode copyHead;
	IntNode copyTail;

	if (source == null)
	    return null;

	copyHead = new IntNode(source.data, null);
	copyTail = copyHead;

	while (source.link != null) {
	    source = source.link;
	    copyTail.addNodeAfter(source.data);
	    copyTail = copyTail.link;
	}
	return copyHead;
    }

    public static IntNode[] listCopyWithTail(IntNode source) {
	IntNode[] answer = new IntNode[2];

	IntNode copyHead = listCopy(source);
	IntNode copyTail = copyHead;

	while (copyTail.link != null)
	    copyTail = copyTail.link;

	answer[0] = copyHead;
	answer[1] = copyTail;
	return answer;
    }

    public static int listLength(IntNode head) {
	IntNode cursor;
	int answer = 0;

	for (cursor = head; cursor != null; cursor = cursor.link)
	    answer++;

	return answer;
    }

    public static IntNode[] listPart(IntNode start, IntNode end) {
	if (start == null)
	    throw new IllegalArgumentException("dasjdaslkj");
	if (end == null)
	    throw new IllegalArgumentException("asdsadsa");

	IntNode copyHead = new IntNode(start.data, null);
	IntNode copyTail = copyHead;

	while (start != end) {
	    start = start.link;
	    if (start == null)
		throw new IllegalArgumentException("zzzzzzzzzzzzzzz");
	    copyTail.addNodeAfter(start.data);
	    copyTail = copyTail.link;
	}
	IntNode answer[] = new IntNode[2];
	answer[0] = copyHead;
	answer[1] = copyTail;
	return answer;
    }

    public static IntNode listPosition(IntNode head, int position) {
	IntNode cursor = head;
	int i;

	if (position <= 0)
	    throw new IllegalArgumentException("blah blah");

	for (i = 1; (i < position) && (cursor != null); i++)
	    cursor = cursor.link;

	return cursor;
    }

    public static IntNode listSearch(IntNode head, int target) {
	IntNode cursor;
	
	for (cursor = head; cursor != null; cursor = cursor.link)
	    if (cursor.data == target)
		return cursor;
	return null;
    }

    public void removeNodeAfter() {
	link = link.link;
    }

    public void setData(int newData) {
	data = newData;
    }

    public void setLink(IntNode newLink) {
	link = newLink;
    }
    
    public static IntNode reverseList(IntNode head) {
	if (head == null)
	    return null;

	IntNode reverseHead = new IntNode(head.data, null);
	IntNode cursor;

	for (cursor = head.link; cursor != null; cursor = cursor.link)
	    reverseHead = new IntNode(cursor.data, reverseHead);

	return reverseHead;
    }
}