Top Description Inners Fields Constructors Methods
net.sf.ehcache.store.disk.ods

public Class AATreeSet<T extends java.lang.Comparable<T>>

extends AbstractSet<T extends Comparable<T>>
implements SortedSet<T extends Comparable<T>>
Class Inheritance
All Implemented Interfaces
java.util.SortedSet, java.util.SequencedSet, java.util.Set, java.util.Collection, java.lang.Iterable, java.util.SequencedCollection
Known Direct Subclasses
net.sf.ehcache.store.disk.ods.RegionSet
Type Parameters
<T>
type of values stored
Imports
java.util.AbstractSet, .Comparator, .Iterator, .SortedSet, .Stack
A AA-Tree based SortedSet implementation
Author
Chris Dennis

Nested and Inner Type Summary

Modifier and TypeClass and Description
public abstract static class
AATreeSet.AbstractTreeNode<E>

Abstract node implementation that can be extended with a custom payload.

public static interface
AATreeSet.Node<E>

Interface implemented by nodes within this tree.

private class
AATreeSet.SubSet

SortedSet representation of a range of the tree.

private class
AATreeSet.SubTreeIterator

Iterator that iterates over a subset of the tree.

private static class
AATreeSet.TerminalNode<E>

Node implementation that is used to mark the terminal (leaf) nodes of the tree.

private class
AATreeSet.TreeIterator

Iterator that iterates over the tree.

private static class
AATreeSet.TreeNode<E extends Comparable<T>>

Default Comparable wrapping node implementation.

Field Summary

Modifier and TypeField and Description
private AATreeSet.Node<T>
heir

private AATreeSet.Node<T>
item

private boolean
mutated

private T
removed

private AATreeSet.Node<T>
root

private int
size

private static final AATreeSet.Node<?>
TERMINAL

Constructor Summary

AccessConstructor and Description
public
AATreeSet()

Method Summary

Modifier and TypeMethod and Description
public boolean
add(T
element to be added to this set
o)

Overrides java.util.AbstractCollection.add.

Implements java.util.Set.add, java.util.Collection.add.

Adds the specified element to this set if it is not already present (optional operation).
public void
clear()

Overrides java.util.AbstractCollection.clear.

Implements java.util.Set.clear, java.util.Collection.clear.

Removes all of the elements from this set (optional operation).
public Comparator<? super T>
comparator()

Implements java.util.SortedSet.comparator.

Returns the comparator used to order the elements in this set, or null if this set uses the natural ordering of its elements.
private AATreeSet.Node<T>
createNode(T data)

public T
find(Object probe)

Find the node within this tree equal to the probe node.

private AATreeSet.Node<T>
find(AATreeSet.Node<T> top, T probe)

public T
first()

Implements java.util.SortedSet.first.

Returns the first (lowest) element currently in this set.
protected final AATreeSet.Node<T>
getRoot()

Returns the root node of this tree.

public SortedSet<T>
headSet(T
high endpoint (exclusive) of the returned set
toElement)

Implements java.util.SortedSet.headSet.

Returns a view of the portion of this set whose elements are strictly less than toElement.
private AATreeSet.Node<T>
insert(AATreeSet.Node<T> top, T data)

public boolean
isEmpty()

Overrides java.util.AbstractCollection.isEmpty.

Implements java.util.Set.isEmpty, java.util.Collection.isEmpty.

Returns true if this set contains no elements.
public Iterator<T>
iterator()

Implements abstract java.util.AbstractCollection.iterator.

Implements java.util.Set.iterator, java.util.Collection.iterator.

Returns an iterator over the elements in this set.
public T
last()

Implements java.util.SortedSet.last.

Returns the last (highest) element currently in this set.
public boolean
remove(Object
object to be removed from this set, if present
o)

Overrides java.util.AbstractCollection.remove.

Implements java.util.Set.remove, java.util.Collection.remove.

Removes the specified element from this set if it is present (optional operation).
private AATreeSet.Node<T>
remove(AATreeSet.Node<T> top, T data)

public T
removeAndReturn(Object o)

Remove the node matching this object and return it.

public int
size()

Implements abstract java.util.AbstractCollection.size.

Implements java.util.Set.size, java.util.Collection.size.

Returns the number of elements in this set (its cardinality).
private static <T> AATreeSet.Node<T>
skew(AATreeSet.Node<T> top)

private static <T> AATreeSet.Node<T>
split(AATreeSet.Node<T> top)

public SortedSet<T>
subSet(T
low endpoint (inclusive) of the returned set
fromElement, T
high endpoint (exclusive) of the returned set
toElement)

Implements java.util.SortedSet.subSet.

Returns a view of the portion of this set whose elements range from fromElement, inclusive, to toElement, exclusive.
public SortedSet<T>
tailSet(T
low endpoint (inclusive) of the returned set
fromElement)

Implements java.util.SortedSet.tailSet.

Returns a view of the portion of this set whose elements are greater than or equal to fromElement.
private AATreeSet.Node<T>
terminal()

Inherited from java.util.AbstractSet:
equalshashCoderemoveAll