/*
 *  Licensed to the Apache Software Foundation (ASF) under one
 *  or more contributor license agreements.  See the NOTICE file
 *  distributed with this work for additional information
 *  regarding copyright ownership.  The ASF licenses this file
 *  to you under the Apache License, Version 2.0 (the
 *  "License"); you may not use this file except in compliance
 *  with the License.  You may obtain a copy of the License at
 *
 *    http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing,
 *  software distributed under the License is distributed on an
 *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 *  KIND, either express or implied.  See the License for the
 *  specific language governing permissions and limitations
 *  under the License.
 *
 */
package org.apache.directory.mavibot.btree;


import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertNotNull;
import static org.junit.Assert.assertTrue;
import static org.junit.Assert.fail;

import java.io.File;
import java.io.IOException;
import java.util.NoSuchElementException;
import java.util.UUID;

import org.apache.commons.io.FileUtils;
import org.apache.directory.mavibot.btree.BTree;
import org.apache.directory.mavibot.btree.RecordManager;
import org.apache.directory.mavibot.btree.Tuple;
import org.apache.directory.mavibot.btree.TupleCursor;
import org.apache.directory.mavibot.btree.exception.BTreeAlreadyManagedException;
import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
import org.apache.directory.mavibot.btree.serializer.LongSerializer;
import org.apache.directory.mavibot.btree.serializer.StringSerializer;
import org.junit.After;
import org.junit.Before;
import org.junit.Rule;
import org.junit.Test;
import org.junit.rules.TemporaryFolder;


/**
 * Tests the browse methods on a managed BTree
 * 
 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
 */
public class PersistedBTreeBrowseTest
{
    private BTree<Long, String> btree = null;

    private RecordManager recordManager1 = null;

    @Rule
    public TemporaryFolder tempFolder = new TemporaryFolder();

    private File dataDir = null;


    /**
     * Create a BTree for this test
     */
    @Before
    public void createBTree()
    {
        dataDir = tempFolder.newFolder( UUID.randomUUID().toString() );

        openRecordManagerAndBtree();

        try
        {
            // Create a new BTree which allows duplicate values
            btree = recordManager1.addBTree( "test", new LongSerializer(), new StringSerializer(), true );
        }
        catch ( Exception e )
        {
            throw new RuntimeException( e );
        }
    }


    @After
    public void cleanup() throws IOException
    {
        dataDir = new File( System.getProperty( "java.io.tmpdir" ) + "/recordman" );

        btree.close();

        if ( dataDir.exists() )
        {
            FileUtils.deleteDirectory( dataDir );
        }
    }


    /**
     * Reload the BTree into a new record manager
     */
    private void openRecordManagerAndBtree()
    {
        try
        {
            if ( recordManager1 != null )
            {
                recordManager1.close();
            }

            // Now, try to reload the file back
            recordManager1 = new RecordManager( dataDir.getAbsolutePath() );

            // load the last created btree
            if ( btree != null )
            {
                btree = recordManager1.getManagedTree( btree.getName() );
            }
        }
        catch ( Exception e )
        {
            throw new RuntimeException( e );
        }
    }


    /**
     * Check a tuple
     */
    private void checkTuple( Tuple<Long, String> tuple, long key, String value ) throws EndOfFileExceededException,
        IOException
    {
        assertNotNull( tuple );
        assertEquals( key, ( long ) tuple.getKey() );
        assertEquals( value, tuple.getValue() );
    }


    /**
     * Check a next() call
     */
    private void checkNext( TupleCursor<Long, String> cursor, long key, String value, boolean next, boolean prev )
        throws EndOfFileExceededException, IOException
    {
        Tuple<Long, String> tuple = cursor.next();

        checkTuple( tuple, key, value );
        assertEquals( next, cursor.hasNext() );
        assertEquals( prev, cursor.hasPrev() );
    }


