DeleteResult delete()

in mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryLeaf.java [119:272]
100 lines of code
12 McCabe index (conditional complexity)

    /* no qualifier */DeleteResult<K, V> delete( K key, V value, long revision, Page<K, V> parent, int parentPos )
        throws IOException
    {
        // Check that the leaf is not empty
        if ( nbElems == 0 )
        {
            // Empty leaf
            return NotPresentResult.NOT_PRESENT;
        }

        // Find the key in the page
        int pos = findPos( key );

        if ( pos >= 0 )
        {
            // Not found : return the not present result.
            return NotPresentResult.NOT_PRESENT;
        }

        // Get the removed element
        Tuple<K, V> removedElement = null;

        // flag to detect if a key was completely removed
        boolean keyRemoved = false;

        int index = -( pos + 1 );

        ValueHolder<V> valueHolder = values[index];

        if ( value == null )
        {
            // we have to delete the whole value
            removedElement = new Tuple<K, V>( getKey( index ), valueHolder.getCursor().next() ); // the entire value was removed
            keyRemoved = true;
        }
        else
        {
            if ( valueHolder.contains( value ) )
            {
                // this is a case to delete entire <K,sub-BTree> or <K,single-V>
                if ( valueHolder.size() == 1 )
                {
                    // Ok, we can remove the value
                    removedElement = new Tuple<K, V>( getKey( index ), null ); // the entire value was removed
                    keyRemoved = true;
                }
                else
                {
                    // Update the ValueHolder
                    valueHolder.remove( value );
                    removedElement = new Tuple<K, V>( getKey( index ), value ); // the entire value was removed
                }
            }
            else
            {
                // Not found
                return NotPresentResult.NOT_PRESENT;
            }
        }

        InMemoryLeaf<K, V> newLeaf = null;

        if ( keyRemoved )
        {
            newLeaf = new InMemoryLeaf<K, V>( btree, revision, nbElems - 1 );
        }
        else
        {
            newLeaf = new InMemoryLeaf<K, V>( btree, revision, nbElems );
        }

        // Create the result
        DeleteResult<K, V> defaultResult = new RemoveResult<K, V>( newLeaf, removedElement );

        // If the parent is null, then this page is the root page.
        if ( parent == null )
        {
            // Just remove the entry if it's present
            copyAfterRemovingElement( keyRemoved, newLeaf, index );

            // The current page is added in the copied page list
            defaultResult.addCopiedPage( this );

            return defaultResult;
        }
        else if ( keyRemoved )
        {
            // The current page is not the root. Check if the leaf has more than N/2
            // elements
            int halfSize = btree.getPageSize() / 2;

            if ( nbElems == halfSize )
            {
                // We have to find a sibling now, and either borrow an entry from it
                // if it has more than N/2 elements, or to merge the two pages.
                // Check in both next and previous page, if they have the same parent
                // and select the biggest page with the same parent to borrow an element.
                int siblingPos = selectSibling( parent, parentPos );
                InMemoryLeaf<K, V> sibling = ( InMemoryLeaf<K, V> ) ( ( ( InMemoryNode<K, V> ) parent )
                    .getPage( siblingPos ) );

                if ( sibling.getNbElems() == halfSize )
                {
                    // We will merge the current page with its sibling
                    DeleteResult<K, V> result = mergeWithSibling( removedElement, revision, sibling,
                        ( siblingPos < parentPos ), index );

                    return result;
                }
                else
                {
                    // We can borrow the element from the left sibling
                    if ( siblingPos < parentPos )
                    {
                        DeleteResult<K, V> result = borrowFromLeft( removedElement, revision, sibling, index );

                        return result;
                    }
                    else
                    {
                        // Borrow from the right sibling
                        DeleteResult<K, V> result = borrowFromRight( removedElement, revision, sibling, index );

                        return result;
                    }
                }
            }
            else
            {
                // The page has more than N/2 elements.
                // We simply remove the element from the page, and if it was the leftmost,
                // we return the new pivot (it will replace any instance of the removed
                // key in its parents)
                copyAfterRemovingElement( keyRemoved, newLeaf, index );

                // The current page is added in the copied page list
                defaultResult.addCopiedPage( this );

                return defaultResult;
            }
        }
        else
        {
            // Last, not least : we can copy the full page
            // Copy the keys and the values
            System.arraycopy( getKeys(), 0, newLeaf.getKeys(), 0, nbElems );
            System.arraycopy( values, 0, newLeaf.values, 0, nbElems );

            // The current page is added in the copied page list
            defaultResult.addCopiedPage( this );

            return defaultResult;
        }
    }