edu.princeton.cs.algs4

Class SET<Key extends java.lang.Comparable<Key>>

java.lang.Object

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

Type Parameters:

Key - the generic type of a key in this set

All Implemented Interfaces:

java.lang.Iterable<Key>

public class SET<Key extends java.lang.Comparable<Key>>
extends java.lang.Object
implements java.lang.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.

Even though this implementation include the method equals(), it does not support the method hashCode() because sets are mutable.

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.

Constructor Summary

Constructors

Constructor and Description
SET() Initializes an empty set.
SET(SET<Key> x) Initializes a new set that is an independent copy of the specified set.

Method Summary

Modifier and Type	Method and Description
void	add(Key key) Adds the key to this set (if it is not already present).
Key	ceiling(Key key) Returns the smallest key in this set greater than or equal to key.
boolean	contains(Key key) Returns true if this set contains the given key.
void	delete(Key key) Removes the specified key from this set (if the set contains the specified key).
boolean	equals(java.lang.Object other) Compares this set to the specified set.
Key	floor(Key key) Returns the largest key in this set less than or equal to key.
int	hashCode() This operation is not supported because sets are mutable.
SET<Key>	intersects(SET<Key> that) Returns the intersection of this set and that set.
boolean	isEmpty() Returns true if this set is empty.
java.util.Iterator<Key>	iterator() Returns all of the keys in this set, as an iterator.
static void	main(java.lang.String[] args) Unit tests the SET data type.
Key	max() Returns the largest key in this set.
Key	min() Returns the smallest key in this set.
int	size() Returns the number of keys in this set.
java.lang.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

getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Constructor Detail

SET

public SET()

Initializes an empty set.

SET

public SET(SET<Key> x)

Initializes a new set that is an independent copy of the specified set.

Parameters:

x - the set to copy

Method Detail

add

public void add(Key key)

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

Parameters:

key - the key to add

Throws:

java.lang.IllegalArgumentException - if key is null

contains

public boolean contains(Key key)

Returns true if this set contains the given key.

Parameters:

key - the key

Returns:

true if this set contains key; false otherwise

Throws:

java.lang.IllegalArgumentException - if key is null

delete

public void delete(Key key)

Removes the specified key from this set (if the set contains the specified key).

Parameters:

key - the key

Throws:

java.lang.IllegalArgumentException - if key is null

size

public int size()

Returns the number of keys in this set.

Returns:

the number of keys in this set

isEmpty

public boolean isEmpty()

Returns true if this set is empty.

Returns:

true if this set is empty; false otherwise

iterator

public java.util.Iterator<Key> iterator()

Returns all of the keys in this 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 java.lang.Iterable<Key extends java.lang.Comparable<Key>>

Returns:

an iterator to all of the keys in this set

max

public Key max()

Returns the largest key in this set.

Returns:

the largest key in this set

Throws:

java.util.NoSuchElementException - if this set is empty

min

public Key min()

Returns the smallest key in this set.

Returns:

the smallest key in this set

Throws:

java.util.NoSuchElementException - if this set is empty

ceiling

public Key ceiling(Key key)

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

Parameters:

key - the key

Returns:

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

Throws:

java.lang.IllegalArgumentException - if key is null

java.util.NoSuchElementException - if there is no such key

floor

public Key floor(Key key)

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

Parameters:

key - the key

Returns:

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

Throws:

java.lang.IllegalArgumentException - if key is null

java.util.NoSuchElementException - if there is no such key

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:

java.lang.IllegalArgumentException - 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:

java.lang.IllegalArgumentException - if that is null

equals

public boolean equals(java.lang.Object other)

Compares this set to the specified set.

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 java.lang.Object

Parameters:

other - the other set

Returns:

true if this set equals other; false otherwise

hashCode

public int hashCode()

This operation is not supported because sets are mutable.

Overrides:

hashCode in class java.lang.Object

Returns:

does not return a value

Throws:

java.lang.UnsupportedOperationException - if called

toString

public java.lang.String toString()

Returns a string representation of this set.

Overrides:

toString in class java.lang.Object

Returns:

a string representation of this set, enclosed in curly braces, with adjacent keys separated by a comma and a space

main

public static void main(java.lang.String[] args)

Unit tests the SET data type.

Parameters:

args - the command-line arguments