org.danilopianini.lang

Class FlexibleQuadTree<E>

java.lang.Object

org.danilopianini.lang.FlexibleQuadTree<E>

Type Parameters:

E -

All Implemented Interfaces:

Serializable, SpatialIndex<E>

public final class FlexibleQuadTree<E>
extends Object
implements SpatialIndex<E>

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
private static class	FlexibleQuadTree.Child
private static class	FlexibleQuadTree.QuadTreeEntry<E>
private static class	FlexibleQuadTree.Rectangle2D

Field Summary

Fields

Modifier and Type	Field and Description
private FlexibleQuadTree.Rectangle2D	bounds
private List<com.google.common.base.Optional<FlexibleQuadTree<E>>>	children
private boolean	childrenCreated
static int	DEFAULT_CAPACITY Default maximum number of entries per node.
private Deque<FlexibleQuadTree.QuadTreeEntry<E>>	elements
private int	maxElements
private FlexibleQuadTree<E>	parent
private FlexibleQuadTree<E>	root root is NOT consistent everywhere.
private static long	serialVersionUID

Constructor Summary

Constructors

Modifier	Constructor and Description
	FlexibleQuadTree() Builds a FlexibleQuadTree with the default node capacity.
private	FlexibleQuadTree(double minx, double maxx, double miny, double maxy, int elemPerQuad, FlexibleQuadTree<E> rootNode, FlexibleQuadTree<E> parentNode)
	FlexibleQuadTree(int elemPerQuad)

Method Summary

Modifier and Type	Method and Description
private double	centerX()
private double	centerY()
private boolean	contains(double x, double y)
private FlexibleQuadTree<E>	create(double minx, double maxx, double miny, double maxy, FlexibleQuadTree<E> father)
private void	createChildIfAbsent(FlexibleQuadTree.Child c)
private void	createParent(double x, double y)
private FlexibleQuadTree<E>	getChild(FlexibleQuadTree.Child c)
int	getDimensions()
int	getMaxElementsNumber()
private boolean	hasChildren()
private boolean	hasSpace()
void	insert(E e, double... pos) Inserts an element in the SpatialIndex.
void	insert(E e, double x, double y) Same of insert(Object, double...), but with explicit parameters.
private void	insertHere(E e, double x, double y)
private void	insertNode(E e, double x, double y)
private double	maxX()
private double	maxX(FlexibleQuadTree.Child c)
private double	maxY()
private double	maxY(FlexibleQuadTree.Child c)
private double	minX()
private double	minX(FlexibleQuadTree.Child c)
private double	minY()
private double	minY(FlexibleQuadTree.Child c)
boolean	move(E e, double[] start, double[] end) If an element is moved, updates the SpatialIndex accordingly.
boolean	move(E e, double sx, double sy, double fx, double fy) Same of move(Object, double[], double[]), but with explicit parameters.
private boolean	moveFromNode(FlexibleQuadTree<E> root, E e, double sx, double sy, double fx, double fy)
List<E>	query(double[]... space) Queries the SpatialIndex, searching for elements in a parallelotope.
List<E>	query(double x1, double y1, double x2, double y2) Same of #query(double...), but with explicit parameters.
private void	query(double sx, double sy, double fx, double fy, List<E> results)
boolean	remove(E e, double... pos) Deletes an element from the SpatialIndex.
boolean	remove(E e, double x, double y) Same of remove(Object, double...) with explicit parameters.
private boolean	removeHere(E e, double x, double y)
private boolean	removeInChildren(E e, double x, double y)
private FlexibleQuadTree<E>	selectChild(double x, double y)
private void	setChild(FlexibleQuadTree.Child c, FlexibleQuadTree<E> child)
private void	subdivide()
private boolean	swapMostStatic(E e, double fx, double fy)
String	toString()

Methods inherited from class java.lang.Object

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

Field Detail

serialVersionUID

private static final long serialVersionUID

See Also:

Constant Field Values

DEFAULT_CAPACITY

public static final int DEFAULT_CAPACITY

Default maximum number of entries per node.

See Also:

Constant Field Values

bounds

private final FlexibleQuadTree.Rectangle2D bounds

elements

private final Deque<FlexibleQuadTree.QuadTreeEntry<E>> elements

maxElements

private final int maxElements

children

private final List<com.google.common.base.Optional<FlexibleQuadTree<E>>> children

root

private FlexibleQuadTree<E> root

root is NOT consistent everywhere. It is only guaranteed to be consistent in the entry point node and in the current root.

parent

private FlexibleQuadTree<E> parent

childrenCreated

private boolean childrenCreated

Constructor Detail

FlexibleQuadTree

public FlexibleQuadTree()

Builds a FlexibleQuadTree with the default node capacity.

FlexibleQuadTree

private FlexibleQuadTree(double minx,
                         double maxx,
                         double miny,
                         double maxy,
                         int elemPerQuad,
                         FlexibleQuadTree<E> rootNode,
                         FlexibleQuadTree<E> parentNode)

