You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@directory.apache.org by Emmanuel Lécharny <el...@gmail.com> on 2013/12/06 14:37:50 UTC

[Mavibot] Cursor usage

Hi guys,

today, while I was working on the in-memory btree cursor, I looked at
the testDuplicateKey() test.

There are a few things that I disagree with in this test, or more
specifically on the semantic of next and prev methods. At the beginning
of the test, we start to browse the tree containing 2 elements, 1 and 2 :

    public void testDuplicateKey() throws IOException
    {
        BTreeConfiguration<Integer, Integer> config = new
BTreeConfiguration<Integer, Integer>();
        config.setAllowDuplicates( true );
        config.setName( "master" );
        config.setSerializers( serializer, serializer );
        BTree<Integer, Integer> btree = new BTree<Integer, Integer>(
config );

        btree.insert( 1, 1 );
        btree.insert( 1, 2 );

        TupleCursor<Integer, Integer> cursor = btree.browse();


At this point, we are BEFORE the first element, so a call to next()
should return <1, 1>, and it does :

        assertTrue( cursor.hasNext() );

        Tuple<Integer, Integer> t = cursor.next();

        assertEquals( Integer.valueOf( 1 ), t.getKey() );
        assertEquals( Integer.valueOf( 1 ), t.getValue() );


If we call next() a second time, we should get <1,2>, and we do :

        assertTrue( cursor.hasNext() );

        t = cursor.next();

        assertEquals( Integer.valueOf( 1 ), t.getKey() );
        assertEquals( Integer.valueOf( 2 ), t.getValue() );


There are no next value :

        assertFalse( cursor.hasNext() );


Now, the test is moving backward, and here, I disagree. The test is
expercing that doing a prev, we get again the same tuple <1,2> which
makes no sense to me :

        // test backward move
        assertTrue( cursor.hasPrev() );

        t = cursor.prev();

        assertEquals( Integer.valueOf( 1 ), t.getKey() );
        assertEquals( Integer.valueOf( 2 ), t.getValue() );

We should get instead <1,1>

o--[1]--[2]--x
^
|
+-- btreeBrowse()


o--[1]--[2]--x
    ^
    |
    +-- next()  : we are on 1


o--[1]--[2]--x
         ^
         |
         +-- next()  : we are on 2


At this point, a call to prev should move back to [1]



o--[1]--[2]--x
    ^
    |
    +-- prev()  : we are on 1


My point is that a next or a prev operation should move forward or
backward and return the current element *after* the move, not the opposite.

-- 
Regards,
Cordialement,
Emmanuel Lécharny
www.iktek.com 


Re: [Mavibot] Cursor usage

Posted by Kiran Ayyagari <ka...@apache.org>.
On Fri, Dec 6, 2013 at 7:07 PM, Emmanuel Lécharny <el...@gmail.com>wrote:

> Hi guys,
>
> today, while I was working on the in-memory btree cursor, I looked at
> the testDuplicateKey() test.
>
> There are a few things that I disagree with in this test, or more
> specifically on the semantic of next and prev methods. At the beginning
> of the test, we start to browse the tree containing 2 elements, 1 and 2 :
>
>     public void testDuplicateKey() throws IOException
>     {
>         BTreeConfiguration<Integer, Integer> config = new
> BTreeConfiguration<Integer, Integer>();
>         config.setAllowDuplicates( true );
>         config.setName( "master" );
>         config.setSerializers( serializer, serializer );
>         BTree<Integer, Integer> btree = new BTree<Integer, Integer>(
> config );
>
>         btree.insert( 1, 1 );
>         btree.insert( 1, 2 );
>
>         TupleCursor<Integer, Integer> cursor = btree.browse();
>
>
> At this point, we are BEFORE the first element, so a call to next()
> should return <1, 1>, and it does :
>
>         assertTrue( cursor.hasNext() );
>
>         Tuple<Integer, Integer> t = cursor.next();
>
>         assertEquals( Integer.valueOf( 1 ), t.getKey() );
>         assertEquals( Integer.valueOf( 1 ), t.getValue() );
>
>
> If we call next() a second time, we should get <1,2>, and we do :
>
>         assertTrue( cursor.hasNext() );
>
>         t = cursor.next();
>
>         assertEquals( Integer.valueOf( 1 ), t.getKey() );
>         assertEquals( Integer.valueOf( 2 ), t.getValue() );
>
>
> There are no next value :
>
>         assertFalse( cursor.hasNext() );
>
>
> Now, the test is moving backward, and here, I disagree. The test is
> expercing that doing a prev, we get again the same tuple <1,2> which
> makes no sense to me :
>
>         // test backward move
>         assertTrue( cursor.hasPrev() );
>
> agree, the above statement should be called after doing cursor.next()
with an assertion like assertFalse(cursor.next()), and then the cursor will
be at the far end.
and the reason the current test does what it does is due to an issue
in the Cursor implementation w.r.t switching direction, but I don't think
that issue still exists after recent refactoring and fixes.

>         t = cursor.prev();
>
>         assertEquals( Integer.valueOf( 1 ), t.getKey() );
>         assertEquals( Integer.valueOf( 2 ), t.getValue() );
>
> We should get instead <1,1>
>
> o--[1]--[2]--x
> ^
> |
> +-- btreeBrowse()
>
>
> o--[1]--[2]--x
>     ^
>     |
>     +-- next()  : we are on 1
>
>
> o--[1]--[2]--x
>          ^
>          |
>          +-- next()  : we are on 2
>
>
> At this point, a call to prev should move back to [1]
>
>
>
> o--[1]--[2]--x
>     ^
>     |
>     +-- prev()  : we are on 1
>
>
> My point is that a next or a prev operation should move forward or
> backward and return the current element *after* the move, not the opposite.
>
> --
> Regards,
> Cordialement,
> Emmanuel Lécharny
> www.iktek.com
>
>


-- 
Kiran Ayyagari
http://keydap.com