Package org.magicwerk.brownies.collections.primitive

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