Class BigList.BlockNode<E>

  • Enclosing class:
    BigList<E>

    static class BigList.BlockNode<E>
    extends java.lang.Object
    Implements an AVLNode storing a Block. 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.
    • Constructor Detail

      • BlockNode

        private BlockNode​(BigList.BlockNode<E> parent,
                          int relPos,
                          BigList.Block<E> block,
                          BigList.BlockNode<E> rightFollower,
                          BigList.BlockNode<E> leftFollower)
        Constructs a new node.
        Parameters:
        parent - parent node (null for root)
        relativePosition - the relative position of the node (absolute position for root)
        block - the block to store
        rightFollower - the node following this one
        leftFollower - the node leading this one
    • Method Detail

      • getBlock

        private BigList.Block<E> getBlock()
        Gets the block stored by this node.
        Returns:
        block stored by this node
      • setBlock

        private void setBlock​(BigList.Block<E> block)
        Sets block to store by this node.
        Parameters:
        block - the block to store
      • next

        private BigList.BlockNode<E> next()
        Gets the next node in the list after this one.
        Returns:
        the next node
      • previous

        private BigList.BlockNode<E> previous()
        Gets the node in the list before this one.
        Returns:
        the previous node
      • insert

        private BigList.BlockNode<E> insert​(int index,
                                            BigList.Block<E> 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 BigList.BlockNode<E> insertOnLeft​(int relIndex,
                                                  BigList.Block<E> 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 BigList.BlockNode<E> insertOnRight​(int relIndex,
                                                   BigList.Block<E> 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)
      • getLeftSubTree

        private BigList.BlockNode<E> getLeftSubTree()
        Gets the left node, returning null if its a faedelung.
      • getRightSubTree

        private BigList.BlockNode<E> getRightSubTree()
        Gets the right node, returning null if its a faedelung.
      • max

        private BigList.BlockNode<E> max()
        Gets the rightmost child of this node.
        Returns:
        the rightmost child (greatest index)
      • min

        private BigList.BlockNode<E> min()
        Gets the leftmost child of this node.
        Returns:
        the leftmost child (smallest index)
      • removeSelf

        private BigList.BlockNode<E> removeSelf()
        Removes this node from the tree.
        Returns:
        the node that replaces this one in the parent (can be null)
      • balance

        private BigList.BlockNode<E> balance()
        Balances according to the AVL algorithm.
      • getOffset

        private int getOffset​(BigList.BlockNode<E> node)
        Gets the relative position.
      • setOffset

        private int setOffset​(BigList.BlockNode<E> node,
                              int newOffest)
        Sets the relative position.
      • recalcHeight

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

        private int getHeight​(BigList.BlockNode<E> node)
        Returns the height of the node or -1 if the node is null.
      • heightRightMinusLeft

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

        private BigList.BlockNode<E> rotateLeft()
        Rotate tree to the left using this node as center.
        Returns:
        node which will take the place of this node
      • rotateRight

        private BigList.BlockNode<E> 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​(BigList.BlockNode<E> node,
                             BigList.BlockNode<E> 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
      • setRight

        private void setRight​(BigList.BlockNode<E> node,
                              BigList.BlockNode<E> next)
        Sets the right field to the node, or the next node if that is null
        Parameters:
        node - the new right subtree node
        next - the next node in the linked list
      • toString

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