ap.java.util
Class TreeSet

java.lang.Object
  ap.java.util.TreeSet

All Implemented Interfaces:

Set

public class TreeSet

extends java.lang.Object

implements Set

This collection implements the Set interface so that add, remove, and contains each execute in O(log n) time for a set of n elements. Though not required, the naming convention hints that a typical implementation will use a balanced tree. The 1.4 Sun JDK uses a red-black tree for implementation of this class. The TreeSet class is only used in the AB course.

Elements accessed via a TreeSet iterator will be returned in ascending order according to the natural order of the elements, that is using the element compareTo method. This means, for example, that a TreeSet's minimal element is returned by the first call of an iterator's next method.

Though not in the AP subset it's possible to construct a TreeSet from any java.util.Collection object, e.g., from a List or Set. Similarly, it is possible to add all the elements from any Collection to a set using the non-AP subset method addAll. Finally, it is possible to change the ordering property used by a TreeSet to something other than an object's natural order. This requires using a java.util.Comparator object, also not in the AP subset. The code below shows how to construct a copy of a set whose iterator accesses elements in descending rather than ascending order.

    public class ReverseComparator implements Comparator
    {
        // "reverse" the value of o1.compareTo(o2)
        public int compare(Object o1, Object o2)
        {
            Comparable c = (Comparable) o1;
            return -1 * c.compareTo(o2);
         }
    }

    // return a set whose items are accessed in descending order
    public TreeSet reverseCopy(Set s)
    {
        TreeSet rs = new TreeSet(new ReverseComparator());
        rs.addAll(s);
        return rs;
    }
 

Constructor Summary

TreeSet()
Construct an initially empty set.

Method Summary

boolean	add(java.lang.Object o) Adds the parameter as an element to this set if it is not already stored in this set.
boolean	contains(java.lang.Object x) Returns true if this set contains the element passed as an argument, otherwise returns false.
Iterator	iterator() Returns an Iterator that provides access to the the elements of this set.
boolean	remove(java.lang.Object x) Removes the argument from this set and returns true if the argument is in this set; if not present returns false.
int	size() Returns the number of elements in this set.

Methods inherited from class java.lang.Object

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

Constructor Detail

TreeSet

public TreeSet()

Construct an initially empty set.

Method Detail

add

public boolean add(java.lang.Object o)

Adds the parameter as an element to this set if it is not already stored in this set. If the element is added, the function returns true. If the element is not added because it is already stored in the set, the function returns false.

Specified by:

add in interface Set

Parameters:

o - is the element to be added to this set

Returns:

true if o is added, false if not added because it is already in the set

Throws:

ClassCastException - if the argument cannot be compared to elements already in this set

contains

public boolean contains(java.lang.Object x)

Returns true if this set contains the element passed as an argument, otherwise returns false. More specifically, returns true if this set contains an element e such that e.equals(o).

Specified by:

contains in interface Set

Parameters:

x - is the element being tested for inclusion in this set

Returns:

true if this set contains the argument, and false if the argument is not in this set.

Throws:

ClassCastException - if the argument cannot be compared to elements already in this set

remove

public boolean remove(java.lang.Object x)

Removes the argument from this set and returns true if the argument is in this set; if not present returns false.

Specified by:

remove in interface Set

Parameters:

x - is the element to be removed from this set

Returns:

true if element is removed, otherwise return false

Throws:

ClassCastException - if the argument cannot be compared to elements already in this set

size

public int size()

Description copied from interface: Set

Returns the number of elements in this set.

Specified by:

size in interface Set

Returns:

the number of elements in the set

iterator

public Iterator iterator()

Returns an Iterator that provides access to the the elements of this set. The elements are returned in ascending order.

Specified by:

iterator in interface Set

Returns:

an iterator that provides access to elements from this set in ascending order