Package org.apache.commons.collections.list

Class TreeList.AVLNode

java.lang.Object
org.apache.commons.collections.list.TreeList.AVLNode
Enclosing class:
TreeList
static class TreeList.AVLNode extends Object
Implements an AVLNode which keeps the offset updated.

This node contains the real work. TreeList is just there to implement List. 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.

The Faedelung calculation stores a 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

    • left

      private TreeList.AVLNode left
      The left child node or the predecessor if leftIsPrevious.

    • leftIsPrevious

      private boolean leftIsPrevious
      Flag indicating that left reference is not a subtree but the predecessor.

    • rightIsNext

      private boolean rightIsNext
      Flag indicating that right reference is not a subtree but the successor.

    • height

      private int height
      How many levels of left/right are below this one.

    • relativePosition

      private int relativePosition
      The relative position, root holds absolute position.

    • value

      private Object value
      The stored element.

  • Constructor Details

    • AVLNode

      private AVLNode(int relativePosition, Object obj, TreeList.AVLNode rightFollower, TreeList.AVLNode leftFollower)
      Constructs a new node with a relative position.
      Parameters:
      relativePosition - the relative position of the node
      obj - the value for the ndoe
      rightFollower - the node with the value following this one
      leftFollower - the node with the value leading this one

  • Method Details

    • getValue

      Object getValue()
      Gets the value.
      Returns:
      the value of this node

    • setValue

      void setValue(Object obj)
      Sets the value.
      Parameters:
      obj - the value to store

    • get

      TreeList.AVLNode get(int index)
      Locate the element with the given index relative to the offset of the parent of this node.

    • indexOf

      int indexOf(Object object, int index)
      Locate the index that contains the specified object.

    • toArray

      void toArray(Object[] array, int index)
      Stores the node and its children into the array specified.
      Parameters:
      array - the array to be filled
      index - the index of this node

    • next

      TreeList.AVLNode next()
      Gets the next node in the list after this one.
      Returns:
      the next node

    • previous

      TreeList.AVLNode previous()
      Gets the node in the list before this one.
      Returns:
      the previous node

    • insert

      TreeList.AVLNode insert(int index, Object obj)
      Inserts a node at the position index.
      Parameters:
      index - is the index of the position relative to the position of the parent node.
      obj - is the object to be stored in the position.

    • insertOnLeft

      private TreeList.AVLNode insertOnLeft(int indexRelativeToMe, Object obj)

    • insertOnRight

      private TreeList.AVLNode insertOnRight(int indexRelativeToMe, Object obj)

    • getLeftSubTree

      private TreeList.AVLNode getLeftSubTree()
      Gets the left node, returning null if its a faedelung.

    • getRightSubTree

      private TreeList.AVLNode getRightSubTree()
      Gets the right node, returning null if its a faedelung.

    • max

      private TreeList.AVLNode max()
      Gets the rightmost child of this node.
      Returns:
      the rightmost child (greatest index)

    • min

      private TreeList.AVLNode min()
      Gets the leftmost child of this node.
      Returns:
      the leftmost child (smallest index)

    • remove

      TreeList.AVLNode remove(int index)
      Removes the node at a given position.
      Parameters:
      index - is the index of the element to be removed relative to the position of the parent node of the current node.

    • removeMax

      private TreeList.AVLNode removeMax()

    • removeMin

      private TreeList.AVLNode removeMin()

    • removeSelf

      private TreeList.AVLNode removeSelf()
      Removes this node from the tree.
      Returns:
      the node that replaces this one in the parent

    • balance

      private TreeList.AVLNode balance()
      Balances according to the AVL algorithm.

    • getOffset

      private int getOffset(TreeList.AVLNode node)
      Gets the relative position.

    • setOffset

      private int setOffset(TreeList.AVLNode node, int newOffest)
      Sets the relative position.

    • recalcHeight

      private void recalcHeight()
      Sets the height by calculation.

    • getHeight

      private int getHeight(TreeList.AVLNode 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 TreeList.AVLNode rotateLeft()

    • rotateRight

      private TreeList.AVLNode rotateRight()

    • setLeft

      private void setLeft(TreeList.AVLNode node, TreeList.AVLNode 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(TreeList.AVLNode node, TreeList.AVLNode next)
      Sets the right field to the node, or the next node if that is null
      Parameters:
      node - the new left subtree node
      next - the next node in the linked list

    • toString

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