BPlusTree2.h

// BPlusTree2.h
//
// Author David Barrett-Lennard
// (C)opyright Cedanet Pty Ltd 2011

@import "cxPersistStore.h"
@import "IPersistable.h"
@import "IPersistStore.h"
@import "pref.h"
@import "IPrefVisitor.h"
@import "TypeInfo.h"
@import "Ceda/cxObject/TypeOps.h"
@import "Ceda/cxObject/ReflectionByteCodeValue.h"
#include "Ceda/cxUtils/CedaAssert.h"
#include "Ceda/cxUtils/Tracer.h"
#include "Ceda/cxUtils/MakeIterator.h"
#include <utility>
#include <iterator>

/*
Key comparisons in maps
-----------------------

Overloading on comparison operator.  Does this mean a key type is parameterised on the comparison
operator?

It is suggested that the application programmer must define a new type using a model whenever the
comparison operator needs to be manipulated.

Use of xvector<octet_t> to represent keys and/or payloads
------------------------------------------------------

An xvector supports the concept of a size and a capacity.  A capacity can mean we avoid 
resizing of the vector.

This raises the question as to whether the size of the xvector indicates the number of keys.
For now we will assume no, and simply assume the xvector has a fixed size.

We assume B+Tree will persist in a PersistStore
-----------------------------------------------

To keep things simple we will assume this B+Tree will persist in a PersistStore, so nodes need
to implement IPersistable.

The following classes are relevent

    $class+ BPlusTree isa IPersistable
    {
    private:
        ssize_t m_size;
        cref<LeafNode> m_firstLeaf;
        cref<LeafNode> m_lastLeaf;
        cref<_Node> m_root;
        ssize_t m_height;                       // 0 if root node is a leaf node
    };

    $struct+ LeafNode isa IPersistable
    {
        LeafNode() : m_numKeyEntrys(0) {}

        // Implementation of IObject
        void VisitObjects(IObjectVisitor& v) const;

        // Implementation of IPersistable
        void Serialise(Archive& ar) const;
        void VisitPrefs(IPrefVisitor& v) const;

        ////////////////// State //////////////////////
        
        // Leaf nodes form a double linked list to allow forwards and reverse iteration in sorted order
        cref<LeafNode> m_prev;
        cref<LeafNode> m_next;
        
        ssize_t m_numKeyEntrys;
        xvector<octet_t> m_entrys;
    };

    template <typename K, typename V>
    class xmap
    {
    public:
        // all public functions set TLS before accessing m_btree
    
    private:
        cref<BPlusTree> m_btree;
    };
*/

