Question: --------------------------------------------------------------------------------------------- ResizableArrayBag.java (You may not need this class, however if you do it's here) --------------------------------------------------------------------------------------------- import java.util.Arrays; public final class ResizableArrayBag implements BagInterface { private
---------------------------------------------------------------------------------------------
ResizableArrayBag.java (You may not need this class, however if you do it's here) ---------------------------------------------------------------------------------------------
import java.util.Arrays;
public final class ResizableArrayBag
/** Creates an empty bag whose initial capacity is 25. */ public ResizableArrayBag() { this(DEFAULT_CAPACITY); } // end default constructor
/** Creates an empty bag having a given initial capacity. @param initialCapacity The integer capacity desired. */ public ResizableArrayBag(int initialCapacity) { checkCapacity(initialCapacity); // The cast is safe because the new array contains null entries @SuppressWarnings("unchecked") T[] tempBag = (T[])new Object[initialCapacity]; // Unchecked cast bag = tempBag; numberOfEntries = 0; initialized = true; } // end constructor
/** Creates a bag containing given entries. @param contents An array of objects. */ public ResizableArrayBag(T[] contents) { checkCapacity(contents.length); bag = Arrays.copyOf(contents, contents.length); numberOfEntries = contents.length; initialized = true; } // end constructor /** Adds a new entry to this bag. @param newEntry The object to be added as a new entry. @return True. */ public boolean add(T newEntry) { checkInitialization(); if (isArrayFull()) { doubleCapacity(); } // end if bag[numberOfEntries] = newEntry; numberOfEntries++; return true; } // end add
/** Retrieves all entries that are in this bag. @return A newly allocated array of all the entries in this bag. */ public T[] toArray() { checkInitialization(); // The cast is safe because the new array contains null entries. @SuppressWarnings("unchecked") T[] result = (T[])new Object[numberOfEntries]; // Unchecked cast for (int index = 0; index -1; // or >= 0 } // end contains /** Removes all entries from this bag. */ public void clear() { while (!isEmpty()) remove(); } // end clear /** Removes one unspecified entry from this bag, if possible. @return Either the removed entry, if the removal was successful, or null. */ public T remove() { checkInitialization(); T result = removeEntry(numberOfEntries - 1); return result; } // end remove /** Removes one occurrence of a given entry from this bag. @param anEntry The entry to be removed. @return True if the removal was successful, or false if not. */ public boolean remove(T anEntry) { checkInitialization(); int index = getIndexOf(anEntry); T result = removeEntry(index); return anEntry.equals(result); } // end remove // Locates a given entry within the array bag. // Returns the index of the entry, if located, // or -1 otherwise. // Precondition: checkInitialization has been called. private int getIndexOf(T anEntry) { int where = -1; boolean found = false; int index = 0; while (!found && (index -1, anEntry is in the array bag, and it // equals bag[where]; otherwise, anEntry is not in the array. return where; } // end getIndexOf // Removes and returns the entry at a given index within the array. // If no such entry exists, returns null. // Precondition: 0 = 0)) { result = bag[givenIndex]; // Entry to remove int lastIndex = numberOfEntries - 1; bag[givenIndex] = bag[lastIndex]; // Replace entry to remove with last entry bag[lastIndex] = null; // Remove reference to last entry numberOfEntries--; } // end if return result; } // end removeEntry // Returns true if the array bag is full, or false if not. private boolean isArrayFull() { return numberOfEntries >= bag.length; } // end isArrayFull // Doubles the size of the array bag. // Precondition: checkInitialization has been called. private void doubleCapacity() { int newLength = 2 * bag.length; checkCapacity(newLength); bag = Arrays.copyOf(bag, newLength); } // end doubleCapacity // Throws an exception if the client requests a capacity that is too large. private void checkCapacity(int capacity) { if (capacity > MAX_CAPACITY) throw new IllegalStateException("Attempt to create a bag whose capacity exceeds " + "allowed maximum of " + MAX_CAPACITY); } // end checkCapacity // Throws an exception if receiving object is not initialized. private void checkInitialization() { if (!initialized) throw new SecurityException ("Uninitialized object used " + "to call an ArrayBag method."); } // end checkInitialization } // end ResizableArrayBag ---------------------------------------------------------------------------------------------------------------------
BagInterface.java (You may not need this class, however if you do it's here) ---------------------------------------------------------------------------------------------------------------------
public interface BagInterface
/** Removes one unspecified entry from this bag, if possible. @return Either the removed entry, if the removal. was successful, or null. */ public T remove(); /** Removes one occurrence of a given entry from this bag. @param anEntry The entry to be removed. @return True if the removal was successful, or false if not. */ public boolean remove(T anEntry); /** Removes all entries from this bag. */ public void clear(); /** Counts the number of times a given entry appears in this bag. @param anEntry The entry to be counted. @return The number of times anEntry appears in the bag. */ public int getFrequencyOf(T anEntry); /** Tests whether this bag contains a given entry. @param anEntry The entry to locate. @return True if the bag contains anEntry, or false if not. */ public boolean contains(T anEntry); /** Retrieves all entries that are in this bag. @return A newly allocated array of all the entries in the bag. Note: If the bag is empty, the returned array is empty. */ public T[] toArray(); // public
/** Creates a new bag that combines the contents of this bag and anotherBag. @param anotherBag The bag that is to be added. @return A combined bag. */ // public BagInterface
SetInterface.java
---------------------------------------------------------------------------------------------------------------------
public interface SetInterface
/** Removes a specific entry from this set, if possible. @param anEntry The entry to be removed. @return True if the removal was successful, or false if not. */ public boolean remove(T anEntry); public T remove(); public void clear(); public boolean contains(T anEntry); public T[] toArray(); } // end SetInterface ---------------------------------------------------------------------------------------------------------------------
ResizableArrayBagDemo.java (You may not need this class, however if you do it's here) ---------------------------------------------------------------------------------------------------------------------
public class ResizableArrayBagDemo { public static void main(String[] args) { // A bag whose initial capacity is small BagInterface
testIsEmpty(aBag, false); String[] testStrings2 = {"A", "B", "C", "D", "Z"}; testFrequency(aBag, testStrings2); testContains(aBag, testStrings2); // Removing strings String[] testStrings3 = {"", "B", "A", "C", "Z"}; testRemove(aBag, testStrings3);
System.out.println(" Clearing the bag:"); aBag.clear(); testIsEmpty(aBag, true); displayBag(aBag); } // end main // Tests the method add. private static void testAdd(BagInterface // Tests the two remove methods. private static void testRemove(BagInterface // Tests the method isEmpty. // correctResult indicates what isEmpty should return. private static void testIsEmpty(BagInterface // Tests the method getFrequencyOf. private static void testFrequency(BagInterface // Tests the method toArray while displaying the bag. private static void displayBag(BagInterface --------------------------------------------------------------------------------------------- LinkedBag.java --------------------------------------------------------------------------------------------- public final class LinkedBag { private Node firstNode; // Reference to first node private int numberOfEntries; public LinkedBag() { firstNode = null; numberOfEntries = 0; } // end default constructor /** Sees whether this bag is empty. @return True if this bag is empty, or false if not. */ public boolean isEmpty() { return numberOfEntries == 0; } // end isEmpty /** Gets the number of entries currently in this bag. @return The integer number of entries currently in this bag. */ public int getCurrentSize() { return numberOfEntries; } // end getCurrentSize /** Adds a new entry to this bag. @param newEntry The object to be added as a new entry @return True if the addition is successful, or false if not. */ public boolean add(T newEntry) // OutOfMemoryError possible { // Add to beginning of chain: Node newNode = new Node(newEntry); newNode.next = firstNode; // Make new node reference rest of chain // (firstNode is null if chain is empty) firstNode = newNode; // New node is at beginning of chain numberOfEntries++; return true; } // end add /** Retrieves all entries that are in this bag. @return A newly allocated array of all the entries in this bag. */ public T[] toArray() { // The cast is safe because the new array contains null entries @SuppressWarnings("unchecked") T[] result = (T[])new Object[numberOfEntries]; // Unchecked cast int index = 0; Node currentNode = firstNode; while ((index { result[index] = currentNode.data; index++; currentNode = currentNode.next; } // end while return result; } // end toArray /** Produces a string equivalent of the linked list. @return A newly allocated String of all the entries in this bag. */ public String toString() { String x = " "; Node currentNode = firstNode; while ( currentNode != null ) { x = x + currentNode.data + " "; currentNode = currentNode.next; } // end while return x; } // end toArray /** Counts the number of times a given entry appears in this bag. @param anEntry The entry to be counted. @return The number of times anEntry appears in this bag. */ public int getFrequencyOf(T anEntry) { int frequency = 0; int counter = 0; Node currentNode = firstNode; while ((counter { if (anEntry.equals(currentNode.data)) { frequency++; } // end if counter++; currentNode = currentNode.next; } // end while return frequency; } // end getFrequencyOf /** Tests whether this bag contains a given entry. @param anEntry The entry to locate. @return True if the bag contains anEntry, or false otherwise. */ public boolean contains(T anEntry) { boolean found = false; Node currentNode = firstNode; while (!found && (currentNode != null)) { if (anEntry.equals(currentNode.data)) found = true; else currentNode = currentNode.next; } // end while return found; } // end contains // Locates a given entry within this bag. // Returns a reference to the node containing the entry, if located, // or null otherwise. private Node getReferenceTo(T anEntry) { boolean found = false; Node currentNode = firstNode; while (!found && (currentNode != null)) { if (anEntry.equals(currentNode.data)) found = true; else currentNode = currentNode.next; } // end while return currentNode; } // end getReferenceTo /** Removes all entries from this bag. */ public void clear() { while (!isEmpty()) remove(); } // end clear /** Removes one unspecified entry from this bag, if possible. @return Either the removed entry, if the removal was successful, or null. */ public T remove() { T result = null; if (firstNode != null) { result = firstNode.data; firstNode = firstNode.next; // Remove first node from chain numberOfEntries--; } // end if return result; } // end remove /** Removes one occurrence of a given entry from this bag, if possible. @param anEntry The entry to be removed. @return True if the removal was successful, or false otherwise. */ public boolean remove(T anEntry) { boolean result = false; Node nodeN = getReferenceTo(anEntry); if (nodeN != null) { nodeN.data = firstNode.data; // Replace located entry with entry in first node firstNode = firstNode.next; // Remove first node numberOfEntries--; result = true; } // end if return result; } // end remove private class Node { private T data; // Entry in bag private Node next; // Link to next node private Node(T dataPortion) { this(dataPortion, null); } // end constructor private Node(T dataPortion, Node nextNode) { data = dataPortion; next = nextNode; } // end constructor } // end Node } // end LinkedBag
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help