Bags - Data Structures and Abstractions with Java - page 2

are specified abstractly and can differ in purpose according to the collection. Thus, a collection is
an abstraction and is an abstract data type. However, an ADT is not necessarily a collection.
To provide an example of a collection and of an abstract data type, we will specify and use the ADT
bag. In doing so we will provide a Java interface for our bag. Knowing just this interface, you will be able
to use a bag in a Java program. You do not need to know how the entries in the bag are represented or how
the bag operations are implemented. Indeed, your program will not depend on these specifics. As you will
see, this important program characteristic is what data abstraction is all about.

The Bag

1.1

Imagine a paper bag, a reusable cloth bag, or even a plastic bag. People use bags when they shop, pack a
lunch, or eat potato chips. Bags contain things. In everyday language, a bag is a kind of container. In Java,
however, a container is an object whose class extends the standard class Container . Such containers are
used in graphics programs. Rather than being considered a container, a bag in Java is a kind of collection.
What distinguishes a bag from other collections? A bag doesn't do much more than contain its items.
It doesn't order them in a particular way, nor does it prevent duplicate items. Most of its behaviors could be
performed by other kinds of collections. While describing the behaviors for the collection that we'll design
in this chapter, let's keep in mind that we are specifying an abstraction inspired by an actual physical bag.
For example, a paper bag holds things of various dimensions and shapes in no particular order and without
regard for duplicates. Our abstract bag will hold unordered and possibly duplicate objects, but let's insist
that these objects have the same or related types.

Note: A bag is a finite collection of objects in no particular order. A bag can contain dupli-
cate items.

A Bag's Behaviors
1.2

Since a bag contains a finite number of objects, reporting how many objects it contains could be
one of a bag's behaviors:

Get the number of items currently in the bag

Two related behaviors detect whether a bag is full or empty:
See whether the bag is full
See whether the bag is empty

1.3

We should be able to add and remove objects:

Add a given object to the bag
Remove an unspecified object from the bag
Remove an occurrence of a particular object from the bag, if possible
Remove all objects from the bag
While you hope that the bagger at the grocery store does not toss six cans of soup into a bag on top
of your bread and eggs, our add operation does not indicate where in the bag an object should go.
Remember that a bag does not order its contents. Likewise, the first remove operation just removes
any object it can. This operation is like reaching into a grab bag and pulling something out. On the
other hand, the second remove operation looks for a particular item in the bag. If you find it, you
take it out. If the bag contains several equal objects that satisfy your search, you remove any one of