namespace ceda
{
// Used to provide some documentation on what a void* means!
// Either a LeafNode or an InternalNode
@def _Node = void

/*
The following types are declared but never defined.  Their only purpose is to provide strong data
type checking on what would otherside be void pointers.
*/
struct _Key;
struct _Payload;
struct _KeyAndCref;       // Element type of array used in InternalNode
struct _KeyAndPayload;    // Element type of array used in LeafNode

@def int _minInternalKeys = 50
@def int _minLeafKeys = 50

// Due to limitations of the current implementation of the delete code, we cannot support
// the case where _minInternalKeys = 1 or _minLeafKeys = 1.
// The problem is that this case allows for the number of key entries in a node to transition
// to zero, and yet the code in various places assumes there is a 0th entry.
// MergeInternalRightToLeft and BalanceInternalLeftToRight require 
// right->m_numKeyEntrys > 0, and RecursiveDelete has a statement that initialises
// oldkey from leaf->m_entrys[0].first after the number of keys has dropped to zero.
// This limitation became apparent after being careful to destruct elements that were no longer
// in use.
// IDEA: This limitation will be lifted if we avoid arrays of elements that inevitably destruct
// all elements.  Would be better to only destruct the first m_numKeyEntrys entries.
@assert(_minInternalKeys > 1)
@assert(_minLeafKeys > 1)

// Let k be the number of keys stored in a given internal node that is not the root
// Then we require MIN_NUM_INTERNAL_KEY_ENTRYS <= k <= MAX_NUM_INTERNAL_KEY_ENTRYS
//
// Let c be the number of child nodes under a given internal node that is not the root
// Then c = k+1 
// and we require MIN_NUM_INTERNAL_KEY_ENTRYS+1 <= c <= MAX_NUM_INTERNAL_KEY_ENTRYS+1
//
// For an internal node that is the root, we require
//      1 <= k <= MAX_NUM_INTERNAL_KEY_ENTRYS
//      2 <= c <= MAX_NUM_INTERNAL_KEY_ENTRYS+1
@assert(_minInternalKeys > 0)
@def int MIN_NUM_INTERNAL_KEY_ENTRYS = _minInternalKeys
@def int MAX_NUM_INTERNAL_KEY_ENTRYS = _minInternalKeys*2

// Let k be the number of (key,payload) pairs stored in a given leaf node that is not the root
// Then we require MIN_NUM_LEAF_KEY_ENTRYS <= k <= MAX_NUM_LEAF_KEY_ENTRYS
@assert(_minLeafKeys > 0)
@def int MIN_NUM_LEAF_KEY_ENTRYS = _minLeafKeys
@def int MAX_NUM_LEAF_KEY_ENTRYS = _minLeafKeys*2

@assert(MIN_NUM_INTERNAL_KEY_ENTRYS > 0)
@assert(MIN_NUM_LEAF_KEY_ENTRYS > 0)

/*
This version of a B+Tree promotes code reuse by assuming that the key and payload are reflected
in a way that allows for relatively high performance.
*/

struct TypeOps;
struct InternalNode;
struct LeafNode;
class KeyAndCrefSlot;

///////////////////////////////////////////////////////////////////////////////////////////////////
// CalculatedBTreeTypeInfo

struct CalculatedBTreeTypeInfo    
{
    const TypeOps* m_keyType = nullptr;
    const TypeOps* m_payloadType = nullptr;       // nullptr indicates there is no payload - we have an xset<K>
    mutable ssize_t m_keyAndCrefSize = 0;
    mutable ssize_t m_keyAndPayloadSize = 0;
    mutable ssize_t m_crefOffset = 0;
    mutable ssize_t m_payloadOffset = 0;
};

///////////////////////////////////////////////////////////////////////////////////////////////////
// BTreeTypeInfo

struct @api BTreeTypeInfo
{
    BTreeTypeInfo() : m_keyTid(0), m_payloadTid(0) {}

    const CalculatedBTreeTypeInfo& GetCalculatedBTreeTypeInfo() const;
    
    void InitSizes() const;
    
    template <typename K>
    void SetKey()
    {
        m_bi.m_keyType = &GetTypeOps<K>();
        m_bi.m_payloadType = nullptr;
        if (PersistStore* ps = GetThreadPersistStore())
        {
            ReflectionByteCodeValue rk(GetReflectionByteCode<K>());
            m_keyTid = GetTypeOpsId(ps, rk, *m_bi.m_keyType);
        }
        else
        {
            m_keyTid = 0;
        }
        m_payloadTid = 0;
        InitSizes();
    }

    template <typename K, typename V>
    void SetKeyAndPayload()
    {
        m_bi.m_keyType = &GetTypeOps<K>();
        m_bi.m_payloadType = &GetTypeOps<V>();;
        if (PersistStore* ps = GetThreadPersistStore())
        {
            ReflectionByteCodeValue rk(GetReflectionByteCode<K>());
            ReflectionByteCodeValue rv(GetReflectionByteCode<V>());
            
            m_keyTid = GetTypeOpsId(ps, rk, *m_bi.m_keyType);
            m_payloadTid = GetTypeOpsId(ps, rv, *m_bi.m_payloadType);
        }
        else
        {
            m_keyTid = 0;
            m_payloadTid = 0;
        }
        InitSizes();
    }

    //////////// state //////////////
    
