Module org.arakhne.afc.core.mathtree

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

Class IcosepBinaryTreeNode<D,N extends IcosepBinaryTreeNode<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.BinaryTreeNode<D,N>

org.arakhne.afc.math.tree.node.IcosepBinaryTreeNode<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:

IcosepBinaryTreeNode.DefaultIcosepBinaryTreeNode

public abstract class IcosepBinaryTreeNode<D,N extends IcosepBinaryTreeNode<D,N>>
extends BinaryTreeNode<D,N>
implements IcosepTreeNodeContainer<N>

This is the generic implementation of a tree for which each node has two 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	IcosepBinaryTreeNode.DefaultIcosepBinaryTreeNode<D>	This is the generic implementation of a quad tree with icosep heuristic.
static class	IcosepBinaryTreeNode.IcosepBinaryTreeZone	This is the generic implementation of a tree for which each node has two children.

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

BinaryTreeNode.BinaryTreeZone, BinaryTreeNode.DefaultBinaryTreeNode<D>

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
IcosepBinaryTreeNode()	Empty node.
IcosepBinaryTreeNode(boolean useLinkedList)	Construct node.
IcosepBinaryTreeNode(boolean useLinkedList, boolean copyDataCollection, List<D> data)	Construct node.
IcosepBinaryTreeNode(boolean useLinkedList, D data)	Construct node.
IcosepBinaryTreeNode(D data)	Construct node.
IcosepBinaryTreeNode(Collection<D> data)	Construct 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(IcosepBinaryTreeNode.IcosepBinaryTreeZone 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.BinaryTreeNode

getChildAt, getLeftChild, getNotNullChildCount, getRightChild, moveTo, setChildAt, setLeftChild, setRightChild

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

IcosepBinaryTreeNode

public IcosepBinaryTreeNode()

Empty node.

IcosepBinaryTreeNode

public IcosepBinaryTreeNode(Collection<D> data)

Construct node.

Parameters:

data - are the initial user data

IcosepBinaryTreeNode

public IcosepBinaryTreeNode(D data)

Construct node.

Parameters:

data - are the initial user data

IcosepBinaryTreeNode

public IcosepBinaryTreeNode(boolean useLinkedList)

Construct node.

Parameters:

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

IcosepBinaryTreeNode

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

Construct 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

IcosepBinaryTreeNode

public IcosepBinaryTreeNode(boolean useLinkedList,
                            D data)

Construct 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 IcosepBinaryTreeNode<D,N>>

Overrides:

getPartitionEnumeration in class BinaryTreeNode<D,N extends IcosepBinaryTreeNode<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 IcosepBinaryTreeNode<D,N>>

Overrides:

clear in class BinaryTreeNode<D,N extends IcosepBinaryTreeNode<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 BinaryTreeNode<D,N extends IcosepBinaryTreeNode<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 BinaryTreeNode<D,N extends IcosepBinaryTreeNode<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(IcosepBinaryTreeNode.IcosepBinaryTreeZone 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 BinaryTreeNode<D,N extends IcosepBinaryTreeNode<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 IcosepBinaryTreeNode<D,N>>

Overrides:

setChildAt in class BinaryTreeNode<D,N extends IcosepBinaryTreeNode<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 BinaryTreeNode<D,N extends IcosepBinaryTreeNode<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 IcosepBinaryTreeNode<D,N>>

Overrides:

removeChild in class BinaryTreeNode<D,N extends IcosepBinaryTreeNode<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 IcosepBinaryTreeNode<D,N>>

Overrides:

indexOf in class BinaryTreeNode<D,N extends IcosepBinaryTreeNode<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 IcosepBinaryTreeNode<D,N>>

Overrides:

getChildren in class BinaryTreeNode<D,N extends IcosepBinaryTreeNode<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 IcosepBinaryTreeNode<D,N>>

Overrides:

getMinHeight in class BinaryTreeNode<D,N extends IcosepBinaryTreeNode<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 IcosepBinaryTreeNode<D,N>>

Overrides:

getMaxHeight in class BinaryTreeNode<D,N extends IcosepBinaryTreeNode<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: BinaryTreeNode

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

Overrides:

getHeights in class BinaryTreeNode<D,N extends IcosepBinaryTreeNode<D,N>>

Parameters:

currentHeight - is the current height of this node.

heights - is the list of heights to fill