mavibot/src/test/java/org/apache/directory/mavibot/btree/InMemoryLeafTest.java

/*
 *  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.assertTrue;
import static org.junit.Assert.fail;

import java.io.IOException;

import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
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.Test;


/**
 * A unit test class for Leaf
 *
 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
 */
public class InMemoryLeafTest
{
    private BTree<Long, String> btree = null;


    /**
     * Create a btree
     */
    @Before
    public void setup() throws IOException
    {
        btree = BTreeFactory.createInMemoryBTree( "test", LongSerializer.INSTANCE, StringSerializer.INSTANCE );
        btree.setPageSize( 8 );
    }


    @After
    public void shutdown() throws IOException
    {
        btree.close();
    }


    /**
     * A helper method to insert elements in a Leaf
     * @throws IOException
     */
    private InMemoryLeaf<Long, String> insert( InMemoryLeaf<Long, String> leaf, long key, String value )
        throws IOException
    {
        InsertResult<Long, String> result = leaf.insert( key, value, 1L );

        return ( InMemoryLeaf<Long, String> ) ( ( ModifyResult<Long, String> ) result ).getModifiedPage();
    }


    /**
     * Test that deleting an entry from an empty page returns a NOT_PRESENT result
     * @throws IOException
     */
    @Test
    public void testDeleteFromEmptyLeaf() throws IOException
    {
        InMemoryLeaf<Long, String> leaf = new InMemoryLeaf<Long, String>( btree );

        DeleteResult<Long, String> result = leaf.delete( 1L, null, 1L, null, -1 );

        assertEquals( NotPresentResult.NOT_PRESENT, result );
    }


    /**
     * Test that deleting an entry which is not present in the leaf works
     * @throws IOException
     */
    @Test
    public void testDeleteNotPresentElementFromRootLeaf() throws IOException
    {
        InMemoryLeaf<Long, String> leaf = new InMemoryLeaf<Long, String>( btree );
        leaf = insert( leaf, 1L, "v1" );
        leaf = insert( leaf, 2L, "v2" );
        leaf = insert( leaf, 3L, "v3" );
        leaf = insert( leaf, 4L, "v4" );

        DeleteResult<Long, String> result = leaf.delete( 5L, null, 2L, null, -1 );

        assertEquals( NotPresentResult.NOT_PRESENT, result );
    }


    /**
     * Test that deleting an entry which is present in the leaf works
     * @throws IOException
     */
    @Test
    public void testDeletePresentElementFromRootLeaf() throws IOException
    {
        InMemoryLeaf<Long, String> leaf = new InMemoryLeaf<Long, String>( btree );
        leaf = insert( leaf, 1L, "v1" );
        leaf = insert( leaf, 2L, "v2" );
        leaf = insert( leaf, 3L, "v3" );
        leaf = insert( leaf, 4L, "v4" );

        DeleteResult<Long, String> result = leaf.delete( 3L, null, 4L, null, -1 );

        assertTrue( result instanceof RemoveResult );

        Tuple<Long, String> removedElement = ( ( RemoveResult<Long, String> ) result ).getRemovedElement();
        Page<Long, String> newLeaf = ( ( RemoveResult<Long, String> ) result ).getModifiedPage();

        assertEquals( Long.valueOf( 3L ), removedElement.getKey() );
        assertEquals( "v3", removedElement.getValue() );
        assertEquals( 3, newLeaf.getNbElems() );

        try
        {
            assertEquals( "v1", newLeaf.get( 1L ) );
            assertEquals( "v2", newLeaf.get( 2L ) );
            assertEquals( "v4", newLeaf.get( 4L ) );
        }
        catch ( KeyNotFoundException knfe )
        {
            fail();
        }

        try
        {
            newLeaf.get( 3L );
            fail();
        }
        catch ( KeyNotFoundException knfe )
        {
            // Expected
        }
    }


