de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants
Class AbstractRStarTreeNode<N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry>

java.lang.Object
  de.lmu.ifi.dbs.elki.persistent.AbstractPage<N>
      de.lmu.ifi.dbs.elki.index.tree.AbstractNode<N,E>
          de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTreeNode<N,E>

Type Parameters:

N - Node type

E - Entry type

All Implemented Interfaces:

Node<N,E>, SpatialComparable, SpatialNode<N,E>, SpatialObject, Page<N>, Externalizable, Serializable

Direct Known Subclasses:

DeLiCluNode, RdKNNNode, RStarTreeNode

public abstract class AbstractRStarTreeNode<N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry>
extends AbstractNode<N,E>
implements SpatialNode<N,E>

Abstract superclass for nodes in a R*-Tree.

Author:

Elke Achtert

See Also:

Serialized Form

Field Summary

Fields inherited from class de.lmu.ifi.dbs.elki.index.tree.AbstractNode

eclass, entries, isLeaf, numEntries

Constructor Summary

AbstractRStarTreeNode()
Empty constructor for Externalizable interface.

AbstractRStarTreeNode(PageFile<N> file, int capacity, boolean isLeaf, Class<? super E> eclass)
Creates a new AbstractRStarTreeNode with the specified parameters.

Method Summary

void	adjustEntry(E entry) Adjusts the parameters of the entry representing this node.
protected abstract N	createNewDirectoryNode(int capacity) Creates a new directory node with the specified capacity.
protected abstract N	createNewLeafNode(int capacity) Creates a new leaf node with the specified capacity.
int	getDimensionality() Returns the dimensionality of this spatial object.
double	getMax(int dimension) Returns the maximum coordinate at the specified dimension.
double	getMin(int dimension) Returns the minimum coordinate at the specified dimension.
protected <D extends Distance<D>> void	initReInsert(int start, DistanceEntry<D,E>[] reInsertEntries) Initializes a reinsert operation.
void	integrityCheck() Tests this node (for debugging purposes).
protected void	integrityCheckParameters(N parent, int index) Tests, if the parameters of the entry representing this node, are correctly set.
HyperBoundingBox	mbr() Computes and returns the MBR of this spatial object.
void	readExternal(ObjectInput in) Reads the id of this node, the numEntries and the entries array from the specified stream.
N	splitEntries(List<E> sorting, int splitPoint) Splits the entries of this node into a new node at the specified splitPoint and returns the newly created node.
void	writeExternal(ObjectOutput out) Calls the super method and writes the id of this node, the numEntries and the entries array to the specified stream.

Methods inherited from class de.lmu.ifi.dbs.elki.index.tree.AbstractNode

addDirectoryEntry, addLeafEntry, children, deleteAllEntries, deleteEntry, equals, getCapacity, getEntries, getEntry, getNumEntries, increaseEntries, isLeaf, toString

Methods inherited from class de.lmu.ifi.dbs.elki.persistent.AbstractPage

getFile, getID, hashCode, isDirty, setDirty, setFile, setID

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface de.lmu.ifi.dbs.elki.index.tree.Node

addDirectoryEntry, addLeafEntry, children, getEntry, getNumEntries, isLeaf

Methods inherited from interface de.lmu.ifi.dbs.elki.persistent.Page

getID, isDirty, setDirty, setFile, setID

Methods inherited from interface de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialObject

getID

Constructor Detail

AbstractRStarTreeNode

public AbstractRStarTreeNode()

Empty constructor for Externalizable interface.

AbstractRStarTreeNode

public AbstractRStarTreeNode(PageFile<N> file,
                             int capacity,
                             boolean isLeaf,
                             Class<? super E> eclass)

Creates a new AbstractRStarTreeNode with the specified parameters.

Parameters:

file - the file storing the R*-Tree

capacity - the capacity (maximum number of entries plus 1 for overflow) of this node

isLeaf - indicates whether this node is a leaf node

