com.bigdata.btree

Class BTree.LeafCursor

java.lang.Object

com.bigdata.btree.BTree.LeafCursor

All Implemented Interfaces:

ILeafCursor<Leaf>, Cloneable

Enclosing class:

BTree

public class BTree.LeafCursor
extends Object
implements ILeafCursor<Leaf>

A cursor that may be used to traversal Leafs.

Note: Instances of this class do NOT register an Leaf.ILeafListener and therefore do NOT notice if mutation causes the current leaf to become invalid. In general, you need to have a specific key in mind in order to re-locate the appropriate leaf after such mutation events.

Note: The AbstractBTreeTupleCursor.MutableBTreeTupleCursor does register such listeners.

Author:

Bryan Thompson

Constructor Summary

Constructors

Constructor and Description
BTree.LeafCursor(byte[] key)
BTree.LeafCursor(SeekEnum where)

Method Summary

Methods

Modifier and Type	Method and Description
BTree.LeafCursor	clone() Clone the cursor.
Leaf	first() Return the first leaf.
BTree	getBTree() The backing B+Tree.
Leaf	last() Return the last leaf.
Leaf	leaf() The current leaf (always defined).
Leaf	next() Return the next leaf in the natural order of the B+Tree.
Leaf	prior() Materialize the prior leaf in the natural order of the index (this is more general than the right sibling which is restricted to leaves that are children of the same direct parent).
Leaf	seek(byte[] key) Descend from the root node to the leaf spanning that key.
Leaf	seek(ILeafCursor<Leaf> src) Position this cursor on the same leaf as the given cursor.

Methods inherited from class java.lang.Object

equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

BTree.LeafCursor

public BTree.LeafCursor(SeekEnum where)

BTree.LeafCursor

public BTree.LeafCursor(byte[] key)

Method Detail

leaf

public Leaf leaf()

Description copied from interface: ILeafCursor

The current leaf (always defined).

Specified by:

leaf in interface ILeafCursor<Leaf>

getBTree

public BTree getBTree()

Description copied from interface: ILeafCursor

The backing B+Tree.

Specified by:

getBTree in interface ILeafCursor<Leaf>

clone

public BTree.LeafCursor clone()

Description copied from interface: ILeafCursor

Clone the cursor.

Specified by:

clone in interface ILeafCursor<Leaf>

Overrides:

clone in class Object

first

public Leaf first()

Description copied from interface: ILeafCursor

Return the first leaf.

Specified by:

first in interface ILeafCursor<Leaf>

last

public Leaf last()

Description copied from interface: ILeafCursor

Return the last leaf.

Specified by:

last in interface ILeafCursor<Leaf>

seek

public Leaf seek(byte[] key)

Descend from the root node to the leaf spanning that key. Note that the leaf may not actually contain the key, in which case it is the leaf that contains the insertion point for the key.

Specified by:

seek in interface ILeafCursor<Leaf>

Parameters:

key - The key

Returns:

The leaf which would span that key and never null.

seek

public Leaf seek(ILeafCursor<Leaf> src)

Description copied from interface: ILeafCursor

Position this cursor on the same leaf as the given cursor.

Specified by:

seek in interface ILeafCursor<Leaf>

Parameters:

src - A cursor.

Returns:

The leaf on which the given cursor was positioned.

next

public Leaf next()

Description copied from interface: ILeafCursor

Return the next leaf in the natural order of the B+Tree. The cursor position is unchanged if there is no successor.

Specified by:

next in interface ILeafCursor<Leaf>

Returns:

The next leaf -or- null iff there is no next leaf.

prior

public Leaf prior()

Materialize the prior leaf in the natural order of the index (this is more general than the right sibling which is restricted to leaves that are children of the same direct parent). The algorithm is:

1. Recursive ascent via the parent until there is a left-sibling of the child node (the index of the child in the parent must be GT zero). If we reach the root and there is no left-sibling then we are already on the left-most leaf and we are done.
2. t = leftSibling
3. while(!t.isLeaf()) right-descend

As we go up we pop each parent off of the hard reference stack.

As we go down we add each non-leaf node to the hard reference stack.

In order to make this operation atomic, the nodes to be popped are added to a temporary stack until we

Specified by:

prior in interface ILeafCursor<Leaf>

Returns:

The prior leaf -or- null if there is no predecessor of this leaf.