FlexibleQuadTree

public FlexibleQuadTree(int elemPerQuad)

Parameters:

elemPerQuad - maximum number of elements per quad

Method Detail

moveFromNode

private boolean moveFromNode(FlexibleQuadTree<E> root,
                             E e,
                             double sx,
                             double sy,
                             double fx,
                             double fy)

centerX

private double centerX()

centerY

private double centerY()

contains

private boolean contains(double x,
                         double y)

create

private FlexibleQuadTree<E> create(double minx,
                                   double maxx,
                                   double miny,
                                   double maxy,
                                   FlexibleQuadTree<E> father)

createChildIfAbsent

private void createChildIfAbsent(FlexibleQuadTree.Child c)

createParent

private void createParent(double x,
                          double y)

getChild

private FlexibleQuadTree<E> getChild(FlexibleQuadTree.Child c)

getDimensions

public int getDimensions()

Specified by:

getDimensions in interface SpatialIndex<E>

Returns:

the number of dimension of space for this SpatialIndex.

getMaxElementsNumber

public int getMaxElementsNumber()

Returns:

the maximum number of elements per node

hasChildren

private boolean hasChildren()

hasSpace

private boolean hasSpace()

insert

public void insert(E e,
                   double... pos)

Description copied from interface: SpatialIndex

Inserts an element in the SpatialIndex.

Specified by:

insert in interface SpatialIndex<E>

Parameters:

e - The element to add

pos - the coordinates where the element should be added

insert

public void insert(E e,
                   double x,
                   double y)

Same of insert(Object, double...), but with explicit parameters.

Parameters:

e - element

x - X

y - Y

insertHere

private void insertHere(E e,
                        double x,
                        double y)

insertNode

private void insertNode(E e,
                        double x,
                        double y)

maxX

private double maxX()

maxX

private double maxX(FlexibleQuadTree.Child c)

maxY

private double maxY()

maxY

private double maxY(FlexibleQuadTree.Child c)

minX

private double minX()

minX

private double minX(FlexibleQuadTree.Child c)

minY

private double minY()

minY

private double minY(FlexibleQuadTree.Child c)

move

public boolean move(E e,
                    double[] start,
                    double[] end)

Description copied from interface: SpatialIndex

If an element is moved, updates the SpatialIndex accordingly.

Specified by:

move in interface SpatialIndex<E>

Parameters:

e - The element to add

start - the coordinates where the element is currently located

end - the coordinates where the element is should be moved

Returns:

true if the element is found and moved

move

public boolean move(E e,
                    double sx,
                    double sy,
                    double fx,
                    double fy)

Same of move(Object, double[], double[]), but with explicit parameters.

Parameters:

e - the element

sx - the start x

sy - the start y

fx - the final x

fy - the final y

Returns:

true if the element is found and no error occurred

query

public List<E> query(double[]... space)

Description copied from interface: SpatialIndex

Queries the SpatialIndex, searching for elements in a parallelotope. "Parallelotope" is a fancy word for "N-dimensional rectangle". A 2-parallelotope is in fact a rectangle, a 3-parallelotope is a parallelepiped, and so on.

Specified by:

query in interface SpatialIndex<E>

Parameters:

space - the space where to search for elements

Returns:

the list of elements in this area of the SpatialIndex.

query

public List<E> query(double x1,
                     double y1,
                     double x2,
                     double y2)

Same of #query(double...), but with explicit parameters.

Parameters:

x1 - Rectangle X coordinate of the first point

y1 - Rectangle Y coordinate of the first point

x2 - Rectangle X coordinate of the second point

y2 - Rectangle Y coordinate of the second point

Returns:

List of Objects in range.

query

private void query(double sx,
                   double sy,
                   double fx,
                   double fy,
                   List<E> results)

remove

public boolean remove(E e,
                      double... pos)

Description copied from interface: SpatialIndex

Deletes an element from the SpatialIndex.

Specified by:

remove in interface SpatialIndex<E>

Parameters:

e - The element to add

pos - the coordinates where the element should be added

Returns:

true if the element is found and removed

remove

public boolean remove(E e,
                      double x,
                      double y)

Same of remove(Object, double...) with explicit parameters.

Parameters:

e - Element to remove

x - X position of the element

y - Y position of the element

Returns:

true if the element has been found and removed

removeHere

private boolean removeHere(E e,
                           double x,
                           double y)

removeInChildren

private boolean removeInChildren(E e,
                                 double x,
                                 double y)

selectChild

private FlexibleQuadTree<E> selectChild(double x,
                                        double y)

setChild

private void setChild(FlexibleQuadTree.Child c,
                      FlexibleQuadTree<E> child)

subdivide

private void subdivide()

swapMostStatic

private boolean swapMostStatic(E e,
                               double fx,
                               double fy)

toString

public String toString()

Overrides:

toString in class Object