    /**
     * Test that deleting the first element return the correct result
     * @throws IOException
     */
    @Test
    public void testDeleteFirstElementFromRootLeaf() throws IOException
    {
        InMemoryLeaf<Long, String> leaf = new InMemoryLeaf<Long, String>( btree );
        leaf = insert( leaf, 1L, "v1" );
        leaf = insert( leaf, 2L, "v2" );
        leaf = insert( leaf, 3L, "v3" );
        leaf = insert( leaf, 4L, "v4" );

        DeleteResult<Long, String> result = leaf.delete( 1L, null, 4L, null, -1 );

        assertTrue( result instanceof RemoveResult );

        RemoveResult<Long, String> removeResult = ( RemoveResult<Long, String> ) result;

        Tuple<Long, String> removedElement = removeResult.getRemovedElement();
        Page<Long, String> newLeaf = removeResult.getModifiedPage();

        assertEquals( Long.valueOf( 1L ), removedElement.getKey() );
        assertEquals( "v1", removedElement.getValue() );
        assertEquals( 3, newLeaf.getNbElems() );

        try
        {
            newLeaf.get( 1L );
            fail();
        }
        catch ( KeyNotFoundException knfe )
        {
            // expected
        }

        try
        {
            assertEquals( "v2", newLeaf.get( 2L ) );
            assertEquals( "v3", newLeaf.get( 3L ) );
            assertEquals( "v4", newLeaf.get( 4L ) );
        }
        catch ( KeyNotFoundException knfe )
        {
            fail();
        }
    }


    /**
     * Check that deleting an element from a leaf with N/2 element works when we borrow
     * an element in a left page with more than N/2 elements.
     * The BTree contains :
     *            +--[1, 2, 3, 4, 5]
     * [6, 10]-+--[6, 7, 8, 9]
     *            +--[10, 11, 12, 13]
     * @throws IOException
     */
    @Test
    public void testDeleteBorrowingFromLeftSibling() throws IOException
    {
        InMemoryNode<Long, String> parent = new InMemoryNode<Long, String>( btree, 1L, 2 );
        InMemoryLeaf<Long, String> left = new InMemoryLeaf<Long, String>( btree );
        InMemoryLeaf<Long, String> target = new InMemoryLeaf<Long, String>( btree );
        InMemoryLeaf<Long, String> right = new InMemoryLeaf<Long, String>( btree );

        // Fill the left page
        left = insert( left, 1L, "v1" );
        left = insert( left, 2L, "v2" );
        left = insert( left, 3L, "v3" );
        left = insert( left, 4L, "v4" );
        left = insert( left, 5L, "v5" );

        // Fill the target page
        target = insert( target, 6L, "v6" );
        target = insert( target, 7L, "v7" );
        target = insert( target, 8L, "v8" );
        target = insert( target, 9L, "v9" );

        // Fill the right page
        right = insert( right, 10L, "v10" );
        right = insert( right, 11L, "v11" );
        right = insert( right, 12L, "v12" );
        right = insert( right, 13L, "v13" );

        parent.setPageHolder( 0, new PageHolder<Long, String>( btree, left ) );
        parent.setPageHolder( 1, new PageHolder<Long, String>( btree, target ) );
        parent.setPageHolder( 2, new PageHolder<Long, String>( btree, right ) );

        // Update the parent
        parent.setKey( 0, new KeyHolder<Long>( 6L ) );
        parent.setKey( 1, new KeyHolder<Long>( 10L ) );

        // Now, delete the element from the target page
        DeleteResult<Long, String> result = target.delete( 7L, null, 2L, parent, 1 );

        assertTrue( result instanceof BorrowedFromLeftResult );

        BorrowedFromLeftResult<Long, String> borrowed = ( BorrowedFromLeftResult<Long, String> ) result;
        Tuple<Long, String> removedKey = borrowed.getRemovedElement();

        assertEquals( Long.valueOf( 7L ), removedKey.getKey() );

        // Check the modified leaf
        InMemoryLeaf<Long, String> newLeaf = ( InMemoryLeaf<Long, String> ) borrowed.getModifiedPage();

        assertEquals( 4, newLeaf.getNbElems() );
        assertEquals( Long.valueOf( 5L ), newLeaf.getKey( 0 ) );
        assertEquals( Long.valueOf( 6L ), newLeaf.getKey( 1 ) );
        assertEquals( Long.valueOf( 8L ), newLeaf.getKey( 2 ) );
        assertEquals( Long.valueOf( 9L ), newLeaf.getKey( 3 ) );

        // Check the sibling
        InMemoryLeaf<Long, String> leftSibling = ( InMemoryLeaf<Long, String> ) borrowed.getModifiedSibling();

        assertEquals( 4, leftSibling.getNbElems() );
        assertEquals( Long.valueOf( 1L ), leftSibling.getKey( 0 ) );
        assertEquals( Long.valueOf( 2L ), leftSibling.getKey( 1 ) );
        assertEquals( Long.valueOf( 3L ), leftSibling.getKey( 2 ) );
        assertEquals( Long.valueOf( 4L ), leftSibling.getKey( 3 ) );
    }


