Class IntBigList.IntBlockNode

  • Enclosing class:
    IntBigList

    static class IntBigList.IntBlockNode
    extends java.lang.Object
    Implements an AVLNode storing a IntBlock. 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

      • IntBlockNode

        private IntBlockNode​(IntBigList.IntBlockNode parent,
                             int relPos,
                             IntBigList.IntBlock block,
                             IntBigList.IntBlockNode rightFollower,
                             IntBigList.IntBlockNode 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

      • getIntBlock

        private IntBigList.IntBlock getIntBlock()
        Gets the block stored by this node.
        Returns:
        block stored by this node
      • setIntBlock

        private void setIntBlock​(IntBigList.IntBlock block)
        Sets block to store by this node.
        Parameters:
        block - the block to store
      • next

        private IntBigList.IntBlockNode next()
        Gets the next node in the list after this one.
        Returns:
        the next node
      • previous

        private IntBigList.IntBlockNode previous()
        Gets the node in the list before this one.
        Returns:
        the previous node
      • insert

        private IntBigList.IntBlockNode insert​(int index,
                                               IntBigList.IntBlock 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 IntBigList.IntBlockNode insertOnLeft​(int relIndex,
                                                     IntBigList.IntBlock 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 IntBigList.IntBlockNode insertOnRight​(int relIndex,
                                                      IntBigList.IntBlock 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 IntBigList.IntBlockNode getLeftSubTree()
        Gets the left node, returning null if its a faedelung.
      • getRightSubTree

        private IntBigList.IntBlockNode getRightSubTree()
        Gets the right node, returning null if its a faedelung.
      • max

        private IntBigList.IntBlockNode max()
        Gets the rightmost child of this node.
        Returns:
        the rightmost child (greatest index)
      • min

        private IntBigList.IntBlockNode min()
        Gets the leftmost child of this node.
        Returns:
        the leftmost child (smallest index)
      • removeSelf

        private IntBigList.IntBlockNode 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.
      • getHeight

        private int getHeight​(IntBigList.IntBlockNode 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 IntBigList.IntBlockNode rotateLeft()
        Rotate tree to the left using this node as center.
        Returns:
        node which will take the place of this node
      • rotateRight

        private IntBigList.IntBlockNode 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​(IntBigList.IntBlockNode node,
                             IntBigList.IntBlockNode 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​(IntBigList.IntBlockNode node,
                              IntBigList.IntBlockNode 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