Module org.arakhne.afc.core.mathtree

Package org.arakhne.afc.math.tree.node

Class IcosepQuadTreeNode<D,N extends IcosepQuadTreeNode<D,N>>

java.lang.Object

org.arakhne.afc.math.tree.node.AbstractParentlessTreeNode<D,N>

org.arakhne.afc.math.tree.node.AbstractTreeNode<D,N>

org.arakhne.afc.math.tree.node.QuadTreeNode<D,N>

org.arakhne.afc.math.tree.node.IcosepQuadTreeNode<D,N>

Type Parameters:

D - is the type of the data inside the tree

N - is the type of the tree nodes.

All Implemented Interfaces:

Serializable, Comparable<N>, IcosepTreeNodeContainer<N>, IterableNode<N>, TreeNode<D,N>, JsonableObject

Direct Known Subclasses:

AbstractGISTreeSetNode, IcosepQuadTreeNode.DefaultIcosepQuadTreeNode

public abstract class IcosepQuadTreeNode<D,N extends IcosepQuadTreeNode<D,N>>
extends QuadTreeNode<D,N>
implements IcosepTreeNodeContainer<N>

This is the generic implementation of a tree for which each node has four children and that implements the Icosep heuristic.

The icosep heuristic implies that all objects that intersect the split lines will be stored inside an addition child that contains only the corresponding objects.

Since:

13.0

Version:

17.0 2020-01-04 14:41:41

Author:

Stéphane GALLAND

See Also:

Serialized Form

Maven Group Id:

org.arakhne.afc.core

Maven Artifact Id:

mathtree

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	IcosepQuadTreeNode.DefaultIcosepQuadTreeNode<D>	This is the generic implementation of a quad tree with icosep heuristic.
static class	IcosepQuadTreeNode.IcosepQuadTreeZone	Available zones of a quad tree.

Nested classes/interfaces inherited from class org.arakhne.afc.math.tree.node.QuadTreeNode

QuadTreeNode.DefaultQuadTreeNode<D>, QuadTreeNode.QuadTreeZone

Field Summary

Fields inherited from class org.arakhne.afc.math.tree.node.AbstractParentlessTreeNode

DEFAULT_COPY_USER_DATA, DEFAULT_LINK_LIST_USE, nodeListeners, notNullChildCount

Constructor Summary

Constructors

Constructor	Description
IcosepQuadTreeNode()	Empty node.
IcosepQuadTreeNode(boolean useLinkedList)	Construct a node.
IcosepQuadTreeNode(boolean useLinkedList, boolean copyDataCollection, List<D> data)	Construct a node.
IcosepQuadTreeNode(boolean useLinkedList, D data)	Construct a node.
IcosepQuadTreeNode(D data)	Construct a node.
IcosepQuadTreeNode(Collection<D> data)	Construct a node.

Method Summary

Modifier and Type	Method	Description
void	clear()	Clear the tree.
N	getChildAt(int index)	Replies the n-th child in this node.
N	getChildAt(IcosepQuadTreeNode.IcosepQuadTreeZone zone)	Replies the node that is corresponding to the given zone.
int	getChildCount()	Replies count of children in this node.
void	getChildren(Object[] array)	Replies the child nodes of this node.
protected void	getHeights(int currentHeight, List<Integer> heights)	Replies the heights of all the leaf nodes.
N	getIcosepChild()	Get the icosep node of this node.
int	getMaxHeight()	Replies the maximal height of the tree.
int	getMinHeight()	Replies the minimal height of the tree.
Class<? extends Enum<?>>	getPartitionEnumeration()	Replies the enumeration type that is defining the children of the nodes.
int	indexOf(N child)	Replies the index of the specified child.
boolean	isLeaf()	Replies if this node is a leaf.
boolean	removeChild(N child)	Remove the specified node from this node if it is a child.
boolean	setChildAt(int index, N newChild)	Set the n-th child in this node.
protected void	setChildAtWithoutEventFiring(int index, N newChild)	Invoked by the inner classes to set the child at the given index without firing the events.
boolean	setIcosepChild(N newChild)	Set the icosep child of this node.

Methods inherited from class org.arakhne.afc.math.tree.node.QuadTreeNode

getChildAt, getFirstChild, getFourthChild, getNotNullChildCount, getSecondChild, getThirdChild, moveTo, moveTo, setChildAt, setFirstChild, setFourthChild, setSecondChild, setThirdChild, zoneOf

Methods inherited from class org.arakhne.afc.math.tree.node.AbstractTreeNode

