CSc 150

Objectives

• To make your own abstract data structure
• To learn how to separate the behavior of an object from its implementation
• To practice thorough testing of your code

Introduction

One common container is called a Bag. Like an array, a bag stores objects that are all of the same type. Unlike an array, a bag's contents have no inherent order to them, and they are not accessible by an integer index. In addition, a bag can grow and shrink to accommodate the insertion and deletion of items.

Your Mission

To help get you started, the following are methods that the Bag class must have, with exactly these prototypes:

public Bag(int capacity)
{
  //constructor: creates a new Bag whose initial capacity 
  //(i.e. the number of items it can hold total) is the given int.
  //This translates to the length of the internal array.
}
	
public void add(String value)
{
  //adds the given String to the bag.  If the bag's capacity has
  //been reached, the bag will expand to twice its current
  //capacity to accommodate the new entry.
}

public void remove(String value)
{
  //deletes an element from the bag with the same string contents
  //as the parameter.  So if value points to "hello", this method
  //deletes one (and only one) object from the bag that also
  //points to "hello".  If value is not in the bag, do nothing.
  //You should "close up" the hole left by the vacated entry. 
}	

public String removeRandom()
{
  //removes a random element from the bag and returns it.
  //Returns null if the bag is empty.
}

public boolean contains(String value)
{
  //returns true if value is in the bag. 
  //Returns false otherwise.
}	
	
public boolean equals(Bag otherBag)
{
  //returns true if this Bag and otherBag are equal.
  //Returns false otherwise.  Two bags are equal if (1) they
  //have the same size (not necessarily the same capacity) and 
  //(2) they contain exactly the same elements.  So the two bags
  //
  //{hi, hi, bye}  and  {hi, bye, hi} are equal.
  //
  //The two bags:
  //
  //{hi, hi, bye}  and  {hi, bye, bye} are not.
}
	
public boolean isEmpty()
{
  //returns true if this bag is empty.  Returns false otherwise.
}

public void clear()
{
  //removes all elements from this bag.
}

public int size()
{
  //returns the number of items in this bag.
  //This corresponds to the number of Strings that
  //the internal array currently contains.
}

public int capacity()
{
  //returns the current capacity of this bag.
  //This corresponds to the length of the internal array.
}
	
public void trimToSize()
{
  //Trims the capacity of this bag to be the bag's current size.
  //If the capacity (length of internal array) is larger than the 
  //current size, the internal array is replaced by a smaller one.
}

public String toString()
{
  //Returns all elements of this bag as a single printable String.
  //For example, if the bag contains the strings 
  //
  //"Al", "Barb", "Charlie" 
  //
  //then this method will return the string:
  //
  //	"{Al, Barb, Charlie}"
  //
  //with the curly braces and commas correctly included, and on 1 line.
  //There should be no comma after the last element.  In other words,
  //your method should return a string in the same way as this example.
  //Empty spaces in the bag (i.e. nulls at end of the array) should 
  //not be included as part of the returned string.  The order
  //in which the elements are printed does not matter since bags
  //have no order.
}
	
public Bag copy()
{
  //Makes an exact duplicate of this Bag and returns it.
  //The result should be an independent bag from the original,
  //and the elements within should be brand new objects that
  //happen to have the same values as the original (i.e. brand
  //new String objects).  This method is non-destructive: it
  //should NOT alter the original bag!  Note: you are not allowed
  //to use Object's clone method for this.  Make the copy
  //manually.
}
	
public Bag union(Bag otherBag)
{
  //returns a new Bag containing all of the elements from 
  //both this Bag and otherBag.  For example, if this bag
  //is {Al, Barb, Charlie} and otherBag is {Dave, Charlie, Ernie},
  //then this method returns the bag:
  //
  // {Al, Barb, Charlie, Dave, Charlie, Ernie}. 
  //
  //where, again, order does not matter.  This method is 
  //non-destructive: it should NOT alter the original two bags!
}

You are not allowed to change the prototypes of the above methods in any way. You are also not allowed to use any of Java's built-in containers for this project, like ArrayList or Vector. You may build private methods, however, if you wish. It is your job to figure out what instance variables are appropriate.

Testing is part of the job

You should write a main method that will test each and every method on its own. Write separate static methods that main will call to test each method individually. (Be modular, remember?) You should also test to be sure you account for all "real world" cases like the one I gave above. Good testing is an important part of good programming. When I run your main method, I should see evidence that each of your methods has been tested completely. Thus, everyone will have different final output. At the very least, each test should print:

• What the test is trying to do
• The expected outcome
• The actual outcome
• Whether or not the test PASSed or FAILed

Here's an example of good output:

add method tests
----------------
testing bag with room: add 'A' to {B, C} (capacity=5)
expect: {B, C, A} (capacity=5)
actual: {B, C, A} (capacity=5)
PASS

testing bag with no room: add 'A' to {B, C} (capacity=2)
expect: {B, C, A} (capacity=4)
actual: {B, C} (capacity=4)
FAIL

Remember, you don't even need to have the program working to create a good testing method. Don't lose points unnecessarily for not writing tests! You can even write the tests first -- which is actually a practice that professionals use!

Grading

• 20 points for the output. Every method should produce correct results.
• 30 points for program design. This includes:
  • good testing
  • good understandability (including the output of your tests!)
  • good modularity and robustness (especially error-checking)

As always, practice good programming skills:

• Use good comments and variables names. Use Javadoc format for all comments.
• Test each method individually
• Use good debugging skills: tracing and checkpointing
• Be robust. Make sure you account for "abnormal" use of your code. What should happen if someone uses remove() on an empty bag?

Having trouble? Don't wait until the last minute! Come see me and get your $80 worth.

Gentle Reminder