org.miv.pherd.ntree
Class NTree

java.lang.Object
  org.miv.pherd.ntree.NTree

public class NTree
extends Object

n-Tree.

Since:

2007

Author:

Antoine Dutot

See Also:

Cell

Nested Class Summary

static class

NTree.OutOfUniverseMode How to handle particles that go out of the root cell space ?.

Field Summary

protected int	depthmax Maximum depth of the n-tree.
protected Cell	laMama The root cell.
protected ArrayList<NTreeListener>	listeners The set of listeners.
protected Point3	max The minimum and maximum points of the universe when growing the root cell, if a resize of the root cell space is needed.
protected Point3	min The minimum and maximum points of the universe when growing the root cell, if a resize of the root cell space is needed.
protected boolean	needResize Set to true each time some particles left the root cell space and this space needs to be resized.
protected NTree.OutOfUniverseMode	oum How to handle particles that leave the universe initial bounding box.
protected ParticleBox	pbox The particle set.
protected int	pmax Maximum number of particles by cell.

Constructor Summary

NTree(int pmax, CellData data, ParticleBox pbox)
New n-Tree with a universe of (-1,-1,-1) to (1,1,1).

NTree(int pmax, CellSpace space, CellData data, ParticleBox pbox)
New n-Tree with a universe defined by the given space.

Method Summary

void	addListener(NTreeListener listener) Add a listener that will receive events abound the ntree.
void	addParticle(Particle particle) Add a particle in the tree.
void	checkDivisions() Recursively check if cells need subdivision or fusion.
protected void	delete(Particle particle) Ask a particle to remove itself from the particle box.
protected void	describeTheCurrentState(NTreeListener listener) Send events for all already existing cells to the newly added listener.
String	generateCellIdentifier(Cell parent, int index) Generate an identifier for a cell given its parent and index in this parent.
Point3	getHighestPoint() The highest coordinate used by a particle.
ArrayList<NTreeListener>	getListeners() The set of listeners of this tree.
Point3	getLowestPoint() The lowest coordinate used by a particle.
int	getMaxDepth() Maximum number of subdivisions of a cell.
int	getMaxParticlePerCell() Maximum number of particles per cell.
NTree.OutOfUniverseMode	getOutOfUniverseMode() What to do if a particle leaves the root cell ?.
Cell	getRootCell() The tree root cell.
protected void	handleOutParticle(Particle particle) Decide what to do for a particle that moved out of the root cell space.
protected boolean	isValid() Make a recursive check of each cell of the tree.
void	removeListener(NTreeListener listener) Remove a listener.
void	removeParticle(Particle particle) Remove a particle from the tree.
protected void	resize(Particle particle) Specify that a particle is out of the root cell space.
void	setDepthMax(int max) Set the maximum depth of the tree.
void	setOutOfUniverseMode(NTree.OutOfUniverseMode mode) Tell what to do when a particle leaves the root cell.

Methods inherited from class java.lang.Object

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

Field Detail

pbox

protected ParticleBox pbox

The particle set.

laMama

protected Cell laMama

The root cell.

pmax

protected int pmax

Maximum number of particles by cell.

depthmax

protected int depthmax

Maximum depth of the n-tree.

listeners

protected ArrayList<NTreeListener> listeners

The set of listeners.

oum

protected NTree.OutOfUniverseMode oum

How to handle particles that leave the universe initial bounding box. If the mode is RESIZE, the universe is resized. Else the particle is deleted.

needResize

protected boolean needResize

Set to true each time some particles left the root cell space and this space needs to be resized.

See Also:

checkDivisions()

min

protected Point3 min

The minimum and maximum points of the universe when growing the root cell, if a resize of the root cell space is needed.

See Also:

checkDivisions()

max

protected Point3 max

The minimum and maximum points of the universe when growing the root cell, if a resize of the root cell space is needed.

See Also:

checkDivisions()

Constructor Detail

NTree

public NTree(int pmax,
             CellData data,
             ParticleBox pbox)

