edu.neu.ccs.demeterf.lib
Class RBTree<X extends java.lang.Comparable<X>>

java.lang.Object
  edu.neu.ccs.demeterf.lib.RBTree<X>

All Implemented Interfaces:

java.lang.Iterable<X>

Direct Known Subclasses:

RBLeaf, RBNode

public abstract class RBTree<X extends java.lang.Comparable<X>>
extends java.lang.Object
implements java.lang.Iterable<X>

Java Functional implementation of Red-Black Trees. Use the static methods to create them, then insert/remove to modify them. Note that they are completely functional, so insert/remove return a new tree with or without the given element respectively

The elements stored in the tree must implement Comparable, though insertion and deletion can accept a seperate Comparator if the implementation requires more than one, or you would rather use an external comparator.

Constructor Summary

RBTree()

Method Summary

static RBColor	black() Return the RBColor "Black"
boolean	contains(X x) Is the given (Comparable) element in this RBTree?
abstract boolean	contains(X x, java.util.Comparator<X> comp) Is the given element in this RBTree, using the given Comparator?
boolean	containsAll(RBTree<X> x) Are all the (Comparable) elements int the given RBTree contained in this RBTree?
abstract boolean	containsAll(RBTree<X> x, java.util.Comparator<X> comp) Are all the elements int the given RBTree contained in this RBTree, using the given Comparator?
static <X extends java.lang.Comparable<X>> RBTree<X>	create(List<X> l) Create an RBTree containing the given elements, using the given Comparator
static <X extends java.lang.Comparable<X>> RBTree<X>	create(X... xs) Create an RBTree containing the given elements
X	find(X x) Return the (Comparable) X in this RBTree that matches the given one
abstract X	find(X x, java.util.Comparator<X> comp) Return the X in this RBTree that matches the given one, using the given Comparator
abstract int	hashCode()
RBTree<X>	insert(X x) Returns a new RBTree that includes the given Comparable element
RBTree<X>	insert(X x, java.util.Comparator<X> comp) Returns a new RBTree that includes the given element using the given Comparator
RBTree<X>	insertAll(List<X> lst) Returns a new RBTree that includes all the (Comparable) elements from the given List
RBTree<X>	insertAll(List<X> lst, java.util.Comparator<X> c) Returns a new RBTree that includes all the elements from the given List, using the given Comparator
RBTree<X>	insertAll(RBTree<X> t) Returns a new RBTree that includes all the (Comparable) elements from the given RBTree
RBTree<X>	insertAll(RBTree<X> t, java.util.Comparator<X> c) Returns a new RBTree that includes all the elements from the given RBTree, using the given Comparator
abstract boolean	isLeaf() Is this RBTree a leaf?
java.util.Iterator<X>	iterator() Return an Interator for the elements in this list, in Comparator order.
static <X extends java.lang.Comparable<X>> RBLeaf<X>	leaf() Create a new RBLeaf
abstract X	max() Return this RBTree's maximum element (Only valid on RBNodes)
abstract X	min() Return this RBTree's minimum element (Only valid on RBNodes)
static <X extends java.lang.Comparable<X>> RBNode<X>	node(RBColor c, X d, RBTree<X> l, RBTree<X> r) Create a new RBNode
abstract X	pred() Return this RBTree's predicessor element (Only valid on RBNodes)
static RBColor	red() Return the RBColor "Red"
RBTree<X>	remove(X x) Return this RBTree without the given (Comparable) element
abstract RBTree<X>	remove(X x, java.util.Comparator<X> comp) Return this RBTree without the given element, using the given Comparator
RBTree<X>	replace(X x) Return a new RBTree without the given (Comparable) element
abstract RBTree<X>	replace(X x, java.util.Comparator<X> comp) Return a new RBTree without the given element, using the given Comparator
abstract int	size() Return the number of elements in the RBTree
abstract X	succ() Return this RBTree's successor element (Only valid on RBNodes)
abstract List<X>	toList() Return all the elements in thei RBTree as a List in order

