Class ShortBigList.ShortBlockNode

  • Enclosing class:
    ShortBigList

    static class ShortBigList.ShortBlockNode
    extends java.lang.Object
    Implements an AVLNode storing a ShortBlock. 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).
    • Field Detail

      • leftIsPrevious

        boolean leftIsPrevious
        Flag indicating that left reference is not a subtree but the predecessor.
      • rightIsNext

        boolean rightIsNext
        Flag indicating that right reference is not a subtree but the successor.
      • height

        int height
        How many levels of left/right are below this one.
      • relPos

        int relPos
        Relative position of node relative to its parent, root holds absolute position.
    • Method Detail

      • getShortBlock

        private ShortBigList.ShortBlock getShortBlock()
        Gets the block stored by this node.
        Returns:
        block stored by this node
      • setShortBlock

        private void setShortBlock​(ShortBigList.ShortBlock block)
        Sets block to store by this node.
        Parameters:
        block - the block to store
      • insert

        private ShortBigList.ShortBlockNode insert​(int index,
                                                   ShortBigList.ShortBlock 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 ShortBigList.ShortBlockNode insertOnLeft​(int relIndex,
                                                         ShortBigList.ShortBlock 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 ShortBigList.ShortBlockNode insertOnRight​(int relIndex,
                                                          ShortBigList.ShortBlock 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 ShortBigList.ShortBlockNode 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 ShortBigList.ShortBlockNode rotateLeft()
        Rotate tree to the left using this node as center.
        Returns:
        node which will take the place of this node
      • rotateRight

        private ShortBigList.ShortBlockNode rotateRight()
        Rotate tree to the right using this node as center.
        Returns:
        node which will take the place of this node
      • setLeft

        private void setLeft​(ShortBigList.ShortBlockNode node,
                             ShortBigList.ShortBlockNode previous)
        Sets the left field to the node, or the previous node if that is null
        Parameters:
        node - the new left subtree node
        previous - the previous node in the linked list
      • toString

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