net.sf.joafip.redblacktree.service

Class RedBlackTree<E>

java.lang.Object

net.sf.joafip.redblacktree.service.RedBlackTree<E>

All Implemented Interfaces:

Serializable, Iterable<IRBTNode<E>>, IRBTVisitable<E>

@StoreNotUseStandardSerialization
@StorableClass
public class RedBlackTree<E>
extends Object
implements IRBTVisitable<E>, Iterable<IRBTNode<E>>, Serializable

red black tree manager
attached / detached to the tree
Independent of kind of element stored by the nodes
no more duplicate key
browsing
Optionally manage index

Author:

luc peuvrier

See Also:

Serialized Form

Field Summary

Fields

Modifier and Type	Field and Description
static boolean	BLACK
static boolean	RED

Constructor Summary

Constructors

Constructor and Description
RedBlackTree(IInstanceFactory instanceFactory, IRBTNodeManager<E> nodeManager, boolean manageNodeIndex, boolean uniqueValue)
RedBlackTree(IRBTNodeManager<E> nodeManager, boolean manageNodeIndex, boolean uniqueValue) construct the red black tree using a node manager

Method Summary

Methods

Modifier and Type	Method and Description
void	accept(IRBTVisitor<E> visitor) accept red black tree visitor
void	append(IRBTNode<E> nodeToAppend) append a node in the tree if same value exist node is add at end of the existing value(s) set the node to append must be detached to the tree
void	appendAfterLast(IRBTNode<E> nodeToAppend) append node after last node
void	appendBeforeFirst(IRBTNode<E> nodeToInsert) insert node before first node
boolean	appendIfNotexist(IRBTNode<E> nodeToAppend) append a node in the tree if value not already store in it the node to append must be detached to the tree
IRBTNode<E>	appendOrReplace(IRBTNode<E> nodeToAppendOrSubstitute) append or replace node if exist the replaced node is detached from the tree
IRBTNode<E>	closestGreaterOrEqual(E referenceElement) search node by reference element or closest greater if not exist closest is the smaller greater than reference element the found node is attached to the tree
IRBTNode<E>	closestLessOrEqual(E referenceElement) search for node by reference element or closest less if not exist closest is the greater smaller than reference element the found node is attached to the tree
boolean	delete(E referenceElement) delete record if found it, returning deletion operation status delete the first value of group of same value
IRBTNode<E>	deleteByIndex(int index) delete a node at position after deletion the node to delete is in detached to the tree state
void	deleteExistingNode(IRBTNode<E> nodeToDelete) delete a node attached to the tree the node to delete must be attached to the tree after deletion the node to delete is in detached to the tree state
IRBTNode<E>	deleteGetRemoved(E referenceElement) delete record if found it, returning deleted node if any delete the first value of group of same value after deletion the node to delete returned is in detached to the tree state
boolean	deleteLast(E referenceElement) delete record if found it, returning deletion operation status delete the last value of group of same value
IRBTNode<E>	deleteLastGetRemoved(E referenceElement) delete record if found it, returning deleted node if any delete the last value of group of same value after deletion the node to delete returned is in detached to the tree state
IRBTNode<E>	first() get the first node ( smallest value ) the found node is attached to the tree
int	getNumberOfElement() to obtains number of elements of this tree
int	index(IRBTNode<E> node) obtains the position of the node in list view of this tree
void	insertAfter(IRBTNode<E> nodeToInsert, int index) insert a node after the node at position, the inserted node index will be the insert position + 1
void	insertBefore(IRBTNode<E> nodeToInsert, int index) insert a node before the node at position, the inserted node index will be the insert position
boolean	isManageNodeIndex()
boolean	isNodeAttachedToTree(IRBTNode<E> node) to know if a node is attached to the tree
boolean	isUniqueValue()
Iterator<IRBTNode<E>>	iterator()
IRBTNode<E>	last() get the last node ( greater value ) the found node is attached to the tree
ListIterator<IRBTNode<E>>	listIterator()
ListIterator<IRBTNode<E>>	listIterator(int index)
static RedBlackTree	newInstance(IInstanceFactory instanceFactory, IRBTNodeManager nodeManager, boolean manageNodeIndex, boolean uniqueValue)
IRBTNode<E>	next(IRBTNode<E> node) to obtains the next node of a node the reference node must be attached to the tree
IRBTNode<E>	nodeAtIndex(int index) to obtains node at position in the sorted list view of this tree
IRBTNode<E>	pollFirst() Retrieves and removes the first (lowest) element, or returns null if the tree is empty.
IRBTNode<E>	pollLast() Retrieves and removes the last (highest) element, or returns null if the tree is empty.
IRBTNode<E>	previous(IRBTNode<E> node) to obtains the previous node of a node the reference node must be attached to the tree
IRBTNode<E>	search(E referenceElement) search for a node referencing element equals to reference element, return the first of group of same value the found node is attached to the tree
IRBTNode<E>	searchLast(E referenceElement) search for a node referencing element equals to reference element, return the last of group of same value the found node is attached to the tree
IRBTNode<E>	strictlyGreater(E referenceElement) search for node by reference element strictly greater the found node is attached to the tree
IRBTNode<E>	strictlyLess(E referenceElement) search for node by reference element strictly less the found node is attached to the tree

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