    TypeOpsId m_keyTid;
    TypeOpsId m_payloadTid;     // Can be zero for an xset<>
    mutable CalculatedBTreeTypeInfo m_bi;
};

template <typename K>
BTreeTypeInfo GetBTreeTypeInfo_K()
{
    BTreeTypeInfo bti;
    bti.SetKey<K>();
    return bti;
}

template <typename K, typename V>
BTreeTypeInfo GetBTreeTypeInfo_KV()
{
    BTreeTypeInfo bti;
    bti.SetKeyAndPayload<K,V>();
    cxAssert( bti.GetCalculatedBTreeTypeInfo().m_keyAndPayloadSize == sizeof(std::pair<K,V>) );
    return bti;
}

///////////////////////////////////////////////////////////////////////////////////////////////////
// BPlusTree

$class+ BPlusTree isa IPersistable
{
public:
    BPlusTree();
    explicit BPlusTree(const BTreeTypeInfo& bti);

    BPlusTree(const BPlusTree& rhs);
    BPlusTree& operator=(const BPlusTree& rhs);
    
    bool operator==(const BPlusTree& rhs) const;
    bool operator!=(const BPlusTree& rhs) const { return !operator==(rhs); }

    bool operator<(const BPlusTree& rhs) const;
    bool operator<=(const BPlusTree& rhs) const { return !rhs.operator<(*this); }
    bool operator>(const BPlusTree& rhs) const { return rhs.operator<(*this); }
    bool operator>=(const BPlusTree& rhs) const { return !operator<(rhs); }
                
    ssize_t size() const { return m_size; }
    bool empty() const { return m_size == 0; }

    ///////////////////////////////////////////////////////////////////////////////////////
    // iterators

    class @api Iterator
    {
    public:
        Iterator() : m_leaf(nullptr), m_offset(0) {}
        Iterator(LeafNode* leaf, ssize_t offset) : 
            m_leaf(leaf), 
            m_offset(offset) {}
        
        // Returns true if the iterator is pointing at an actual element
        // (i.e. not at one before first or one after the last)
        bool can_dereference() const;
        
        bool operator==(const Iterator& rhs) const
        {
            return m_offset == rhs.m_offset && m_leaf == rhs.m_leaf; 
        }
        bool operator!=(const Iterator& rhs) const { return !operator==(rhs); }
        
        void next();
        void prev();

        // Marks leaf node as dirty on the assumption that the payload will be modified
        _KeyAndPayload* deref() const;
        
        // Doesn't mark leaf node as dirty
        const _KeyAndPayload* const_deref() const;
         
    private:
        /*
        Rules for how m_leaf, m_offset are defined:    

            if (iterator points at an actual element of the B+Tree)
               [i.e. it is valid to call operator*()]
            {    
                m_leaf = leaf node containing the element
                m_offset = index of the element in m_leaf
                
                Note that 0 <= m_offset < m_leaf->m_numKeyEntrys
            }    
            else if (iterator corresponds to one before the first element    
                     of the B+Tree (i.e. rend()))
            {        
                if (B+Tree is empty)
                {
                    m_leaf = nullptr
                    m_offset = -1
                }
                else
                {
                    m_leaf = first leaf node
                    m_offset = -1
                }
            {
            else (iterator corresponds to one after the last element
                  of the B+Tree (i.e. end()))
            {      
                if (B+Tree is empty)
                {
                    m_leaf = nullptr
                    m_offset = 0
                }
                else
                {
                    m_leaf = last leaf node
                    m_offset = m_leaf->m_numKeyEntrys
                }
            }
                
        This approach allows for the bidirectional iterator to represent
        and distinguish between "one before first" and "one after last". 
        Furthermore if the B+Tree is non-empty then:
        
            a) an iterator at "one before first" can be incremented so it 
               points at first; and 
               
            b) an iterator at "one after last" can be decremented so it 
               points at last.
        */
        LeafNode* m_leaf; // Is nullptr if and only if the B+Tree is empty
        ssize_t m_offset;

        friend class BPlusTree;
    };

    Iterator begin();
    Iterator end();
    
    ///////////////////////////////////////////////////////////////////////////////////////

    ssize_t count(const _Key* key) const;

    Iterator find(const _Key* key);
    
    const _Payload* operator[](const _Key* key) const;
    _Payload* operator[](const _Key* key);

    /*
    Returns an iterator pointing to the first element in the map whose key does not compare 
    less than the given key value or else end().  i.e. returns first iterator i satisfying 
    *k <= i->key
    */
    Iterator lower_bound(const _Key* k);
    
    /*
    Returns an iterator pointing to the first element in the map whose key compares greater 
    than the given key value or else end().  i.e. returns first iterator i satisfying 
    *k < i->key
    */
    Iterator upper_bound(const _Key* k);

    // Returns number of elements erased (0 or 1)
    size_t erase(const _Key* key);
    
    void erase(Iterator i);
    //void erase(iterator first, iterator last);
    
    std::pair<Iterator,bool> insert(const _KeyAndPayload* x);

    void clear();
    void swap(BPlusTree& rhs);
    
    ///////////////////////////////////////////////////////////////////////////////////////
    // Unconventional API    

    ssize_t GetPayloadOffset() const;
    
    // Implementation of IObject
    void VisitObjects(IObjectVisitor& v) const;

    // Implementation of ISerialisable
    void VisitPrefs(IPrefVisitor& v) const;
    void Serialise(Archive& ar) const;
    void Deserialise(InputArchive& ar);

    // Provides the return value for wFind
    struct wFindRet
    {
        // The B+Tree leaf node that contains the payload.  Should be marked as dirty
        // if the payload is subsequently modified.
        // Can be null if wFind() called with allowCreate = false and no entry with the
        // provided key exists.
        ptr<IPersistable> m_containingNode;

        _Payload* m_payload;        // The payload for the requested key

        LeafNode* m_leaf;           // Leaf node containing the key
        ssize_t m_index;            // Index position in m_leaf
        bool m_created;             // Was a (key,payload) entry created?
    };
    
    /*
    Find the payload with the given key.  Returns the address of the payload in ret.m_payload.
    
    If allowCreate = true then 
    
        *   If no entry currently exists for the given key this function creates a new entry 
            (with the payload initialsed using the default ctor).
            
        *   ret.m_created indicates whether an entry was created (because no entry with 
            the given key previously existed)
        
    If allowCreate = false then
    
        *   If no entry exists for the given key this function returns 
            ret.m_payload = nullptr and ret.m_containingNode = null.
            
        *   Always returns ret.m_created = false.
    */
    void wFind(wFindRet& ret,const _Key* key,bool allowCreate);

    // Insert the given key and payload into the B+Tree.  Returns false if an entry with the given
    // key is already present.
    // If this B+Tree represents a set of keys (with no payloads) then call with payload = nullptr
    // and allowReplace = false
    bool Insert(const _Key* key, const _Payload* payload, bool allowReplace = true);

    // Insert the given key into the set.  Returns false if an entry with the given key is already present.
    bool Insert(const _Key* key)
    {
        return Insert(key, nullptr, false);
    }
    
    ssize_t GetNumNodes() const;
    
    void Write(xostream& os) const;

    void Validate() const;

    // Find the payload for given key.  Returns nullptr if not found.
    // If this B+Tree represents a set of keys (i.e. payload = void) then this function can still 
    // be used to test whether a key is present, by testing whether the return value isn't nullptr
    const _Payload* rFind(const _Key* key) const;
    
private:
    void SwapMembers(BPlusTree& rhs);
    void SwapPersistentWithTransient(BPlusTree& rhs);

    const CalculatedBTreeTypeInfo& GetCalculatedBTreeTypeInfo() const { return m_bti.GetCalculatedBTreeTypeInfo(); }

    bool Delete(const _Key* key);

    /////////////////////////////////// Insertion ///////////////////////////////////////

    LeafNode* wFindInLeaf(wFindRet& ret, LeafNode* left, const _Key* key, bool allowCreate);
    void InsertIntoInternalNode(InternalNode* node, KeyAndCrefSlot& e, KeyAndCrefSlot& overflow);
    void wFindInNode(wFindRet& ret,_Node* left, ssize_t height, const _Key* key, KeyAndCrefSlot& rightEntry, bool allowCreate);
    void wRecursiveFind(wFindRet& ret,InternalNode* left, ssize_t height, const _Key* key, KeyAndCrefSlot& rightEntry, bool allowCreate);

    /////////////////////////////////// Deletion ///////////////////////////////////////

    void MergeLeafRightToLeft(LeafNode* left, LeafNode* right);
    void BalanceLeafRightToLeft(LeafNode* left, LeafNode* right, InternalNode* anchor);
    void BalanceLeafLeftToRight(LeafNode* left, LeafNode* right, InternalNode* anchor);
    void ReplaceKeyInAnchor(InternalNode* node, const _Key* oldKey, const _Key* newKey);
    void MergeInternalRightToLeft(InternalNode* left, InternalNode* right, InternalNode* anchor);
    void BalanceInternalLeftToRight(InternalNode* left, InternalNode* right, InternalNode* anchor);
    void BalanceInternalRightToLeft(InternalNode* left, InternalNode* right, InternalNode* anchor);
    bool RecursiveDelete(
        ssize_t height, _Node* thisNode, _Node* lNode, _Node* rNode, 
        InternalNode* lAnchor, InternalNode* rAnchor,
        InternalNode* parent,
        _Node*& deleteNode,
        const _Key* key);

    /////////////////////////////////// Debugging ///////////////////////////////////////

    void ValidateNode(ssize_t height, _Node* node, bool isRoot, const _Key* k1, const _Key* k2) const;

    ssize_t GetNumNodes(ssize_t height, _Node* node) const;
    void WriteNode(xostream& os, ssize_t height, _Node* node) const;

private:
    ssize_t m_size;                 // Total number of (key,payload) entries stored in the B+Tree
    cref<LeafNode> m_firstLeaf;	    // pointer to first leaf node in a linked list.  Never nullptr
    cref<LeafNode> m_lastLeaf;	    // pointer to last leaf node in a linked list.  Never nullptr
    cref<_Node> m_root;             // pointer to root node.  Could be leaf node or internal node
    ssize_t m_height;               // 0 if root node is a leaf node
    BTreeTypeInfo m_bti;
};

///////////////////////////////////////////////////////////////////////////////////////////////////

class bptreebase
{
public:
    explicit bptreebase(const BTreeTypeInfo& bti)
    {
        m_tree.Set($new BPlusTree(bti));
    }

