Summary Ch02_Bag_Implementations_That_Use_Arrays

Data Structures and Abstractions with Java ™
5th Edition

Chapter 2


Bag
Implementations
That Use Arrays

Copyright © 2019, 2015, 2012 Pearson Education, Inc. All Rights Reserved

,Fixed-Size Array to Implement the ADT Bag




FIGURE 2-1 A classroom that contains desks in fixed positions
Copyright © 2019, 2015, 2012 Pearson Education, Inc. All Rights Reserved

, UML for a fixed size ArrayBag
ArrayBag
-bag: T[]
-numberOfEntries: integer
-DEFAULT_CAPACITY: integer
+getCurrentSize(): integer
+isEmpty(): boolean
+add(newEntry: T): boolean
+remove(): T
+remove(anEntry: T): boolean
+clear(): void
+getFrequencyOf(anEntry: T):
integer
+contains(anEntry: T): boolean
+toArray(): T[]
–isArrayFull(): boolean


FIGURE 2-2 UML notation for the class ArrayBag, including the class’s data fields
Copyright © 2019, 2015, 2012 Pearson Education, Inc. All Rights Reserved

, The Class ArrayBag (Part 1)
/**A class of bags whose entries are stored in a fixed-size array.
INITIAL, INCOMPLETE DEFINITION; no security checks */
public final class ArrayBag<T> implements BagInterface<T>
{
private final T[] bag;
private int numberOfEntries;
private static final int DEFAULT_CAPACITY = 25;

/** Creates an empty bag whose initial capacity is 25. */
public ArrayBag()
{
this(DEFAULT_CAPACITY);
} // end default constructor

/** Creates an empty bag having a given initial capacity.
@param desiredCapacity The integer capacity desired. */
public ArrayBag(int desiredCapacity)
{
// The cast is safe because the new array contains null entries.
@SuppressWarnings("unchecked")
T[] tempBag = (T[])new Object[desiredCapacity]; // Unchecked cast
bag = tempBag;
numberOfEntries = 0;
} // end constructor

LISTING 2-1 An outline of the class ArrayBag
Copyright © 2019, 2015, 2012 Pearson Education, Inc. All Rights Reserved