BLACK

public static final boolean BLACK

See Also:

Constant Field Values

RED

public static final boolean RED

See Also:

Constant Field Values

Constructor Detail

RedBlackTree

public RedBlackTree(IRBTNodeManager<E> nodeManager,
            boolean manageNodeIndex,
            boolean uniqueValue)

construct the red black tree using a node manager

Parameters:

nodeManager - the node access manager

RedBlackTree

public RedBlackTree(IInstanceFactory instanceFactory,
            IRBTNodeManager<E> nodeManager,
            boolean manageNodeIndex,
            boolean uniqueValue)

Method Detail

newInstance

public static RedBlackTree newInstance(IInstanceFactory instanceFactory,
                       IRBTNodeManager nodeManager,
                       boolean manageNodeIndex,
                       boolean uniqueValue)

accept

public void accept(IRBTVisitor<E> visitor)
            throws RBTException

Description copied from interface: IRBTVisitable

accept red black tree visitor

Specified by:

accept in interface IRBTVisitable<E>

Parameters:

visitor - the red black tree visitor

Throws:

RBTException - node access error

isManageNodeIndex

public boolean isManageNodeIndex()

isUniqueValue

public boolean isUniqueValue()

search

public IRBTNode<E> search(E referenceElement)
                   throws RBTException

search for a node referencing element equals to reference element, return the first of group of same value
the found node is attached to the tree

Parameters:

referenceElement - the reference element to search

Returns:

the node found for the element or null if not found

Throws:

RBTException

IllegalArgumentException - reference element is null

searchLast

public IRBTNode<E> searchLast(E referenceElement)
                       throws RBTException

search for a node referencing element equals to reference element, return the last of group of same value
the found node is attached to the tree

Parameters:

referenceElement - the reference element to search

Returns:

the node found for the element or null if not found

Throws:

RBTException

IllegalArgumentException - reference element is null

closestGreaterOrEqual

public IRBTNode<E> closestGreaterOrEqual(E referenceElement)
                                  throws RBTException

search node by reference element or closest greater if not exist
closest is the smaller greater than reference element
the found node is attached to the tree

Parameters:

referenceElement - reference element to search for closest greater

Returns:

the closest greater than reference node, null if none

Throws:

RBTException

strictlyGreater

public IRBTNode<E> strictlyGreater(E referenceElement)
                            throws RBTException

search for node by reference element strictly greater
the found node is attached to the tree

Parameters:

referenceElement - reference element to search for strictly greater

Returns:

the strictly greater than reference node, null if none

Throws:

RBTException

last

public IRBTNode<E> last()
                 throws RBTException

get the last node ( greater value )
the found node is attached to the tree

Returns:

the last node, null if not exist

Throws:

RBTException

pollLast

public IRBTNode<E> pollLast()
                     throws RBTException

Retrieves and removes the last (highest) element, or returns null if the tree is empty.
the found node is detached to the tree

Returns:

the last element, or null if this tree is empty

Throws:

RBTException

first

public IRBTNode<E> first()
                  throws RBTException

get the first node ( smallest value )
the found node is attached to the tree

Returns:

the first node, null if not exist

Throws:

RBTException

pollFirst

public IRBTNode<E> pollFirst()
                      throws RBTException

Retrieves and removes the first (lowest) element, or returns null if the tree is empty.
the found node is detached to the tree

Returns:

the first element, or null if this tree is empty

Throws:

RBTException

closestLessOrEqual

public IRBTNode<E> closestLessOrEqual(E referenceElement)
                               throws RBTException

search for node by reference element or closest less if not exist
closest is the greater smaller than reference element
the found node is attached to the tree

Parameters:

referenceElement - reference element to search for closest less

Returns:

the less greater than reference node, null if none

Throws:

RBTException

strictlyLess

public IRBTNode<E> strictlyLess(E referenceElement)
                         throws RBTException

search for node by reference element strictly less
the found node is attached to the tree

Parameters:

referenceElement - reference element to search for strictly less

Returns:

the strictly less greater than reference node, null if none

Throws:

RBTException

append

public void append(IRBTNode<E> nodeToAppend)
            throws RBTException

append a node in the tree
if same value exist node is add at end of the existing value(s) set
the node to append must be detached to the tree

Parameters:

nodeToAppend - the node to append

Throws:

RBTException - the node to append is attached to the tree, node access error

appendOrReplace

public IRBTNode<E> appendOrReplace(IRBTNode<E> nodeToAppendOrSubstitute)
                            throws RBTException

append or replace node if exist
the replaced node is detached from the tree

Parameters:

nodeToAppendOrSubstitute - the node to append or substitute if exist

Returns:

the node replaced or null if append done

Throws:

RBTException

appendIfNotexist

public boolean appendIfNotexist(IRBTNode<E> nodeToAppend)
                         throws RBTException

append a node in the tree if value not already store in it
the node to append must be detached to the tree

Parameters:

nodeToAppend - the node to append

Returns:

true if appended, false if not appended because node with same element value already exist