    /**
     * Check that deleting an element from a leaf with N/2 element works when we borrow
     * an element in a right page with more than N/2 elements
     * @throws IOException
     */
    @Test
    public void testDeleteBorrowingFromRightSibling() throws IOException
    {
        InMemoryNode<Long, String> parent = new InMemoryNode<Long, String>( btree, 1L, 2 );
        InMemoryLeaf<Long, String> left = new InMemoryLeaf<Long, String>( btree );
        InMemoryLeaf<Long, String> target = new InMemoryLeaf<Long, String>( btree );
        InMemoryLeaf<Long, String> right = new InMemoryLeaf<Long, String>( btree );

        // Fill the left page
        left = insert( left, 1L, "v1" );
        left = insert( left, 2L, "v2" );
        left = insert( left, 3L, "v3" );
        left = insert( left, 4L, "v4" );

        // Fill the target page
        target = insert( target, 6L, "v6" );
        target = insert( target, 7L, "v7" );
        target = insert( target, 8L, "v8" );
        target = insert( target, 9L, "v9" );

        // Fill the right page
        right = insert( right, 10L, "v10" );
        right = insert( right, 11L, "v11" );
        right = insert( right, 12L, "v12" );
        right = insert( right, 13L, "v13" );
        right = insert( right, 14L, "v14" );

        parent.setPageHolder( 0, new PageHolder<Long, String>( btree, left ) );
        parent.setPageHolder( 1, new PageHolder<Long, String>( btree, target ) );
        parent.setPageHolder( 2, new PageHolder<Long, String>( btree, right ) );

        // Update the parent
        parent.setKey( 0, new KeyHolder<Long>( 6L ) );
        parent.setKey( 1, new KeyHolder<Long>( 10L ) );

        // Now, delete the element from the target page
        DeleteResult<Long, String> result = target.delete( 7L, null, 2L, parent, 1 );

        assertTrue( result instanceof BorrowedFromRightResult );

        BorrowedFromRightResult<Long, String> borrowed = ( BorrowedFromRightResult<Long, String> ) result;
        assertEquals( Long.valueOf( 11L ), borrowed.getModifiedSibling().getKey( 0 ) );
        Tuple<Long, String> removedKey = borrowed.getRemovedElement();

        assertEquals( Long.valueOf( 7L ), removedKey.getKey() );

        // Check the modified leaf
        InMemoryLeaf<Long, String> newLeaf = ( InMemoryLeaf<Long, String> ) borrowed.getModifiedPage();

        assertEquals( 4, newLeaf.getNbElems() );
        assertEquals( Long.valueOf( 6L ), newLeaf.getKey( 0 ) );
        assertEquals( Long.valueOf( 8L ), newLeaf.getKey( 1 ) );
        assertEquals( Long.valueOf( 9L ), newLeaf.getKey( 2 ) );
        assertEquals( Long.valueOf( 10L ), newLeaf.getKey( 3 ) );

        // Check the sibling
        InMemoryLeaf<Long, String> rightSibling = ( InMemoryLeaf<Long, String> ) borrowed.getModifiedSibling();

        assertEquals( 4, rightSibling.getNbElems() );
        assertEquals( Long.valueOf( 11L ), rightSibling.getKey( 0 ) );
        assertEquals( Long.valueOf( 12L ), rightSibling.getKey( 1 ) );
        assertEquals( Long.valueOf( 13L ), rightSibling.getKey( 2 ) );
        assertEquals( Long.valueOf( 14L ), rightSibling.getKey( 3 ) );
    }


