Key
- the generic type of a key in this setpublic class SET<Key extends Comparable<Key>>
extends Object
implements Iterable<Key>
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.
This implementation uses a balanced binary search tree. It requires that For additional documentation, see Section 4.4 of Computer Science: An Interdisciplinary Approach by Robert Sedgewick and Kevin Wayne.
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.
|
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(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(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.
|
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 addIllegalArgumentException
- if key
is null
public boolean contains(Key key)
key
- the keytrue
if this set contains key
;
false
otherwiseIllegalArgumentException
- if key
is null
public void delete(Key key)
key
- the keyIllegalArgumentException
- if key
is null
public int size()
public boolean isEmpty()
true
if this set is empty;
false
otherwisepublic java.util.Iterator<Key> iterator()
set
, use the
foreach notation: for (Key key : set)
.public Key max()
java.util.NoSuchElementException
- if this set is emptypublic Key min()
java.util.NoSuchElementException
- if this set is emptypublic Key ceiling(Key key)
key
.key
- the keykey
IllegalArgumentException
- if key
is null
java.util.NoSuchElementException
- if there is no such keypublic Key floor(Key key)
key
.key
- the keykey
IllegalArgumentException
- if key
is null
java.util.NoSuchElementException
- if there is no such keypublic SET<Key> union(SET<Key> that)
that
- the other setIllegalArgumentException
- if that
is null
public SET<Key> intersects(SET<Key> that)
that
- the other setIllegalArgumentException
- if that
is null
public boolean equals(Object other)
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.
equals
in class Object
other
- the other settrue
if this set equals other
;
false
otherwisepublic int hashCode()
hashCode
in class Object
UnsupportedOperationException
- if calledpublic String toString()
toString
in class Object
public static void main(String[] args)
SET
data type.args
- the command-line arguments