Hi,
some thoughts about the current implementation :
Cursor support in Mavibot
-------------------------
The current implementation is a bit unsastifactory, and it does not
necessarily fits with the simplifications we are introducing (namely,
the removal of duplicate values). Typically, the current cursor allows
the user to move forward and backward across keys and values, when we
only need to move across keys now.
Moving
------
First of all, we must be able to move backward and forward. Fetching an
element is a different operation than moving, but one should still be
able to get back an element when moving. This is done through 4 methods,
2 which are relative, and 2 which are absolute.
Relative moves :
next() : move forward to the net key
prev() : move forward to the net key
Absolute moves :
next(K) : move after the given key
prev(K) : move before the given key
The difference is that the relative move operation use the current
position, when the absolute moves use a key as a base. The following
picture shows what it means :
+---+ +---+ +---+ +---+ +---+
...--| A |--| B |--| C |--| D |--| E |--...
+---+ +---+ +---+ +---+ +---+
^
|
Current Position
When on C, next() -> returns D
When on C, prev() -> returns B
(for the record, When on C, a get() retunes C)
And
next(B) -> returns C
prev(B) -> returns A
Starting from a new cursor
--------------------------
Those operations are fine, but that raises an issue : how do we start
browing a B-tre if we can't use code like :
Cursor cursor = btree.browse();
while ( ??? )
{
Tuple tuple = cursor.next();
}
The problem, with such a code, is that you will not be able to get the
first element. Actually, the other question is how do we start from the
end of the B-tree ?
There are two solutions :
First we may have methods like hasNext()/hasPrev() that can be used in
this loop :
while ( cursor.hasNext() )
{
Tuple tuple = cursor.next();
}
That assumes we are not positionned at the first element, but *before*
the first element (same thing for the reverse browse).
The second solution is to ignore the returned tuple and use the get()
method :
while ( cursor.next() )
{
Tuple tuple = cursor.get();
}
but in this case, we don't need to return a Tuple when calling the
next() method, it's purely a positionning method..
Those are two posibilities to handle this feature. The first one is
close to what the Iterator interface offers, and it's probably more
natural for users. It fits well with the before(K)/after(K) methods.
I'd rather see the API implementing the first solution...
Last, not leat, to answer the initial question : how do we start ? We
need two extra methods :
- beforeFirst() and afterLast() that move the current position beofre
the first element and after the last one so that a call to next()/prev()
will return what we expect.
Methods removal
---------------
Some methods might need to be removed, they are useless :
- hasNextKey()/hasPrevKey()
- nextKey()/prevKey()
They are not anymore needed, we don't browse through values anymore.
Methods addition
----------------
We need some new methods :
- before(K)/after(K)
- get()
- first()
- last()
- isBeforeFirst()/isAfterLast()
Thoughts ?
