DeleteResult delete()

in mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryNode.java [526:643]
77 lines of code
10 McCabe index (conditional complexity)

    /* no qualifier */ DeleteResult<K, V> delete( K key, V value, long revision, Page<K, V> parent, int parentPos )
        throws IOException
    {
        // We first try to delete the element from the child it belongs to
        // Find the key in the page
        int pos = findPos( key );
        boolean found = pos < 0;
        int index = pos;
        Page<K, V> child = null;
        DeleteResult<K, V> deleteResult = null;

        if ( found )
        {
            index = -( pos + 1 );
            child = children[-pos].getValue();
            deleteResult = ((AbstractPage<K, V>)child).delete( key, value, revision, this, -pos );
        }
        else
        {
            child = children[pos].getValue();
            deleteResult = ((AbstractPage<K, V>)child).delete( key, value, revision, this, pos );
        }

        // If the key is not present in the tree, we simply return
        if ( deleteResult instanceof NotPresentResult )
        {
            // Nothing to do...
            return deleteResult;
        }

        // If we just modified the child, return a modified page
        if ( deleteResult instanceof RemoveResult )
        {
            RemoveResult<K, V> removeResult = handleRemoveResult( ( RemoveResult<K, V> ) deleteResult, index, pos,
                found );

            return removeResult;
        }

        // If we had to borrow an element in the child, then have to update
        // the current page
        if ( deleteResult instanceof BorrowedFromSiblingResult )
        {
            RemoveResult<K, V> removeResult = handleBorrowedResult( ( BorrowedFromSiblingResult<K, V> ) deleteResult,
                pos );

            return removeResult;
        }

        // Last, not least, we have merged two child pages. We now have to remove
        // an element from the local page, and to deal with the result.
        if ( deleteResult instanceof MergedWithSiblingResult )
        {
            MergedWithSiblingResult<K, V> mergedResult = ( MergedWithSiblingResult<K, V> ) deleteResult;

            // If the parent is null, then this page is the root page.
            if ( parent == null )
            {
                RemoveResult<K, V> result = handleRootRemove( mergedResult, pos, found );

                return result;
            }

            // We have some parent. Check if the current page is not half full
            int halfSize = btree.getPageSize() / 2;

            if ( nbElems > halfSize )
            {
                // 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)
                RemoveResult<K, V> result = removeKey( mergedResult, revision, pos );

                return result;
            }
            else
            {
                // We will remove one element from a page that will have less than N/2 elements,
                // which will lead to some reorganization : either we can borrow an element from
                // a sibling, or we will have to merge two pages
                int siblingPos = selectSibling( parent, parentPos );

                InMemoryNode<K, V> sibling = ( InMemoryNode<K, V> ) ( ( ( InMemoryNode<K, V> ) parent ).children[siblingPos]
                    .getValue() );

                if ( sibling.getNbElems() > halfSize )
                {
                    // The sibling contains enough elements
                    // We can borrow the element from the sibling
                    if ( siblingPos < parentPos )
                    {
                        DeleteResult<K, V> result = borrowFromLeft( revision, mergedResult, sibling, pos );

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

                        return result;
                    }
                }
                else
                {
                    // We need to merge the sibling with the current page
                    DeleteResult<K, V> result = mergeWithSibling( revision, mergedResult, sibling,
                        ( siblingPos < parentPos ), pos );

                    return result;
                }
            }
        }

        // We should never reach this point
        return null;
    }