org.jcae.mesh.amibe.util
Class QSortedTree<E>

java.lang.Object
  org.jcae.mesh.amibe.util.QSortedTree<E>

All Implemented Interfaces:

java.io.Serializable

Direct Known Subclasses:

PAVLSortedTree, PRedBlackSortedTree

public abstract class QSortedTree<E>
extends java.lang.Object
implements java.io.Serializable

Binary trees to store quality factors. These trees are used to sort vertices, edges, or triangles according to their quality factors, and to process them in increasing or decreasing order after they have been sorted. They differ from casual binary trees in that duplicate quality factors are allowed. See examples in algorithms from org.jcae.mesh.amibe.algos3d.

See Also:

Serialized Form

Nested Class Summary

static class

QSortedTree.Node<E>

Field Summary

protected QSortedTree.Node<E>

root

Constructor Summary

QSortedTree()

Method Summary

java.util.Iterator<QSortedTree.Node<E>>	backwardIterator()
void	clear() Clear this tree.
boolean	contains(E o) Checks whether an object exist is the tree.
double	getRootValue() Return the value found at root binary tree.
void	insert(E o, double value) Insert a node to the tree.
protected abstract boolean	insertNode(QSortedTree.Node<E> node) Insert a new note into the binary tree.
boolean	isEmpty() Tell whether this tree is empty.
java.util.Iterator<QSortedTree.Node<E>>	iterator()
protected abstract QSortedTree.Node<E>	newNode(E o, double v) Constructor to cast new nodes into subclass type.
protected void	readObject(java.io.ObjectInputStream s)
boolean	remove(E o) Remove the node associated to an object from the tree.
protected abstract QSortedTree.Node<E>	removeNode(QSortedTree.Node<E> p) Remove a note from the binary tree.
void	show() Pretty-print this tree.
void	showValues() Pretty-print this tree.
int	size() Return the object with the lowest quality factor.
boolean	update(E o, double value) Update the quality factor of an object, if it was already present in tree.

Methods inherited from class java.lang.Object

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

Field Detail

root

protected final QSortedTree.Node<E> root

Constructor Detail

QSortedTree

public QSortedTree()

Method Detail

newNode

protected abstract QSortedTree.Node<E> newNode(E o,
                                               double v)

Constructor to cast new nodes into subclass type.

insertNode

protected abstract boolean insertNode(QSortedTree.Node<E> node)

Insert a new note into the binary tree. This method always returns true.

removeNode

protected abstract QSortedTree.Node<E> removeNode(QSortedTree.Node<E> p)

Remove a note from the binary tree. Some algorithms may remove another node (for instance PRedBlackSortedTree), this method returns the node which has been removed.

readObject

protected void readObject(java.io.ObjectInputStream s)
                   throws java.io.IOException,
                          java.lang.ClassNotFoundException

Throws:

java.io.IOException

java.lang.ClassNotFoundException

isEmpty

public boolean isEmpty()

Tell whether this tree is empty.

insert

public final void insert(E o,
                         double value)

Insert a node to the tree. Tree is sorted according to value, and duplicates are not checked.

Parameters:

o - object

value - quality factor

remove

public final boolean remove(E o)

Remove the node associated to an object from the tree.

Parameters:

o - object being removed

Returns:

true if node was present in tree, false otherwise.

update

public final boolean update(E o,
                            double value)

Update the quality factor of an object, if it was already present in tree.

Parameters:

o - object being updated

value - new quality factor

Returns:

true if object was present in tree, false otherwise.

clear

public void clear()

Clear this tree.

show

public void show()

Pretty-print this tree.

showValues

public void showValues()

Pretty-print this tree.

contains

public final boolean contains(E o)

Checks whether an object exist is the tree.

Parameters:

o - object being checked

Returns:

true if this tree contains this object, false otherwise.

size

public final int size()

Return the object with the lowest quality factor.

Returns:

the object with the lowest quality factor.

getRootValue

public final double getRootValue()

Return the value found at root binary tree. As trees are balanced, this is a good approximation of tree median value.

Returns:

the value found at root binary tree.

iterator

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

backwardIterator

public java.util.Iterator<QSortedTree.Node<E>> backwardIterator()