    /**
     * Check a prev() call
     */
    private void checkPrev( TupleCursor<Long, String> cursor, long key, String value, boolean next, boolean prev )
        throws EndOfFileExceededException, IOException
    {
        Tuple<Long, String> tuple = cursor.prev();
        assertNotNull( tuple );
        assertEquals( key, ( long ) tuple.getKey() );
        assertEquals( value, tuple.getValue() );
        assertEquals( next, cursor.hasNext() );
        assertEquals( prev, cursor.hasPrev() );
    }


    /**
     * Construct a String representation of a number padded with 0 on the left
     */
    private String toString( long value, int size )
    {
        String valueStr = Long.toString( value );

        StringBuilder sb = new StringBuilder();

        if ( size > valueStr.length() )
        {
            for ( int i = valueStr.length(); i < size; i++ )
            {
                sb.append( "0" );
            }
        }

        sb.append( valueStr );

        return sb.toString();
    }


    //----------------------------------------------------------------------------------------
    // The Browse tests
    //----------------------------------------------------------------------------------------
    /**
     * Test the browse methods on an empty btree  
     */
    @Test
    public void testBrowseEmptyBTree() throws IOException, BTreeAlreadyManagedException
    {
        TupleCursor<Long, String> cursor = btree.browse();

        assertFalse( cursor.hasNext() );
        assertFalse( cursor.hasPrev() );

        try
        {
            cursor.next();
            fail();
        }
        catch ( NoSuchElementException nsee )
        {
            // Expected
        }

        try
        {
            cursor.prev();
            fail();
        }
        catch ( NoSuchElementException nsee )
        {
            // Expected
        }

        assertEquals( -1L, cursor.getRevision() );
    }


    /**
     * Test the browse methods on a btree containing just a leaf
     */
    @Test
    public void testBrowseBTreeLeafNext() throws IOException, BTreeAlreadyManagedException
    {
        // Inject some data
        btree.insert( 1L, "1" );
        btree.insert( 4L, "4" );
        btree.insert( 2L, "2" );
        btree.insert( 3L, "3" );
        btree.insert( 5L, "5" );

        // Create the cursor
        TupleCursor<Long, String> cursor = btree.browse();

        // Move forward
        cursor.beforeFirst();

        assertFalse( cursor.hasPrev() );
        assertTrue( cursor.hasNext() );

        checkNext( cursor, 1L, "1", true, false );
        checkNext( cursor, 2L, "2", true, true );
        checkNext( cursor, 3L, "3", true, true );
        checkNext( cursor, 4L, "4", true, true );
        checkNext( cursor, 5L, "5", false, true );
    }


    /**
     * Test the browse methods on a btree containing just a leaf
     */
    @Test
    public void testBrowseBTreeLeafPrev() throws IOException, BTreeAlreadyManagedException
    {
        // Inject some data
        btree.insert( 1L, "1" );
        btree.insert( 4L, "4" );
        btree.insert( 2L, "2" );
        btree.insert( 3L, "3" );
        btree.insert( 5L, "5" );

        // Create the cursor
        TupleCursor<Long, String> cursor = btree.browse();

        // Move backward
        cursor.afterLast();

        checkPrev( cursor, 5L, "5", false, true );
        checkPrev( cursor, 4L, "4", true, true );
        checkPrev( cursor, 3L, "3", true, true );
        checkPrev( cursor, 2L, "2", true, true );
        checkPrev( cursor, 1L, "1", true, false );
    }


