AVLSet

Class AVLSet<E>

java.lang.Object
  java.util.AbstractCollection<E>
      java.util.AbstractSet<E>
          AVLSet<E>

All Implemented Interfaces:: Iterable<E>, Collection<E>, Set<E>, SortedSet<E>

public class AVLSet<E>
extends java.util.AbstractSet<E>
implements java.util.SortedSet<E>
extends java.util.AbstractSet<E>
implements java.util.SortedSet<E>

This class implements the SortedSet interface, backed by an AVL tree. This class guarantees that the sorted set will be in ascending element order, sorted according to the natural order of the elements (see Comparable), or by the comparator provided at set creation time, depending on which constructor is used.

This implementation provides guaranteed log(n) time cost for the operations add, remove and contains.

Note that the ordering maintained by the set (whether or not an explicit comparator is provided) must be consistent with equals because the Set interface is defined in terms of the equals operation, but an AVLSet instance performs all key comparisons using its compareTo (or compare) method.

Version:: CSI3050 Spring 2006
Author:: Dr. Jody Paul

Constructor Summary
`AVLSet()` Constructs a new, empty set, sorted according to the elements' natural order.
`AVLSet(Collection<? extends E> coll)` Constructs a new set containing the elements in the specified collection, sorted according to the elements' natural order.
`AVLSet(Comparator<? super E> comp)` Constructs a new, empty set, sorted according to the specified comparator.
`AVLSet(SortedSet<E> set)` Constructs a new set containing the same elements as the specified sorted set, sorted according to the same ordering as the specified set.

Method Summary
`boolean`	`add(E o)` Adds the specified element to this set if it is not already present.
`boolean`	`addAll(Collection<? extends E> coll)` Adds all of the elements in the specified collection to this set.
`void`	`clear()` Removes all of the elements from this set.
`Comparator<? super E>`	`comparator()` Returns the comparator associated with this sorted set, or `null` if it uses its elements' natural ordering.
`boolean`	`contains(Object o)` Returns `true` if this set contains the specified element.
`E`	`first()` Returns the first (lowest) element currently in this sorted set.
`SortedSet<E>`	`headSet(E toElement)` Returns a view of the portion of this set whose elements are strictly less than `toElement`.
`boolean`	`isEmpty()` Returns `true` if this set contains no elements.
`Iterator<E>`	`iterator()` Returns an iterator over the elements in this set.
`E`	`last()` Returns the last (highest) element currently in this sorted set.
`boolean`	`remove(Object o)` Removes the specified element from this set if it is present.
`int`	`size()` Returns the number of elements in this set (its cardinality).
`SortedSet<E>`	`subSet(E fromElement, E toElement)` Returns a view of the portion of this set whose elements range from `fromElement`, inclusive, to `toElement`, exclusive.
`SortedSet<E>`	`tailSet(E fromElement)` Returns a view of the portion of this sorted set whose elements are greater than or equal to `fromElement`.

Methods inherited from class java.util.AbstractSet
`equals, hashCode, removeAll`

Methods inherited from class java.util.AbstractCollection
`add, addAll, containsAll, retainAll, toArray, toArray, toString`

Methods inherited from class java.lang.Object
`clone, finalize, getClass, notify, notifyAll, wait, wait, wait`

Methods inherited from interface java.util.SortedSet
`headSet, subSet, tailSet`

Methods inherited from interface java.util.Set
`add, addAll, containsAll, equals, hashCode, removeAll, retainAll, toArray, toArray`

Constructor Detail

AVLSet

public AVLSet()

Constructs a new, empty set, sorted according to the elements' natural order.

AVLSet

public AVLSet(Collection<? extends E> coll)

Constructs a new set containing the elements in the specified collection, sorted according to the elements' natural order. All keys inserted into the set must implement the Comparable interface. All such keys must be mutually comparable: k1.compareTo(k2) must not throw a ClassCastException for any elements k1 and k2 in the set.

Parameters:: coll - The elements that will comprise the new set.
Throws:: ClassCastException - if the keys in the specified collection are not comparable, or are not mutually comparable.; NullPointerException - - if the specified collection is null.
See Also:: Comparable, Collection

AVLSet

public AVLSet(Comparator<? super E> comp)

Constructs a new, empty set, sorted according to the specified comparator. All elements inserted into the set must be mutually comparable by the specified comparator: comparator.compare(e1, e2) must not throw a ClassCastException for any elements e1 and e2 in the set. If the user attempts to add an element to the set that violates this constraint, the add(Object) call will throw a ClassCastException.

Parameters:: comp - the comparator that will be used to sort this set. A null value indicates that the elements' natural ordering should be used.

AVLSet

public AVLSet(SortedSet<E> set)

Constructs a new set containing the same elements as the specified sorted set, sorted according to the same ordering as the specified set.

Parameters:: set - the sorted set whose elements will comprise the new set.
Throws:: NullPointerException - if the specified sorted set is null.

Method Detail

add

public boolean add(E o)

Adds the specified element to this set if it is not already present.

