Class DoubleBigList.DoubleBlockNode

  • Enclosing class:
    DoubleBigList

    static class DoubleBigList.DoubleBlockNode
    extends java.lang.Object
    Implements an AVLNode storing a DoubleBlock. The nodes don't know the index of the object they are holding. They do know however their position relative to their parent node. This allows to calculate the index of a node while traversing the tree. There is a faedelung flag for both the left and right child to indicate if they are a child (false) or a link as in linked list (true).
    • Method Detail

      • getDoubleBlock

        private DoubleBigList.DoubleBlock getDoubleBlock()
        Gets the block stored by this node.
        Returns:
        block stored by this node
      • setDoubleBlock

        private void setDoubleBlock​(DoubleBigList.DoubleBlock block)
        Sets block to store by this node.
        Parameters:
        block - the block to store
      • insert

        private DoubleBigList.DoubleBlockNode insert​(int index,
                                                     DoubleBigList.DoubleBlock obj)
        Inserts new node holding specified block at the position index.
        Parameters:
        index - index of the position relative to the position of the parent node
        obj - object to store in the position
        Returns:
        this node or node replacing this node in the tree (if tree must be rebalanced)
      • insertOnLeft

        private DoubleBigList.DoubleBlockNode insertOnLeft​(int relIndex,
                                                           DoubleBigList.DoubleBlock obj)
        Inserts new node holding specified block on the node's left side.
        Parameters:
        index - index of the position relative to the position of the parent node
        obj - object to store in the position
        Returns:
        this node or node replacing this node in the tree (if tree must be rebalanced)
      • insertOnRight

        private DoubleBigList.DoubleBlockNode insertOnRight​(int relIndex,
                                                            DoubleBigList.DoubleBlock obj)
        Inserts new node holding specified block on the node's right side.
        Parameters:
        index - index of the position relative to the position of the parent node
        obj - object to store in the position
        Returns:
        this node or node replacing this node in the tree (if tree must be rebalanced)
      • removeSelf

        private DoubleBigList.DoubleBlockNode removeSelf()
        Removes this node from the tree.
        Returns:
        the node that replaces this one in the parent (can be null)
      • recalcHeight

        private void recalcHeight()
        Sets the height by calculation.
      • heightRightMinusLeft

        private int heightRightMinusLeft()
        Returns the height difference right - left
      • rotateLeft

        private DoubleBigList.DoubleBlockNode rotateLeft()
        Rotate tree to the left using this node as center.
        Returns:
        node which will take the place of this node
      • rotateRight

        private DoubleBigList.DoubleBlockNode rotateRight()
        Rotate tree to the right using this node as center.
        Returns:
        node which will take the place of this node
      • toString

        public java.lang.String toString()
        Used for debugging.
        Overrides:
        toString in class java.lang.Object