Package algs13

Class ResizingArrayBag<Item>

java.lang.Object

algs13.ResizingArrayBag<Item>

All Implemented Interfaces:

Iterable<Item>

public class ResizingArrayBag<Item>
extends Object
implements Iterable<Item>

The ResizingArrayBag class represents a bag (or multiset) of generic items. It supports insertion and iterating over the items in arbitrary order.

This implementation uses a resizing array. See

invalid reference

LinkedBag

for a version that uses a singly linked list. The add operation takes constant amortized time; the isEmpty, and size operations take constant time. Iteration takes time proportional to the number of items.

For additional documentation, see Section 1.3 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

Author:

Robert Sedgewick, Kevin Wayne

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
private class	ResizingArrayBag.ArrayIterator

Field Summary

Fields

Modifier and Type	Field	Description
private Item[]	a
private static final int	INIT_CAPACITY
private int	n

Constructor Summary

Constructors

Constructor	Description
ResizingArrayBag()	Initializes an empty bag.

Method Summary

Modifier and Type	Method	Description
void	add(Item item)	Adds the item to this bag.
boolean	isEmpty()	Is this bag empty?
Iterator<Item>	iterator()	Returns an iterator that iterates over the items in the bag in arbitrary order.
static void	main(String[] args)	Unit tests the ResizingArrayBag data type.
private void	resize(int capacity)
int	size()	Returns the number of items in this bag.

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Field Details

INIT_CAPACITY

private static final int INIT_CAPACITY

See Also:

• Constant Field Values

a

private Item[] a

n

private int n

Constructor Details

ResizingArrayBag

public ResizingArrayBag()

Initializes an empty bag.

Method Details

isEmpty

public boolean isEmpty()

Is this bag empty?

Returns:

true if this bag is empty; false otherwise

size

public int size()

Returns the number of items in this bag.

Returns:

the number of items in this bag

resize

private void resize(int capacity)

add

public void add(Item item)

Adds the item to this bag.

Parameters:

item - the item to add to this bag

iterator

public Iterator<Item> iterator()

Returns an iterator that iterates over the items in the bag in arbitrary order.

Specified by:

iterator in interface Iterable<Item>

Returns:

an iterator that iterates over the items in the bag in arbitrary order

main

public static void main(String[] args)

Unit tests the ResizingArrayBag data type.

Parameters:

args - the command-line arguments