Parameters:: o - the element to be added to this set
Returns:: true if the set did not already contain the specified element
Throws:: ClassCastException - if the specified object cannot be compared with the elements currently in the set

addAll

public boolean addAll(Collection<? extends E> coll)

Adds all of the elements in the specified collection to this set.

Parameters:: coll - the elements to be added
Returns:: trueif this set changed as a result of the call
Throws:: ClassCastException - if the specified object cannot be compared with the elements currently in the set; NullPointerException - if the specified collection is null

clear

public void clear()

Removes all of the elements from this set.

Specified by:: clear in interface Collection
Specified by:: clear in interface Set
Overrides:: clear in class AbstractCollection

comparator

public Comparator<? super E> comparator()

Returns the comparator associated with this sorted set, or null if it uses its elements' natural ordering.

Specified by:: comparator in interface SortedSet

Returns:: the comparator associated with this sorted set or null if natural ordering is used

contains

public boolean contains(Object o)

Returns true if this set contains the specified element.

Specified by:: contains in interface Collection
Specified by:: contains in interface Set
Overrides:: contains in class AbstractCollection

Parameters:: o - the object to be checked for membership in this set.
Returns:: true if the specified element is in this set
Throws:: ClassCastException - if the specified object cannot be compared with the elements currently in the set

first

public E first()

Returns the first (lowest) element currently in this sorted set.

Specified by:: first in interface SortedSet

Returns:: the first (lowest) element currently in this sorted set
Throws:: NoSuchElementException - if the sorted set is empty

headSet

public SortedSet<E> headSet(E toElement)

Returns a view of the portion of this set whose elements are strictly less than toElement. The returned sorted set is backed by this set, so changes in the returned sorted set are reflected in this set, and vice-versa. The returned sorted set supports all optional set operations.

Parameters:: toElement - high endpoint (exclusive) of the headSet
Returns:: a view of the portion of this set whose elements are strictly less than toElement
Throws:: ClassCastException - if toElement is not compatible with this set's comparator, or, if the set has no comparator, if toElement does not implement Comparable.; IllegalArgumentException - if this set is itself a subSet, headSet, or tailSet, and toElement is not within the specified range of the subSet, headSet, or tailSet; NullPointerException - if toElement is null and this set does not tolerate null elements

isEmpty

public boolean isEmpty()

Returns true if this set contains no elements.

Specified by:: isEmpty in interface Collection
Specified by:: isEmpty in interface Set
Overrides:: isEmpty in class AbstractCollection

Returns:: true if no elements in this set

iterator

public Iterator<E> iterator()

Returns an iterator over the elements in this set. The elements are returned in ascending order.

Specified by:: iterator in interface Iterable
Specified by:: iterator in interface Collection
Specified by:: iterator in interface Set
Specified by:: iterator in class AbstractCollection

Returns:: an iterator over the elements in this set

last

public E last()

Returns the last (highest) element currently in this sorted set.

Specified by:: last in interface SortedSet

Returns:: the last (highest) element currently in this sorted set
Throws:: NoSuchElementException - if the sorted set is empty

remove

public boolean remove(Object o)

Removes the specified element from this set if it is present.

Specified by:: remove in interface Collection
Specified by:: remove in interface Set
Overrides:: remove in class AbstractCollection

Parameters:: o - object to be removed from this set, if present
Returns:: true if the set contained the specified element
Throws:: ClassCastException - if the specified object cannot be compared with the elements currently in the set

size

public int size()

Returns the number of elements in this set (its cardinality).

Specified by:: size in interface Collection
Specified by:: size in interface Set
Specified by:: size in class AbstractCollection

Returns:: the number of elements in this set

subSet

public SortedSet<E> subSet(E fromElement,
                           E toElement)

Returns a view of the portion of this set whose elements range from fromElement, inclusive, to toElement, exclusive. (If fromElement and toElement are equal, the returned sorted set is empty.) The returned sorted set is backed by this set, so changes in the returned sorted set are reflected in this set, and vice-versa.

Parameters:: fromElement - low endpoint (inclusive) of the subSet; toElement - high endpoint (exclusive) of the subSet
Returns:: a view of the portion of this set whose elements range from fromElement to toElement
Throws:: ClassCastException - if fromElement and toElement cannot be compared to one another; IllegalArgumentException - if fromElement is greater than toElement; NullPointerException - if fromElement or toElement is null and this set does not tolerate null elements

tailSet

public SortedSet<E> tailSet(E fromElement)

Returns a view of the portion of this sorted set whose elements are greater than or equal to fromElement. The returned sorted set is backed by this sorted set, so changes in the returned sorted set are reflected in this sorted set, and vice-versa. The returned sorted set supports all optional set operations.

Parameters:: fromElement - low endpoint (inclusive) of the subSet
Returns:: a view of the specified final range of this sorted set
Throws:: ClassCastException - if fromElement is not compatible with this set's comparator, or, if the set has no comparator, if toElement does not implement Comparable.; IllegalArgumentException - if this set is itself a subSet, headSet, or tailSet, and fromElement is not within the specified range of the subSet, headSet, or tailSet; NullPointerException - if fromElement is null and this set does not tolerate null elements