Class MultiSet

java.lang.Object
  MultiSet

public class MultiSet
extends java.lang.Object

Stores a number of objects without using extra space for duplicates, which are determined by equals(). No specific ordering of objects is guaranteed. Example use: store a probability distribution, use findKth to obtain a random number in that distribution.

Constructor Summary

MultiSet()
Produces a new, empty MultiSet.

Method Summary

void	add(java.lang.Object o) Adds the specified object once to the data structure.
void	add(java.lang.Object o, int times) Adds an object several times to the data structure.
java.lang.Object	findKth(int k) Gets an object stored in this MultiSet.
int	getMultiplicity(java.lang.Object o) Returns the multiplicity stored of the object in question, some nonnegative integer.
int	numEntries() Gets the number of distinct entries in this MultiSet.
int	size() Gets the number of entries, including multiplicity, in this MultiSet.
java.util.ArrayList	values() Gets a list of distinct objects stored in this MultiSet.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

MultiSet

public MultiSet()

Produces a new, empty MultiSet.

Method Detail

getMultiplicity

public int getMultiplicity(java.lang.Object o)

Returns the multiplicity stored of the object in question, some nonnegative integer.

Parameters:

o - the object in question

Returns:

the multiplicity of stated object or 0 if object is not stored

add

public void add(java.lang.Object o)

Adds the specified object once to the data structure.

Parameters:

o - the object in question

add

public void add(java.lang.Object o,
                int times)

Adds an object several times to the data structure. Note that add(o,1) is equivalent to add(o).

Parameters:

o - the object in question

times - a positive integer

Throws:

java.lang.IllegalArgumentException - if times is less than 1

numEntries

public int numEntries()

Gets the number of distinct entries in this MultiSet.

Returns:

the number of distinct entries

findKth

public java.lang.Object findKth(int k)

Gets an object stored in this MultiSet. The general contract of findKth is that if findKth(i) is called for each 0 <= i < size(), for an object O stored m times in this MultiSet, of the size() calls to findKth, m of the returns will be O. findKth returns null if no object is present at position k; if k is negative or greater than or equal to size().

Parameters:

k - the position of the object to return

Returns:

the object at position k or null if no object present

size

public int size()

Gets the number of entries, including multiplicity, in this MultiSet.

Returns:

the number of total entries

values

public java.util.ArrayList values()

Gets a list of distinct objects stored in this MultiSet. No particular order is guaranteed.

Returns:

an ArrayList containing the distinct objects