de.lmu.ifi.dbs.elki.index.tree

Class AbstractNode<E extends Entry>

java.lang.Object

de.lmu.ifi.dbs.elki.persistent.AbstractExternalizablePage

de.lmu.ifi.dbs.elki.index.tree.AbstractNode<E>

Type Parameters:

E - the type of Entry used in the index

All Implemented Interfaces:

Node<E>, ExternalizablePage, Page, Externalizable, Serializable

Direct Known Subclasses:

AbstractMTreeNode, AbstractRStarTreeNode

public abstract class AbstractNode<E extends Entry>
extends AbstractExternalizablePage
implements Node<E>

Abstract superclass for nodes in an tree based index structure.

Since:

0.2

Author:

Elke Achtert

See Also:

Serialized Form

Field Summary

Fields

Modifier and Type	Field and Description
protected E[]	entries The entries (children) of this node.
protected boolean	isLeaf Indicates whether this node is a leaf node.
protected int	numEntries The number of entries in this node.

Constructor Summary

Constructors

Constructor and Description
AbstractNode() Empty constructor for Externalizable interface.
AbstractNode(int capacity, boolean isLeaf, Class<? super E> eclass) Creates a new Node with the specified parameters.

Method Summary

Methods

Modifier and Type	Method and Description
int	addDirectoryEntry(E entry) Adds a new directory entry to this node's children and returns the index of the entry in this node's children array.
private int	addEntry(E entry) Adds the specified entry to the entries array and increases the numEntries counter.
int	addLeafEntry(E entry) Adds a new leaf entry to this node's children and returns the index of the entry in this node's children array.
Enumeration<IndexTreePath<E>>	children(IndexTreePath<E> parentPath) Returns an enumeration of the children paths of this node.
void	deleteAllEntries() Deletes all entries in this node.
boolean	deleteEntry(int index) Deletes the entry at the specified index and shifts all entries after the index to left.
boolean	equals(Object o) Returns true if this == o has the value true or o is not null and o is of the same class as this instance and super.equals(o) returns true and both nodes are of the same type (leaf node or directory node) and have contain the same entries, false otherwise.
int	getCapacity() Returns the capacity of this node (i.e. the length of the entries arrays).
List<E>	getEntries() Deprecated. Using this method means an extra copy - usually at the cost of performance.
E	getEntry(int index) Returns the entry at the specified index.
int	getNumEntries() Returns the number of entries of this node.
boolean	isLeaf() Returns true if this node is a leaf node, false otherwise.
void	readExternal(ObjectInput in) Reads the id of this node, the numEntries and the entries array from the specified stream.
void	removeMask(long[] mask) Remove entries according to the given mask.
void	splitByMask(AbstractNode<E> newNode, long[] assignment) Splits the entries of this node into a new node using the given assignments
void	splitTo(AbstractNode<E> newNode, List<E> sorting, int splitPoint) Redistribute entries according to the given sorting.
void	splitTo(AbstractNode<E> newNode, List<E> assignmentsToFirst, List<E> assignmentsToSecond) Splits the entries of this node into a new node using the given assignments
String	toString() Returns a string representation of this 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.persistent.AbstractExternalizablePage

getPageID, hashCode, isDirty, setDirty, setPageID

Methods inherited from class java.lang.Object

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

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

getPageID, isDirty, setDirty, setPageID

Field Detail

numEntries

protected int numEntries

The number of entries in this node.

entries

protected E extends Entry[] entries

The entries (children) of this node.

isLeaf

protected boolean isLeaf

Indicates whether this node is a leaf node.

Constructor Detail

AbstractNode

public AbstractNode()

Empty constructor for Externalizable interface.

AbstractNode

public AbstractNode(int capacity,
            boolean isLeaf,
            Class<? super E> eclass)

Creates a new Node with the specified parameters.

Parameters:

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

children

public final Enumeration<IndexTreePath<E>> children(IndexTreePath<E> parentPath)

Description copied from interface: Node

Returns an enumeration of the children paths of this node.

Specified by:

children in interface Node<E extends Entry>

Parameters:

parentPath - the path to this node

Returns:

an enumeration of the children paths of this node