    bptreebase(const bptreebase& rhs)
    {
        cxAssert(rhs.m_tree);
        m_tree.Set($new BPlusTree(*rhs.m_tree));
    }
    bptreebase& operator=(const bptreebase& rhs)
    {
        if (this != &rhs)
        {
            cxAssert(m_tree);
            cxAssert(rhs.m_tree);
            
            // Note that this assignment doesn't change the value of the cref<BPlusTree>, so if 
            // this bptreebase appears in an IPersistable object there is no need to mark it as
            // dirty.  
            *m_tree = *rhs.m_tree;
        }
        return *this;
    }
    
    void VisitObjects(IObjectVisitor& v) const { v << m_tree; }
    void VisitPrefs(IPrefVisitor& v) const { v << m_tree; }
    void Serialise(Archive& ar) const { ar << m_tree; }
    void Deserialise(InputArchive& ar) { ar >> m_tree; }
    void Write(xostream& os) const { m_tree->Write(os); }

    ssize_t GetNumNodes() const { return m_tree->GetNumNodes(); }
    void Validate() const { m_tree->Validate(); }
    
    void clear() { m_tree->clear(); }
    bool empty() const { return m_tree->empty(); }
    ssize_t size() const { return m_tree->size(); }
    
    BPlusTree& GetUnderlyingBPlusTree() { return *m_tree; }
    const BPlusTree& GetUnderlyingBPlusTree() const { return *m_tree; }

protected:
    cref<BPlusTree> m_tree;
};

///////////////////////////////////////////////////////////////////////////////////////////////////
// bptreeset

template <typename K>
class bptreeset : public bptreebase
{
private:
    class IteratorPolicy : public BPlusTree::Iterator
    {
    public:
        IteratorPolicy() {}
        explicit IteratorPolicy(BPlusTree::Iterator it) : BPlusTree::Iterator(it) {}
    