    /**
     * Test the browse methods on a btree containing just a leaf and see if we can
     * move at the end or at the beginning
     */
    @Test
    public void testBrowseBTreeLeafFirstLast() throws IOException, BTreeAlreadyManagedException
    {
        // Inject some data
        btree.insert( 1L, "1" );
        btree.insert( 4L, "4" );
        btree.insert( 2L, "2" );
        btree.insert( 3L, "3" );
        btree.insert( 5L, "5" );

        // Create the cursor
        TupleCursor<Long, String> cursor = btree.browse();

        // We should not be able to move backward
        try
        {
            cursor.prev();
            fail();
        }
        catch ( NoSuchElementException nsee )
        {
            // Expected
        }

        // Start browsing three elements
        assertFalse( cursor.hasPrev() );
        assertTrue( cursor.hasNext() );
        Tuple<Long, String> tuple = cursor.next();
        tuple = cursor.next();
        tuple = cursor.next();

        // We should be at 3 now
        assertTrue( cursor.hasPrev() );
        assertTrue( cursor.hasNext() );
        assertEquals( 3L, ( long ) tuple.getKey() );
        assertEquals( "3", tuple.getValue() );

        // Move to the end
        cursor.afterLast();

        assertTrue( cursor.hasPrev() );
        assertFalse( cursor.hasNext() );

        // We should not be able to move forward
        try
        {
            cursor.next();
            fail();
        }
        catch ( NoSuchElementException nsee )
        {
            // Expected
        }

        // We should be at 5
        tuple = cursor.prev();
        assertEquals( 5L, ( long ) tuple.getKey() );
        assertEquals( "5", tuple.getValue() );

        assertTrue( cursor.hasPrev() );
        assertFalse( cursor.hasNext() );

        // Move back to the origin
        cursor.beforeFirst();

        assertFalse( cursor.hasPrev() );
        assertTrue( cursor.hasNext() );

        // We should be at 1
        tuple = cursor.next();
        assertEquals( 1L, ( long ) tuple.getKey() );
        assertEquals( "1", tuple.getValue() );

        assertFalse( cursor.hasPrev() );
        assertTrue( cursor.hasNext() );
    }


    /**
     * Test the browse methods on a btree containing just a leaf and see if we can
     * move back and forth
     */
    @Test
    public void testBrowseBTreeLeafNextPrev() throws IOException, BTreeAlreadyManagedException
    {
        // Inject some data
        btree.insert( 1L, "1" );
        btree.insert( 4L, "4" );
        btree.insert( 2L, "2" );
        btree.insert( 3L, "3" );
        btree.insert( 5L, "5" );

        // Create the cursor
        TupleCursor<Long, String> cursor = btree.browse();

        // We should not be able to move backward
        try
        {
            cursor.prev();
            fail();
        }
        catch ( NoSuchElementException nsee )
        {
            // Expected
        }

        // Start browsing three elements
        assertFalse( cursor.hasPrev() );
        assertTrue( cursor.hasNext() );
        Tuple<Long, String> tuple = cursor.next();
        tuple = cursor.next();
        tuple = cursor.next();

        // We should be at 3 now
        assertTrue( cursor.hasPrev() );
        assertTrue( cursor.hasNext() );
        assertEquals( 3L, ( long ) tuple.getKey() );
        assertEquals( "3", tuple.getValue() );

        // Now, move to the prev value
        cursor.prev();
        assertEquals( 2L, ( long ) tuple.getKey() );
        assertEquals( "2", tuple.getValue() );

        // And to the next value
        cursor.next();
        assertEquals( 3L, ( long ) tuple.getKey() );
        assertEquals( "3", tuple.getValue() );
    }


    /**
     * Test the browse methods on a btree containing many nodes
     */
    @Test
    public void testBrowseBTreeNodesNext() throws IOException, BTreeAlreadyManagedException
    {
        // Inject some data
        for ( long i = 1; i < 1000L; i++ )
        {
            btree.insert( i, Long.toString( i ) );
        }

        // Create the cursor
        TupleCursor<Long, String> cursor = btree.browse();

        // Move forward
        cursor.beforeFirst();

        assertFalse( cursor.hasPrev() );
        assertTrue( cursor.hasNext() );

        checkNext( cursor, 1L, "1", true, false );

        for ( long i = 2L; i < 999L; i++ )
        {
            checkNext( cursor, i, Long.toString( i ), true, true );
        }

        checkNext( cursor, 999L, "999", false, true );
    }


