Chapter 1

Chapter 1: Bags

The ADT Bag

  • Definition: A finite collection of objects in no particular order.

  • Properties:

    • Can contain duplicate items.

  • Possible behaviors:

    • Get the number of items in the bag.

    • Check if the bag is empty.

    • Add objects to the bag.

    • Remove objects from the bag.

CRC Card for the Bag Class

Responsibilities:

  • Get the number of items currently in the bag.

  • Check whether the bag is empty.

  • Add a given object to the bag.

  • Remove an unspecified object from the bag.

  • Remove a particular object from the bag (if possible).

  • Remove all objects from the bag.

  • Count occurrences of a certain object in the bag.

  • Test whether the bag contains a specific object.

  • Look at all objects present in the bag.

Collaborations:

  • Defines the class of objects that the bag can contain.

Specifying a Bag

  • Importance of describing data and specifying methods in detail.

  • Options when an 'add' operation cannot complete:

    • Do nothing.

    • Leave the bag unchanged but signal the client.

  • Note which methods change the object and which do not.

Using UML Notation to Specify a Class

  • Class Specifications in UML:

    • Bag +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[]

Design Decisions

  • Considerations for managing unusual conditions:

    • Assume it won’t happen, ignore it, or guess the client's intention.

    • Possible responses include returning a value that signals a problem, a boolean, or throwing an exception.

Interface for a Bag (Part 1)

BagInterface Definition
/** An interface that describes the operations of a bag of objects. */
public interface BagInterface<T> {
  /**
   * Gets the current number of entries in this bag.
   * @return The integer number of entries currently in the bag.
   */
  public int getCurrentSize();

  /**
   * Sees whether this bag is empty.
   * @return True if the bag is empty, or false if not.
   */
  public boolean isEmpty();

  /**
   * 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);

  /**
   * Removes one unspecified entry from this bag, if possible.
   * @return Either the removed entry, if the removal was successful, or null.
   */
  public T remove();

Interface for a Bag (Part 2)

Continuation of BagInterface Definition
/**
 * 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 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 find.
 * @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();
}
// end BagInterface

Using the ADT Bag

Example: Online Shopping Cart
/** A class that maintains a shopping cart for an online store. */
public class OnlineShopper {
  public static void main(String[] args) {
    Item[] items = {new Item("Bird feeder", 2050),
                     new Item("Squirrel guard", 1547),
                     new Item("Bird bath", 4499),
                     new Item("Sunflower seeds", 1295)};
    BagInterface<Item> shoppingCart = new Bag<>();
    int totalCost = 0;

    // Statements that add selected items to the shopping cart:
    for (int index = 0; index < items.length; index++) {
      Item nextItem = items[index]; // Simulate getting item from shopper
      shoppingCart.add(nextItem);
      totalCost = totalCost + nextItem.getPrice();
    } // end for

    // Simulate checkout
    while (!shoppingCart.isEmpty())
      System.out.println(shoppingCart.remove());
    System.out.println("Total cost: " + "\t$" + totalCost / 100 + "." + totalCost % 100);
  } // end main
} // end OnlineShopper
Output:

  • Sunflower seeds $12.95

  • Bird bath $44.99

  • Squirrel guard $15.47

  • Bird feeder $20.50

  • Total cost: $93.91

Example: Piggy Bank

Piggy Bank Class Implementation
/** A class that implements a piggy bank by using a bag. */
public class PiggyBank {
  private BagInterface<Coin> coins;

  public PiggyBank() {
    coins = new ArrayBag<>();
  } // end default constructor

  public boolean add(Coin aCoin) { return coins.add(aCoin); }

  public Coin remove() { return coins.remove(); }

  public boolean isEmpty() { return coins.isEmpty(); }
} // end PiggyBank
Using the Piggy Bank Example
/** A class that demonstrates the class PiggyBank. */
public class PiggyBankExample {
  public static void main(String[] args) {
    PiggyBank myBank = new PiggyBank();
    addCoin(new Coin(1, 2010), myBank);
    addCoin(new Coin(5, 2011), myBank);
    addCoin(new Coin(10, 2000), myBank);
    addCoin(new Coin(25, 2012), myBank);

    System.out.println("Removing all the coins:");
    int amountRemoved = 0;
    while (!myBank.isEmpty()) {
      Coin removedCoin = myBank.remove();
      System.out.println("Removed a " + removedCoin.getCoinName() + ".");
      amountRemoved = amountRemoved + removedCoin.getValue();
    } // end while
    System.out.println("All done. Removed " + amountRemoved + " cents.");
  } // end main

  private static void addCoin(Coin aCoin, PiggyBank aBank) {
    if (aBank.add(aCoin))
      System.out.println("Added a " + aCoin.getCoinName() + ".");
    else
      System.out.println("Tried to add a " + aCoin.getCoinName() + ", but couldn't");
  } // end addCoin
} // end PiggyBankExample
Program Output:

  • Added a PENNY.

  • Added a NICKEL.

  • Added a DIME.

  • Added a QUARTER.

  • Removing all the coins:

    • Removed a QUARTER.

    • Removed a DIME.

    • Removed a NICKEL.

    • Removed a PENNY.

  • All done. Removed 41 cents.

Observations about Vending Machines

  • They can perform only the tasks presented by the machine’s interface.

  • Users must understand the tasks available.

  • Accessing the inside of the machine is not necessary for functionality.

  • Machines can still be used even if their internal workings are unknown.

Observations about ADT Bag

  • The ADT bag can perform tasks specific to it.

  • Users must adhere to the specifications of the operations of the ADT.

  • Data cannot be accessed directly without operations defined by the ADT.

  • The ADT remains usable, even with new implementations.

Java Class Library: The Interface Set

SetInterface Definition
/** An interface that describes the operations of a set of objects. */
public interface SetInterface<T> {
  public int getCurrentSize();
  public boolean isEmpty();

  /** Adds a new entry to this set, avoiding duplicates.
   * @param newEntry The object to be added as a new entry.
   * @return True if the addition is successful, or false if the item already is in the set.
   */
  public boolean add(T newEntry);

  /** 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