cs132.markov
Class DenseBag<E>

java.lang.Object
  java.util.AbstractCollection<E>
      cs132.markov.DenseBag<E>

All Implemented Interfaces:

java.lang.Iterable<E>, java.util.Collection<E>

public class DenseBag<E>
extends java.util.AbstractCollection<E>

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 efficienctly 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). You don't need to worry about a DenseBag containing more than Integer.MAX_VALUE instances of an Object. 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 may extend AbstractCollection in order to get implementations of addAll, removeAll, retainAll and containsAll. All other methods defined in the Collection interface must be implemented here.

Constructor Summary

DenseBag()
Initialize a new, empty DenseBag

Method Summary

boolean	add(E o) Adds an instance of o to the Bag
E	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(E 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<E>	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<E>	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).

Methods inherited from class java.util.AbstractCollection

addAll, clear, containsAll, isEmpty, removeAll, retainAll, toArray, toArray

Methods inherited from class java.lang.Object

getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

DenseBag

public DenseBag()

Initialize a new, empty DenseBag

Method Detail

add

public boolean add(E o)

Adds an instance of o to the Bag

Specified by:

add in interface java.util.Collection<E>

Overrides:

add in class java.util.AbstractCollection<E>

Returns:

always returns true, since added an element to a bag always changes it

choose

public E 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. This operation can take time proportional to the number of unique objects in the Bag, but no more. This operation should not affect the Bag.

Parameters:

r - Random number generator

Returns:

randomly choosen element

contains

public boolean contains(java.lang.Object o)

Returns true if the Bag contains one or more instances of o

Specified by:

contains in interface java.util.Collection<E>

Overrides:

contains in class java.util.AbstractCollection<E>

equals

public boolean equals(java.lang.Object o)

Tests if two DenseBags are equal. Comparing a DenseBag to an instance of any other class should return false;

Specified by:

equals in interface java.util.Collection<E>

Overrides:

equals in class java.lang.Object

getCount

public int getCount(E o)

Return the number of instances of a particular object in the bag. Return 0 if it doesn't exist at all.

Parameters:

o - object of interest

Returns:

number of times that object occurs in the Bag

hashCode

public 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).

Specified by:

hashCode in interface java.util.Collection<E>

Overrides:

hashCode in class java.lang.Object

iterator

public java.util.Iterator<E> 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 iterator over 3 a's. There is a test for the honors section to see if the iterator correctly handles Iterator.remove(). Students in non-honors section do not have to implement remove() in their DenseBag iterator (it should throw UnsupportedOperationException if not implemented).

Specified by:

iterator in interface java.lang.Iterable<E>

Specified by:

iterator in interface java.util.Collection<E>

Specified by:

iterator in class java.util.AbstractCollection<E>

remove

public boolean remove(java.lang.Object o)

Decrements the number of instances of o in the Bag.

Specified by:

remove in interface java.util.Collection<E>

Overrides:

remove in class java.util.AbstractCollection<E>

Returns:

return true if and only if at least one instance of o exists in the Bag and was removed.

size

public int size()

Total number of instances of any object in the Bag (counting duplicates)

Specified by:

size in interface java.util.Collection<E>

Specified by:

size in class java.util.AbstractCollection<E>

toString

public java.lang.String toString()

Generate a String representation of the DenseBag. This will be useful for your own debugging purposes, but will not be tested other to ensure that it does return a String and that two different DenseBags return two different Strings.

Overrides:

toString in class java.util.AbstractCollection<E>

uniqueElements

public java.util.Set<E> 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).

Returns:

A set of elements in the Bag