class SortBuffer
extends java.lang.Object
This algorithm will insert/delete N elements in O(N log(N)) time using O(N) space.
Modifier and Type | Field | 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.
|
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 | Description |
---|---|
SortBuffer(MergeSort sort) |
Construct doesn't do anything, callers must call init
and check its return code.
|
Modifier and Type | Method | Description |
---|---|---|
(package private) int |
capacity() |
Return the number of elements this sorter can sort.
|
void |
check() |
|
private java.lang.String |
checkNode(Node n) |
|
(package private) 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) |
|
(package private) int |
getLastAux() |
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 |
init() |
Initialize.
|
(package private) int |
insert(DataValueDescriptor[] k) |
Insert a key k into the tree.
|
void |
print() |
|
private void |
printRecursive(Node n,
int depth) |
|
(package private) DataValueDescriptor[] |
removeFirst() |
Return the lowest key and delete it from
the tree, preserving the balance of the tree.
|
(package private) 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.
|
(package private) void |
setNextAux(int aux) |
Arrange that the next node allocated in the tree have
it's aux field set to the argument.
|
public static final int INSERT_OK
public static final int INSERT_DUPLICATE
public static final int INSERT_FULL
private MergeSort sort
private NodeAllocator allocator
private Node head
private int height
private DataValueDescriptor[] deletedKey
private boolean subtreeShrunk
private int nextAux
private int lastAux
SortBuffer(MergeSort sort)
void setNextAux(int aux)
int getLastAux()
boolean init()
void reset()
void close()
void grow(int percent)
int capacity()
int insert(DataValueDescriptor[] k) throws StandardException
See Knuth Vol. 3, Sec. 6.2.3, pp. 455-457 for the algorithm.
StandardException
DataValueDescriptor[] removeFirst()
private Node deleteLeftmost(Node thisNode)
private Node rotateRight(Node thisNode)
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).
public void check()
private java.lang.String checkNode(Node n)
private int depth(Node n)
public void print()
private void printRecursive(Node n, int depth)
private void debug(java.lang.String s)
Apache Derby V10.14 Internals - Copyright © 2004,2018 The Apache Software Foundation. All Rights Reserved.