org.hypergraphdb.util
Class LLRBTree<E>

java.lang.Object
  java.util.AbstractCollection<E>
      java.util.AbstractSet<E>
          org.hypergraphdb.util.LLRBTree<E>

Type Parameters:

E - The type of elements this set stores. It must implement the Comparable interface.

All Implemented Interfaces:

java.io.Serializable, java.lang.Cloneable, java.lang.Iterable<E>, java.util.Collection<E>, java.util.Set<E>, java.util.SortedSet<E>, HGSortedSet<E>

public class LLRBTree<E>
extends java.util.AbstractSet<E>
implements HGSortedSet<E>, java.lang.Cloneable, java.io.Serializable

Implements a set of elements as a left-leaning red-black tree. The node doesn't contain a pointer to a value, nor does it contains a pointer to the parent which should make it more memory efficient than most implementations (e.g. the standard java.util.TreeMap). However, tree mutations are implemented recursively, which is not optimal and could be removed in the future. Unfortunately, Java uses 4 bytes to store a boolean so we don't gain as much in space compactness as we could theoretically, but it's still an improvement.

Author:

Borislav Iordanov

See Also:

Serialized Form

Constructor Summary

LLRBTree()

LLRBTree(java.util.Comparator<E> comparator)

Method Summary

boolean	add(E key)
boolean	check()
void	clear()
java.lang.Object	clone()
java.util.Comparator<E>	comparator()
boolean	contains(java.lang.Object key)
int	depth()
E	first()
HGRandomAccessResult<E>	getSearchResult()
java.util.SortedSet<E>	headSet(E toElement)
boolean	is234()
boolean	isBalanced()
boolean	isBalanced(org.hypergraphdb.util.LLRBTree.Node<E> r)
boolean	isBST()
boolean	isEmtpy()
java.util.Iterator<E>	iterator()
E	last()
boolean	remove(java.lang.Object key)
void	removeMax()
void	removeMin()
int	size()
java.util.SortedSet<E>	subSet(E fromElement, E toElement)
java.util.SortedSet<E>	tailSet(E 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

getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Set

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

Constructor Detail

LLRBTree

public LLRBTree()

LLRBTree

public LLRBTree(java.util.Comparator<E> comparator)

Method Detail

removeMax

public void removeMax()

removeMin

public void removeMin()

size

public int size()

Specified by:

size in interface java.util.Collection<E>

Specified by:

size in interface java.util.Set<E>

Specified by:

size in class java.util.AbstractCollection<E>

isEmtpy

public boolean isEmtpy()

comparator

public java.util.Comparator<E> comparator()

Specified by:

comparator in interface java.util.SortedSet<E>

clear

public void clear()

Specified by:

clear in interface java.util.Collection<E>

Specified by:

clear in interface java.util.Set<E>

Overrides:

clear in class java.util.AbstractCollection<E>

contains

public boolean contains(java.lang.Object key)

Specified by:

contains in interface java.util.Collection<E>

Specified by:

contains in interface java.util.Set<E>

Overrides:

contains in class java.util.AbstractCollection<E>

add

public boolean add(E key)

Specified by:

add in interface java.util.Collection<E>

Specified by:

add in interface java.util.Set<E>

Overrides:

add in class java.util.AbstractCollection<E>

remove

public boolean remove(java.lang.Object key)

Specified by:

remove in interface java.util.Collection<E>

Specified by:

remove in interface java.util.Set<E>

Overrides:

remove in class java.util.AbstractCollection<E>

first

public E first()

Specified by:

first in interface java.util.SortedSet<E>

last

public E last()

Specified by:

last in interface java.util.SortedSet<E>

headSet

public java.util.SortedSet<E> headSet(E toElement)

Specified by:

headSet in interface java.util.SortedSet<E>

subSet

public java.util.SortedSet<E> subSet(E fromElement,
                                     E toElement)

Specified by:

subSet in interface java.util.SortedSet<E>

tailSet

public java.util.SortedSet<E> tailSet(E fromElement)

Specified by:

tailSet in interface java.util.SortedSet<E>

iterator

public java.util.Iterator<E> iterator()

Specified by:

iterator in interface java.lang.Iterable<E>

Specified by:

iterator in interface java.util.Collection<E>

Specified by:

iterator in interface java.util.Set<E>

Specified by:

iterator in class java.util.AbstractCollection<E>

getSearchResult

public HGRandomAccessResult<E> getSearchResult()

Specified by:

getSearchResult in interface HGSortedSet<E>

clone

public java.lang.Object clone()
                       throws java.lang.CloneNotSupportedException

Overrides:

clone in class java.lang.Object

Throws:

java.lang.CloneNotSupportedException

depth

public int depth()

check

public boolean check()

isBST

public boolean isBST()

is234

public boolean is234()

isBalanced

public boolean isBalanced()

isBalanced

public boolean isBalanced(org.hypergraphdb.util.LLRBTree.Node<E> r)