Class QuadTreeNode<D,N extends QuadTreeNode<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>
-
- Type Parameters:
D
- is the type of the data inside the treeN
- is the type of the tree nodes.
- All Implemented Interfaces:
Serializable
,Comparable<N>
,IterableNode<N>
,TreeNode<D,N>
,JsonableObject
- Direct Known Subclasses:
IcosepQuadTreeNode
,QuadTreeNode.DefaultQuadTreeNode
public abstract class QuadTreeNode<D,N extends QuadTreeNode<D,N>> extends AbstractTreeNode<D,N>
This is the generic implementation of a tree for which each node has four children.moveTo
According to its definition inTreeNode.moveTo(TreeNode, int)
, the binary tree node implementation ofmoveTo
replaces any existing node at the position given as parameter ofmoveTo
..- 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
QuadTreeNode.DefaultQuadTreeNode<D>
This is the generic implementation of a quad tree.static class
QuadTreeNode.QuadTreeZone
Available zones of a quad tree.
-
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 QuadTreeNode()
Empty node.QuadTreeNode(boolean useLinkedList)
Constructor.QuadTreeNode(boolean useLinkedList, boolean copyDataCollection, List<D> data)
Constructor.QuadTreeNode(boolean useLinkedList, D data)
Constructor.QuadTreeNode(D data)
Construct a node.QuadTreeNode(Collection<D> data)
Construct a node.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description void
clear()
Clear the tree.N
getChildAt(int index)
Replies the n-th child in this node.N
getChildAt(QuadTreeNode.QuadTreeZone 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.N
getFirstChild()
Get the first child of this node.N
getFourthChild()
Get the fourth child of this node.protected void
getHeights(int currentHeight, List<Integer> heights)
Replies the heights of all the leaf nodes.int
getMaxHeight()
Replies the maximal height of the tree.int
getMinHeight()
Replies the minimal height of the tree.int
getNotNullChildCount()
Replies count of not-null children in this node.Class<? extends Enum<?>>
getPartitionEnumeration()
Replies the enumeration type that is defining the children of the nodes.N
getSecondChild()
Get the second child of this node.N
getThirdChild()
Get the third child of this node.int
indexOf(N child)
Replies the index of the specified child.boolean
isLeaf()
Replies if this node is a leaf.boolean
moveTo(N newParent, int index)
Move this node in the given new node.boolean
moveTo(N newParent, QuadTreeNode.QuadTreeZone zone)
Move this node in the given new node.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.boolean
setChildAt(QuadTreeNode.QuadTreeZone zone, N newChild)
Set the child at the specified zone.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
setFirstChild(N newChild)
Set the first child of this node.boolean
setFourthChild(N newChild)
Set the Fourth child of this node.boolean
setSecondChild(N newChild)
Set the second child of this node.boolean
setThirdChild(N newChild)
Set the third child of this node.QuadTreeNode.QuadTreeZone
zoneOf(N child)
Replies the zone of the specified child.-
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
-
-
-
-
Constructor Detail
-
QuadTreeNode
public QuadTreeNode()
Empty node.
-
QuadTreeNode
public QuadTreeNode(Collection<D> data)
Construct a node.- Parameters:
data
- are initial user data
-
QuadTreeNode
public QuadTreeNode(D data)
Construct a node.- Parameters:
data
- are initial user data
-
QuadTreeNode
public QuadTreeNode(boolean useLinkedList)
Constructor.- Parameters:
useLinkedList
- indicates if a linked list must be used to store the data. Iffalse
, an ArrayList will be used.
-
QuadTreeNode
public QuadTreeNode(boolean useLinkedList, boolean copyDataCollection, List<D> data)
Constructor.- Parameters:
useLinkedList
- indicates if a linked list must be used to store the data. Iffalse
, an ArrayList will be used.copyDataCollection
- indicates if the given data collection is copied iftrue
or the inner data collection will be the given collection itself iffalse
.data
- are initial user data
-
QuadTreeNode
public QuadTreeNode(boolean useLinkedList, D data)
Constructor.- Parameters:
useLinkedList
- indicates if a linked list must be used to store the data. Iffalse
, an ArrayList will be used.data
- are 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.- 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)
.
-
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()
.- Returns:
- the count of children.
- See Also:
IterableNode.getNotNullChildCount()
-
getNotNullChildCount
@Pure public int getNotNullChildCount()
Description copied from interface:IterableNode
Replies count of not-null children in this node.The number of not-null children is lower or equal to the value replied by
IterableNode.getChildCount()
.- Returns:
- the count of not-null children.
- See Also:
IterableNode.getChildCount()
-
getChildAt
@Pure public N getChildAt(int index) throws IndexOutOfBoundsException
Description copied from interface:IterableNode
Replies the n-th child in this node.- 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(QuadTreeNode.QuadTreeZone 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
.
-
setFirstChild
public boolean setFirstChild(N newChild)
Set the first child of this node.- Parameters:
newChild
- is the new child for the first zone- Returns:
true
on success, otherwhisefalse
-
getFirstChild
@Pure public final N getFirstChild()
Get the first child of this node.- Returns:
- the child for the first zone
-
setSecondChild
public boolean setSecondChild(N newChild)
Set the second child of this node.- Parameters:
newChild
- is the new child for the second zone- Returns:
true
on success, otherwhisefalse
-
getSecondChild
@Pure public final N getSecondChild()
Get the second child of this node.- Returns:
- the child for the second zone
-
setThirdChild
public boolean setThirdChild(N newChild)
Set the third child of this node.- Parameters:
newChild
- is the new child for the third zone- Returns:
true
on success, otherwhisefalse
-
getThirdChild
@Pure public final N getThirdChild()
Get the third child of this node.- Returns:
- the child for the third zone
-
setFourthChild
public boolean setFourthChild(N newChild)
Set the Fourth child of this node.- Parameters:
newChild
- is the new child for the fourth zone- Returns:
true
on success, otherwhisefalse
-
getFourthChild
@Pure public final N getFourthChild()
Get the fourth child of this node.- Returns:
- the child for the fourth zone
-
isLeaf
@Pure public boolean isLeaf()
Description copied from interface:IterableNode
Replies if this node is a leaf.- Returns:
true
is this node is a leaf, otherwisefalse
-
moveTo
public boolean moveTo(N newParent, int index)
Description copied from interface:TreeNode
Move this node in the given new node.If any child node is already present at the given position in the new parent node, the tree node may replace the existing node or insert the moving node according to its implementation.
This function is preferred to a sequence of calls to
IterableNode.removeFromParent()
andTreeNode.setChildAt(int, TreeNode)
because it fires a limited set of events dedicated to the move the node.- Parameters:
newParent
- is the new parent for this node.index
- is the position of this node in the new parent.- Returns:
true
on success, otherwisefalse
.
-
moveTo
public boolean moveTo(N newParent, QuadTreeNode.QuadTreeZone zone)
Move this node in the given new node.This function is preferred to a sequence of calls to
AbstractTreeNode.removeFromParent()
andsetChildAt(int, QuadTreeNode)
because it fires a limited set of events dedicated to the move the node.- Parameters:
newParent
- is the new parent for this node.zone
- is the position of this node in the new parent.- Returns:
true
on success, otherwisefalse
.
-
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 interfaceTreeNode<D,N extends QuadTreeNode<D,N>>
- Specified by:
setChildAt
in classAbstractTreeNode<D,N extends QuadTreeNode<D,N>>
- Parameters:
index
- is the index of the child to replynewChild
- is the new child node.- Returns:
true
if it was set, otherwisefalse
- Throws:
IndexOutOfBoundsException
- if the given index was invalid
-
setChildAt
public boolean setChildAt(QuadTreeNode.QuadTreeZone zone, N newChild)
Set the child at the specified zone.- Parameters:
zone
- is the zone to setnewChild
- is the new node for the given zone- Returns:
true
on success,false
otherwise
-
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 invokeAbstractTreeNode.setParentNodeReference(AbstractTreeNode, boolean)
.- Specified by:
setChildAtWithoutEventFiring
in classAbstractTreeNode<D,N extends QuadTreeNode<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.- Parameters:
child
- is the child to remove.- Returns:
true
if the node was removed, otherwisefalse
-
indexOf
@Pure public int indexOf(N child)
Description copied from interface:TreeNode
Replies the index of the specified child.- Parameters:
child
- is the node to search for.- Returns:
- the index or
-1
.
-
zoneOf
@Pure public QuadTreeNode.QuadTreeZone zoneOf(N child)
Replies the zone of the specified child.- Parameters:
child
- the child.- Returns:
- the index or
null
.
-
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.- 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.- 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.- 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.- Specified by:
getHeights
in classAbstractParentlessTreeNode<D,N extends QuadTreeNode<D,N>>
- Parameters:
currentHeight
- is the current height of this node.heights
- is the list of heights to fill
-
-