eclass - Entry class, to initialize array storage

Method Detail

getMin

public double getMin(int dimension)

Description copied from interface: SpatialComparable

Returns the minimum coordinate at the specified dimension.

Specified by:

getMin in interface SpatialComparable

Parameters:

dimension - the dimension for which the coordinate should be returned, where 1 ≤ dimension ≤ getDimensionality()

Returns:

the minimum coordinate at the specified dimension

getMax

public double getMax(int dimension)

Description copied from interface: SpatialComparable

Returns the maximum coordinate at the specified dimension.

Specified by:

getMax in interface SpatialComparable

Parameters:

dimension - the dimension for which the coordinate should be returned, where 1 ≤ dimension ≤ getDimensionality()

Returns:

the maximum coordinate at the specified dimension

mbr

public HyperBoundingBox mbr()

Description copied from interface: SpatialNode

Computes and returns the MBR of this spatial object.

Specified by:

mbr in interface SpatialNode<N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry>

Returns:

the MBR of this spatial object

getDimensionality

public int getDimensionality()

Description copied from interface: SpatialNode

Returns the dimensionality of this spatial object.

Specified by:

getDimensionality in interface SpatialComparable

Specified by:

getDimensionality in interface SpatialNode<N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry>

Returns:

the dimensionality of this spatial object

adjustEntry

public void adjustEntry(E entry)

Adjusts the parameters of the entry representing this node.

Parameters:

entry - the entry representing this node

initReInsert

protected <D extends Distance<D>> void initReInsert(int start,
                                                    DistanceEntry<D,E>[] reInsertEntries)

Initializes a reinsert operation. Deletes all entries in this node and adds all entries from start index on to this node's children.

Parameters:

start - the start index of the entries that will be reinserted

reInsertEntries - the array of entries to be reinserted

splitEntries

public N splitEntries(List<E> sorting,
                      int splitPoint)

Splits the entries of this node into a new node at the specified splitPoint and returns the newly created node.

Parameters:

sorting - the sorted entries of this node

splitPoint - the split point of the entries

Returns:

the newly created split node

integrityCheck

public final void integrityCheck()

Tests this node (for debugging purposes).

integrityCheckParameters

protected void integrityCheckParameters(N parent,
                                        int index)

Tests, if the parameters of the entry representing this node, are correctly set. Subclasses may need to overwrite this method.

Parameters:

parent - the parent holding the entry representing this node

index - the index of the entry in the parents child array

writeExternal

public void writeExternal(ObjectOutput out)
                   throws IOException

Calls the super method and writes the id of this node, the numEntries and the entries array to the specified stream.

Specified by:

writeExternal in interface Externalizable

Overrides:

writeExternal in class AbstractNode<N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry>

Parameters:

out - the stream to write the object to

Throws:

IOException - Includes any I/O exceptions that may occur

readExternal

public void readExternal(ObjectInput in)
                  throws IOException,
                         ClassNotFoundException

Reads the id of this node, the numEntries and the entries array from the specified stream.

Specified by:

readExternal in interface Externalizable

Overrides:

readExternal in class AbstractNode<N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry>

Parameters:

in - the stream to read data from in order to restore the object

Throws:

IOException - if I/O errors occur

ClassNotFoundException - If the class for an object being restored cannot be found.

createNewLeafNode

protected abstract N createNewLeafNode(int capacity)

Creates a new leaf node with the specified capacity.

Specified by:

createNewLeafNode in class AbstractNode<N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry>

Parameters:

capacity - the capacity of the new node

Returns:

a new leaf node

createNewDirectoryNode

protected abstract N createNewDirectoryNode(int capacity)

Creates a new directory node with the specified capacity.

Specified by:

createNewDirectoryNode in class AbstractNode<N extends AbstractRStarTreeNode<N,E>,E extends SpatialEntry>

Parameters:

capacity - the capacity of the new node

Returns:

a new directory node