        typedef std::bidirectional_iterator_tag iterator_category;
        typedef K value_type;
        typedef std::ptrdiff_t difference_type;
        
        // These are actually irrelevant
        typedef value_type* pointer;
        typedef const value_type* const_pointer;

        // todo: why is this here?
        typedef value_type& reference;
        
        typedef const value_type& const_reference;

        const value_type& const_deref() const
        {
            return *cast_ptr<K>(BPlusTree::Iterator::const_deref());
        }
        
    private:
        value_type& deref() const;
    };

public:
    typedef K key_type;
    typedef size_t size_type;
    typedef std::ptrdiff_t difference_type;
    typedef K value_type;
    typedef value_type* pointer;
    typedef const value_type* const_pointer;
    typedef value_type& reference;
    typedef const value_type& const_reference;

    bptreeset() : bptreebase( GetBTreeTypeInfo_K<K>() ) {}

    ///////////////////////////////////////////////////////////////////////////////////////
    // iterators
    
    /*
    Note that a set<K> only supports a const_iterator.  It makes no sense for an iterator
    to allow for modifications to the elements in the set (because the modification can
    affect its location according to the sorted order of the elements)
    */

    typedef make_const_iterator<IteratorPolicy> const_iterator;
    typedef const_iterator iterator;

    /*
    We have two user-defined implicit conversions defined:

        BPlusTree::Iterator -->  IteratorPolicy

        IteratorPolicy      -->  make_const_iterator<IteratorPolicy> (= const_iterator)
                                                                     (= iterator)

    Unfortunately C++ applies at most one user-defined conversion so the conversion
    
        BPlusTree::Iterator -->  make_const_iterator<IteratorPolicy>
        
    is unavailable.
    
    Nevertheless VS2010 allows this conversion.    
    */