    /**
     * Test the browse methods on a btree containing many nodes
     */
    @Test
    public void testBrowseBTreeNodesPrev() throws IOException, BTreeAlreadyManagedException
    {
        // Inject some data
        for ( long i = 1; i < 1000L; i++ )
        {
            btree.insert( i, Long.toString( i ) );
        }

        // Create the cursor
        TupleCursor<Long, String> cursor = btree.browse();

        // Move backward
        cursor.afterLast();

        assertTrue( cursor.hasPrev() );
        assertFalse( cursor.hasNext() );

        checkPrev( cursor, 999L, "999", false, true );

        for ( long i = 998L; i > 1L; i-- )
        {
            checkPrev( cursor, i, Long.toString( i ), true, true );
        }

        checkPrev( cursor, 1L, "1", true, false );
    }


    /**
     * Test the browse methods on a btree containing just a leaf with duplicate values
     */
    @Test
    public void testBrowseBTreeLeafNextDups1() throws IOException, BTreeAlreadyManagedException
    {
        // Inject some duplicate data
        btree.insert( 1L, "1" );
        btree.insert( 1L, "4" );
        btree.insert( 1L, "2" );
        btree.insert( 1L, "3" );
        btree.insert( 1L, "5" );

        // Create the cursor
        TupleCursor<Long, String> cursor = btree.browse();

        // Move forward
        cursor.beforeFirst();

        assertFalse( cursor.hasPrev() );
        assertTrue( cursor.hasNext() );

        checkNext( cursor, 1L, "1", true, false );
        checkNext( cursor, 1L, "2", true, true );
        checkNext( cursor, 1L, "3", true, true );
        checkNext( cursor, 1L, "4", true, true );
        checkNext( cursor, 1L, "5", false, true );
    }


    /**
     * Test the browse methods on a btree containing just a leaf with duplicate values
     */
    @Test
    public void testBrowseBTreeLeafNextDupsN() throws IOException, BTreeAlreadyManagedException
    {
        // Inject some duplicate data
        btree.insert( 1L, "1" );
        btree.insert( 1L, "4" );
        btree.insert( 1L, "2" );
        btree.insert( 2L, "3" );
        btree.insert( 3L, "5" );
        btree.insert( 3L, "7" );
        btree.insert( 3L, "6" );

        // Create the cursor
        TupleCursor<Long, String> cursor = btree.browse();

        // Move forward
        cursor.beforeFirst();

        assertFalse( cursor.hasPrev() );
        assertTrue( cursor.hasNext() );

        checkNext( cursor, 1L, "1", true, false );
        checkNext( cursor, 1L, "2", true, true );
        checkNext( cursor, 1L, "4", true, true );
        checkNext( cursor, 2L, "3", true, true );
        checkNext( cursor, 3L, "5", true, true );
        checkNext( cursor, 3L, "6", true, true );
        checkNext( cursor, 3L, "7", false, true );
    }


    /**
     * Test the browse methods on a btree containing just a leaf with duplicate values
     */
    @Test
    public void testBrowseBTreeLeafPrevDups1() throws IOException, BTreeAlreadyManagedException
    {
        // Inject some duplicate data
        btree.insert( 1L, "1" );
        btree.insert( 1L, "4" );
        btree.insert( 1L, "2" );
        btree.insert( 1L, "3" );
        btree.insert( 1L, "5" );

        // Create the cursor
        TupleCursor<Long, String> cursor = btree.browse();

        // Move backward
        cursor.afterLast();

        assertTrue( cursor.hasPrev() );
        assertFalse( cursor.hasNext() );

        checkPrev( cursor, 1L, "5", false, true );
        checkPrev( cursor, 1L, "4", true, true );
        checkPrev( cursor, 1L, "3", true, true );
        checkPrev( cursor, 1L, "2", true, true );
        checkPrev( cursor, 1L, "1", true, false );
    }


