Dense Bag

Introduction

"Bag" is an abstract data type that is like a set, but allows duplication of elements. By "Dense Bag" we mean a bag that is capable of efficiently handling cases where some of the elements are repeated a huge number of times. For example, if the bag contains 100,000,000 copies of a particular item then you would not want to store 100,000,000 references to the item. We will use a Map, described later, to accomplish this.

What You Will Do

You will write a class called DenseBag, which will extend the AbstractCollection class. We will be employing Java generics, so your DenseBag can be used to store any type of objects the user desires. The DenseBag must support the "iterator" method, and so you will also be writing an inner class implementing an iterator over the DenseBag.

Data Structure

The DenseBag class will contain an instance variable of type Map<T, Integer> . This is the data structure we have chosen to represent the contents of the bag.

For example, if T happens to represent type "String", then we can imagine a DenseBag containing the following:
"apple", "apple", "apple", "duck", "duck", "zebra", "zebra", "zebra", "zebra"

In this case the underlying map would look like this:

KEY        VALUE
================
"apple"    3
"duck"     2
"zebra"    4

Implementation Details

In a Bag, removing an item removes a single instance of the item. For example, a Bag b could contain additional instances of the String "a" even after calling b.remove("a").

The iterator for a dense bag must iterate over all instances, including duplicates. In other words, if a bag contains 5 instances of the String "a", an iterator will generate the String "a" 5 times.

In addition to the methods defined in the Collection interface, the DenseBag class supports several additional methods: uniqueElements, getCount, and choose.

The class extends AbstractCollection in order to get implementations of addAll, removeAll, retainAll and containsAll. (We will not be over-riding those). All other methods defined in the Collection interface will be implemented here.

For more specific implementation details, please read the javadoc.

Grading

The public tests and release tests together will comprise 90% of your grade on the project. The remaining 10% will be "style grading", done by visual inspection. Be sure to use good variable names, proper indentation and use of braces, etc. Also be careful to avoid redundant code.

Web Accessibility