    const_iterator begin() const 
    { 
        return const_iterator(IteratorPolicy(m_tree->begin()));
    }
    const_iterator end() const 
    { 
        return const_iterator(IteratorPolicy(m_tree->end()));
    }

    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
    const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
    const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }

    ///////////////////////////////////////////////////////////////////////////////////////

    bool operator<(const bptreeset& _rhs) const { return *m_tree < *_rhs.m_tree; }
    bool operator==(const bptreeset& _rhs) const { return *m_tree == *_rhs.m_tree; }
    bool operator!=(const bptreeset& _rhs) const { return !operator==(_rhs); }
    bool operator<=(const bptreeset& _rhs) const { return !_rhs.operator<(*this); }
    bool operator>(const bptreeset& _rhs) const { return _rhs.operator<(*this); }
    bool operator>=(const bptreeset& _rhs) const { return !operator<(_rhs); }

    void swap(bptreeset& _rhs) { m_tree->swap(*_rhs.m_tree); }

    const_iterator find(const key_type& key) const 
    {
        return const_iterator(IteratorPolicy(m_tree->find(cast_ptr<_Key>(&key))));
    }
    const_iterator lower_bound(const key_type& key) const 
    {
        return const_iterator(IteratorPolicy(m_tree->lower_bound(cast_ptr<_Key>(&key))));
    }
    const_iterator upper_bound(const key_type& key) const 
    {
        return const_iterator(IteratorPolicy(m_tree->upper_bound(cast_ptr<_Key>(&key))));
    }

    ssize_t count(const key_type& key) const { return m_tree->count(cast_ptr<_Key>(&key)); }
    
    size_type erase(const key_type& key) { return m_tree->erase(cast_ptr<_Key>(&key)); }
    void erase(const_iterator i) { m_tree->erase(i); }
    
    std::pair<const_iterator,bool> insert(const value_type& x) 
    { 
        std::pair<BPlusTree::Iterator,bool> r = m_tree->insert( cast_ptr<_KeyAndPayload>(&x) );
        return std::pair<const_iterator,bool>(const_iterator(IteratorPolicy(r.first)),r.second);
    }
};

///////////////////////////////////////////////////////////////////////////////////////////////////
// bptreemap

template <typename K, typename V>
class bptreemap : public bptreebase
{
private:
    class IteratorPolicy : public BPlusTree::Iterator
    {
    public:
        IteratorPolicy() {}
        explicit IteratorPolicy(const BPlusTree::Iterator& it) : BPlusTree::Iterator(it) {}
    
        typedef std::bidirectional_iterator_tag iterator_category;
        typedef std::pair<const K,V> value_type;
        typedef std::ptrdiff_t difference_type;
        
        // These are actually irrelevant
        typedef value_type* pointer;
        typedef const value_type* const_pointer;

        // todo: why is this here?
        typedef value_type& reference;
        
        typedef const value_type& const_reference;

        value_type& deref() const
        {
            return *cast_ptr<value_type>(BPlusTree::Iterator::deref());
        }

