public BTree build()

in mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryBTreeBuilder.java [75:197]
77 lines of code
13 McCabe index (conditional complexity)

    public BTree<K, V> build( Iterator<Tuple<K, V>> sortedTupleItr ) throws IOException
    {
        BTree<K, V> btree = BTreeFactory.createInMemoryBTree( btreeConfiguration );
        int pageSize = btree.getPageSize();
        int maxElements = ( pageSize + 1 ) * pageSize;

        // The stack used to store all the levels. No need to have more than 16 levels, 
        // it will allow the storage of 2^64 elements with pages containing 4 elements each.
        List<InMemoryNode<K, V>>[] pageStack = new ArrayList[15];

        for ( int i = 0; i < 15; i++ )
        {
            pageStack[i] = new ArrayList<InMemoryNode<K, V>>( maxElements );
        }

        // The number of added elements
        int nbAdded = 0;

        // The btree height
        int btreeHeight = 0;

        // An array containing the number of elements necessary to fulfill a layer :
        // pageSize * (pageSize + 1)
        List<Tuple<K, V>> tuples = new ArrayList<Tuple<K, V>>( maxElements );

        // A list of nodes that are going to be created
        List<InMemoryNode<K, V>> nodes = new ArrayList<InMemoryNode<K, V>>();

        // Now, loop on all the elements
        while ( sortedTupleItr.hasNext() )
        {
            nbAdded++;

            // Get the tuple to inject
            Tuple<K, V> tuple = sortedTupleItr.next();
            tuples.add( tuple );

            if ( tuples.size() == maxElements )
            {
                // We have enough elements to create pageSize leaves, and the upper node
                InMemoryNode<K, V> node = ( InMemoryNode<K, V> ) addLeaves( btree, tuples, maxElements );
                int level = 0;

                if ( node != null )
                {
                    while ( true )
                    {
                        pageStack[level].add( node );

                        // If the node list has enough elements to fulfill a parent node,
                        // then process 
                        if ( pageStack[level].size() > btree.getPageSize() )
                        {
                            node = createParentNode( btree, pageStack[level], btree.getPageSize() );
                            pageStack[level].clear();
                            level++;
                        }
                        else
                        {
                            break;
                        }
                    }

                    ( ( AbstractBTree<K, V> ) btree ).setRootPage( pageStack[level].get( 0 ) );

                    // Update the btree height
                    if ( btreeHeight < level )
                    {
                        btreeHeight = level;
                    }
                }

                tuples.clear();
            }
        }

        if ( tuples.size() > 0 )
        {
            // Let's deal with the remaining elements
            Page<K, V> page = addLeaves( btree, tuples, maxElements );

            if ( page instanceof InMemoryNode )
            {
                nodes.add( ( InMemoryNode<K, V> ) page );

                // If the node list has enough elements to fulfill a parent node,
                // then process 
                if ( nodes.size() == maxElements )
                {
                    Page<K, V> rootPage = createParentNode( btree, nodes, maxElements );

                    ( ( AbstractBTree<K, V> ) btree ).setRootPage( rootPage );
                }
            }
            else
            {
                InMemoryLeaf<K, V> leaf = ( InMemoryLeaf<K, V> ) page;

                // Its a leaf. That means we may have to balance the btree
                if ( pageStack[0].size() != 0 )
                {
                    // We have some leaves in level 0, which means we just have to add the new leaf
                    // there, after having check we don't have to borrow some elements from the last leaf
                    if ( leaf.getNbElems() < btree.getPageSize() / 2 )
                    {
                        // Not enough elements in the added leaf. Borrow some from the left.
                        // TODO
                    }
                    else
                    {
                        // Enough elements in the added leaf (at least N/2). We just have to update
                        // the parent's node.
                        // TODO
                    }
                }
            }
        }

        // Update the number of elements
        ( ( AbstractBTree<K, V> ) btree ).getBtreeHeader().setNbElems( nbAdded );

        return btree;
    }