Package edu.princeton.cs.algs4

Class SET<Key extends Comparable<Key>>

  • Type Parameters:
    Key - the generic type of each key in this set
    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.

    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.

    Author:
    Robert Sedgewick, Kevin Wayne

    • Constructor Summary

      Constructors 
      Constructor 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

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method 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.
      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.
      void remove​(Key key)
      Removes the specified key from this set (if the set contains the specified key).
      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.

    • 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:
        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:
        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). This is equivalent to remove(), but we plan to deprecate delete().
        Parameters:
        key - the key
        Throws:
        IllegalArgumentException - if key is null

      • remove

        public void remove​(Key key)
        Removes the specified key from this set (if the set contains the specified key). This is equivalent to delete(), but we plan to deprecate delete().
        Parameters:
        key - the key
        Throws:
        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 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 Iterable<Key extends 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:
        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:
        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:
        IllegalArgumentException - if key is null
        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:
        IllegalArgumentException - if key is null
        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:
        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:
        IllegalArgumentException - if that is null

      • equals

        public boolean equals​(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 Object
        Parameters:
        other - the other set
        Returns:
        true if this set equals other; 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, enclosed in curly braces, with adjacent keys separated by a comma and a space

      • main

        public static void main​(String[] args)
        Unit tests the SET data type.
        Parameters:
        args - the command-line arguments