cytoscape.geom.rtree
Class RTree

java.lang.Object
  cytoscape.geom.rtree.RTree

All Implemented Interfaces:

MutableSpacialIndex2D, SpacialIndex2D, Serializable

public final class RTree
extends Object
implements MutableSpacialIndex2D, Serializable

An in-memory R-tree over real numbers in two dimensions.

An instance of this class is serializable; however, serialized instances of this class should not be stored in a persistent manner because the serialization implemented in this class makes no attempt at handling class versioning.

See Also:

Serialized Form

Field Summary

static int

DEFAULT_MAX_BRANCHES Deprecated. Use the no-arg constructor.

Constructor Summary

RTree()
Instantiates a new R-tree.

RTree(int maxBranches)
Deprecated. Use the no-arg constructor instead.

Method Summary

boolean	delete(int objKey) Deletes the specified data entry from this tree.
void	empty() Empties this R-tree of all entries.
boolean	exists(int objKey, float[] extentsArr, int offset) Determines whether or not a given entry exists in this R-tree structure, and conditionally retrieves the extents of that entry.
void	insert(int objKey, float xMin, float yMin, float xMax, float yMax) Inserts a new data entry into this tree; the entry's extents are specified by the input parameters.
SpacialEntry2DEnumerator	queryOverlap(float xMin, float yMin, float xMax, float yMax, float[] extentsArr, int offset, boolean reverse) Returns an enumeration of entries whose extents intersect the specified axis-aligned rectangular area.
int	size() Returns the number of entries currently in this R-tree.

Methods inherited from class java.lang.Object

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

Field Detail

DEFAULT_MAX_BRANCHES

public static final int DEFAULT_MAX_BRANCHES

Deprecated. Use the no-arg constructor.

See Also:

Constant Field Values

Constructor Detail

RTree

public RTree()

Instantiates a new R-tree. A new R-tree is empty (it has no entries).

RTree

public RTree(int maxBranches)

Deprecated. Use the no-arg constructor instead.

Instantiates a new R-tree with the specified maximum branching factor. Overriding the default maximum branching factor is only useful for testing purposes; there are no performance gains to be had.

Parameters:

maxBranches - the maximum branching factor of this tree.

Throws:

IllegalArgumentException - if maxBranches is less than three.

Method Detail

empty

public final void empty()

Empties this R-tree of all entries. This method returns in constant time (note however that garbage collection will take place in the background).

Specified by:

empty in interface MutableSpacialIndex2D

size

public final int size()

Returns the number of entries currently in this R-tree. This method returns in constant time.

NOTE: To retrieve an enumeration of all entries in this R-tree, call queryOverlap() with Float.NEGATIVE_INFINITY minimum values and Float.POSITIVE_INFINITY maximum values.

Specified by:

size in interface SpacialIndex2D

insert

public final void insert(int objKey,
                         float xMin,
                         float yMin,
                         float xMax,
                         float yMax)

Inserts a new data entry into this tree; the entry's extents are specified by the input parameters. "Extents" is a short way of saying "minimum bounding rectangle". The minimum bounding rectangle of an entry is axis-aligned, meaning that its sides are parallel to the axes of the data space.

Specified by:

insert in interface MutableSpacialIndex2D

Parameters:

objKey - a user-defined unique identifier used to refer to the entry being inserted in later operations; this identifier must be non-negative.

xMin - the minimum X coordinate of the entry's extents rectangle.

yMin - the minimum Y coordinate of the entry's extents rectangle.

xMax - the maximum X coordinate of the entry's extents rectangle.

yMax - the maximum Y coordinate of the entry's extents rectangle.

Throws:

IllegalStateException - if objKey is already used for an existing entry in this R-tree.

IllegalArgumentException - if objKey is negative, if xMin is not less than or equal to xMax, or if yMin is not less than or equal to yMax.

exists

public final boolean exists(int objKey,
                            float[] extentsArr,
                            int offset)

Determines whether or not a given entry exists in this R-tree structure, and conditionally retrieves the extents of that entry. The parameter extentsArr is written into by this method only if it is not null and if objKey exists in this R-tree. The information written into extentsArr consists of the minimum bounding rectangle (MBR) of objKey:

array index	value if objKey exists
offset	xMin of MBR
offset+1	yMin of MBR
offset+2	xMax of MBR
offset+3	yMax of MBR

The values written into extentsArr are exactly the same ones that were previously passed to insert() using the same objKey.

Specified by:

exists in interface SpacialIndex2D

Parameters:

objKey - a user-defined identifier that was [potentially] used in a previous insertion.

extentsArr - an array to which extent values will be written by this method; may be null.

offset - specifies the beginning index of where to write extent values into extentsArr; exactly four entries are written starting at this index (see above table); if extentsArr is null then this offset is ignored.

Returns:

true if and only if objKey was previously inserted into this R-tree and has not since been deleted.

Throws:

ArrayIndexOutOfBoundsException - if objKey exists, if extentsArr is not null, and if extentsArr cannot be written to in the index range [offset, offset+3].

delete

public final boolean delete(int objKey)

Deletes the specified data entry from this tree.

Specified by:

delete in interface MutableSpacialIndex2D

Parameters:

objKey - a user-defined identifier that was potentially used in a previous insertion.

Returns:

true if and only if objKey existed in this R-tree prior to this method invocation.

queryOverlap

public final SpacialEntry2DEnumerator queryOverlap(float xMin,
                                                   float yMin,
                                                   float xMax,
                                                   float yMax,
                                                   float[] extentsArr,
                                                   int offset,
                                                   boolean reverse)

Returns an enumeration of entries whose extents intersect the specified axis-aligned rectangular area. By "axis-aligned" I mean that the query rectangle's sides are parallel to the axes of the data space.

The parameter extentsArr is written into by this method if it is not null. It provides a way for this method to communicate additional information to the caller of this method. If not null, extentsArr is populated with information regarding the minimum bounding rectangle (MBR) that contains all returned entries. The following table describes what is written to extentsArr if it is not null:

array index	value if query generates results	value if query does not generate results
offset	xMin of MBR	Float.POSITIVE_INFINITY
offset+1	yMin of MBR	Float.POSITIVE_INFINITY
offset+2	xMax of MBR	Float.NEGATIVE_INFINITY
offset+3	yMax of MBR	Float.NEGATIVE_INFINITY

This R-tree has the subquery order-preserving property, which can be described as follows. Suppose we query the R-tree using this queryOverlap() method, specifying the maximum possible query rectangle (spanned by Float.NEGATIVE_INFINITY and Float.POSITIVE_INFINITY values); we get back all entries currently in this R-tree; the entries returned have a certain order to them. Let's remember this order. Now if we immediately perform any further query, specifying a different (or the same) query rectangle, then the entries that are returned in the query are returned in the same order as they were returned in the "all" query. This phenomenon continues to hold true with any additional queries until the R-tree undergoes a mutating operation such as insert() or delete(). The order of entries returned is in fact a left-to-right order in the underlying tree structure; in the future, if additional query methods are implemented, then they will also return entries in this same order.

IMPORTANT: The returned enumeration becomes invalid as soon as any structure-modifying operation (insert or delete) is performed on this R-tree. Accessing an invalid enumeration's methods will result in unpredictable and ill-defined behavior in that enumeration, but will have no effect on the integrity of the underlying tree structure.

NOTE: It may be possible to provide a more optimized version of this algorithm for point queries. Such a public method may be a future addition to this class.

Specified by:

queryOverlap in interface SpacialIndex2D

Parameters:

xMin - the minimum X coordinate of the query rectangle.

yMin - the minimum Y coordinate of the query rectangle.

xMax - the maximum X coordinate of the query rectangle.

yMax - the maximum Y coordinate of the query rectangle.

extentsArr - an array to which extent values will be written by this method; may be null.

offset - specifies the beginning index of where to write extent values into extentsArr; exactly four entries are written starting at this index (see table above); if extentsArr is null then this offset is ignored.

reverse - if true, the order in which the query hits are returned is reversed.

Returns:

a non-null enumeration of all [distinct] R-tree entries (objKeys) whose extents intersect the specified rectangular query area.

Throws:

IllegalArgumentException - if xMin is not less than or equal to xMax or if yMin is not less than or equal to yMax.

ArrayIndexOutOfBoundsException - if extentsArr is not null and if it cannot be written to in the index range [offset, offset+3].