    /**
     * Check that deleting an element from a leaf with N/2 element works when we merge
     * it with one of its sibling, if both has N/2 elements
     * @throws IOException
     */
    @Test
    public void testDeleteMergeWithSibling() throws IOException
    {
        InMemoryNode<Long, String> parent = new InMemoryNode<Long, String>( btree, 1L, 2 );
        InMemoryLeaf<Long, String> left = new InMemoryLeaf<Long, String>( btree );
        InMemoryLeaf<Long, String> target = new InMemoryLeaf<Long, String>( btree );
        InMemoryLeaf<Long, String> right = new InMemoryLeaf<Long, String>( btree );

        // Fill the left page
        left = insert( left, 1L, "v1" );
        left = insert( left, 2L, "v2" );
        left = insert( left, 3L, "v3" );
        left = insert( left, 4L, "v4" );

        // Fill the target page
        target = insert( target, 5L, "v5" );
        target = insert( target, 6L, "v6" );
        target = insert( target, 7L, "v7" );
        target = insert( target, 8L, "v8" );

        // Fill the right page
        right = insert( right, 9L, "v9" );
        right = insert( right, 10L, "v10" );
        right = insert( right, 11L, "v11" );
        right = insert( right, 12L, "v12" );

        parent.setPageHolder( 0, new PageHolder<Long, String>( btree, left ) );
        parent.setPageHolder( 1, new PageHolder<Long, String>( btree, target ) );
        parent.setPageHolder( 2, new PageHolder<Long, String>( btree, right ) );

        // Update the parent
        parent.setKey( 0, new KeyHolder<Long>( 5L ) );
        parent.setKey( 1, new KeyHolder<Long>( 9L ) );

        // Now, delete the element from the target page
        DeleteResult<Long, String> result = target.delete( 7L, null, 2L, parent, 1 );

        assertTrue( result instanceof MergedWithSiblingResult );

        MergedWithSiblingResult<Long, String> merged = ( MergedWithSiblingResult<Long, String> ) result;
        Tuple<Long, String> removedKey = merged.getRemovedElement();

        assertEquals( Long.valueOf( 7L ), removedKey.getKey() );

        // Check the modified leaf
        InMemoryLeaf<Long, String> newLeaf = ( InMemoryLeaf<Long, String> ) merged.getModifiedPage();

        assertEquals( 7, newLeaf.getNbElems() );
        assertEquals( Long.valueOf( 1L ), newLeaf.getKey( 0 ) );
        assertEquals( Long.valueOf( 2L ), newLeaf.getKey( 1 ) );
        assertEquals( Long.valueOf( 3L ), newLeaf.getKey( 2 ) );
        assertEquals( Long.valueOf( 4L ), newLeaf.getKey( 3 ) );
        assertEquals( Long.valueOf( 5L ), newLeaf.getKey( 4 ) );
        assertEquals( Long.valueOf( 6L ), newLeaf.getKey( 5 ) );
        assertEquals( Long.valueOf( 8L ), newLeaf.getKey( 6 ) );
    }


    /**
     * Test the findPos() method
     * @throws Exception
     */
    @Test
    public void testFindPos() throws Exception
    {
        InMemoryLeaf<Long, String> leaf = new InMemoryLeaf<Long, String>( btree );

        // Inject the values
        for ( long i = 0; i < 8; i++ )
        {
            long value = i + i + 1;
            leaf = ( InMemoryLeaf<Long, String> ) ( ( ModifyResult<Long, String> ) leaf.insert( value, "V" + value, 0L ) )
                .getModifiedPage();
        }

        // Check the findPos() method now
        for ( long i = 0; i < 17; i++ )
        {
            if ( i % 2 == 1 )
            {
                assertEquals( -( i / 2 + 1 ), leaf.findPos( i ) );
            }
            else
            {
                assertEquals( i / 2, leaf.findPos( i ) );
            }
        }
    }
}