Suppose that you want to implement a bag class to hold non-negative integers, and you know that the biggest number in the bag will never be more than a few thousand. One approach for implementing this bag is to have a private instance variable that is an array of integers called count with indexes from 0 to M (where M is the maximum number in the bag). If the bag contains six copies of a number n, then the object has count[n] equal to 6 to represent this fact.

For this project, reimplement the bag class from Figure 3.1 using this idea. You will have an entirely new set of private instance variables; for the public methods, you may delete the capacity methods, but please add a new method that the programmer can use to specify the maximum number that he or she anticipates putting into the bag. Also note that the add method must check to see whether the current maximum index of the array is at least as big as the new number. If not, then the array size must be increased.

Figure 3.1

Class IntArrayBag

public class IntArrayBag from the package edu.colorado.collections

An IntArrayBag is a collection of int numbers.

Limitations:

(1) The capacity of one of these bags can change after it’s created, but the maximum capacity is limited by the amount of free memory on the machine. The constructor, add, clone, and union will result in an OutOfMemoryError when free memory is exhausted.

(2) A bag’s capacity cannot exceed the largest integer, 2,147,483,647 (Integer.MAX_VALUE). Any attempt to create a larger capacity results in failure due to an arithmetic overflow.

(3) Because of the slow linear algorithms of this class, large bags will have poor performance.

Specification

♦ Constructor for the IntArrayBag

public IntArrayBag( )

Initialize an empty bag with an initial capacity of 10. Note that the add method works efficiently (without needing more memory) until this capacity is reached.

Postcondition:

This bag is empty and has an initial capacity of 10.

Throws: OutOfMemoryError

Indicates insufficient memory for new int[10].

♦ Second Constructor for the IntArrayBag

public IntArrayBag(int initialCapacity)

Initialize an empty bag with a specified initial capacity.

Parameter:

initialCapacity – the initial capacity of this bag

Precondition:

initialCapacity is non-negative.

Postcondition:

This bag is empty and has the specified initial capacity.

Throws: IllegalArgumentException

Indicates that initialCapacity is negative.

Throws: OutOfMemoryError

Indicates insufficient memory for allocating the bag.

♦ add

public void add(int element)

Add a new element to this bag. If this new element would take this bag beyond its current capacity, then the capacity is increased before adding the new element.

Parameter:

element – the new element that is being added

Postcondition:

A new copy of the element has been added to this bag.

Throws: OutOfMemoryError

Indicates insufficient memory for increasing the capacity.

Note:

Creating a bag with capacity beyond Integer.MAX_VALUE causes arithmetic overflow.

♦ addAll

public void addAll(IntArrayBag addend)

Add the contents of another bag to this bag.

Parameter:

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.

Throws: NullPointerException

Indicates that addend is null.

Throws: OutOfMemoryError

Indicates insufficient memory to increase the size of this bag.

Note:

Creating a bag with capacity beyond Integer.MAX_VALUE causes arithmetic overflow.

♦ addMany

public void addMany(int... elements)

Add a variable number of new elements to this bag. If these new elements would take this bag

beyond its current capacity, then the capacity is increased before adding the new elements.

Parameter:

elements – a variable number of new elements that are all being added

Postcondition:

New copies of all the elements have been added to this bag.

Throws: OutOfMemoryError

Indicates insufficient memory for increasing the capacity.

Note:

Creating a bag with capacity beyond Integer.MAX_VALUE causes arithmetic overflow.

♦ clone

public IntArrayBag clone( )

Generate a copy of this bag.

Returns:

The return value is a copy of this bag. Subsequent changes to the copy will not affect the original, nor vice versa. The return value must be typecast to an IntArrayBag before it is used.

Throws: OutOfMemoryError

Indicates insufficient memory for creating the clone.

♦ countOccurrences

public int countOccurrences(int target)

Accessor method to count the number of occurrences of a particular element in this bag.

Parameter:

target – the element that needs to be counted

Returns:
the number of times that target occurs in this bag

♦ ensureCapacity

public void ensureCapacity(int minimumCapacity)

Change the current capacity of this bag.

Parameter:

minimumCapacity – the new capacity for this bag

Postcondition:

This bag’s capacity has been changed to at least minimumCapacity. If the capacity was already at or greater than minimumCapacity, then the capacity is left unchanged.

Throws: OutOfMemoryError

Indicates insufficient memory for new int[minimumCapacity].

♦ getCapacity

public int getCapacity( )

Accessor method to determine the current capacity of this bag. The add method works efficiently (without needing more memory) until this capacity is reached.

Returns:

the current capacity of this bag

♦ remove

public boolean remove(int target)

Remove one copy of a specified element from this bag.

Parameter:

target – the element to remove from this bag

Postcondition:

If target was found in this bag, then one copy of target has been removed and the method returns true. Otherwise, this bag remains unchanged, and the method returns false.

♦ size

public int size( )

Accessor method to determine the number of elements in this bag.

Returns:

the number of elements in this bag

♦ trimToSize

public void trimToSize( )

Reduce the current capacity of this bag to its actual size (i.e., the number of elements it contains).

Postcondition:

This bag’s capacity has been changed to its current size.

Throws: OutOfMemoryError

Indicates insufficient memory for altering the capacity.

♦ union

public static IntArrayBag union(IntArrayBag b1, IntArrayBag b2)

Create a new bag that contains all the elements from two other bags.

Parameters:

b1 – the first of two bags

b2 – the second of two bags

Precondition:

Neither b1 nor b2 is null.

Returns:

a new bag that is the union of b1 and b2

Throws: NullPointerException

Indicates that one of the arguments is null.

Throws: OutOfMemoryError

Indicates insufficient memory for the new bag.

Note:

Creating a bag with capacity beyond Integer.MAX_VALUE causes arithmetic overflow.