common
Class IndexedTreeSet

java.lang.Object
  java.util.AbstractCollection<E>
      java.util.AbstractSet
          common.IndexedTreeSet

All Implemented Interfaces:

IndexedSet, IndexedSortedSet, java.lang.Cloneable, java.lang.Iterable, java.util.Collection, java.util.Set, java.util.SortedSet

public class IndexedTreeSet
extends java.util.AbstractSet
implements IndexedSortedSet, java.lang.Cloneable

An implementation of the IndexedSet interface that keeps elements in sorted order. The order can be the natural ordering of the elements (if they implement the Comparable interface), or it can be specified by passing a Comparator object to the constructor.

This implementation uses a red-black tree, as described in Chapter 13 of Cormen, Leiserson, Rivest and Stein, "Introduction to Algorithms", 2nd ed. Each node in the tree also stores the size of the subtree rooted at it; this allows us to find the element at any given index in the ordering in O(lg n) time.

Nested Class Summary

Nested classes/interfaces inherited from interface common.IndexedSet

IndexedSet.EmptyIndexedSet

Field Summary

Fields inherited from interface common.IndexedSet

EMPTY_INDEXED_SET

Constructor Summary

IndexedTreeSet()
Creates an empty IndexedTreeSet that uses the natural ordering on its elements.

IndexedTreeSet(java.util.Collection c)
Creates an IndexedTreeSet that contains the same elements as the given collection and uses the natural ordering on the elements.

IndexedTreeSet(java.util.Comparator comparator)
Creates an empty IndexedTreeSet that uses the given comparator.

IndexedTreeSet(java.util.SortedSet s)
Creates an IndexedTreeSet that contains the same elements as the given SortedSet and uses the same comparator.

Method Summary

boolean	add(java.lang.Object o)
void	clear()
java.lang.Object	clone()
java.util.Comparator	comparator()
boolean	contains(java.lang.Object o)
java.lang.Object	first()
java.lang.Object	get(int index) Returns the object with the specified index in this IndexedSet.
java.util.SortedSet	headSet(java.lang.Object toElement)
int	indexOf(java.lang.Object o) Returns the index of the given object in this IndexedSet, or -1 if this IndexedSet does not contain the given object.
java.util.Iterator	iterator()
java.lang.Object	last()
static void	main(java.lang.String[] args) Test program.
void	print()
boolean	remove(java.lang.Object o)
int	size()
java.util.SortedSet	subSet(java.lang.Object fromElement, java.lang.Object toElement)
java.util.SortedSet	tailSet(java.lang.Object fromElement)

Methods inherited from class java.util.AbstractSet

equals, hashCode, removeAll

Methods inherited from class java.util.AbstractCollection

addAll, containsAll, isEmpty, retainAll, toArray, toArray, toString

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Set

addAll, containsAll, equals, hashCode, isEmpty, removeAll, retainAll, toArray, toArray

Constructor Detail

IndexedTreeSet

public IndexedTreeSet()

Creates an empty IndexedTreeSet that uses the natural ordering on its elements. The elements must implement the Comparable interface.

IndexedTreeSet

public IndexedTreeSet(java.util.Comparator comparator)

Creates an empty IndexedTreeSet that uses the given comparator.

IndexedTreeSet

public IndexedTreeSet(java.util.Collection c)

Creates an IndexedTreeSet that contains the same elements as the given collection and uses the natural ordering on the elements. The elements must implement the Comparable interface.

IndexedTreeSet

public IndexedTreeSet(java.util.SortedSet s)

Creates an IndexedTreeSet that contains the same elements as the given SortedSet and uses the same comparator.

Method Detail

contains

public boolean contains(java.lang.Object o)

Specified by:

contains in interface java.util.Collection

Specified by:

contains in interface java.util.Set

Overrides:

contains in class java.util.AbstractCollection

size

public int size()

Specified by:

size in interface java.util.Collection

Specified by:

size in interface java.util.Set

Specified by:

size in class java.util.AbstractCollection

iterator

public java.util.Iterator iterator()

Specified by:

iterator in interface java.lang.Iterable

Specified by:

iterator in interface java.util.Collection

Specified by:

iterator in interface java.util.Set

Specified by:

iterator in class java.util.AbstractCollection

add

public boolean add(java.lang.Object o)

Specified by:

add in interface java.util.Collection

Specified by:

add in interface java.util.Set

Overrides:

add in class java.util.AbstractCollection

remove

public boolean remove(java.lang.Object o)

Specified by:

remove in interface java.util.Collection

Specified by:

remove in interface java.util.Set

Overrides:

remove in class java.util.AbstractCollection

clear

public void clear()

Specified by:

clear in interface java.util.Collection

Specified by:

clear in interface java.util.Set

Overrides:

clear in class java.util.AbstractCollection

comparator

public java.util.Comparator comparator()

Specified by:

comparator in interface java.util.SortedSet

first

public java.lang.Object first()

Specified by:

first in interface java.util.SortedSet

last

public java.lang.Object last()

Specified by:

last in interface java.util.SortedSet

headSet

public java.util.SortedSet headSet(java.lang.Object toElement)

Specified by:

headSet in interface java.util.SortedSet

tailSet

public java.util.SortedSet tailSet(java.lang.Object fromElement)

Specified by:

tailSet in interface java.util.SortedSet

subSet

public java.util.SortedSet subSet(java.lang.Object fromElement,
                                  java.lang.Object toElement)

Specified by:

subSet in interface java.util.SortedSet

get

public java.lang.Object get(int index)

Description copied from interface: IndexedSet

Returns the object with the specified index in this IndexedSet.

Specified by:

get in interface IndexedSet

indexOf

public int indexOf(java.lang.Object o)

Description copied from interface: IndexedSet

Returns the index of the given object in this IndexedSet, or -1 if this IndexedSet does not contain the given object.

Specified by:

indexOf in interface IndexedSet

clone

public java.lang.Object clone()

Overrides:

clone in class java.lang.Object

print

public void print()

main

public static void main(java.lang.String[] args)

Test program.