Top Description Fields Constructors Methods
org.apache.derby.impl.store.access.sort

pack-priv Class SortBuffer

extends Object
Class Inheritance
Imports
org.apache.derby.shared.common.sanity.SanityManager, org.apache.derby.shared.common.error.StandardException, org.apache.derby.iapi.types.DataValueDescriptor
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

Modifier and TypeField and Description
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.

public static final int
INSERT_DUPLICATE

Returned from insert when the row which was inserted was a duplicate.

public static final int
INSERT_FULL

Returned from insert when the row was not able to be inserted because the set was full.

public static final 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

AccessConstructor and Description
pack-priv
SortBuffer(MergeSort sort)

Construct doesn't do anything, callers must call init and check its return code.

Method Summary

Modifier and TypeMethod and Description
pack-priv int
capacity()

Return the number of elements this sorter can sort.

public void
check()

private String
checkNode(Node n)

pack-priv void
close()

private void
debug(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)

pack-priv int
getLastAux()

Retrieve the aux value from the last node deallocated from the tree.

pack-priv void
grow(int percent)

Grow by a certain percent if we can

pack-priv boolean
init()

Initialize.

pack-priv int
insert(DataValueDescriptor[] k)

Insert a key k into the tree.

private void
printRecursive(Node n, int depth)

pack-priv DataValueDescriptor[]
removeFirst()

Return the lowest key and delete it from the tree, preserving the balance of the tree.

pack-priv 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.

pack-priv void
setNextAux(int aux)

Arrange that the next node allocated in the tree have it's aux field set to the argument.

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

allocatorback to summary
private NodeAllocator allocator

Where to allocate nodes from.

deletedKeyback to summary
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.

heightback to summary
private int height

The current height of the tree.

INSERT_DUPLICATEback to summary
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.

INSERT_FULLback to summary
public static final int INSERT_FULL

Returned from insert when the row was not able to be inserted because the set was full.

INSERT_OKback to summary
public static final int INSERT_OK

Returned from insert when the row was inserted without incident.

lastAuxback to summary
private int lastAux

Read by the getLastAux() method. This value is read out of the last node that was deallocated from the tree.

nextAuxback to summary
private int nextAux

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

sortback to summary
private MergeSort sort

The sort this set is associated with.

subtreeShrunkback to summary
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.

Constructor Detail

SortBufferback to summary
pack-priv SortBuffer(MergeSort sort)

Construct doesn't do anything, callers must call init and check its return code.

Method Detail

capacityback to summary
pack-priv 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.

checkback to summary
public void check()
checkNodeback to summary
private String checkNode(Node n)
closeback to summary
pack-priv void close()
debugback to summary
private void debug(String s)
deleteLeftmostback to summary
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'.

depthback to summary
private int depth(Node n)
getLastAuxback to summary
pack-priv int getLastAux()

Retrieve the aux value from the last node deallocated from the tree.

growback to summary
pack-priv void grow(int percent)

Grow by a certain percent if we can

initback to summary
pack-priv boolean init()

Initialize. Returns false if the allocator couldn't be initialized.

insertback to summary
pack-priv 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.

printback to summary
public void print()
printRecursiveback to summary
private void printRecursive(Node n, int depth)
removeFirstback to summary
pack-priv DataValueDescriptor[] removeFirst()

Return the lowest key and delete it from the tree, preserving the balance of the tree.

resetback to summary
pack-priv void reset()
rotateRightback to summary
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).

setNextAuxback to summary
pack-priv void setNextAux(int aux)

Arrange that the next node allocated in the tree have it's aux field set to the argument.