Package elki.index.tree

Class AbstractNode<E>

    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected java.lang.Object[] 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 Description
      AbstractNode()
      Empty constructor for Externalizable interface.
      AbstractNode​(int capacity, boolean isLeaf)
      Creates a new Node with the specified parameters.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      int addEntry​(E entry)
      Adds a new entry to this node's children and returns the index of the entry in the children array.
      java.util.Iterator<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.
      int getCapacity()
      Returns the capacity of this node (i.e. the length of the entries arrays).
      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​(java.io.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, java.util.List<E> sorting, int splitPoint)
      Redistribute entries according to the given sorting.
      void splitTo​(AbstractNode<E> newNode, java.util.List<E> assignmentsToFirst, java.util.List<E> assignmentsToSecond)
      Splits the entries of this node into a new node using the given assignments
      java.lang.String toString()
      Returns a string representation of this node.
      void writeExternal​(java.io.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 java.lang.Object

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

    • Field Detail

      • numEntries

        protected int numEntries
        The number of entries in this node.

      • entries

        protected java.lang.Object[] 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)
        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

    • Method Detail

      • children

        public final java.util.Iterator<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>
        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>
        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>
        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>
        Parameters:
        index - the index of the entry to be returned
        Returns:
        the entry at the specified index

      • writeExternal

        public void writeExternal​(java.io.ObjectOutput out)
                   throws java.io.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 java.io.Externalizable
        Overrides:
        writeExternal in class AbstractExternalizablePage
        Parameters:
        out - the stream to write the object to
        Throws:
        java.io.IOException - Includes any I/O exceptions that may occur

      • readExternal

        public void readExternal​(java.io.ObjectInput in)
                  throws java.io.IOException,
                         java.lang.ClassNotFoundException
        Reads the id of this node, the numEntries and the entries array from the specified stream.
        Specified by:
        readExternal in interface java.io.Externalizable
        Overrides:
        readExternal in class AbstractExternalizablePage
        Parameters:
        in - the stream to read data from in order to restore the object
        Throws:
        java.io.IOException - if I/O errors occur
        java.lang.ClassNotFoundException - If the class for an object being restored cannot be found.

      • toString

        public java.lang.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

      • addEntry

        public final int addEntry​(E entry)
        Description copied from interface: Node
        Adds a new entry to this node's children and returns the index of the entry in the children array. An IllegalStateException will be thrown when inserting leaf entries into directory nodes or conversely.
        Specified by:
        addEntry in interface Node<E>
        Parameters:
        entry - the entry to be added
        Returns:
        the index of the entry in this node's children array

      • 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

      • 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,
                          java.util.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,
                          java.util.List<E> assignmentsToFirst,
                          java.util.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