children, firePropertyChildAdded, firePropertyChildAdded, firePropertyChildRemoved, firePropertyChildRemoved, firePropertyParentChanged, firePropertyParentChanged, firePropertyParentChanged, getChildren, getDepth, getParentNode, isRoot, moveTo, removeDeeplyFromParent, removeFromParent, setParentNodeReference

Methods inherited from class org.arakhne.afc.math.tree.node.AbstractParentlessTreeNode

addTreeNodeListener, addUserData, addUserData, addUserData, addUserData, compareTo, firePropertyDataChanged, firePropertyDataChanged, firePropertyDataChanged, getAllUserData, getAllUserData, getDeepNodeCount, getDeepUserDataCount, getHeights, getInternalDataStructureForUserData, getUserData, getUserDataAt, getUserDataCount, isEmpty, isValid, removeAllUserData, removeTreeNodeListener, removeUserData, removeUserData, removeUserData, setUserData, setUserData, setUserDataAt, toJson, toN, toString

Methods inherited from class java.lang.Object

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

Constructor Detail

IcosepQuadTreeNode

public IcosepQuadTreeNode()

Empty node.

IcosepQuadTreeNode

public IcosepQuadTreeNode(Collection<D> data)

Construct a node.

Parameters:

data - are the initial user data

IcosepQuadTreeNode

public IcosepQuadTreeNode(D data)

Construct a node.

Parameters:

data - are the initial user data

IcosepQuadTreeNode

public IcosepQuadTreeNode(boolean useLinkedList)

Construct a node.

Parameters:

useLinkedList - indicates if a linked list must be used to store the data. If false, an ArrayList will be used.

IcosepQuadTreeNode

public IcosepQuadTreeNode(boolean useLinkedList,
                          boolean copyDataCollection,
                          List<D> data)

Construct a node.

Parameters:

useLinkedList - indicates if a linked list must be used to store the data. If false, an ArrayList will be used.

copyDataCollection - indicates if the given data collection is copied if true or the inner data collection will be the given collection itself if false.

data - are the initial user data

IcosepQuadTreeNode

public IcosepQuadTreeNode(boolean useLinkedList,
                          D data)

Construct a node.

Parameters:

useLinkedList - indicates if a linked list must be used to store the data. If false, an ArrayList will be used.

data - are the initial user data

Method Detail

getPartitionEnumeration

@Pure
public Class<? extends Enum<?>> getPartitionEnumeration()

Description copied from interface: TreeNode

Replies the enumeration type that is defining the children of the nodes.

Specified by:

getPartitionEnumeration in interface TreeNode<D,N extends IcosepQuadTreeNode<D,N>>

Overrides:

getPartitionEnumeration in class QuadTreeNode<D,N extends IcosepQuadTreeNode<D,N>>

Returns:

the enumeration type of the child partition, or null if no such enumeration type is defined.

clear

public void clear()

Clear the tree.

Caution: this method also destroyes the links between the child nodes inside the tree. If you want to unlink the first-level child node with this node but leave the rest of the tree unchanged, please call setChildAt(i,null).

Specified by:

clear in interface TreeNode<D,N extends IcosepQuadTreeNode<D,N>>

Overrides:

clear in class QuadTreeNode<D,N extends IcosepQuadTreeNode<D,N>>

getChildCount

@Pure
public int getChildCount()

Description copied from interface: IterableNode

Replies count of children in this node.

The number of children is greater or equal to the value replied by IterableNode.getNotNullChildCount().

Specified by:

getChildCount in interface IterableNode<D>

Overrides:

getChildCount in class QuadTreeNode<D,N extends IcosepQuadTreeNode<D,N>>

Returns:

the count of children.

See Also:

IterableNode.getNotNullChildCount()

getChildAt

@Pure
public N getChildAt(int index)
             throws IndexOutOfBoundsException

Description copied from interface: IterableNode

Replies the n-th child in this node.

Specified by:

getChildAt in interface IterableNode<D>

Overrides:

getChildAt in class QuadTreeNode<D,N extends IcosepQuadTreeNode<D,N>>

Parameters:

index - is the index of the child to reply

Returns:

the child node.

Throws:

IndexOutOfBoundsException - if the given index was invalid

getChildAt

@Pure
public N getChildAt(IcosepQuadTreeNode.IcosepQuadTreeZone zone)

Replies the node that is corresponding to the given zone.

Parameters:

zone - the zone.

Returns:

the child node for the given zone, or null

setIcosepChild

public boolean setIcosepChild(N newChild)

Description copied from interface: IcosepTreeNodeContainer

Set the icosep child of this node.

Specified by:

setIcosepChild in interface IcosepTreeNodeContainer<D>

