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);
}
}
}
}