answer in java programming language
6. Simple Container Classes a. Given a bag, describe its contents (abstract value) after the series of operations: insert 42, insert 5, insert 56, insert 12, insert 29, insert 8 b. Given a sequence, describe its contents (abstract value) after the series of operations: addBefore 42, addAfter 5, addAfter 56, addBefore 12, addBefore 29, addBefore 8 c. How do the bag and sequence differ even though they contain the same values? d. Draw a picture of the internal contents (instance variables) of the sequence where the series was applied Be complete with your picture. e. Describe the representation of the sequence as we implemented it with a partially-filled array. 116 Chapter 37 Collection Classes FIGURE 3.1 Specification for the IntArrayBag Class 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. Parameters: initialCapacity--the initial capacity of this bag Precondition: initialCapacity is non-negative. Postcondition: This bag is empty and has the specified initial capacity. Throws: Illegal ArgumentException Indicates that initial Capacity is negative. Throws: OutOfMemoryError Indicates insufficient memory for allocating the bag. (continued An ADT for a Bag of Integers 117 (FIGURE 3.1 continued) 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. Parameters: 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. Parameters: 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. Parameters: 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 (continued) 118 Chapter 3 / Collection Classes (FIGURE 3.1 continued) 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. Parameters: 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. Parameters: minimum Capacity--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. Parameters: 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. (continued An ADT for a Bag of Integer 119 (FIGURE 3.1 continued) size public int size() Accessor method to determine the number of elements in this bar Returns: the number of elements in this bag trim To Size 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 bi, IntArrayBag b2) Create a new bag that contains all the elements from two other bags. Parameters: bl- the first of two bags b2-the second of two bags Precondition: Neither bl 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. The IntArrayBag Class-Demonstration Program With the specification in hand, we can write a program that uses a bag. We don't need to know what the instance variables of a bag are, and we don't need to know how the methods are implemented. As an example, a demonstration program appears in Figure 3.2. The program asks a user about the ages of fam- ily members. The user enters the ages followed by a negative number to indicate the end of the input. (Using a special value to end a list is a common technique called a sentinel value.) A typical dialogue with the program looks like this: 6. Simple Container Classes a. Given a bag, describe its contents (abstract value) after the series of operations: insert 42, insert 5, insert 56, insert 12, insert 29, insert 8 29 42 5 56 8 12 size: 6 b. Given a sequence, describe its contents (abstract value) after the series of operations: addBefore 42, addAfter 5, addAfter 56, addBefore 12, addBefore 29, addBefore 8 42 5 8 29 12 56 Size: 6 c. How do the bag and sequence differ even though they contain the same values? The order of the items is important in sequence, as is the concept of a current element d. Draw a picture of the internal contents (instance variables) of the sequence where the series was applied. Data: 42 5 8 29 12 56 ? ? ? ? manyltems 6 current 2 Be complete with your picture. e. Describe the representation of the sequence as we implemented it with a partially-filled array. Elements are in order and are stored from data[0] through data[manyltems-1). Current keeps track of index of current element
