public class SET<Key extends java.lang.Comparable<Key>> extends java.lang.Object implements java.lang.Iterable<Key>
This implementation uses a balanced binary search tree. It requires that the key type implements the Comparable interface and calls the compareTo() 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 isEmpty 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 and Description |
---|
SET()
Initializes an empty set.
|
Modifier and Type | Method and Description |
---|---|
void |
add(Key key)
Adds the key to the set if it is not already present.
|
Key |
ceil(Key key)
Returns the smallest key in the set greater than or equal to key.
|
boolean |
contains(Key key)
Does this symbol table contain the given key?
|
void |
delete(Key key)
Removes the key from the set if the key is present.
|
boolean |
equals(java.lang.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 this symbol table empty?
|
java.util.Iterator<Key> |
iterator()
Returns all of the keys in the symbol table as an iterator.
|
static void |
main(java.lang.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 key-value pairs in this symbol table.
|
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.
|
public void add(Key key)
key
- the key to addjava.lang.NullPointerException
- if key is nullpublic boolean contains(Key key)
key
- the keyjava.lang.NullPointerException
- if key is nullpublic void delete(Key key)
key
- the keyjava.lang.NullPointerException
- if key is nullpublic int size()
public boolean isEmpty()
public java.util.Iterator<Key> iterator()
public Key max()
java.util.NoSuchElementException
- if the set is emptypublic Key min()
java.util.NoSuchElementException
- if the set is emptypublic Key ceil(Key key)
key
- the keyjava.util.NoSuchElementException
- if the set is emptyjava.lang.NullPointerException
- if key is nullpublic Key floor(Key key)
key
- the keyjava.util.NoSuchElementException
- if the set is emptyjava.lang.NullPointerException
- if key is nullpublic SET<Key> union(SET<Key> that)
that
- the other setjava.lang.NullPointerException
- if that is nullpublic SET<Key> intersects(SET<Key> that)
that
- the other setjava.lang.NullPointerException
- if that is nullpublic boolean equals(java.lang.Object y)
equals
in class java.lang.Object
y
- the other setpublic java.lang.String toString()
toString
in class java.lang.Object
public static void main(java.lang.String[] args)