    /**
     * Test the browse methods on a btree containing just a leaf with duplicate values
     */
    @Test
    public void testBrowseBTreeLeafPrevDupsN() throws IOException, BTreeAlreadyManagedException
    {
        // Inject some duplicate data
        btree.insert( 1L, "1" );
        btree.insert( 1L, "4" );
        btree.insert( 1L, "2" );
        btree.insert( 2L, "3" );
        btree.insert( 3L, "5" );
        btree.insert( 3L, "7" );
        btree.insert( 3L, "6" );

        // Create the cursor
        TupleCursor<Long, String> cursor = btree.browse();

        // Move backward
        cursor.afterLast();

        assertTrue( cursor.hasPrev() );
        assertFalse( cursor.hasNext() );

        checkPrev( cursor, 3L, "7", false, true );
        checkPrev( cursor, 3L, "6", true, true );
        checkPrev( cursor, 3L, "5", true, true );
        checkPrev( cursor, 2L, "3", true, true );
        checkPrev( cursor, 1L, "4", true, true );
        checkPrev( cursor, 1L, "2", true, true );
        checkPrev( cursor, 1L, "1", true, false );
    }


    /**
     * Test the browse methods on a btree containing nodes with duplicate values
     */
    @Test
    public void testBrowseBTreeNodesNextDupsN() throws IOException, BTreeAlreadyManagedException
    {
        // Inject some data
        for ( long i = 1; i < 1000L; i++ )
        {
            for ( long j = 1; j < 10; j++ )
            {
                btree.insert( i, Long.toString( j ) );
            }
        }

        // Create the cursor
        TupleCursor<Long, String> cursor = btree.browse();

        // Move backward
        cursor.beforeFirst();

        assertFalse( cursor.hasPrev() );
        assertTrue( cursor.hasNext() );
        boolean next = true;
        boolean prev = false;

        for ( long i = 1L; i < 1000L; i++ )
        {
            for ( long j = 1L; j < 10L; j++ )
            {
                checkNext( cursor, i, Long.toString( j ), next, prev );

                if ( ( i == 1L ) && ( j == 1L ) )
                {
                    prev = true;
                }

                if ( ( i == 999L ) && ( j == 8L ) )
                {
                    next = false;
                }
            }
        }
    }


    /**
     * Test the browse methods on a btree containing nodes with duplicate values
     */
    @Test
    public void testBrowseBTreeNodesPrevDupsN() throws IOException, BTreeAlreadyManagedException
    {
        // Inject some data
        for ( long i = 1; i < 1000L; i++ )
        {
            for ( int j = 1; j < 10; j++ )
            {
                btree.insert( i, Long.toString( j ) );
            }
        }

        // Create the cursor
        TupleCursor<Long, String> cursor = btree.browse();

        // Move backward
        cursor.afterLast();

        assertTrue( cursor.hasPrev() );
        assertFalse( cursor.hasNext() );
        boolean next = false;
        boolean prev = true;

        for ( long i = 999L; i > 0L; i-- )
        {
            for ( long j = 9L; j > 0L; j-- )
            {
                checkPrev( cursor, i, Long.toString( j ), next, prev );

                if ( ( i == 1L ) && ( j == 2L ) )
                {
                    prev = false;
                }

                if ( ( i == 999L ) && ( j == 9L ) )
                {
                    next = true;
                }
            }
        }
    }


    /**
     * Test the browse methods on a btree containing just a leaf with duplicate values
     * stored into a sub btree
     */
    @Test
    public void testBrowseBTreeLeafNextDupsSubBTree1() throws IOException, BTreeAlreadyManagedException
    {
        // Inject some duplicate data which will be stored into a sub btree
        for ( long i = 1L; i < 32L; i++ )
        {
            btree.insert( 1L, toString( i, 2 ) );
        }

        // Create the cursor
        TupleCursor<Long, String> cursor = btree.browse();

        // Move forward
        cursor.beforeFirst();

        assertFalse( cursor.hasPrev() );
        assertTrue( cursor.hasNext() );

        checkNext( cursor, 1L, "01", true, false );

        for ( long i = 2L; i < 31L; i++ )
        {
            checkNext( cursor, 1L, toString( i, 2 ), true, true );
        }

        checkNext( cursor, 1L, "31", false, true );
    }


