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.persistent.AbstractPage<N>
      de.lmu.ifi.dbs.elki.index.tree.AbstractNode<N,E>

Type Parameters:

N - the type of Node used in the index

E - the type of Entry used in the index

All Implemented Interfaces:

Node<N,E>, 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

protected Class<E>	eclass Entry class.
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

AbstractNode()
Empty constructor for Externalizable interface.

AbstractNode(PageFile<N> file, int capacity, boolean isLeaf, Class<? super E> eclass)
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) 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() 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) 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.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.persistent.Page

getID, isDirty, setDirty, setFile, setID

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.

eclass

protected Class<E extends Entry> eclass

Entry class.

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(PageFile<N> file,
                    int capacity,
                    boolean isLeaf,
                    Class<? super E> eclass)

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 whether 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

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

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

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

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 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)

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 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.

See Also:

AbstractPage.equals(Object)

toString

public final String toString()

Returns a string representation of this node.

Overrides:

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

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<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 deleted

Returns:

true id deletion was successful

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