| java.lang.Object
 org.apache.derby.impl.store.access.sort.SortBuffer
| SortBuffer | | class SortBuffer (Code) | | 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 | |
| final public static int | INSERT_DUPLICATE
Returned from insert when the row which was
inserted was a duplicate. | | final public static int | INSERT_FULL
Returned from insert when the row was not able to be
inserted because the set was full. | | final public static int | INSERT_OK
Returned from insert when the row was inserted
without incident. |
| Constructor Summary | |
| public | SortBuffer(MergeSort sort)
Construct doesn't do anything, callers must call init
and check its return code. |
| Method Summary | |
| public int | capacity()
Return the number of elements this sorter can sort. | | public void | check()
| | public void | close()
| | public int | getLastAux()
Retrieve the aux value from the last node deallocated
from the tree. | | public void | grow(int percent)
| | public boolean | init()
Initialize. | | public int | insert(DataValueDescriptor[] k)
Insert a key k into the tree. | | public void | print()
| | public DataValueDescriptor[] | removeFirst()
Return the lowest key and delete it from
the tree, preserving the balance of the tree. | | public void | reset()
| | public void | setNextAux(int aux)
Arrange that the next node allocated in the tree have
it's aux field set to the argument. |
| INSERT_DUPLICATE | | final public static int INSERT_DUPLICATE(Code) | | Returned from insert when the row which was
inserted was a duplicate. The set will have
aggregated it in.
|
| INSERT_FULL | | final public static int INSERT_FULL(Code) | | Returned from insert when the row was not able to be
inserted because the set was full.
|
| INSERT_OK | | final public static int INSERT_OK(Code) | | Returned from insert when the row was inserted
without incident.
|
| SortBuffer | | public SortBuffer(MergeSort sort)(Code) | | Construct doesn't do anything, callers must call init
and check its return code.
|
| capacity | | public int capacity()(Code) | | 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.
|
| check | | public void check()(Code) | | |
| close | | public void close()(Code) | | |
| getLastAux | | public int getLastAux()(Code) | | Retrieve the aux value from the last node deallocated
from the tree.
|
| grow | | public void grow(int percent)(Code) | | Grow by a certain percent if we can
|
| init | | public boolean init()(Code) | | Initialize. Returns false if the allocator
couldn't be initialized.
|
| insert | | public int insert(DataValueDescriptor[] k) throws StandardException(Code) | | 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.
|
| print | | public void print()(Code) | | |
| removeFirst | | public DataValueDescriptor[] removeFirst()(Code) | | Return the lowest key and delete it from
the tree, preserving the balance of the tree.
|
| reset | | public void reset()(Code) | | |
| setNextAux | | public void setNextAux(int aux)(Code) | | Arrange that the next node allocated in the tree have
it's aux field set to the argument.
|
|
|