edu.princeton.cs.algorithms

Class SET<Key extends Comparable<Key>>

java.lang.Object

edu.princeton.cs.algorithms.SET<Key>

All Implemented Interfaces:

Iterable<Key>

public class SET<Key extends Comparable<Key>>
extends Object
implements Iterable<Key>

The SET class represents an ordered set of comparable keys. It supports the usual add, contains, and delete methods. It also provides ordered methods for finding the minimum, maximum, floor, and ceiling and set methods for union, intersection, and equality.

This implementation uses a balanced binary search tree. It requires that the key type implements the Comparable interface and calls the compareTo() and method to compare two keys. It does not call either equals() or hashCode(). The add, contains, delete, minimum, maximum, ceiling, and floor methods take logarithmic time in the worst case. The size, and is-empty operations take constant time. Construction takes constant time.

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

Author:

Robert Sedgewick, Kevin Wayne

Constructor Summary

Constructors

Constructor and Description
SET() Initializes an empty set.

Method Summary

Methods

Modifier and Type	Method and Description
void	add(Key key) Adds the key to the set if it is not already present.
Key	ceiling(Key key) Returns the smallest key in the set greater than or equal to key.
boolean	contains(Key key) Does the set contain the given key?
void	delete(Key key) Removes the key from the set if the key is present.
boolean	equals(Object y) Does this set equal y? Note that this method declares two empty sets to be equal even if they are parameterized by different generic types.
Key	floor(Key key) Returns the largest key in the set less than or equal to key.
SET<Key>	intersects(SET<Key> that) Returns the intersection of this set and that set.
boolean	isEmpty() Is the set empty?
Iterator<Key>	iterator() Returns all of the keys in the set, as an iterator.
static void	main(String[] args) Unit tests the SET data type.
Key	max() Returns the largest key in the set.
Key	min() Returns the smallest key in the set.
int	size() Returns the number of keys in the set.
String	toString() Returns a string representation of this set.
SET<Key>	union(SET<Key> that) Returns the union of this set and that set.

Methods inherited from class java.lang.Object

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

Constructor Detail

SET

public SET()

Initializes an empty set.

Method Detail

add

public void add(Key key)

Adds the key to the set if it is not already present.

Parameters:

key - the key to add

Throws:

NullPointerException - if key is null

contains

public boolean contains(Key key)

Does the set contain the given key?

Parameters:

key - the key

Returns:

true if the set contains key and false otherwise

Throws:

NullPointerException - if key is null

delete

public void delete(Key key)

Removes the key from the set if the key is present.

Parameters:

key - the key

Throws:

NullPointerException - if key is null

size

public int size()

Returns the number of keys in the set.

Returns:

the number of keys in the set

isEmpty

public boolean isEmpty()

Is the set empty?

Returns:

true if the set is empty, and false otherwise

iterator

public Iterator<Key> iterator()

Returns all of the keys in the set, as an iterator. To iterate over all of the keys in a set named set, use the foreach notation: for (Key key : set).

Specified by:

iterator in interface Iterable<Key extends Comparable<Key>>

Returns:

an iterator to all of the keys in the set

max

public Key max()

Returns the largest key in the set.

Returns:

the largest key in the set

Throws:

NoSuchElementException - if the set is empty

min

public Key min()

Returns the smallest key in the set.

Returns:

the smallest key in the set

Throws:

NoSuchElementException - if the set is empty

ceiling

public Key ceiling(Key key)

Returns the smallest key in the set greater than or equal to key.

Parameters:

key - the key

Returns:

the smallest key in the set greater than or equal to key

Throws:

NoSuchElementException - if there is no such key

NullPointerException - if key is null

floor

public Key floor(Key key)

Returns the largest key in the set less than or equal to key.

Parameters:

key - the key

Returns:

the largest key in the set table less than or equal to key

Throws:

NoSuchElementException - if there is no such key

NullPointerException - if key is null

union

public SET<Key> union(SET<Key> that)

Returns the union of this set and that set.

Parameters:

that - the other set

Returns:

the union of this set and that set

Throws:

NullPointerException - if that is null

intersects

public SET<Key> intersects(SET<Key> that)

Returns the intersection of this set and that set.

Parameters:

that - the other set

Returns:

the intersection of this set and that set

Throws:

NullPointerException - if that is null

equals

public boolean equals(Object y)

Does this set equal y? Note that this method declares two empty sets to be equal even if they are parameterized by different generic types. This is consistent with the behavior of equals() within Java's Collections framework.

Overrides:

equals in class Object

Parameters:

y - the other set

Returns:

true if the two sets are equal; false otherwise

toString

public String toString()

Returns a string representation of this set.

Overrides:

toString in class Object

Returns:

a string representation of this set, with the keys separated by single spaces

main

public static void main(String[] args)

Unit tests the SET data type.