Environment for
DeveLoping
KDD-Applications
Supported by Index-Structures

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

java.lang.Object
  extended by de.lmu.ifi.dbs.elki.logging.AbstractLoggable
      extended by de.lmu.ifi.dbs.elki.persistent.AbstractPage<N>
          extended by 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

Release 0.1 (2008-07-10_1838)