Throws:

RBTException - the node to append is attached to the tree, node access error

deleteByIndex

public IRBTNode<E> deleteByIndex(int index)
                          throws RBTException,
                                 RBTExceptionOutOfBound

delete a node at position
after deletion the node to delete is in detached to the tree state

Parameters:

index - the position of the node to delete

Returns:

the deleted node

Throws:

RBTException - node access error

RBTExceptionOutOfBound - index out of bound

insertBefore

public void insertBefore(IRBTNode<E> nodeToInsert,
                int index)
                  throws RBTException,
                         RBTExceptionOutOfBound

insert a node before the node at position, the inserted node index will be the insert position

Parameters:

nodeToInsert - the node to insert

index - the position where insert before

Throws:

RBTException - node access error

RBTExceptionOutOfBound - index out of bound

insertAfter

public void insertAfter(IRBTNode<E> nodeToInsert,
               int index)
                 throws RBTException,
                        RBTExceptionOutOfBound

insert a node after the node at position, the inserted node index will be the insert position + 1

Parameters:

nodeToInsert - the node to insert

index - the position where insert after

Throws:

RBTException - node access error

RBTExceptionOutOfBound - index out of bound

appendAfterLast

public void appendAfterLast(IRBTNode<E> nodeToAppend)
                     throws RBTException

append node after last node

Parameters:

nodeToAppend - the node to append

Throws:

RBTException

appendBeforeFirst

public void appendBeforeFirst(IRBTNode<E> nodeToInsert)
                       throws RBTException

insert node before first node

Parameters:

nodeToInsert - the node to insert

Throws:

RBTException

delete

public boolean delete(E referenceElement)
               throws RBTException

delete record if found it, returning deletion operation status
delete the first value of group of same value

Parameters:

referenceElement - reference element to find the node to delete

Returns:

true if reference node found and deleted

Throws:

RBTException - node access error

deleteLast

public boolean deleteLast(E referenceElement)
                   throws RBTException

delete record if found it, returning deletion operation status
delete the last value of group of same value

Parameters:

referenceElement - reference element to find the node to delete

Returns:

true if reference node found and deleted

Throws:

RBTException - node access error

deleteGetRemoved

public IRBTNode<E> deleteGetRemoved(E referenceElement)
                             throws RBTException

delete record if found it, returning deleted node if any
delete the first value of group of same value
after deletion the node to delete returned is in detached to the tree state

Parameters:

referenceElement - reference element to find the node to delete

Returns:

the deleted node, null if node reference not found

Throws:

RBTException - node access error

deleteLastGetRemoved

public IRBTNode<E> deleteLastGetRemoved(E referenceElement)
                                 throws RBTException

delete record if found it, returning deleted node if any
delete the last value of group of same value
after deletion the node to delete returned is in detached to the tree state

Parameters:

referenceElement - reference element to find the node to delete

Returns:

the deleted node, null if node reference not found

Throws:

RBTException - node access error

deleteExistingNode

public void deleteExistingNode(IRBTNode<E> nodeToDelete)
                        throws RBTException

delete a node attached to the tree
the node to delete must be attached to the tree
after deletion the node to delete is in detached to the tree state

Parameters:

nodeToDelete - node to delete

Throws:

RBTException - the node is attached to the tree, node access error

previous

public IRBTNode<E> previous(IRBTNode<E> node)
                     throws RBTException

to obtains the previous node of a node
the reference node must be attached to the tree

Parameters:

node - the node which for previous is to obtains

Returns:

the previous node, null if none

Throws:

RBTException - node access error

next

public IRBTNode<E> next(IRBTNode<E> node)
                 throws RBTException

to obtains the next node of a node
the reference node must be attached to the tree

Parameters:

node - the node which for next is to obtains

Returns:

the next node, null if none

Throws:

RBTException - node access error

iterator

public Iterator<IRBTNode<E>> iterator()

Specified by:

iterator in interface Iterable<IRBTNode<E>>

listIterator

public ListIterator<IRBTNode<E>> listIterator()

listIterator

public ListIterator<IRBTNode<E>> listIterator(int index)

getNumberOfElement

public int getNumberOfElement()
                       throws RBTException

to obtains number of elements of this tree

Returns:

number of elements of this tree

Throws:

RBTException - node access error

index

public int index(IRBTNode<E> node)
          throws RBTException

obtains the position of the node in list view of this tree

Parameters:

node - the node searching its index, must be attached to the tree

Returns:

index of the node in the sorted list view of this tree

Throws:

RBTException - node access error

nodeAtIndex

public IRBTNode<E> nodeAtIndex(int index)
                        throws RBTException,
                               RBTExceptionOutOfBound

to obtains node at position in the sorted list view of this tree

Parameters:

index - the index of the node

Returns:

node at index position in the tree

Throws:

RBTException - node access error

RBTExceptionOutOfBound - index out of bound

isNodeAttachedToTree

public boolean isNodeAttachedToTree(IRBTNode<E> node)
                             throws RBTException

to know if a node is attached to the tree

Parameters:

node - node to check if attached to the tree

Returns:

true if node attached to the tree

Throws:

RBTException - node access error