getNumEntries

public final int getNumEntries()

Description copied from interface: Node

Returns the number of entries of this node.

Specified by:

getNumEntries in interface Node<E extends Entry>

Returns:

the number of entries of this node

isLeaf

public final boolean isLeaf()

Description copied from interface: Node

Returns true if this node is a leaf node, false otherwise.

Specified by:

isLeaf in interface Node<E extends Entry>

Returns:

true if this node is a leaf node, false otherwise

getEntry

public final E getEntry(int index)

Description copied from interface: Node

Returns the entry at the specified index.

Specified by:

getEntry in interface Node<E extends Entry>

Parameters:

index - the index of the entry to be returned

Returns:

the entry at the specified index

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 AbstractExternalizablePage

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 AbstractExternalizablePage

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.

equals

public boolean equals(Object o)

Returns true if this == o has the value true or o is not null and o is of the same class as this instance and super.equals(o) returns true and both nodes are of the same type (leaf node or directory node) and have contain the same entries, false otherwise.

Overrides:

equals in class AbstractExternalizablePage

Parameters:

o - the object to be tested

Returns:

true, if o is an AbstractNode and has the same id and the same entries as this node.

See Also:

AbstractExternalizablePage.equals(Object)

toString

public final String toString()

Returns a string representation of this node.

Overrides:

toString in class AbstractExternalizablePage

Returns:

the type of this node (LeafNode or DirNode) followed by its id

addLeafEntry

public final int addLeafEntry(E entry)

Adds a new leaf entry to this node's children and returns the index of the entry in this node's children array. An UnsupportedOperationException will be thrown if the entry is not a leaf entry or this node is not a leaf node.

Specified by:

addLeafEntry in interface Node<E extends Entry>

Parameters:

entry - the leaf entry to be added

Returns:

the index of the entry in this node's children array

Throws:

UnsupportedOperationException - if entry is not a leaf entry or this node is not a leaf node

addDirectoryEntry

public final int addDirectoryEntry(E entry)

Adds a new directory entry to this node's children and returns the index of the entry in this node's children array. An UnsupportedOperationException will be thrown if the entry is not a directory entry or this node is not a directory node.

Specified by:

addDirectoryEntry in interface Node<E extends Entry>

Parameters:

entry - the directory entry to be added

Returns:

the index of the entry in this node's children array

Throws:

UnsupportedOperationException - if entry is not a directory entry or this node is not a directory node

deleteEntry

public boolean deleteEntry(int index)

Deletes the entry at the specified index and shifts all entries after the index to left.

Parameters:

index - the index at which the entry is to be deleted

Returns:

true id deletion was successful

deleteAllEntries

public final void deleteAllEntries()

Deletes all entries in this node.

getCapacity

public final int getCapacity()

Returns the capacity of this node (i.e. the length of the entries arrays).

Returns:

the capacity of this node

getEntries

@Deprecated
public final List<E> getEntries()

Deprecated. Using this method means an extra copy - usually at the cost of performance.

Returns a list of the entries.

Returns:

a list of the entries

addEntry

private int addEntry(E entry)

Adds the specified entry to the entries array and increases the numEntries counter.

Parameters:

entry - the entry to be added

Returns:

the current number of entries

removeMask

public void removeMask(long[] mask)

Remove entries according to the given mask.

Parameters:

mask - Mask to remove

splitTo

public final void splitTo(AbstractNode<E> newNode,
           List<E> sorting,
           int splitPoint)

Redistribute entries according to the given sorting.

Parameters:

newNode - Node to split to

sorting - Sorting to use

splitPoint - Split point

splitTo

public final void splitTo(AbstractNode<E> newNode,
           List<E> assignmentsToFirst,
           List<E> assignmentsToSecond)

Splits the entries of this node into a new node using the given assignments

Parameters:

newNode - Node to split to

assignmentsToFirst - the assignment to this node

assignmentsToSecond - the assignment to the new node

splitByMask

public final void splitByMask(AbstractNode<E> newNode,
               long[] assignment)

Splits the entries of this node into a new node using the given assignments

Parameters:

newNode - Node to split to

assignment - Assignment mask