de.lmu.ifi.dbs.elki.index.tree
Class AbstractNode<N extends AbstractNode<N,E>,E extends Entry>

java.lang.Object
  de.lmu.ifi.dbs.elki.logging.AbstractLoggable
      de.lmu.ifi.dbs.elki.persistent.AbstractPage<N>
          de.lmu.ifi.dbs.elki.index.tree.AbstractNode<N,E>

All Implemented Interfaces:

Node<N,E>, Loggable, Page<N>, Externalizable, Serializable

Direct Known Subclasses:

AbstractMTreeNode, AbstractRStarTreeNode

public abstract class AbstractNode<N extends AbstractNode<N,E>,E extends Entry>
extends AbstractPage<N>
implements Node<N,E>

Abstract superclass for nodes in an tree based index structure.

Author:

Elke Achtert

See Also:

Serialized Form

Field Summary

private E[]	entries The entries (children) of this node.
private boolean	isLeaf Indicates wether this node is a leaf node.
private int	numEntries The number of entries in this node.

Fields inherited from class de.lmu.ifi.dbs.elki.logging.AbstractLoggable

debug

Constructor Summary

AbstractNode()
Empty constructor for Externalizable interface.

AbstractNode(PageFile<N> file, int capacity, boolean isLeaf)
Creates a new Node with the specified parameters.

Method Summary

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<TreeIndexPath<E>>	children(TreeIndexPath<E> parentPath) Returns an enumeration of the children paths of 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.
protected 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) Indicates whether some other object is "equal to" this one.
int	getCapacity() Returns the capacity of this node (i.e. the length of the entries arrays).
List<E>	getEntries() Returns a list of the entries.
E	getEntry(int index) Returns the entry at the specified index.
int	getNumEntries() Returns the number of entries of this node.
void	increaseEntries() Increases the length of the entries array to entries.length + 1.
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.
String	toString() Returns a string representation of this node.
void	writeExternal(ObjectOutput out) 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.AbstractPage

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

Methods inherited from class de.lmu.ifi.dbs.elki.logging.AbstractLoggable

debugFine, debugFiner, debugFinest, exception, message, progress, progress, progress, verbose, verbose, warning

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

getID, isDirty, setDirty, setFile, setID

Field Detail

numEntries

private int numEntries

The number of entries in this node.

entries

private E extends Entry[] entries

The entries (children) of this node.

isLeaf

private boolean isLeaf

Indicates wether this node is a leaf node.

Constructor Detail

AbstractNode

public AbstractNode()

Empty constructor for Externalizable interface.

AbstractNode

public AbstractNode(PageFile<N> file,
                    int capacity,
                    boolean isLeaf)

Creates a new Node with the specified parameters.

Parameters:

file - the file storing the index

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

isLeaf - indicates wether this node is a leaf node

Method Detail

children

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

Description copied from interface: Node

Returns an enumeration of the children paths of this node.

Specified by:

children in interface Node<N extends AbstractNode<N,E>,E extends Entry>

Parameters:

parentPath - the path to this node

Returns:

an enumeration of the children paths of this node

See Also:

Node.children(TreeIndexPath)

getNumEntries

public final int getNumEntries()

Description copied from interface: Node

Returns the number of entries of this node.

Specified by:

getNumEntries in interface Node<N extends AbstractNode<N,E>,E extends Entry>

Returns:

the number of entries of this node

See Also:

Node.getNumEntries()

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<N extends AbstractNode<N,E>,E extends Entry>

Returns:

true if this node is a leaf node, false otherwise

See Also:

Node.isLeaf()

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<N extends AbstractNode<N,E>,E extends Entry>

Parameters:

index - the index of the entry to be returned

Returns:

the entry at the specified index

See Also:

Node.getEntry(int)

writeExternal

public void writeExternal(ObjectOutput out)
                   throws IOException

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 AbstractPage<N extends AbstractNode<N,E>>

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 AbstractPage<N extends AbstractNode<N,E>>

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)

Indicates whether some other object is "equal to" this one.

Overrides:

equals in class AbstractPage<N extends AbstractNode<N,E>>

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.

toString

public final String toString()

Returns a string representation of this node.

Overrides:

toString in class AbstractPage<N extends AbstractNode<N,E>>

Returns:

a string representation of this node

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<N extends AbstractNode<N,E>,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<N extends AbstractNode<N,E>,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 deketed

Returns:

true id deletion was sucessfull

deleteAllEntries

protected final void deleteAllEntries()

Deletes all entries in this node.

increaseEntries

public final void increaseEntries()

Increases the length of the entries array to entries.length + 1.

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

public final List<E> getEntries()

Returns a list of the entries.

Returns:

a list of the entries

createNewLeafNode

protected abstract N createNewLeafNode(int capacity)

Creates a new leaf node with the specified capacity.

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.

Parameters:

capacity - the capacity of the new node

Returns:

a new directory node

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