    /**
     * Test the browse methods on a btree containing just a leaf with duplicate values
     */
    @Test
    public void testBrowseBTreeLeafPrevDupsSubBTree1() throws IOException, BTreeAlreadyManagedException
    {
        // Inject some duplicate data which will be stored into a sub btree
        for ( long i = 1L; i < 32L; i++ )
        {
            btree.insert( 1L, toString( i, 2 ) );
        }

        // Create the cursor
        TupleCursor<Long, String> cursor = btree.browse();

        // Move backward
        cursor.afterLast();

        assertTrue( cursor.hasPrev() );
        assertFalse( cursor.hasNext() );

        checkPrev( cursor, 1L, "31", false, true );

        for ( long i = 30L; i > 1L; i-- )
        {
            checkPrev( cursor, 1L, toString( i, 2 ), true, true );
        }

        checkPrev( cursor, 1L, "01", true, false );
    }


    //----------------------------------------------------------------------------------------
    // The BrowseFrom tests
    //----------------------------------------------------------------------------------------
    /**
     * Test the browseFrom method on an empty tree
     */
    @Test
    public void testBrowseFromEmptyBTree() throws IOException, BTreeAlreadyManagedException
    {
        TupleCursor<Long, String> cursor = btree.browseFrom( 1L );

        assertFalse( cursor.hasNext() );
        assertFalse( cursor.hasPrev() );

        try
        {
            cursor.next();
            fail();
        }
        catch ( NoSuchElementException nsee )
        {
            // Expected
        }

        try
        {
            cursor.prev();
            fail();
        }
        catch ( NoSuchElementException nsee )
        {
            // Expected
        }

        assertEquals( -1L, cursor.getRevision() );
    }


    /**
     * Test the browseFrom methods on a btree containing just a leaf
     */
    @Test
    public void testBrowseFromBTreeLeaf() throws IOException, BTreeAlreadyManagedException
    {
        // Inject some data
        btree.insert( 1L, "1" );
        btree.insert( 7L, "7" );
        btree.insert( 3L, "3" );
        btree.insert( 5L, "5" );
        btree.insert( 9L, "9" );

        // Create the cursor, starting at 5
        TupleCursor<Long, String> cursor = btree.browseFrom( 5L );

        assertTrue( cursor.hasPrev() );
        assertTrue( cursor.hasNext() );

        // Move forward
        checkNext( cursor, 5L, "5", true, true );
        checkNext( cursor, 7L, "7", true, true );
        checkNext( cursor, 9L, "9", false, true );

        cursor.close();

        // now, start at 5 and move backward
        cursor = btree.browseFrom( 5L );

        assertTrue( cursor.hasPrev() );
        assertTrue( cursor.hasNext() );

        // Move backward
        checkPrev( cursor, 3L, "3", true, true );
        checkPrev( cursor, 1L, "1", true, false );
        cursor.close();

        // Start at the first key
        cursor = btree.browseFrom( 1L );
        assertFalse( cursor.hasPrev() );
        assertTrue( cursor.hasNext() );

        checkNext( cursor, 1L, "1", true, false );
        checkNext( cursor, 3L, "3", true, true );

        // Start before the first key
        cursor = btree.browseFrom( 0L );
        assertFalse( cursor.hasPrev() );
        assertTrue( cursor.hasNext() );

        checkNext( cursor, 1L, "1", true, false );
        checkNext( cursor, 3L, "3", true, true );

        // Start at the last key
        cursor = btree.browseFrom( 9L );
        assertTrue( cursor.hasPrev() );
        assertTrue( cursor.hasNext() );

        checkNext( cursor, 9L, "9", false, true );
        checkPrev( cursor, 7L, "7", true, true );

        // Start after the last key
        cursor = btree.browseFrom( 10L );
        assertTrue( cursor.hasPrev() );
        assertFalse( cursor.hasNext() );

        checkPrev( cursor, 9L, "9", false, true );
        checkPrev( cursor, 7L, "7", true, true );

        // Start in the middle with a non existent key
        cursor = btree.browseFrom( 4L );
        assertTrue( cursor.hasPrev() );
        assertTrue( cursor.hasNext() );

        checkNext( cursor, 5L, "5", true, true );

        // Start in the middle with a non existent key
        cursor = btree.browseFrom( 4L );

        checkPrev( cursor, 3L, "3", true, true );
    }