Parameters:

newChild - is the new child used as the icosep branch

Returns:

true on success, otherwise false

getIcosepChild

@Pure
public N getIcosepChild()

Description copied from interface: IcosepTreeNodeContainer

Get the icosep node of this node.

Specified by:

getIcosepChild in interface IcosepTreeNodeContainer<D>

Returns:

the node that is used as the icosep branch.

isLeaf

@Pure
public boolean isLeaf()

Description copied from interface: IterableNode

Replies if this node is a leaf.

Specified by:

isLeaf in interface IterableNode<D>

Overrides:

isLeaf in class QuadTreeNode<D,N extends IcosepQuadTreeNode<D,N>>

Returns:

true is this node is a leaf, otherwise false

setChildAt

public boolean setChildAt(int index,
                          N newChild)
                   throws IndexOutOfBoundsException

Description copied from interface: TreeNode

Set the n-th child in this node.

Specified by:

setChildAt in interface TreeNode<D,N extends IcosepQuadTreeNode<D,N>>

Overrides:

setChildAt in class QuadTreeNode<D,N extends IcosepQuadTreeNode<D,N>>

Parameters:

index - is the index of the child to reply

newChild - is the new child node.

Returns:

true if it was set, otherwise false

Throws:

IndexOutOfBoundsException - if the given index was invalid

setChildAtWithoutEventFiring

protected void setChildAtWithoutEventFiring(int index,
                                            N newChild)
                                     throws IndexOutOfBoundsException

Description copied from class: AbstractTreeNode

Invoked by the inner classes to set the child at the given index without firing the events. This function should never invoke AbstractTreeNode.setParentNodeReference(AbstractTreeNode, boolean).

Overrides:

setChildAtWithoutEventFiring in class QuadTreeNode<D,N extends IcosepQuadTreeNode<D,N>>

Parameters:

index - is the position of the new child.

newChild - is the new child

Throws:

IndexOutOfBoundsException - if the index is invalid.

removeChild

public boolean removeChild(N child)

Description copied from interface: TreeNode

Remove the specified node from this node if it is a child.

Specified by:

removeChild in interface TreeNode<D,N extends IcosepQuadTreeNode<D,N>>

Overrides:

removeChild in class QuadTreeNode<D,N extends IcosepQuadTreeNode<D,N>>

Parameters:

child - is the child to remove.

Returns:

true if the node was removed, otherwise false

indexOf

@Pure
public int indexOf(N child)

Description copied from interface: TreeNode

Replies the index of the specified child.

Specified by:

indexOf in interface TreeNode<D,N extends IcosepQuadTreeNode<D,N>>

Overrides:

indexOf in class QuadTreeNode<D,N extends IcosepQuadTreeNode<D,N>>

Parameters:

child - is the node to search for.

Returns:

the index or -1.

getChildren

public void getChildren(Object[] array)

Description copied from interface: TreeNode

Replies the child nodes of this node.

This function may put null in the array cells if the current tree node has not a child at the corresponding index.

Specified by:

getChildren in interface TreeNode<D,N extends IcosepQuadTreeNode<D,N>>

Overrides:

getChildren in class QuadTreeNode<D,N extends IcosepQuadTreeNode<D,N>>

Parameters:

array - is the array to fill.

See Also:

TreeNode.getChildren(Class), TreeNode.children()

getMinHeight

@Pure
public int getMinHeight()

Description copied from interface: TreeNode

Replies the minimal height of the tree.

Specified by:

getMinHeight in interface TreeNode<D,N extends IcosepQuadTreeNode<D,N>>

Overrides:

getMinHeight in class QuadTreeNode<D,N extends IcosepQuadTreeNode<D,N>>

Returns:

the height of the uppest leaf in the tree.

getMaxHeight

@Pure
public int getMaxHeight()

Description copied from interface: TreeNode

Replies the maximal height of the tree.

Specified by:

getMaxHeight in interface TreeNode<D,N extends IcosepQuadTreeNode<D,N>>

Overrides:

getMaxHeight in class QuadTreeNode<D,N extends IcosepQuadTreeNode<D,N>>

Returns:

the height of the lowest leaf in the tree.

getHeights

protected void getHeights(int currentHeight,
                          List<Integer> heights)

Description copied from class: AbstractParentlessTreeNode

Replies the heights of all the leaf nodes. The order of the heights is given by a depth-first iteration.

Overrides:

getHeights in class QuadTreeNode<D,N extends IcosepQuadTreeNode<D,N>>

Parameters:

currentHeight - is the current height of this node.

heights - is the list of heights to fill