Class SortBuffer

java.lang.Object
org.apache.derby.impl.store.access.sort.SortBuffer

class SortBuffer extends Object
This class implements an in-memory ordered set based on the balanced binary tree algorithm from Knuth Vol. 3, Sec. 6.2.3, pp. 451-471. Nodes are always maintained in order, so that inserts and deletes can be intermixed.

This algorithm will insert/delete N elements in O(N log(N)) time using O(N) space.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    Where to allocate nodes from.
    Set, as a side effect of deleteLeftMost (only), to the key from the node that was deleted from the tree.
    private Node
    Special head node for the tree.
    private int
    The current height of the tree.
    static final int
    Returned from insert when the row which was inserted was a duplicate.
    static final int
    Returned from insert when the row was not able to be inserted because the set was full.
    static final int
    Returned from insert when the row was inserted without incident.
    private int
    Read by the getLastAux() method.
    private int
    Set by the setNextAux() method.
    private MergeSort
    The sort this set is associated with.
    private boolean
    Set, as a side effect of deleteLeftMost and rotateRight, if the subtree they're working on decreased in height.
  • Constructor Summary

    Constructors
    Constructor
    Description
    Construct doesn't do anything, callers must call init and check its return code.
  • Method Summary

    Modifier and Type
    Method
    Description
    (package private) int
    Return the number of elements this sorter can sort.
    void
     
    private String
     
    (package private) void
     
    private void
     
    private Node
    deleteLeftmost(Node thisNode)
    Delete the node with the lowest key from the subtree defined by 'thisNode', maintaining balance in the subtree.
    private int
     
    (package private) int
    Retrieve the aux value from the last node deallocated from the tree.
    (package private) void
    grow(int percent)
    Grow by a certain percent if we can
    (package private) boolean
    Initialize.
    (package private) int
    Insert a key k into the tree.
    void
     
    private void
    printRecursive(Node n, int depth)
     
    (package private) DataValueDescriptor[]
    Return the lowest key and delete it from the tree, preserving the balance of the tree.
    (package private) void
     
    private Node
    rotateRight(Node thisNode)
    Perform either a single or double rotation, as appropriate, to get the subtree 'thisNode' back in balance, assuming that the right subtree of 'thisNode' is higher than the left subtree.
    (package private) void
    setNextAux(int aux)
    Arrange that the next node allocated in the tree have it's aux field set to the argument.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Field Details

    • INSERT_OK

      public static final int INSERT_OK
      Returned from insert when the row was inserted without incident.
      See Also:
    • INSERT_DUPLICATE

      public static final int INSERT_DUPLICATE
      Returned from insert when the row which was inserted was a duplicate. The set will have aggregated it in.
      See Also:
    • INSERT_FULL

      public static final int INSERT_FULL
      Returned from insert when the row was not able to be inserted because the set was full.
      See Also:
    • sort

      private MergeSort sort
      The sort this set is associated with.
    • allocator

      private NodeAllocator allocator
      Where to allocate nodes from.
    • height

      private int height
      The current height of the tree.
    • deletedKey

      private DataValueDescriptor[] deletedKey
      Set, as a side effect of deleteLeftMost (only), to the key from the node that was deleted from the tree. This field is only valid after a call to deleteLeftMost.
    • subtreeShrunk

      private boolean subtreeShrunk
      Set, as a side effect of deleteLeftMost and rotateRight, if the subtree they're working on decreased in height. This field is only valid after a call to deleteLeftMost or rotateRight.
    • nextAux

      private int nextAux
      Set by the setNextAux() method. This value is stuffed into the aux field of the next node that's allocated.
    • lastAux

      private int lastAux
      Read by the getLastAux() method. This value is read out of the last node that was deallocated from the tree.
  • Constructor Details

    • SortBuffer

      SortBuffer(MergeSort sort)
      Construct doesn't do anything, callers must call init and check its return code.
  • Method Details

    • setNextAux

      void setNextAux(int aux)
      Arrange that the next node allocated in the tree have it's aux field set to the argument.
    • getLastAux

      int getLastAux()
      Retrieve the aux value from the last node deallocated from the tree.
    • init

      boolean init()
      Initialize. Returns false if the allocator couldn't be initialized.
    • reset

      void reset()
    • close

      void close()
    • grow

      void grow(int percent)
      Grow by a certain percent if we can
    • capacity

      int capacity()
      Return the number of elements this sorter can sort. It's the capacity of the node allocator minus one because the sorter uses one node for the head.
    • insert

      int insert(DataValueDescriptor[] k) throws StandardException
      Insert a key k into the tree. Returns true if the key was inserted, false if the tree is full. Silently ignores duplicate keys.

      See Knuth Vol. 3, Sec. 6.2.3, pp. 455-457 for the algorithm.

      Throws:
      StandardException
    • removeFirst

      DataValueDescriptor[] removeFirst()
      Return the lowest key and delete it from the tree, preserving the balance of the tree.
    • deleteLeftmost

      private Node deleteLeftmost(Node thisNode)
      Delete the node with the lowest key from the subtree defined by 'thisNode', maintaining balance in the subtree. Returns the node that should be the new root of the subtree. This method sets this.subtreeShrunk if the subtree of thisNode decreased in height. Saves the key that was in the deleted node in 'deletedKey'.
    • rotateRight

      private Node rotateRight(Node thisNode)
      Perform either a single or double rotation, as appropriate, to get the subtree 'thisNode' back in balance, assuming that the right subtree of 'thisNode' is higher than the left subtree. Returns the node that should be the new root of the subtree.

      These are the cases depicted in diagrams (1) and (2) of Knuth (p. 454), and the node names reflect these diagrams. However, in deletion, the single rotation may encounter a case where the "beta" and "gamma" subtrees are the same height (b.balance == 0), so the resulting does not always shrink.

      Note: This code will not do the "mirror image" cases. It only works when the right subtree is the higher one (this is the only case encountered when deleting leftmost nodes from the tree).

    • check

      public void check()
    • checkNode

      private String checkNode(Node n)
    • depth

      private int depth(Node n)
    • print

      public void print()
    • printRecursive

      private void printRecursive(Node n, int depth)
    • debug

      private void debug(String s)