Class CharBigList.CharBlockNode

  • Enclosing class:
    CharBigList

    static class CharBigList.CharBlockNode
    extends java.lang.Object
    Implements an AVLNode storing a CharBlock. 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

      • getCharBlock

        private CharBigList.CharBlock getCharBlock()
        Gets the block stored by this node.
        Returns:
        block stored by this node
      • setCharBlock

        private void setCharBlock​(CharBigList.CharBlock block)
        Sets block to store by this node.
        Parameters:
        block - the block to store
      • previous

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

        private CharBigList.CharBlockNode insert​(int index,
                                                 CharBigList.CharBlock 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 CharBigList.CharBlockNode insertOnLeft​(int relIndex,
                                                       CharBigList.CharBlock 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 CharBigList.CharBlockNode insertOnRight​(int relIndex,
                                                        CharBigList.CharBlock 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)
      • getRightSubTree

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

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

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

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

        private CharBigList.CharBlockNode 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​(CharBigList.CharBlockNode node,
                             CharBigList.CharBlockNode 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​(CharBigList.CharBlockNode node,
                              CharBigList.CharBlockNode 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