    /**
     * Test the browseFrom method on a btree containing nodes with duplicate values
     */
    @Test
    public void testBrowseFromBTreeNodesPrevDupsN() throws IOException, BTreeAlreadyManagedException
    {
        // Inject some data
        for ( long i = 1; i < 1000L; i += 2 )
        {
            for ( int j = 1; j < 10; j++ )
            {
                btree.insert( i, Long.toString( j ) );
            }
        }

        // Create the cursor
        TupleCursor<Long, String> cursor = btree.browseFrom( 500L );

        // Move forward

        assertTrue( cursor.hasPrev() );
        assertTrue( cursor.hasNext() );
        boolean next = true;
        boolean prev = true;

        for ( long i = 501L; i < 1000L; i += 2 )
        {
            for ( long j = 1L; j < 10L; j++ )
            {
                if ( ( i == 999L ) && ( j == 9L ) )
                {
                    next = false;
                }

                checkNext( cursor, i, Long.toString( j ), next, prev );
            }
        }
    }


    //----------------------------------------------------------------------------------------
    // The TupleCursor.moveToNext/PrevNonDuplicateKey method tests
    //----------------------------------------------------------------------------------------
    /**
      * Test the TupleCursor.nextKey method on a btree containing nodes 
      * with duplicate values.
      */
    @Test
    public void testNextKey() throws IOException, BTreeAlreadyManagedException
    {
        // Inject some data
        for ( long i = 1; i < 1000L; i++ )
        {
            for ( long j = 1; j < 10; j++ )
            {
                btree.insert( i, Long.toString( j ) );
            }
        }

        // Create the cursor
        TupleCursor<Long, String> cursor = btree.browse();

        // Move forward
        cursor.beforeFirst();

        assertFalse( cursor.hasPrev() );
        assertTrue( cursor.hasNext() );
        boolean next = true;
        boolean prev = false;

        for ( long i = 1L; i < 999L; i++ )
        {
            Tuple<Long, String> tuple = cursor.nextKey();

            checkTuple( tuple, i, "1" );

            if ( i == 999L )
            {
                next = false;
            }

            assertEquals( next, cursor.hasNext() );
            assertEquals( prev, cursor.hasPrev() );

            if ( i == 1L )
            {
                prev = true;
            }
        }
    }


    /**
     * Test the TupleCursor.moveToPrevNonDuplicateKey method on a btree containing nodes 
     * with duplicate values.
     */
    @Test
    public void testPrevKey() throws IOException, BTreeAlreadyManagedException
    {
        // Inject some data
        for ( long i = 1; i < 1000L; i++ )
        {
            for ( long j = 1; j < 10; j++ )
            {
                btree.insert( i, Long.toString( j ) );
            }
        }

        // Create the cursor
        TupleCursor<Long, String> cursor = btree.browse();

        // Move backward
        cursor.afterLast();

        assertTrue( cursor.hasPrev() );
        assertFalse( cursor.hasNext() );
        boolean next = true;
        boolean prev = true;

        for ( long i = 999L; i > 0L; i-- )
        {
            Tuple<Long, String> tuple = cursor.prevKey();

            if ( i == 1L )
            {
                prev = false;
            }

            checkTuple( tuple, i, "1" );
            assertEquals( next, cursor.hasNext() );
            assertEquals( prev, cursor.hasPrev() );

            if ( i == 999L )
            {
                next = true;
            }
        }
    }
}