BPlusTreeEx.cpp

// BPlusTreeEx.cpp
//
// Author David Barrett-Lennard
// (C)opyright Cedanet Pty Ltd 2007

@import "Ceda/cxPersistStore/IPersistStore.h"
@import "Ceda/cxPersistStore/BPlusTree.h"
@import "Ceda/cxObject/IObjectVisitor.h"
#include "Ceda/cxUtils/TracerUtils.h"
#include "Ceda/cxUtils/Environ.h"

namespace BPlusTreeEx
{
    // Returns > 0 if k1 > k2
    //         = 0 if k1 = k2
    //         < 0 if k1 < k2
    inline int CompareKeys(int k1, int k2)
    {
        return k1 - k2;
    }
    
    // B+Tree from int to int
    mImplementBplusTree(
        true,                   // Generate class definitions?
        true,                   // Generate class implementations?
        false,                  // export?
        MyBTree,                // Name of the B+Tree class to be defined
        int,                    // Key
        int,                    // Payload
        CompareKeys,            // Global function to compare keys in the manner of strcmp
        5,                      // minInternalKeys
        5,                      // minLeafKeys
        true,                   // bPersist
        false,false,            // bKeyMayHavePrefs, bDeclareKeysReachable
        false,false,            // bPayLoadMayHavePrefs, bDeclarePayloadsReachable
        true,                   // bPayloadsOrdered
        true)                   // bWritable
    
    void Run()
    {
        ceda::TraceGroup g("BPlusTree example");

        // Open or create store
        ceda::xstring path = ceda::GetCedaTestPath("BPlusTreeEx.ced");
        ceda::close_ptr<ceda::PersistStore> pstore(ceda::OpenPersistStore(path.c_str()));

        // Open or create PSpace
        ceda::WPSpace pspace(ceda::OpenPSpace(pstore.get(), "P"));

        {
            // Bootstrap MyDeque as a root of the PSpace
            MyBTree* root = ceda::BootstrapPSpaceRoot<MyBTree>("R1");

            ceda::CSpaceTxn txn;
            
            // Insert some (key,value) pairs into the B+Tree
            for (int i=0 ; i < 5 ; ++i)
            {
                //root->Insert(i,10*i);
                (*root)[i] = 10*i;
            }
            
            // Search using a key value
            MyBTree::const_iterator v = root->find(3);
            cxAlwaysAssert(v->second == 30);
            
            // find() returns end() if key not found
            cxAlwaysAssert(root->find(1054) == root->end());

            // erase an entry with the given key
            cxAlwaysAssert(root->erase(1) == 1);

            // erase returns 0 if key not found
            cxAlwaysAssert(root->erase(2004) == 0);

            // size() returns number of (key,value) pairs in the B+Tree
            Tracer() << "Size = " << root->size() << '\n';
            
            // Iterate through entire B+Tree in ascending key order
            Tracer() << "Forwards iteration\n";
            {
                ceda::TraceIndenter indent;
                for (MyBTree::const_iterator i = root->begin() ; i != root->end() ; ++i)
                {
                    int k = i->first;
                    int v = i->second;
                    //i->second = 1;
                    Tracer() << k << " --> " << v << '\n';
                }
            }
            
            Tracer() << "find() making changes\n";
            {
                ceda::TraceIndenter indent;
                root->find(2)->second += 2000;
            }
            
            // Iterate through entire B+Tree in ascending key order
            Tracer() << "Reverse iteration\n";
            {
                ceda::TraceIndenter indent;
                for (MyBTree::const_reverse_iterator i = root->rbegin() ; i != root->rend() ; ++i)
                {
                    int k = i->first;
                    int v = i->second;
                    //i->second = 1;
                    Tracer() << k << " --> " << v << '\n';
                }
            }

            Tracer() << "Forwards iteration making changes\n";
            {
                ceda::TraceIndenter indent;
                for (MyBTree::iterator i = root->begin() ; i != root->end() ; ++i)
                {
                    int k = i->first;
                    i->second++;
                    Tracer() << i->first << " --> " << i->second << '\n';
                }
            }

            Tracer() << "Reverse iteration making changes\n";
            {
                ceda::TraceIndenter indent;
                for (MyBTree::reverse_iterator i = root->rbegin() ; i != root->rend() ; ++i)
                {
                    int k = i->first;
                    i->second++;
                    Tracer() << i->first << " --> " << i->second << '\n';
                }
            }
                                    
            Tracer() << '\n';
        }

        {
            // Bootstrap MyDeque as a root of the PSpace
            MyBTree* root = ceda::BootstrapPSpaceRoot<MyBTree>("R2");

            ceda::CSpaceTxn txn;

            // Search map with key = 0
            int n = 0;
            MyBTree::const_iterator v = root->find(0);
            if (v != root->end())
            {
                n = v->second;
            }
            ++n;

            Tracer() << "n = " << n << '\n';
            
            // Insert (key,value) pair into the B+Tree
            //root->Insert(n, n*10);
            root->insert( MyBTree::value_type(n,n*10) );

            // Insert is able to replace an existing (key,value) pair
            root->Insert(0,n);
            
            // Write() allows for directly dumping the B+Tree, displaying it as a nested tree
            {
                ceda::TracerX os;
                os << "map = ";
                ceda::Indenter indent(os,6);
                root->Write(os);
            } 
        }
    }
}