        const value_type& const_deref() const
        {
            return *cast_ptr<value_type>(BPlusTree::Iterator::const_deref());
        }
    };

public:
    typedef K key_type;
    typedef size_t size_type;
    typedef std::ptrdiff_t difference_type;
    typedef V mapped_type;
    typedef std::pair<const K,V> value_type;
    typedef value_type* pointer;
    typedef const value_type* const_pointer;
    typedef value_type& reference;
    typedef const value_type& const_reference;
    
    bptreemap() : bptreebase( GetBTreeTypeInfo_KV<K,V>() ) 
    {
    }

    ///////////////////////////////////////////////////////////////////////////////////////
    // iterators
    
    typedef make_iterator<IteratorPolicy> iterator;

    iterator begin() { return iterator(IteratorPolicy(m_tree->begin())); }
    iterator end() { return iterator(IteratorPolicy(m_tree->end())); }

    typedef make_const_iterator<IteratorPolicy> const_iterator;
    const_iterator begin() const { return const_cast<bptreemap*>(this)->begin(); }
    const_iterator end() const { return const_cast<bptreemap*>(this)->end(); }
    
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
    const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
    const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }

    typedef std::reverse_iterator<iterator> reverse_iterator;
    reverse_iterator rbegin() { return reverse_iterator(end()); }
    reverse_iterator rend() { return reverse_iterator(begin()); }

    ///////////////////////////////////////////////////////////////////////////////////////

    bool operator<(const bptreemap& _rhs) const { return *m_tree < *_rhs.m_tree; }
    bool operator==(const bptreemap& _rhs) const { return *m_tree == *_rhs.m_tree; }
    bool operator!=(const bptreemap& _rhs) const { return !operator==(_rhs); }
    bool operator<=(const bptreemap& _rhs) const { return !_rhs.operator<(*this); }
    bool operator>(const bptreemap& _rhs) const { return _rhs.operator<(*this); }
    bool operator>=(const bptreemap& _rhs) const { return !operator<(_rhs); }

    void swap(bptreemap& _rhs) { m_tree->swap(*_rhs.m_tree); }

    const_iterator find(const key_type& key) const { return const_iterator(IteratorPolicy(m_tree->find(cast_ptr<_Key>(&key)))); }
    iterator find(const key_type& key) { return iterator(IteratorPolicy(m_tree->find(cast_ptr<_Key>(&key)))); }

    const_iterator lower_bound(const key_type& key) const { return const_iterator(IteratorPolicy(m_tree->lower_bound(cast_ptr<_Key>(&key)))); }
    iterator lower_bound(const key_type& key) { return iterator(IteratorPolicy(m_tree->lower_bound(cast_ptr<_Key>(&key)))); }

    const_iterator upper_bound(const key_type& key) const { return const_iterator(IteratorPolicy(m_tree->upper_bound(cast_ptr<_Key>(&key)))); }
    iterator upper_bound(const key_type& key) { return iterator(IteratorPolicy(m_tree->upper_bound(cast_ptr<_Key>(&key)))); }
    
    // Returns the address of the mapped value for the given key, or nullptr if not found
    const mapped_type* find_2(const key_type& key) const { return cast_ptr<mapped_type>( m_tree->rFind(cast_ptr<_Key>(&key)) ); }

    ssize_t count(const key_type& key) const { return m_tree->count(cast_ptr<_Key>(&key)); }
    
    size_type erase(const key_type& key) { return m_tree->erase(cast_ptr<_Key>(&key)); }
    void erase(const_iterator i) { m_tree->erase(i); }
    
    std::pair<const_iterator,bool> insert(const value_type& x) 
    { 
        std::pair<BPlusTree::Iterator,bool> r = m_tree->insert( cast_ptr<_KeyAndPayload>(&x) );
        return std::pair<const_iterator,bool>(const_iterator(IteratorPolicy(r.first)),r.second);
    }
    
    mapped_type& operator[](const key_type& key) 
    { 
        return *cast_ptr<mapped_type>((*m_tree)[cast_ptr<_Key>(&key)]); 
    }
    const mapped_type& operator[](const key_type& key) const 
    { 
        return const_cast<bptreemap*>(this)->operator[](key);
    }
    
    ssize_t GetPayloadOffset() const { return m_tree->GetPayloadOffset(); }
};

} // namespace ceda