org.apache.derby.impl.store.access.sort
Class SortBuffer

java.lang.Object
  extended byorg.apache.derby.impl.store.access.sort.SortBuffer

class SortBuffer
extends java.lang.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
private  NodeAllocator allocator
          Where to allocate nodes from.
private  DataValueDescriptor[] deletedKey
          Set, as a side effect of deleteLeftMost (only), to the key from the node that was deleted from the tree.
private  Node head
          Special head node for the tree.
private  int height
          The current height of the tree.
static int INSERT_DUPLICATE
          Returned from insert when the row which was inserted was a duplicate.
static int INSERT_FULL
          Returned from insert when the row was not able to be inserted because the set was full.
static int INSERT_OK
          Returned from insert when the row was inserted without incident.
private  int lastAux
          Read by the getLastAux() method.
private  int nextAux
          Set by the setNextAux() method.
private  MergeSort sort
          The sort this set is associated with.
private  boolean subtreeShrunk
          Set, as a side effect of deleteLeftMost and rotateRight, if the subtree they're working on decreased in height.
 
Constructor Summary
SortBuffer(MergeSort sort)
          Construct doesn't do anything, callers must call init and check its return code.
 
Method Summary
 int capacity()
          Return the number of elements this sorter can sort.
 void check()
           
private  java.lang.String checkNode(Node n)
           
 void close()
           
private  void debug(java.lang.String s)
           
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 depth(Node n)
           
 int getLastAux()
          Retrieve the aux value from the last node deallocated from the tree.
 void grow(int percent)
          Grow by a certain percent if we can
 boolean init()
          Initialize.
 int insert(DataValueDescriptor[] k)
          Insert a key k into the tree.
 void print()
           
private  void printRecursive(Node n, int depth)
           
 DataValueDescriptor[] removeFirst()
          Return the lowest key and delete it from the tree, preserving the balance of the tree.
 void reset()
           
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.
 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 Detail

INSERT_OK

public static final int INSERT_OK
Returned from insert when the row was inserted without incident.

See Also:
Constant Field Values

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:
Constant Field Values

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:
Constant Field Values

sort

private MergeSort sort
The sort this set is associated with.


allocator

private NodeAllocator allocator
Where to allocate nodes from.


head

private Node head
Special head node for the tree. Head.rightLink is the root of the tree.


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 Detail

SortBuffer

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

Method Detail

setNextAux

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


getLastAux

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


init

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


reset

public void reset()

close

public void close()

grow

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


capacity

public 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

public 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

public 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 java.lang.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(java.lang.String s)


Apache Derby V10.0 Engine Documentation - Copyright © 1997,2004 The Apache Software Foundation or its licensors, as applicable.