public class DenseBag<T>
extends java.util.AbstractCollection<T>
implements java.io.Serializable
The DenseBag class implements a Set-like collection that allows duplicates (a lot of them).
The DenseBag class provides Bag semantics: it represents a collection with duplicates. The "Dense" part of the class name comes from the fact that the class needs to efficiently handle the case where the bag contains 100,000,000 copies of a particular item (e.g., don't store 100,000,000 references to the item).
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.
| Constructor and Description |
|---|
DenseBag()
Initialize a new, empty DenseBag
|
| Modifier and Type | Method and Description |
|---|---|
boolean |
add(T o)
Adds an instance of o to the Bag
|
boolean |
addMany(T o,
int count)
Adds multiple instances of o to the Bag.
|
T |
choose(java.util.Random r)
Given a random number generator, randomly choose an element from the Bag
according to the distribution of objects in the Bag (e.g., if a Bag
contains 7 a's and 3 b's, then 70% of the time choose should return an a,
and 30% of the time it should return a b.
|
boolean |
contains(java.lang.Object o)
Returns true if the Bag contains one or more instances of o
|
boolean |
equals(java.lang.Object o)
Tests if two DenseBags are equal.
|
int |
getCount(java.lang.Object o)
Return the number of instances of a particular object in the bag.
|
int |
hashCode()
Return a hashCode that fulfills the requirements for hashCode (such as
any two equal DenseBags must have the same hashCode) as well as desired
properties (two unequal DenseBags will generally, but not always, have
unequal hashCodes).
|
java.util.Iterator<T> |
iterator()
Returns an iterator over the elements in a dense bag.
|
boolean |
remove(java.lang.Object o)
Decrements the number of instances of o in the Bag.
|
int |
size()
Total number of instances of any object in the Bag (counting duplicates)
|
java.lang.String |
toString()
Generate a String representation of the DenseBag.
|
java.util.Set<T> |
uniqueElements()
return a Set of the elements in the Bag (since the returned value is a
set, it will contain one value for each UNIQUE value in the Bag).
|
public java.lang.String toString()
toString in class java.util.AbstractCollection<T>public boolean equals(java.lang.Object o)
equals in interface java.util.Collection<T>equals in class java.lang.Objectpublic int hashCode()
hashCode in interface java.util.Collection<T>hashCode in class java.lang.Objectpublic java.util.Iterator<T> iterator()
Returns an iterator over the elements in a dense bag. Note that if a Dense bag contains 3 a's, then the iterator must iterate over 3 a's individually.
public java.util.Set<T> uniqueElements()
public int getCount(java.lang.Object o)
o - object of interestpublic T choose(java.util.Random r)
r - Random number generatorpublic boolean contains(java.lang.Object o)
public boolean add(T o)
public boolean addMany(T o, int count)
o - the element to addcount - the number of instances of o to addpublic boolean remove(java.lang.Object o)