Package org.magicwerk.brownies.collections

Class BigList.BlockNode<E>

java.lang.Object
org.magicwerk.brownies.collections.BigList.BlockNode<E>
Enclosing class:
BigList<E>
static class BigList.BlockNode<E> extends 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 Details

    • parent

      BigList.BlockNode<E> parent
      Pointer to parent node (null for root)

    • left

      BigList.BlockNode<E> left
      The left child node or the predecessor if leftIsPrevious.

    • 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.

    • block

      BigList.Block<E> block
      The stored block

  • Constructor Details

    • 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)
      block - the block to store
      rightFollower - the node following this one
      leftFollower - the node leading this one
      relativePosition - the relative position of the node (absolute position for root)

  • Method Details

    • 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:
      obj - object to store in the position
      index - index of the position relative to the position of the parent node
      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:
      obj - object to store in the position
      index - index of the position relative to the position of the parent node
      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)

    • removeMax

      private BigList.BlockNode<E> removeMax()

    • removeMin

      private BigList.BlockNode<E> removeMin(int size)

    • 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)

    • doRemoveSelf

      private BigList.BlockNode<E> doRemoveSelf()

    • 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 String toString()
      Used for debugging.
      Overrides:
      toString in class Object