io.druid.collections.spatial

Class RTree

java.lang.Object

io.druid.collections.spatial.RTree

public class RTree
extends Object

This RTree has been optimized to work with bitmap inverted indexes. This code will probably make a lot more sense if you read: http://www.sai.msu.su/~megera/postgres/gist/papers/gutman-rtree.pdf

Constructor Summary

Constructors

Constructor and Description
RTree(BitmapFactory bitmapFactory)
RTree(int numDims, SplitStrategy splitStrategy, BitmapFactory bitmapFactory)

Method Summary

Modifier and Type	Method and Description
boolean	delete(double[] coords, int entry) Not yet implemented.
BitmapFactory	getBitmapFactory()
int	getNumDims()
Node	getRoot()
int	getSize()
SplitStrategy	getSplitStrategy()
void	insert(float[] coords, int entry) This description is from the original paper.
void	insert(float[] coords, MutableBitmap entry)

Methods inherited from class java.lang.Object

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

Constructor Detail

RTree

public RTree(BitmapFactory bitmapFactory)

RTree

public RTree(int numDims,
             SplitStrategy splitStrategy,
             BitmapFactory bitmapFactory)

Method Detail

getBitmapFactory

public BitmapFactory getBitmapFactory()

insert

public void insert(float[] coords,
                   int entry)

This description is from the original paper. Algorithm Insert: Insert a new index entry E into an R-tree. I1. [Find position for new record]. Invoke chooseLeaf(Node, Point) to select a leaf node L in which to place E. I2. [Add records to leaf node]. If L has room for another entry, install E. Otherwise invoke SplitStrategy split methods to obtain L and LL containing E and all the old entries of L. I3. [Propagate changes upward]. Invoke adjustTree(Node, Node) on L, also passing LL if a split was performed. I4. [Grow tree taller]. If node split propagation caused the root to split, create a new record whose children are the two resulting nodes.

Parameters:

coords - - the coordinates of the entry

entry - - the integer to insert

insert

public void insert(float[] coords,
                   MutableBitmap entry)

delete

public boolean delete(double[] coords,
                      int entry)

Not yet implemented.

Parameters:

coords - - the coordinates of the entry

entry - - the integer to insert

Returns:

- whether the operation completed successfully

getSize

public int getSize()

getNumDims

public int getNumDims()

getSplitStrategy

public SplitStrategy getSplitStrategy()

getRoot

public Node getRoot()