Methods inherited from class java.lang.Object

equals, getClass, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

RBTree

public RBTree()

Method Detail

isLeaf

public abstract boolean isLeaf()

Is this RBTree a leaf?

insert

public RBTree<X> insert(X x)

Returns a new RBTree that includes the given Comparable element

insert

public RBTree<X> insert(X x,
                        java.util.Comparator<X> comp)

Returns a new RBTree that includes the given element using the given Comparator

insertAll

public RBTree<X> insertAll(RBTree<X> t)

Returns a new RBTree that includes all the (Comparable) elements from the given RBTree

insertAll

public RBTree<X> insertAll(List<X> lst)

Returns a new RBTree that includes all the (Comparable) elements from the given List

insertAll

public RBTree<X> insertAll(RBTree<X> t,
                           java.util.Comparator<X> c)

Returns a new RBTree that includes all the elements from the given RBTree, using the given Comparator

insertAll

public RBTree<X> insertAll(List<X> lst,
                           java.util.Comparator<X> c)

Returns a new RBTree that includes all the elements from the given List, using the given Comparator

remove

public RBTree<X> remove(X x)

Return this RBTree without the given (Comparable) element

remove

public abstract RBTree<X> remove(X x,
                                 java.util.Comparator<X> comp)

Return this RBTree without the given element, using the given Comparator

size

public abstract int size()

Return the number of elements in the RBTree

pred

public abstract X pred()

Return this RBTree's predicessor element (Only valid on RBNodes)

succ

public abstract X succ()

Return this RBTree's successor element (Only valid on RBNodes)

min

public abstract X min()

Return this RBTree's minimum element (Only valid on RBNodes)

max

public abstract X max()

Return this RBTree's maximum element (Only valid on RBNodes)

contains

public boolean contains(X x)

Is the given (Comparable) element in this RBTree?

contains

public abstract boolean contains(X x,
                                 java.util.Comparator<X> comp)

Is the given element in this RBTree, using the given Comparator?

containsAll

public boolean containsAll(RBTree<X> x)

Are all the (Comparable) elements int the given RBTree contained in this RBTree?

containsAll

public abstract boolean containsAll(RBTree<X> x,
                                    java.util.Comparator<X> comp)

Are all the elements int the given RBTree contained in this RBTree, using the given Comparator?

find

public X find(X x)

Return the (Comparable) X in this RBTree that matches the given one

find

public abstract X find(X x,
                       java.util.Comparator<X> comp)

Return the X in this RBTree that matches the given one, using the given Comparator

replace

public RBTree<X> replace(X x)

Return a new RBTree without the given (Comparable) element

replace

public abstract RBTree<X> replace(X x,
                                  java.util.Comparator<X> comp)

Return a new RBTree without the given element, using the given Comparator

toList

public abstract List<X> toList()

Return all the elements in thei RBTree as a List in order

black

public static RBColor black()

Return the RBColor "Black"

red

public static RBColor red()

Return the RBColor "Red"

create

public static <X extends java.lang.Comparable<X>> RBTree<X> create(X... xs)

Create an RBTree containing the given elements

create

public static <X extends java.lang.Comparable<X>> RBTree<X> create(List<X> l)

Create an RBTree containing the given elements, using the given Comparator

leaf

public static <X extends java.lang.Comparable<X>> RBLeaf<X> leaf()

Create a new RBLeaf

node

public static <X extends java.lang.Comparable<X>> RBNode<X> node(RBColor c,
                                                                 X d,
                                                                 RBTree<X> l,
                                                                 RBTree<X> r)

Create a new RBNode

iterator

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

Return an Interator for the elements in this list, in Comparator order.

Specified by:

iterator in interface java.lang.Iterable<X extends java.lang.Comparable<X>>

hashCode

public abstract int hashCode()

Overrides:

hashCode in class java.lang.Object