Class GShuffleBag<E>

java.lang.Object
  GShuffleBag<E>

public class GShuffleBag<E>
extends java.lang.Object

An enlargeable continuous shuffled sequence generator. Basically it's like a List, Collections.shuffle(), remove(), and refilling/reshuffling once it's empty. However, it only uses a single array and the shuffling happens on the go (each next operation swapps two elements). Additionally, it's easier to use and less error prone.

The size, capacity, and next operations run in constant time. The add operation runs in amortized constant time (adding n elements requires O(n) time).

Single elements can only reoccur once this pass is finished. So, if an element was only added once it can be at most be drawn twice - at the end of one pass and at the beginning of the next pass.

See Also:

IntShuffleBag, ShuffleBag

Constructor Summary

GShuffleBag()
Constructs an empty bag with an initial capacity of 10 and the default source of randomness.

GShuffleBag(int capacity)
Constructs an empty bag with the specified initial capacity and the default source of randomness.

GShuffleBag(int capacity, java.util.Random gen)
Constructs an empty bag with the specified initial capacity and the specified source of randomness.

GShuffleBag(java.util.Random gen)
Constructs an empty bag with an initial capacity of 10 and the specified source of randomness.

Method Summary

void	add(E e) Puts the specified element into the bag and sets the cursor to the last position.
void	add(E e, int quantity) Puts the specified element several times into the bag and sets the cursor to the last position.
int	capacity() Returns the capacity of this bag.
E	next() Returns the next item from this bag.
int	size() Returns the number of elements in this bag.
void	trimToSize() Trims the capacity of this GShuffleBag instance to be the bag's current size.

Methods inherited from class java.lang.Object

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

Constructor Detail

GShuffleBag

public GShuffleBag()

Constructs an empty bag with an initial capacity of 10 and the default source of randomness.

Throws:

java.lang.IllegalArgumentException - if the specified initial capacity is negative

GShuffleBag

public GShuffleBag(java.util.Random gen)

Constructs an empty bag with an initial capacity of 10 and the specified source of randomness.

Parameters:

gen - the source of randomness to use to shuffle the bag

Throws:

java.lang.IllegalArgumentException - if the specified initial capacity is negative

GShuffleBag

public GShuffleBag(int capacity)

Constructs an empty bag with the specified initial capacity and the default source of randomness.

Parameters:

capacity - the initial capacity of this bag

Throws:

java.lang.IllegalArgumentException - if the specified initial capacity is negative

GShuffleBag

public GShuffleBag(int capacity,
                   java.util.Random gen)

Constructs an empty bag with the specified initial capacity and the specified source of randomness.

Parameters:

capacity - the initial capacity of this bag

gen - the source of randomness to use to shuffle this bag

Throws:

java.lang.IllegalArgumentException - if the specified initial capacity is negative

Method Detail

add

public void add(E e)

Puts the specified element into the bag and sets the cursor to the last position. Resetting the cursor makes elements which were added on the go as likely as older elements.

Parameters:

e - element to be added

add

public void add(E e,
                int quantity)

Puts the specified element several times into the bag and sets the cursor to the last position. Resetting the cursor makes elements which were added on the go as likely as older elements.

Parameters:

e - element to be added

quantity - the quantity

next

public E next()

Returns the next item from this bag.

The cursor moves from back to front. If the cursor position is smaller than 1 the element at index 0 is returned and the curor is reset to size-1.

Otherwise randomly picked elements from index 0 to the cursor position (inclusive) are swapped with the element at the cursor position. Afterwards the cursor gets moved one step and the element at the old cursor position is returned.

Returns:

the next item from this bag

trimToSize

public void trimToSize()

Trims the capacity of this GShuffleBag instance to be the bag's current size. Use this to minimize the storage of a GShuffleBag instance.

capacity

public int capacity()

Returns the capacity of this bag.

Returns:

the capacity of this bag

size

public int size()

Returns the number of elements in this bag.

Returns:

the number of elements in this bag