New n-Tree with a universe of (-1,-1,-1) to (1,1,1).

Parameters:

pmax - Maximum number of particle by cell, once this number is superseded, the cell subdivides itself.

data - The data specific to each cell.

pbox - The particle set.

NTree

public NTree(int pmax,
             CellSpace space,
             CellData data,
             ParticleBox pbox)

New n-Tree with a universe defined by the given space.

Parameters:

pmax - Maximum number of particle by cell, once this number is superseded, the cell subdivides itself.

space - The universe bounding box.

data - The data specific to each cell.

pbox - The particle set.

Method Detail

getRootCell

public Cell getRootCell()

The tree root cell. Note that this cell may change if the space is enlarged.

Returns:

The root cell.

getMaxParticlePerCell

public int getMaxParticlePerCell()

Maximum number of particles per cell. If a cell contains more particles it subdivides itself.

Returns:

The number of particles per cell.

getMaxDepth

public int getMaxDepth()

Maximum number of subdivisions of a cell.

Returns:

The maximum depth of the tree.

getListeners

public ArrayList<NTreeListener> getListeners()

The set of listeners of this tree.

Returns:

The listeners.

getOutOfUniverseMode

public NTree.OutOfUniverseMode getOutOfUniverseMode()

What to do if a particle leaves the root cell ?.

Returns:

The action to take when a particle leaves the root cell.

getLowestPoint

public Point3 getLowestPoint()

The lowest coordinate used by a particle. With the highest point this forms the universe bounding box.

Returns:

A point.

getHighestPoint

public Point3 getHighestPoint()

The highest coordinate used by a particle. With the lowest point this forms the universe bounding box.

Returns:

A point.

setDepthMax

public void setDepthMax(int max)

Set the maximum depth of the tree. Be careful, this launch a re-computation of the whole tree.

Parameters:

max - The maximum number of decomposition of space (>0).

addListener

public void addListener(NTreeListener listener)

Add a listener that will receive events abound the ntree.

Parameters:

listener - The listener to add.

removeListener

public void removeListener(NTreeListener listener)

Remove a listener.

Parameters:

listener - The listener to remove.

describeTheCurrentState

protected void describeTheCurrentState(NTreeListener listener)

Send events for all already existing cells to the newly added listener.

Parameters:

listener - The newly added listener.

removeParticle

public void removeParticle(Particle particle)

Remove a particle from the tree.

Parameters:

particle - The particle to remove.

addParticle

public void addParticle(Particle particle)

Add a particle in the tree.

Parameters:

particle - The particle to add.

checkDivisions

public void checkDivisions()

Recursively check if cells need subdivision or fusion. In some case if some particles left the root cell space and the policy is to resize this space, instead of checking divisions or fusions, this method recomputes the whole tree and resizes its space.

generateCellIdentifier

public String generateCellIdentifier(Cell parent,
                                     int index)

Generate an identifier for a cell given its parent and index in this parent. This method generates a unique path of the index of each parent cell.

Parameters:

parent - The parent.

index - The cell index.

Returns:

An unique cell identifier.

setOutOfUniverseMode

public void setOutOfUniverseMode(NTree.OutOfUniverseMode mode)

Tell what to do when a particle leaves the root cell. The DELETE mode kills the particle. The RESIZE mode make the root cell a child of as many cell as needed to contain the leaving particle.

Parameters:

mode - The mode to follow.

handleOutParticle

protected void handleOutParticle(Particle particle)

Decide what to do for a particle that moved out of the root cell space.

delete

protected void delete(Particle particle)

Ask a particle to remove itself from the particle box.

Parameters:

particle - The particle to remove.

resize

protected void resize(Particle particle)

Specify that a particle is out of the root cell space. This method remembers the particle position in order to compute the future new root cell space.

Parameters:

particle - The outrageous particle.

isValid

protected boolean isValid()

Make a recursive check of each cell of the tree.

Returns:

True if no discrepancy has been found.