stx/btree.h

Go to the documentation of this file.

// $Id: btree.h 37 2007-04-27 12:13:27Z tb $
/*
 * STX B+ Tree Template Classes v0.7
 * Copyright (C) 2007 Timo Bingmann
 *
 * This library is free software; you can redistribute it and/or modify it
 * under the terms of the GNU Lesser General Public License as published by the
 * Free Software Foundation; either version 2.1 of the License, or (at your
 * option) any later version.
 *
 * This library is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License
 * for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this library; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 */

#ifndef _STX_BTREE_H_
#define _STX_BTREE_H_

// *** Required Headers from the STL

#include <functional>
#include <algorithm>
#include <istream>
#include <ostream>
#include <assert.h>

// *** Debugging Macros

#ifdef BTREE_DEBUG

#include <iostream>

#define BTREE_PRINT(x)          do { if (debug) (std::cout << x); } while(0)

#define BTREE_ASSERT(x)         do { assert(x); } while(0)

#else

#define BTREE_PRINT(x)          do { } while(0)

#define BTREE_ASSERT(x)         do { } while(0)

#endif

#define BTREE_MAX(a,b)          ((a) < (b) ? (b) : (a))

namespace stx {

template <typename _Key>
struct btree_default_set_traits
{
    static const bool   selfverify = false;

    static const bool   debug = false;

    static const int    leafslots = BTREE_MAX( 8, 256 / (sizeof(_Key)) );

    static const int    innerslots = BTREE_MAX( 8, 256 / (sizeof(_Key) + sizeof(void*)) );
};

template <typename _Key, typename _Data>
struct btree_default_map_traits
{
    static const bool   selfverify = false;

    static const bool   debug = false;

    static const int    leafslots = BTREE_MAX( 8, 256 / (sizeof(_Key) + sizeof(_Data)) );

    static const int    innerslots = BTREE_MAX( 8, 256 / (sizeof(_Key) + sizeof(void*)) );
};

template <typename _Key, typename _Data,
          typename _Value = std::pair<_Key, _Data>,
          typename _Compare = std::less<_Key>,
          typename _Traits = btree_default_map_traits<_Key, _Data>,
          bool _Duplicates = false>
class btree
{
public:
    // *** Template Parameter Types

    typedef _Key                        key_type;

    typedef _Data                       data_type;

    typedef _Value                      value_type;

    typedef _Compare                    key_compare;

    typedef _Traits                     traits;

    static const bool                   allow_duplicates = _Duplicates;

public:
    // *** Constructed Types

    typedef btree<key_type, data_type, value_type,
                  key_compare, traits, allow_duplicates>        btree_self;

    typedef size_t                              size_type;

    typedef std::pair<key_type, data_type>      pair_type;

public:
    // *** Static Constant Options and Values of the B+ Tree

    static const unsigned short         leafslotmax =  traits::leafslots;

    static const unsigned short         innerslotmax =  traits::innerslots;

    static const unsigned short         minleafslots = (leafslotmax / 2);

    static const unsigned short         mininnerslots = (innerslotmax / 2);

    static const bool                   selfverify = traits::selfverify;

    static const bool                   debug = traits::debug;

private:
    // *** Node Classes for In-Memory Nodes

    struct node
    {
        unsigned short  level;

        unsigned short  slotuse;

        inline void initialize(const unsigned short l)
        {
            level = l;
            slotuse = 0;
        }
        
        inline bool isleafnode() const
        {
            return (level == 0);
        }
    };

    struct inner_node : public node
    {
        key_type        slotkey[innerslotmax];

        node*           childid[innerslotmax+1];

        inline void initialize(const unsigned short l)
        {
            node::initialize(l);
        }

        inline bool isfull() const
        {
            return (node::slotuse == innerslotmax);
        }

        inline bool isfew() const
        {
            return (node::slotuse <= mininnerslots);
        }

        inline bool isunderflow() const
        {
            return (node::slotuse < mininnerslots);
        }
    };

    struct leaf_node : public node
    {
        leaf_node       *prevleaf;

        leaf_node       *nextleaf;

        key_type        slotkey[leafslotmax];

        data_type       slotdata[leafslotmax];

        inline void initialize()
        {
            node::initialize(0);
            prevleaf = nextleaf = NULL;
        }

        inline bool isfull() const
        {
            return (node::slotuse == leafslotmax);
        }

        inline bool isfew() const
        {
            return (node::slotuse <= minleafslots);
        }

        inline bool isunderflow() const
        {
            return (node::slotuse < minleafslots);
        }
    };

private:
    // *** Template Magic to Convert a pair or key/data types to a value_type

    template <typename value_type, typename pair_type>
    struct btree_pair_to_value
    {
        inline value_type operator()(pair_type& p) const {
            return p.first;
        }
        inline value_type operator()(const pair_type& p) const {
            return p.first;
        }
    };

    template <typename value_type>
    struct btree_pair_to_value<value_type, value_type>
    {
        inline value_type operator()(pair_type& p) const {
            return p;
        }
        inline value_type operator()(const pair_type& p) const {
            return p;
        }
    };

    typedef btree_pair_to_value<value_type, pair_type> pair_to_value_type;

public:
    // *** Iterators and Reverse Iterators

    class iterator;
    class const_iterator;

    class iterator
    {
    public:
        // *** Types

        typedef typename btree::key_type                key_type;

        typedef typename btree::data_type               data_type;

        typedef typename btree::value_type              value_type;

        typedef typename btree::pair_type               pair_type;

        typedef value_type&             reference;

        typedef value_type*             pointer;

        typedef std::bidirectional_iterator_tag iterator_category;

        typedef ptrdiff_t               difference_type;

        typedef iterator                self;

    private:
        // *** Members

        typename btree::leaf_node*      currnode;

        unsigned short  currslot;
    
        friend class btree<key_type, data_type, value_type, key_compare, traits, allow_duplicates>::const_iterator;
        
        mutable value_type              temp_value;

    public:
        // *** Methods

        inline iterator(typename btree::leaf_node *l, unsigned short s)
            : currnode(l), currslot(s)
        { }

        inline reference operator*() const
        {
            temp_value = pair_to_value_type()( pair_type(currnode->slotkey[currslot],
                                                         currnode->slotdata[currslot]) );
            return temp_value;
        }

        inline pointer operator->() const
        {
            temp_value = pair_to_value_type()( pair_type(currnode->slotkey[currslot],
                                                         currnode->slotdata[currslot]) );
            return &temp_value;
        }

        inline const key_type& key() const
        {
            return currnode->slotkey[currslot];
        }

        inline data_type& data() const
        {
            return currnode->slotdata[currslot];
        }

        inline self& operator++()
        {
            if (currslot + 1 < currnode->slotuse) {
                ++currslot;
            }
            else if (currnode->nextleaf != NULL) {
                currnode = currnode->nextleaf;
                currslot = 0;
            }
            else {
                // this is end()
                currslot = currnode->slotuse;
            }

            return *this;
        }

        inline self operator++(int)
        {
            self tmp = *this;   // copy ourselves

            if (currslot + 1 < currnode->slotuse) {
                ++currslot;
            }
            else if (currnode->nextleaf != NULL) {
                currnode = currnode->nextleaf;
                currslot = 0;
            }
            else {
                // this is end()
                currslot = currnode->slotuse;
            }

            return tmp;
        }

        inline self& operator--()
        {
            if (currslot > 0) {
                --currslot;
            }
            else if (currnode->prevleaf != NULL) {
                currnode = currnode->prevleaf;
                currslot = currnode->slotuse - 1;
            }
            else {
                // this is begin()
                currslot = 0;
            }

            return *this;
        }

        inline self operator--(int)
        {
            self tmp = *this;   // copy ourselves

            if (currslot > 0) {
                --currslot;
            }
            else if (currnode->prevleaf != NULL) {
                currnode = currnode->prevleaf;
                currslot = currnode->slotuse - 1;
            }
            else {
                // this is begin()
                currslot = 0;
            }

            return tmp;
        }

        inline bool operator==(const self& x) const
        {
            return (x.currnode == currnode) && (x.currslot == currslot);
        }

        inline bool operator!=(const self& x) const
        {
            return (x.currnode != currnode) || (x.currslot != currslot);
        }    
    };

    class const_iterator
    {
    public:
        // *** Types

        typedef typename btree::key_type                key_type;

        typedef typename btree::data_type               data_type;

        typedef typename btree::value_type              value_type;

        typedef typename btree::pair_type               pair_type;

        typedef const value_type&       reference;

        typedef const value_type*       pointer;

        typedef std::bidirectional_iterator_tag iterator_category;

        typedef ptrdiff_t               difference_type;

        typedef const_iterator          self;

    private:
        // *** Members

        const typename btree::leaf_node*        currnode;

        unsigned short  currslot;
    
        mutable value_type              temp_value;

    public:
        // *** Methods

        inline const_iterator(const typename btree::leaf_node *l, unsigned short s)
            : currnode(l), currslot(s)
        { }

        inline const_iterator(const iterator &it)
            : currnode(it.currnode), currslot(it.currslot)
        { }

        inline reference operator*() const
        {
            temp_value = pair_to_value_type()( pair_type(currnode->slotkey[currslot],
                                                         currnode->slotdata[currslot]) );
            return temp_value;
        }

        inline pointer operator->() const
        {
            temp_value = pair_to_value_type()( pair_type(currnode->slotkey[currslot],
                                                         currnode->slotdata[currslot]) );
            return &temp_value;
        }

        inline const key_type& key() const
        {
            return currnode->slotkey[currslot];
        }

        inline const data_type& data() const
        {
            return currnode->slotdata[currslot];
        }

        inline self& operator++()
        {
            if (currslot + 1 < currnode->slotuse) {
                ++currslot;
            }
            else if (currnode->nextleaf != NULL) {
                currnode = currnode->nextleaf;
                currslot = 0;
            }
            else {
                // this is end()
                currslot = currnode->slotuse;
            }

            return *this;
        }

        inline self operator++(int)
        {
            self tmp = *this;   // copy ourselves

            if (currslot + 1 < currnode->slotuse) {
                ++currslot;
            }
            else if (currnode->nextleaf != NULL) {
                currnode = currnode->nextleaf;
                currslot = 0;
            }
            else {
                // this is end()
                currslot = currnode->slotuse;
            }

            return tmp;
        }

        inline self& operator--()
        {
            if (currslot > 0) {
                --currslot;
            }
            else if (currnode->prevleaf != NULL) {
                currnode = currnode->prevleaf;
                currslot = currnode->slotuse - 1;
            }
            else {
                // this is begin()
                currslot = 0;
            }

            return *this;
        }

        inline self operator--(int)
        {
            self tmp = *this;   // copy ourselves

            if (currslot > 0) {
                --currslot;
            }
            else if (currnode->prevleaf != NULL) {
                currnode = currnode->prevleaf;
                currslot = currnode->slotuse - 1;
            }
            else {
                // this is begin()
                currslot = 0;
            }

            return tmp;
        }

        inline bool operator==(const self& x) const
        {
            return (x.currnode == currnode) && (x.currslot == currslot);
        }

        inline bool operator!=(const self& x) const
        {
            return (x.currnode != currnode) || (x.currslot != currslot);
        }    
    };

    typedef std::reverse_iterator<iterator>       reverse_iterator;

    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

public:
    // *** Small Statistics Structure

    struct tree_stats
    {
        size_type       itemcount;

        size_type       leaves;

        size_type       innernodes;

        static const unsigned short     leafslots = btree_self::leafslotmax;

        static const unsigned short     innerslots = btree_self::innerslotmax;

        inline tree_stats()
            : itemcount(0),
              leaves(0), innernodes(0)
        {
        }

        inline size_type nodes() const
        {
            return innernodes + leaves;
        }

        inline double avgfill_leaves() const
        {
            return static_cast<double>(itemcount) / (leaves * leafslots);
        }
    };

private:
    // *** Tree Object Data Members

    node*       root;

    leaf_node   *headleaf;

    leaf_node   *tailleaf;

    tree_stats  stats;

    key_compare key_less;

public:
    // *** Constructors and Destructor

    inline btree()
        : root(NULL), headleaf(NULL), tailleaf(NULL)
    {
    }

    inline btree(const key_compare &kcf)
        : root(NULL), headleaf(NULL), tailleaf(NULL),
          key_less(kcf)
    {
    }

    template <class InputIterator>
    inline btree(InputIterator first, InputIterator last)
        : root(NULL), headleaf(NULL), tailleaf(NULL)
    {
        insert(first, last);
    }

    template <class InputIterator>
    inline btree(InputIterator first, InputIterator last, const key_compare &kcf)
        : root(NULL), headleaf(NULL), tailleaf(NULL),
          key_less(kcf)
    {
        insert(first, last);
    }

    inline ~btree()
    {
        clear();
    }

    void swap(btree_self& from)
    {
        std::swap(root, from.root);
        std::swap(headleaf, from.headleaf);
        std::swap(tailleaf, from.tailleaf);
        std::swap(stats, from.stats);
        std::swap(key_less, from.key_less);
    }

public:
    // *** Key and Value Comparison Function Objects

    class value_compare
    {
    protected:
        key_compare     key_comp;
 
        inline value_compare(key_compare kc)
            : key_comp(kc)
        { }

        friend class btree<key_type, data_type, value_type, key_compare, traits, allow_duplicates>;
 
    public:
        inline bool operator()(const value_type& x, const value_type& y) const
        {
            return key_comp(x.first, y.first);
        }
    };

    inline key_compare key_comp() const
    {
        return key_less;
    }

    inline value_compare value_comp() const
    {
        return value_compare(key_less);
    }

private:
    // *** Convenient Key Comparison Functions Generated From key_less

    inline bool key_lessequal(const key_type &a, const key_type b) const
    {
        return !key_less(b, a);
    }

    inline bool key_greater(const key_type &a, const key_type &b) const
    {
        return key_less(b, a);
    }

    inline bool key_greaterequal(const key_type &a, const key_type b) const
    {
        return !key_less(a, b);
    }

    inline bool key_equal(const key_type &a, const key_type &b) const
    {
        return !key_less(a, b) && !key_less(b, a);
    }

private:
    // *** Node Object Allocation and Deallocation Functions

    inline leaf_node* allocate_leaf()
    {
        leaf_node* n = new leaf_node;
        n->initialize();
        stats.leaves++;
        return n;
    }

    inline inner_node* allocate_inner(unsigned short l)
    {
        inner_node* n = new inner_node;
        n->initialize(l);
        stats.innernodes++;
        return n;
    }
    
    inline void free_node(node *n)
    {
        if (n->isleafnode()) {
            delete static_cast<leaf_node*>(n);
            stats.leaves--;
        }
        else {
            delete static_cast<inner_node*>(n);
            stats.innernodes--;
        }
    }

public:
    // *** Fast Destruction of the B+ Tree

    void clear()
    {
        if (root)
        {
            clear_recursive(root);
            free_node(root);

            root = NULL;
            headleaf = tailleaf = NULL;

            stats = tree_stats();
        }

        BTREE_ASSERT(stats.itemcount == 0);
    }

private:
    void clear_recursive(node *n)
    {
        if (n->isleafnode())
        {
            leaf_node *leafnode = static_cast<leaf_node*>(n);

            for (unsigned int slot = 0; slot < leafnode->slotuse; ++slot)
            {
                // data objects are deleted by leaf_node's destructor
            }
        }
        else
        {
            inner_node *innernode = static_cast<inner_node*>(n);

            for (unsigned short slot = 0; slot < innernode->slotuse + 1; ++slot)
            {
                clear_recursive(innernode->childid[slot]);
                free_node(innernode->childid[slot]);
            }
        }
    }

public:
    // *** STL Iterator Construction Functions

    inline iterator begin()
    {
        return iterator(headleaf, 0);
    }

    inline iterator end()
    {
        return iterator(tailleaf, tailleaf->slotuse);
    }

    inline const_iterator begin() const
    {
        return const_iterator(headleaf, 0);
    }

    inline const_iterator end() const
    {
        return const_iterator(tailleaf, tailleaf->slotuse);
    }

    inline reverse_iterator rbegin()
    {
        return reverse_iterator(end());
    }

    inline reverse_iterator rend()
    {
        return reverse_iterator(begin());
    }

    inline const_reverse_iterator rbegin() const
    {
        return const_reverse_iterator(end());
    }

    inline const_reverse_iterator rend() const
    {
        return const_reverse_iterator(begin());
    }

private:
    // *** B+ Tree Node Binary Search Functions

    template <typename node_type>
    inline int find_lower(const node_type *n, const key_type& key) const
    {
        if (n->slotuse == 0) return 0;

        int lo = 0,
            hi = n->slotuse - 1;

        while(lo < hi)
        {
            int mid = (lo + hi) / 2;

            if (key_lessequal(key, n->slotkey[mid])) {
                hi = mid - 1;
            }
            else {
                lo = mid + 1;
            }
        }

        if (hi < 0 || key_less(n->slotkey[hi], key))
            hi++;

        BTREE_PRINT("btree::find_lower: on " << n << " key " << key << " -> (" << lo << ") " << hi << ", ");

        // verify result using simple linear search
        if (selfverify)
        {
            int i = n->slotuse - 1;
            while(i >= 0 && key_lessequal(key, n->slotkey[i]))
                i--;
            i++;

            BTREE_PRINT("testfind: " << i << std::endl);
            BTREE_ASSERT(i == hi);
        }
        else {
            BTREE_PRINT(std::endl);
        }
        
        return hi;
    }

    template <typename node_type>
    inline int find_upper(const node_type *n, const key_type& key) const
    {
        if (n->slotuse == 0) return 0;

        int lo = 0,
            hi = n->slotuse - 1;

        while(lo < hi)
        {
            int mid = (lo + hi) / 2;

            if (key_less(key, n->slotkey[mid])) {
                hi = mid - 1;
            }
            else {
                lo = mid + 1;
            }
        }

        if (hi < 0 || key_lessequal(n->slotkey[hi], key))
            hi++;

        BTREE_PRINT("btree::find_upper: on " << n << " key " << key << " -> (" << lo << ") " << hi << ", ");

        // verify result using simple linear search
        if (selfverify)
        {
            int i = n->slotuse - 1;
            while(i >= 0 && key_less(key, n->slotkey[i]))
                i--;
            i++;

            BTREE_PRINT("btree::find_upper testfind: " << i << std::endl);
            BTREE_ASSERT(i == hi);
        }
        else {
            BTREE_PRINT(std::endl);
        }
        
        return hi;
    }

public:
    // *** Access Functions to the Item Count

    inline size_type size() const
    {
        return stats.itemcount;
    }

    inline bool empty() const
    {
        return (size() == size_type(0));
    }
    
    inline size_type max_size() const
    {
        return size_type(-1);
    }

    inline const struct tree_stats& get_stats() const
    {
        return stats;
    }

public:
    // *** Standard Access Functions Querying the Tree by Descending to a Leaf

    bool exists(const key_type &key) const
    {
        const node *n = root;

        if (!n) return false;

        while(!n->isleafnode())
        {
            const inner_node *inner = static_cast<const inner_node*>(n);
            int slot = find_lower(inner, key);

            n = inner->childid[slot];
        }

        const leaf_node *leaf = static_cast<const leaf_node*>(n);

        int slot = find_lower(leaf, key);
        return key_equal(key, leaf->slotkey[slot]);
    }

    iterator find(const key_type &key)
    {
        node *n = root;
        if (!n) return end();

        while(!n->isleafnode())
        {
            const inner_node *inner = static_cast<const inner_node*>(n);
            int slot = find_lower(inner, key);

            n = inner->childid[slot];
        }

        leaf_node *leaf = static_cast<leaf_node*>(n);

        int slot = find_lower(leaf, key);
        return key_equal(key, leaf->slotkey[slot]) ? iterator(leaf, slot) : end();
    }

    const_iterator find(const key_type &key) const
    {
        const node *n = root;
        if (!n) return end();

        while(!n->isleafnode())
        {
            const inner_node *inner = static_cast<const inner_node*>(n);
            int slot = find_lower(inner, key);

            n = inner->childid[slot];
        }

        const leaf_node *leaf = static_cast<const leaf_node*>(n);

        int slot = find_lower(leaf, key);
        return key_equal(key, leaf->slotkey[slot]) ? const_iterator(leaf, slot) : end();
    }

    size_type count(const key_type &key) const
    {
        const node *n = root;
        if (!n) return 0;

        while(!n->isleafnode())
        {
            const inner_node *inner = static_cast<const inner_node*>(n);
            int slot = find_lower(inner, key);

            n = inner->childid[slot];
        }

        const leaf_node *leaf = static_cast<const leaf_node*>(n);

        int slot = find_lower(leaf, key);
        size_type num = 0;

        while (leaf && key_equal(key, leaf->slotkey[slot]))
        {
            ++num;
            if (++slot >= leaf->slotuse)
            {
                leaf = leaf->nextleaf;
                slot = 0;
            }
        }

        return num;
    }

    iterator lower_bound(const key_type& key)
    {
        node *n = root;
        if (!n) return end();

        while(!n->isleafnode())
        {
            const inner_node *inner = static_cast<const inner_node*>(n);
            int slot = find_lower(inner, key);

            n = inner->childid[slot];
        }

        leaf_node *leaf = static_cast<leaf_node*>(n);

        int slot = find_lower(leaf, key);
        return iterator(leaf, slot);
    }

    const_iterator lower_bound(const key_type& key) const
    {
        const node *n = root;
        if (!n) return end();

        while(!n->isleafnode())
        {
            const inner_node *inner = static_cast<const inner_node*>(n);
            int slot = find_lower(inner, key);

            n = inner->childid[slot];
        }

        const leaf_node *leaf = static_cast<const leaf_node*>(n);

        int slot = find_lower(leaf, key);
        return const_iterator(leaf, slot);
    }

    iterator upper_bound(const key_type& key)
    {
        node *n = root;
        if (!n) return end();

        while(!n->isleafnode())
        {
            const inner_node *inner = static_cast<const inner_node*>(n);
            int slot = find_upper(inner, key);

            n = inner->childid[slot];
        }

        leaf_node *leaf = static_cast<leaf_node*>(n);

        int slot = find_upper(leaf, key);
        return iterator(leaf, slot);
    }

    const_iterator upper_bound(const key_type& key) const
    {
        const node *n = root;
        if (!n) return end();

        while(!n->isleafnode())
        {
            const inner_node *inner = static_cast<const inner_node*>(n);
            int slot = find_upper(inner, key);

            n = inner->childid[slot];
        }

        const leaf_node *leaf = static_cast<const leaf_node*>(n);

        int slot = find_upper(leaf, key);
        return const_iterator(leaf, slot);
    }

    inline std::pair<iterator, iterator> equal_range(const key_type& key)
    {
        return std::pair<iterator, iterator>(lower_bound(key), upper_bound(key));
    }

    inline std::pair<const_iterator, const_iterator> equal_range(const key_type& key) const
    {
        return std::pair<const_iterator, const_iterator>(lower_bound(key), upper_bound(key));
    }

public:
    // *** B+ Tree Object Comparison Functions

    inline bool operator==(const btree_self &other) const
    {
        return (size() == other.size()) && std::equal(begin(), end(), other.begin());
    }

    inline bool operator!=(const btree_self &other) const
    {
        return !(*this == other);
    }

    inline bool operator<(const btree_self &other) const
    {
        return std::lexicographical_compare(begin(), end(), other.begin(), other.end());
    }

    inline bool operator>(const btree_self &other) const
    {
        return other < *this;
    }

    inline bool operator<=(const btree_self &other) const
    {
        return !(other < *this);
    }

    inline bool operator>=(const btree_self &other) const
    {
        return !(*this < other);
    }

public:

    inline btree_self& operator= (const btree_self &other)
    {
        if (this != &other)
        {
            clear();

            key_less = other.key_comp();
            if (other.size() != 0)
            {
                stats.leaves = stats.innernodes = 0;
                root = copy_recursive(other.root);
                stats = other.stats;
            }

            if (selfverify) verify();
        }
        return *this;
    }

    inline btree(const btree_self &other)
        : root(NULL), headleaf(NULL), tailleaf(NULL),
          stats( other.stats ),
          key_less( other.key_comp() )
    {
        if (size() > 0)
        {
            stats.leaves = stats.innernodes = 0;
            root = copy_recursive(other.root);
            if (selfverify) verify();
        }
    }
    
private:
    class node* copy_recursive(const node *n)
    {
        if (n->isleafnode())
        {
            const leaf_node *leaf = static_cast<const leaf_node*>(n);
            leaf_node *newleaf = allocate_leaf();

            newleaf->slotuse = leaf->slotuse;
            std::copy(leaf->slotkey, leaf->slotkey + leaf->slotuse, newleaf->slotkey);
            std::copy(leaf->slotdata, leaf->slotdata + leaf->slotuse, newleaf->slotdata);

            if (headleaf == NULL)
            {
                headleaf = tailleaf = newleaf;
                newleaf->prevleaf = newleaf->nextleaf = NULL;
            }
            else
            {
                newleaf->prevleaf = tailleaf;
                tailleaf->nextleaf = newleaf;
                tailleaf = newleaf;
            }

            return newleaf;
        }
        else
        {
            const inner_node *inner = static_cast<const inner_node*>(n);
            inner_node *newinner = allocate_inner(inner->level);

            newinner->slotuse = inner->slotuse;
            std::copy(inner->slotkey, inner->slotkey + inner->slotuse, newinner->slotkey);

            for (unsigned short slot = 0; slot <= inner->slotuse; ++slot)
            {
                newinner->childid[slot] = copy_recursive(inner->childid[slot]);
            }

            return newinner;
        }
    }

public:
    // *** Public Insertion Functions

    inline std::pair<iterator, bool> insert(const pair_type& x)
    {
        return insert_start(x.first, x.second);
    }
    
    inline std::pair<iterator, bool> insert(const key_type& key, const data_type& data)
    {
        return insert_start(key, data);
    }

    inline std::pair<iterator, bool> insert2(const key_type& key, const data_type& data)
    {
        return insert_start(key, data);
    }

    inline iterator insert(iterator /* hint */, const pair_type &x)
    {
        return insert_start(x.first, x.second).first;
    }

    inline iterator insert2(iterator /* hint */, const key_type& key, const data_type& data)
    {
        return insert_start(key, data).first;
    }

    template <typename InputIterator>
    inline void insert(InputIterator first, InputIterator last)
    {
        InputIterator iter = first;
        while(iter != last)
        {
            insert(*iter);
            ++iter;
        }
    }

private:
    // *** Private Insertion Functions

    std::pair<iterator, bool> insert_start(const key_type& key, const data_type& value)
    {
        node *newchild = NULL;
        key_type newkey = key_type();

        if (!root)
        {
            root = headleaf = tailleaf = allocate_leaf();
        }

        std::pair<iterator, bool> r = insert_descend(root, key, value, &newkey, &newchild);

        if (newchild)
        {
            inner_node *newroot = allocate_inner(root->level + 1);
            newroot->slotkey[0] = newkey;

            newroot->childid[0] = root;
            newroot->childid[1] = newchild;

            newroot->slotuse = 1;

            root = newroot;
        }

        // increment itemcount if the item was inserted
        if (r.second) ++stats.itemcount;

        if (debug)
            print();

        if (selfverify) {
            verify();
            BTREE_ASSERT(exists(key));
        }

        return r;
    }

    std::pair<iterator, bool> insert_descend(node* n,
                                             const key_type& key, const data_type& value,
                                             key_type* splitkey, node** splitnode)
    {
        if (!n->isleafnode())
        {
            inner_node *inner = static_cast<inner_node*>(n);

            key_type newkey = key_type();
            node *newchild = NULL;

            int slot = find_lower(inner, key);

            BTREE_PRINT("btree::insert_descend into " << inner->childid[slot] << std::endl);

            std::pair<iterator, bool> r = insert_descend(inner->childid[slot],
                                                         key, value, &newkey, &newchild);

            if (newchild)
            {
                BTREE_PRINT("btree::insert_descend newchild with key " << newkey << " node " << newchild << " at slot " << slot << std::endl);

                if (inner->isfull())
                {
                    split_inner_node(inner, splitkey, splitnode, slot);

                    BTREE_PRINT("btree::insert_descend done split_inner: putslot: " << slot << " putkey: " << newkey << " upkey: " << *splitkey << std::endl);

                    if (debug)
                    {
                        print_node(inner);
                        print_node(*splitnode);
                    }

                    // check if insert slot is in the split sibling node
                    BTREE_PRINT("btree::insert_descend switch: " << slot << " > " << inner->slotuse+1 << std::endl);

                    if (slot == inner->slotuse+1 && inner->slotuse < (*splitnode)->slotuse)
                    {
                        // special case when the insert slot matches the split
                        // place between the two nodes, then the insert key
                        // becomes the split key.

                        BTREE_ASSERT(inner->slotuse + 1 < innerslotmax);

                        inner_node *splitinner = static_cast<inner_node*>(*splitnode);

                        // move the split key and it's datum into the left node
                        inner->slotkey[inner->slotuse] = *splitkey;
                        inner->childid[inner->slotuse+1] = splitinner->childid[0];
                        inner->slotuse++;

                        // set new split key and move corresponding datum into right node
                        splitinner->childid[0] = newchild;
                        *splitkey = newkey;

                        return r;
                    }
                    else if (slot >= inner->slotuse+1)
                    {
                        // in case the insert slot is in the newly create split
                        // node, we reuse the code below.

                        slot -= inner->slotuse+1;
                        inner = static_cast<inner_node*>(*splitnode);
                        BTREE_PRINT("btree::insert_descend switching to splitted node " << inner << " slot " << slot <<std::endl);
                    }
                }

                // put pointer to child node into correct slot
                BTREE_ASSERT(slot >= 0 && slot <= inner->slotuse);

                int i = inner->slotuse;

                while(i > slot) {
                    inner->slotkey[i] = inner->slotkey[i - 1];
                    inner->childid[i + 1] = inner->childid[i];
                    i--;
                }

                inner->slotkey[slot] = newkey;
                inner->childid[slot + 1] = newchild;
                inner->slotuse++;
            }
            
            return r;
        }
        else // n->isleafnode() == true
        {
            leaf_node *leaf = static_cast<leaf_node*>(n);

            int slot = find_lower(leaf, key);

            if (!allow_duplicates && slot < leaf->slotuse && key_equal(key, leaf->slotkey[slot])) {
                return std::pair<iterator, bool>(iterator(leaf, slot), false);
            }

            if (leaf->isfull())
            {
                split_leaf_node(leaf, splitkey, splitnode);

                // check if insert slot is in the split sibling node
                if (slot >= leaf->slotuse)
                {
                    slot -= leaf->slotuse;
                    leaf = static_cast<leaf_node*>(*splitnode);
                }
            }

            // put data item into correct data slot

            int i = leaf->slotuse - 1;
            BTREE_ASSERT(i + 1 < leafslotmax);

            while(i >= 0 && key_less(key, leaf->slotkey[i])) {
                leaf->slotkey[i + 1] = leaf->slotkey[i];
                leaf->slotdata[i + 1] = leaf->slotdata[i];
                i--;
            }
            
            leaf->slotkey[i + 1] = key;
            leaf->slotdata[i + 1] = value;
            leaf->slotuse++;

            if (splitnode && leaf != *splitnode && slot == leaf->slotuse-1)
            {
                // special case: the node was split, and the insert is at the
                // last slot of the old node. then the splitkey must be
                // updated.
                *splitkey = key;
            }

            return std::pair<iterator, bool>(iterator(leaf, i + 1), true);
        }
    }

    void split_leaf_node(leaf_node* leaf, key_type* _newkey, node** _newleaf)
    {
        BTREE_ASSERT(leaf->isfull());

        unsigned int mid = leaf->slotuse / 2;

        BTREE_PRINT("btree::split_leaf_node on " << leaf << std::endl);

        leaf_node *newleaf = allocate_leaf();

        newleaf->slotuse = leaf->slotuse - mid;

        newleaf->nextleaf = leaf->nextleaf;
        if (newleaf->nextleaf == NULL) {
            BTREE_ASSERT(leaf == tailleaf);
            tailleaf = newleaf;
        }
        else {
            newleaf->nextleaf->prevleaf = newleaf;
        }

        for(unsigned int slot = mid; slot < leaf->slotuse; ++slot)
        {
            unsigned int ni = slot - mid;
            newleaf->slotkey[ni] = leaf->slotkey[slot];
            newleaf->slotdata[ni] = leaf->slotdata[slot];
        }
            
        leaf->slotuse = mid;
        leaf->nextleaf = newleaf;
        newleaf->prevleaf = leaf;

        *_newkey = leaf->slotkey[leaf->slotuse-1];
        *_newleaf = newleaf;
    }

    void split_inner_node(inner_node* inner, key_type* _newkey, node** _newinner, unsigned int addslot)
    {
        BTREE_ASSERT(inner->isfull());

        unsigned int mid = inner->slotuse / 2;

        BTREE_PRINT("btree::split_inner: mid " << mid << " addslot " << addslot << std::endl);

        // if the split is uneven and the overflowing item will be put into the
        // larger node, then the smaller split node may underflow
        if (addslot <= mid && mid > inner->slotuse - (mid + 1))
            mid--;

        BTREE_PRINT("btree::split_inner: mid " << mid << " addslot " << addslot << std::endl);

        BTREE_PRINT("btree::split_inner_node on " << inner << " into two nodes " << mid << " and " << inner->slotuse - (mid + 1) << " sized" << std::endl);

        inner_node *newinner = allocate_inner(inner->level);

        newinner->slotuse = inner->slotuse - (mid + 1);

        for(unsigned int slot = mid + 1; slot < inner->slotuse; ++slot)
        {
            unsigned int ni = slot - (mid + 1);
            newinner->slotkey[ni] = inner->slotkey[slot];
            newinner->childid[ni] = inner->childid[slot];
        }
        newinner->childid[newinner->slotuse] = inner->childid[inner->slotuse];
            
        inner->slotuse = mid;

        *_newkey = inner->slotkey[mid];
        *_newinner = newinner;
    }

private:
    // *** Support Class Encapsulating Deletion Results

    enum result_flags_t
    {
        btree_ok = 0,

        btree_not_found = 1,

        btree_update_lastkey = 2,

        btree_fixmerge = 4
    };

    struct result_t
    {
        result_flags_t  flags;

        key_type        lastkey;

        inline result_t(result_flags_t f = btree_ok)
            : flags(f), lastkey()
        { }

        inline result_t(result_flags_t f, const key_type &k)
            : flags(f), lastkey(k)
        { }

        inline bool has(result_flags_t f) const
        {
            return (flags & f);
        }

        inline result_t& operator|= (const result_t &other)
        {
            flags = result_flags_t(flags | other.flags);

            // we overwrite existing lastkeys on purpose
            if (other.has(btree_update_lastkey))
                lastkey = other.lastkey;

            return *this;
        }
    };

public:
    // *** Public Erase Functions

    bool erase_one(const key_type &key)
    {
        BTREE_PRINT("btree::erase_one(" << key << ") on btree size " << size() << std::endl);

        if (selfverify) verify();
        
        result_t result = erase_one_descend(key, root, NULL, NULL, NULL, NULL, NULL, 0);

        if (!result.has(btree_not_found))
            --stats.itemcount;

        if (debug) print();
        if (selfverify) verify();

        return !result.has(btree_not_found);
    }

    size_type erase(const key_type &key)
    {
        size_type c = 0;

        while( erase_one(key) )
        {
            ++c;
            if (!allow_duplicates) break;
        }

        return c;
    }

#ifdef BTREE_TODO
    void erase(iterator iter)
    {

    }
#endif

#ifdef BTREE_TODO
    void erase(iterator /* first */, iterator /* last */)
    {
        abort();
    }
#endif

private:
    // *** Private Erase Functions

    result_t erase_one_descend(const key_type& key,
                               node *curr,
                               node *left, node *right,
                               inner_node *leftparent, inner_node *rightparent,
                               inner_node *parent, unsigned int parentslot)
    {
        if (curr->isleafnode())
        {
            leaf_node *leaf = static_cast<leaf_node*>(curr);
            leaf_node *leftleaf = static_cast<leaf_node*>(left);
            leaf_node *rightleaf = static_cast<leaf_node*>(right);

            int slot = find_lower(leaf, key);

            if (!key_equal(key, leaf->slotkey[slot]))
            {
                BTREE_PRINT("Could not find key " << key << " to erase." << std::endl);

                return btree_not_found;
            }

            BTREE_PRINT("Found key in leaf " << curr << " at slot " << slot << std::endl);

            for (int i = slot; i < leaf->slotuse - 1; i++)
            {
                leaf->slotkey[i] = leaf->slotkey[i + 1];
                leaf->slotdata[i] = leaf->slotdata[i + 1];
            }
            leaf->slotuse--;

            result_t myres = btree_ok;

            // if the last key of the leaf was changed, the parent is notified
            // and updates the key of this leaf
            if (slot == leaf->slotuse)
            {
                if (parent && parentslot < parent->slotuse)
                {
                    BTREE_ASSERT(parent->childid[parentslot] == curr);
                    parent->slotkey[parentslot] = leaf->slotkey[leaf->slotuse - 1];
                }
                else
                {
                    BTREE_PRINT("Scheduling lastkeyupdate: key " << leaf->slotkey[leaf->slotuse - 1] << std::endl);
                    myres |= result_t(btree_update_lastkey, leaf->slotkey[leaf->slotuse - 1]);
                }
            }

            if (leaf->isunderflow() && !(leaf == root && leaf->slotuse >= 1))
            {
                // determine what to do about the underflow

                // case : if this empty leaf is the root, there is no way to
                // correct underflow
                if (leftleaf == NULL && rightleaf == NULL)
                {
                    return btree_ok;
                }
                // case : if both left and right leaves would underflow in case of
                // a shift, then merging is necessary. choose the more local merger
                // with our parent
                else if ( (leftleaf == NULL || leftleaf->isfew()) && (rightleaf == NULL || rightleaf->isfew()) )
                {
                    if (leftparent == parent)
                        myres |= merge_leaves(leftleaf, leaf, leftparent);
                    else
                        myres |= merge_leaves(leaf, rightleaf, rightparent);
                }
                // case : the right leaf has extra data, so balance right with current
                else if ( (leftleaf != NULL && leftleaf->isfew()) && (rightleaf != NULL && !rightleaf->isfew()) )
                {
                    if (rightparent == parent)
                        myres |= shift_left_leaf(leaf, rightleaf, rightparent, parentslot);
                    else
                        myres |= merge_leaves(leftleaf, leaf, leftparent);
                }
                // case : the left leaf has extra data, so balance left with current
                else if ( (leftleaf != NULL && !leftleaf->isfew()) && (rightleaf != NULL && rightleaf->isfew()) )
                {
                    if (leftparent == parent)
                        shift_right_leaf(leftleaf, leaf, leftparent, parentslot - 1);
                    else
                        myres |= merge_leaves(leaf, rightleaf, rightparent);
                }
                // case : both the leaf and right leaves have extra data and our
                // parent, choose the leaf with more data
                else if (leftparent == rightparent)
                {
                    if (leftleaf->slotuse <= rightleaf->slotuse)
                        myres |= shift_left_leaf(leaf, rightleaf, rightparent, parentslot);
                    else
                        shift_right_leaf(leftleaf, leaf, leftparent, parentslot - 1);
                }
                else
                {
                    if (leftparent == parent)
                        shift_right_leaf(leftleaf, leaf, leftparent, parentslot - 1);
                    else
                        myres |= shift_left_leaf(leaf, rightleaf, rightparent, parentslot);
                }
            }

            return myres;
        }
        else // !curr->isleafnode()
        {
            inner_node *inner = static_cast<inner_node*>(curr);
            inner_node *leftinner = static_cast<inner_node*>(left);
            inner_node *rightinner = static_cast<inner_node*>(right);

            node *myleft, *myright;
            inner_node *myleftparent, *myrightparent;

            int slot = find_lower(inner, key);

            if (slot == 0) {
                myleft = (left == NULL) ? NULL : (static_cast<inner_node*>(left))->childid[left->slotuse - 1];
                myleftparent = leftparent;
            }
            else {
                myleft = inner->childid[slot - 1];
                myleftparent = inner;
            }

            if (slot == inner->slotuse) {
                myright = (right == NULL) ? NULL : (static_cast<inner_node*>(right))->childid[0];
                myrightparent = rightparent;
            }
            else {
                myright = inner->childid[slot + 1];
                myrightparent = inner;
            }

            BTREE_PRINT("erase_one_descend into " << inner->childid[slot] << std::endl);

            result_t result = erase_one_descend(key,
                                                inner->childid[slot],
                                                myleft, myright,
                                                myleftparent, myrightparent,
                                                inner, slot);

            result_t myres = btree_ok;

            if (result.has(btree_not_found))
            {
                return result;
            }

            if (result.has(btree_update_lastkey))
            {
                if (parent && parentslot < parent->slotuse)
                {
                    BTREE_PRINT("Fixing lastkeyupdate: key " << result.lastkey << " into parent " << parent << " at parentslot " << parentslot << std::endl);

                    BTREE_ASSERT(parent->childid[parentslot] == curr);
                    parent->slotkey[parentslot] = result.lastkey;
                }
                else
                {
                    BTREE_PRINT("Forwarding lastkeyupdate: key " << result.lastkey << std::endl);
                    myres |= result_t(btree_update_lastkey, result.lastkey);
                }
            }

            if (result.has(btree_fixmerge))
            {
                // either the current node or the next is empty and should be removed
                if (inner->childid[slot]->slotuse != 0)
                    slot++;

                // this is the child slot invalidated by the merge
                BTREE_ASSERT(inner->childid[slot]->slotuse == 0);

                free_node(inner->childid[slot]);

                for(int i = slot; i < inner->slotuse; i++)
                {
                    inner->slotkey[i - 1] = inner->slotkey[i];
                    inner->childid[i] = inner->childid[i + 1];
                }
                inner->slotuse--;

                if (inner->level == 1)
                {
                    // fix split key for children leaves
                    slot--;
                    leaf_node *child = static_cast<leaf_node*>(inner->childid[slot]);
                    inner->slotkey[slot] = child->slotkey[ child->slotuse-1 ];
                }
            }

            if (inner->isunderflow() && !(inner == root && inner->slotuse >= 1))
            {
                // case: the inner node is the root and has just one child. that child becomes the new root
                if (leftinner == NULL && rightinner == NULL)
                {
                    BTREE_ASSERT(inner == root);
                    BTREE_ASSERT(inner->slotuse == 0);

                    root = inner->childid[0];

                    inner->slotuse = 0;
                    free_node(inner);

                    return btree_ok;
                }
                // case : if both left and right leaves would underflow in case of
                // a shift, then merging is necessary. choose the more local merger
                // with our parent
                else if ( (leftinner == NULL || leftinner->isfew()) && (rightinner == NULL || rightinner->isfew()) )
                {
                    if (leftparent == parent)
                        myres |= merge_inner(leftinner, inner, leftparent, parentslot - 1);
                    else
                        myres |= merge_inner(inner, rightinner, rightparent, parentslot);
                }
                // case : the right leaf has extra data, so balance right with current
                else if ( (leftinner != NULL && leftinner->isfew()) && (rightinner != NULL && !rightinner->isfew()) )
                {
                    if (rightparent == parent)
                        shift_left_inner(inner, rightinner, rightparent, parentslot);
                    else
                        myres |= merge_inner(leftinner, inner, leftparent, parentslot - 1);
                }
                // case : the left leaf has extra data, so balance left with current
                else if ( (leftinner != NULL && !leftinner->isfew()) && (rightinner != NULL && rightinner->isfew()) )
                {
                    if (leftparent == parent)
                        shift_right_inner(leftinner, inner, leftparent, parentslot - 1);
                    else
                        myres |= merge_inner(inner, rightinner, rightparent, parentslot);
                }
                // case : both the leaf and right leaves have extra data and our
                // parent, choose the leaf with more data
                else if (leftparent == rightparent)
                {
                    if (leftinner->slotuse <= rightinner->slotuse)
                        shift_left_inner(inner, rightinner, rightparent, parentslot);
                    else
                        shift_right_inner(leftinner, inner, leftparent, parentslot - 1);
                }
                else
                {
                    if (leftparent == parent)
                        shift_right_inner(leftinner, inner, leftparent, parentslot - 1);
                    else
                        shift_left_inner(inner, rightinner, rightparent, parentslot);
                }
            }

            return myres;
        }
    }

    result_t merge_leaves(leaf_node* left, leaf_node* right, inner_node* parent)
    {
        BTREE_PRINT("Merge leaf nodes " << left << " and " << right << " with common parent " << parent << "." << std::endl);
        (void)parent;

        BTREE_ASSERT(left->isleafnode() && right->isleafnode());
        BTREE_ASSERT(parent->level == 1);

        BTREE_ASSERT(left->slotuse + right->slotuse < leafslotmax);

        for (unsigned int i = 0; i < right->slotuse; i++)
        {
            left->slotkey[left->slotuse + i] = right->slotkey[i];
            left->slotdata[left->slotuse + i] = right->slotdata[i];
        }
        left->slotuse += right->slotuse;

        left->nextleaf = right->nextleaf;
        if (left->nextleaf)
            left->nextleaf->prevleaf = left;
        else
            tailleaf = left;

        right->slotuse = 0;

        return btree_fixmerge;
    }

    static result_t merge_inner(inner_node* left, inner_node* right, inner_node* parent, unsigned int parentslot)
    {
        BTREE_PRINT("Merge inner nodes " << left << " and " << right << " with common parent " << parent << "." << std::endl);

        BTREE_ASSERT(left->level == right->level);
        BTREE_ASSERT(parent->level == left->level + 1);

        BTREE_ASSERT(parent->childid[parentslot] == left);

        BTREE_ASSERT(left->slotuse + right->slotuse < innerslotmax);

        if (selfverify)
        {
            // find the left node's slot in the parent's children
            unsigned int leftslot = 0;
            while(leftslot <= parent->slotuse && parent->childid[leftslot] != left)
                ++leftslot;

            BTREE_ASSERT(leftslot < parent->slotuse);
            BTREE_ASSERT(parent->childid[leftslot] == left);
            BTREE_ASSERT(parent->childid[leftslot+1] == right);

            BTREE_ASSERT(parentslot == leftslot);
        }

        // retrieve the decision key from parent
        left->slotkey[left->slotuse] = parent->slotkey[parentslot];
        left->slotuse++;

        // copy over keys and children from right
        for (unsigned int i = 0; i < right->slotuse; i++)
        {
            left->slotkey[left->slotuse + i] = right->slotkey[i];
            left->childid[left->slotuse + i] = right->childid[i];
        }
        left->slotuse += right->slotuse;

        left->childid[left->slotuse] = right->childid[right->slotuse];

        right->slotuse = 0;

        return btree_fixmerge;
    }

    static result_t shift_left_leaf(leaf_node *left, leaf_node *right, inner_node *parent, unsigned int parentslot)
    {
        BTREE_ASSERT(left->isleafnode() && right->isleafnode());
        BTREE_ASSERT(parent->level == 1);

        BTREE_ASSERT(left->nextleaf == right);
        BTREE_ASSERT(left == right->prevleaf);

        BTREE_ASSERT(left->slotuse < right->slotuse);
        BTREE_ASSERT(parent->childid[parentslot] == left);

        unsigned int shiftnum = (right->slotuse - left->slotuse) / 2;

        BTREE_PRINT("Shifting (leaf) " << shiftnum << " entries to left " << left << " from right " << right << " with common parent " << parent << "." << std::endl);

        BTREE_ASSERT(left->slotuse + shiftnum < leafslotmax);

        // copy the first items from the right node to the last slot in the left node.
        for(unsigned int i = 0; i < shiftnum; i++)
        {
            left->slotkey[left->slotuse + i] = right->slotkey[i];
            left->slotdata[left->slotuse + i] = right->slotdata[i];
        }
        left->slotuse += shiftnum;
        
        // shift all slots in the right node to the left
    
        right->slotuse -= shiftnum;
        for(int i = 0; i < right->slotuse; i++)
        {
            right->slotkey[i] = right->slotkey[i + shiftnum];
            right->slotdata[i] = right->slotdata[i + shiftnum];
        }

        // fixup parent
        if (parentslot < parent->slotuse) {
            parent->slotkey[parentslot] = left->slotkey[left->slotuse - 1];
            return btree_ok;
        }
        else { // the update is further up the tree
            return result_t(btree_update_lastkey, left->slotkey[left->slotuse - 1]);
        }
    }

    static void shift_left_inner(inner_node *left, inner_node *right, inner_node *parent, unsigned int parentslot)
    {
        BTREE_ASSERT(left->level == right->level);
        BTREE_ASSERT(parent->level == left->level + 1);

        BTREE_ASSERT(left->slotuse < right->slotuse);
        BTREE_ASSERT(parent->childid[parentslot] == left);

        unsigned int shiftnum = (right->slotuse - left->slotuse) / 2;

        BTREE_PRINT("Shifting (inner) " << shiftnum << " entries to left " << left << " from right " << right << " with common parent " << parent << "." << std::endl);

        BTREE_ASSERT(left->slotuse + shiftnum < innerslotmax);

        if (selfverify)
        {
            // find the left node's slot in the parent's children and compare to parentslot

            unsigned int leftslot = 0;
            while(leftslot <= parent->slotuse && parent->childid[leftslot] != left)
                ++leftslot;

            BTREE_ASSERT(leftslot < parent->slotuse);
            BTREE_ASSERT(parent->childid[leftslot] == left);
            BTREE_ASSERT(parent->childid[leftslot+1] == right);

            BTREE_ASSERT(leftslot == parentslot);
        }

        // copy the parent's decision slotkey and childid to the first new key on the left
        left->slotkey[left->slotuse] = parent->slotkey[parentslot];
        left->slotuse++;

        // copy the other items from the right node to the last slots in the left node.
        for(unsigned int i = 0; i < shiftnum - 1; i++)
        {
            left->slotkey[left->slotuse + i] = right->slotkey[i];
            left->childid[left->slotuse + i] = right->childid[i];
        }
        left->slotuse += shiftnum - 1;

        // fixup parent
        parent->slotkey[parentslot] = right->slotkey[shiftnum - 1];
        // last pointer in left
        left->childid[left->slotuse] = right->childid[shiftnum - 1];
        
        // shift all slots in the right node
    
        right->slotuse -= shiftnum;
        for(int i = 0; i < right->slotuse; i++)
        {
            right->slotkey[i] = right->slotkey[i + shiftnum];
            right->childid[i] = right->childid[i + shiftnum];
        }
        right->childid[right->slotuse] = right->childid[right->slotuse + shiftnum];
    }

    static void shift_right_leaf(leaf_node *left, leaf_node *right, inner_node *parent, unsigned int parentslot)
    {
        BTREE_ASSERT(left->isleafnode() && right->isleafnode());
        BTREE_ASSERT(parent->level == 1);

        BTREE_ASSERT(left->nextleaf == right);
        BTREE_ASSERT(left == right->prevleaf);
        BTREE_ASSERT(parent->childid[parentslot] == left);

        BTREE_ASSERT(left->slotuse > right->slotuse);

        unsigned int shiftnum = (left->slotuse - right->slotuse) / 2;

        BTREE_PRINT("Shifting (leaf) " << shiftnum << " entries to right " << right << " from left " << left << " with common parent " << parent << "." << std::endl);

        if (selfverify)
        {
            // find the left node's slot in the parent's children
            unsigned int leftslot = 0;
            while(leftslot <= parent->slotuse && parent->childid[leftslot] != left)
                ++leftslot;

            BTREE_ASSERT(leftslot < parent->slotuse);
            BTREE_ASSERT(parent->childid[leftslot] == left);
            BTREE_ASSERT(parent->childid[leftslot+1] == right);

            BTREE_ASSERT(leftslot == parentslot);
        }

        // shift all slots in the right node
    
        BTREE_ASSERT(right->slotuse + shiftnum < leafslotmax);

        for(int i = right->slotuse; i >= 0; i--)
        {
            right->slotkey[i + shiftnum] = right->slotkey[i];
            right->slotdata[i + shiftnum] = right->slotdata[i];
        }
        right->slotuse += shiftnum;

        // copy the last items from the left node to the first slot in the right node.
        for(unsigned int i = 0; i < shiftnum; i++)
        {
            right->slotkey[i] = left->slotkey[left->slotuse - shiftnum + i];
            right->slotdata[i] = left->slotdata[left->slotuse - shiftnum + i];
        }
        left->slotuse -= shiftnum;

        parent->slotkey[parentslot] = left->slotkey[left->slotuse-1];
    }

    static void shift_right_inner(inner_node *left, inner_node *right, inner_node *parent, unsigned int parentslot)
    {
        BTREE_ASSERT(left->level == right->level);
        BTREE_ASSERT(parent->level == left->level + 1);

        BTREE_ASSERT(left->slotuse > right->slotuse);
        BTREE_ASSERT(parent->childid[parentslot] == left);

        unsigned int shiftnum = (left->slotuse - right->slotuse) / 2;

        BTREE_PRINT("Shifting (leaf) " << shiftnum << " entries to right " << right << " from left " << left << " with common parent " << parent << "." << std::endl);

        if (selfverify)
        {
            // find the left node's slot in the parent's children
            unsigned int leftslot = 0;
            while(leftslot <= parent->slotuse && parent->childid[leftslot] != left)
                ++leftslot;

            BTREE_ASSERT(leftslot < parent->slotuse);
            BTREE_ASSERT(parent->childid[leftslot] == left);
            BTREE_ASSERT(parent->childid[leftslot+1] == right);

            BTREE_ASSERT(leftslot == parentslot);
        }

        // shift all slots in the right node

        BTREE_ASSERT(right->slotuse + shiftnum < innerslotmax);
    
        right->childid[right->slotuse + shiftnum] = right->childid[right->slotuse];
        for(int i = right->slotuse-1; i >= 0; i--)
        {
            right->slotkey[i + shiftnum] = right->slotkey[i];
            right->childid[i + shiftnum] = right->childid[i];
        }

        right->slotuse += shiftnum;

        // copy the parent's decision slotkey and childid to the last new key on the right
        right->slotkey[shiftnum - 1] = parent->slotkey[parentslot];
        right->childid[shiftnum - 1] = left->childid[left->slotuse];

        // copy the remaining last items from the left node to the first slot in the right node.
        for(unsigned int i = 0; i < shiftnum - 1; i++)
        {
            right->slotkey[i] = left->slotkey[left->slotuse - shiftnum + i + 1];
            right->childid[i] = left->childid[left->slotuse - shiftnum + i + 1];
        }

        // copy the first to-be-removed key from the left node to the parent's decision slot
        parent->slotkey[parentslot] = left->slotkey[left->slotuse - shiftnum];

        left->slotuse -= shiftnum;
    }

public:
    // *** Debug Printing

    void print() const
    {
        print_node(root, 0, true);
    }

    void print_leaves() const
    {
        BTREE_PRINT("leaves:" << std::endl);

        const leaf_node *n = headleaf;

        while(n)
        {
            BTREE_PRINT("  " << n << std::endl);

            n = n->nextleaf;
        }
    }

private:

    static void print_node(const node* node, unsigned int depth=0, bool recursive=false)
    {
        for(unsigned int i = 0; i < depth; i++) BTREE_PRINT("  ");
            
        BTREE_PRINT("node " << node << " level " << node->level << " slotuse " << node->slotuse << std::endl);

        if (node->isleafnode())
        {
            const leaf_node *leafnode = static_cast<const leaf_node*>(node);

            for(unsigned int i = 0; i < depth; i++) BTREE_PRINT("  ");
            BTREE_PRINT("  leaf prev " << leafnode->prevleaf << " next " << leafnode->nextleaf << std::endl);

            for(unsigned int i = 0; i < depth; i++) BTREE_PRINT("  ");

            for (unsigned int slot = 0; slot < leafnode->slotuse; ++slot)
            {
                BTREE_PRINT(leafnode->slotkey[slot] << "  "); // << "(data: " << leafnode->slotdata[slot] << ") ";
            }
            BTREE_PRINT(std::endl);
        }
        else
        {
            const inner_node *innernode = static_cast<const inner_node*>(node);

            for(unsigned int i = 0; i < depth; i++) BTREE_PRINT("  ");

            for (unsigned short slot = 0; slot < innernode->slotuse; ++slot)
            {
                BTREE_PRINT("(" << innernode->childid[slot] << ") " << innernode->slotkey[slot] << " ");
            }
            BTREE_PRINT("(" << innernode->childid[innernode->slotuse] << ")");
            BTREE_PRINT(std::endl);

            if (recursive)
            {
                for (unsigned short slot = 0; slot < innernode->slotuse + 1; ++slot)
                {
                    print_node(innernode->childid[slot], depth + 1, recursive);
                }
            }
        }
    }

public:
    // *** Verification of B+ Tree Invariants

    void verify() const
    {
        key_type minkey, maxkey;
        tree_stats vstats;
        
        if (root)
        {
            verify_node(root, &minkey, &maxkey, vstats);

            assert( vstats.itemcount == stats.itemcount );
            assert( vstats.leaves == stats.leaves );
            assert( vstats.innernodes == stats.innernodes );
        }

        verify_leaflinks();
    }

private:

    void verify_node(const node* n, key_type* minkey, key_type* maxkey, tree_stats &vstats) const
    {
        BTREE_PRINT("verifynode " << n << std::endl);

        if (n->isleafnode())
        {
            const leaf_node *leaf = static_cast<const leaf_node*>(n);

            assert(leaf == root || !leaf->isunderflow());

            for(unsigned short slot = 0; slot < leaf->slotuse - 1; ++slot)
            {
                assert(key_lessequal(leaf->slotkey[slot], leaf->slotkey[slot + 1]));
            }

            *minkey = leaf->slotkey[0];
            *maxkey = leaf->slotkey[leaf->slotuse - 1];

            vstats.leaves++;
            vstats.itemcount += leaf->slotuse;
        }
        else // !n->isleafnode()
        {
            const inner_node *inner = static_cast<const inner_node*>(n);
            vstats.innernodes++;

            assert(inner == root || !inner->isunderflow());

            for(unsigned short slot = 0; slot < inner->slotuse - 1; ++slot)
            {
                assert(key_lessequal(inner->slotkey[slot], inner->slotkey[slot + 1]));
            }

            for(unsigned short slot = 0; slot <= inner->slotuse; ++slot)
            {
                const node *subnode = inner->childid[slot];
                key_type subminkey = key_type();
                key_type submaxkey = key_type();

                assert(subnode->level + 1 == inner->level);
                verify_node(subnode, &subminkey, &submaxkey, vstats);

                BTREE_PRINT("verify subnode " << subnode << ": " << subminkey << " - " << submaxkey << std::endl);

                if (slot == 0)
                    *minkey = subminkey;
                else
                    assert(key_greaterequal(subminkey, inner->slotkey[slot-1]));

                if (slot == inner->slotuse)
                    *maxkey = submaxkey;
                else
                    assert(key_equal(inner->slotkey[slot], submaxkey));

                if (inner->level == 1 && slot < inner->slotuse)
                {
                    // children are leaves and must be linked together in the
                    // correct order
                    const leaf_node *leafa = static_cast<const leaf_node*>(inner->childid[slot]);
                    const leaf_node *leafb = static_cast<const leaf_node*>(inner->childid[slot + 1]);

                    assert(leafa->nextleaf == leafb);
                    assert(leafa == leafb->prevleaf);
                    (void)leafa; (void)leafb;
                }
                if (inner->level == 2 && slot < inner->slotuse)
                {
                    // verify leaf links between the adjacent inner nodes
                    const inner_node *parenta = static_cast<const inner_node*>(inner->childid[slot]);
                    const inner_node *parentb = static_cast<const inner_node*>(inner->childid[slot+1]);

                    const leaf_node *leafa = static_cast<const leaf_node*>(parenta->childid[parenta->slotuse]);
                    const leaf_node *leafb = static_cast<const leaf_node*>(parentb->childid[0]);

                    assert(leafa->nextleaf == leafb);
                    assert(leafa == leafb->prevleaf);
                    (void)leafa; (void)leafb;
                }
            }
        }
    }

    void verify_leaflinks() const
    {
        const leaf_node *n = headleaf;

        assert(n->level == 0);
        assert(!n || n->prevleaf == NULL);

        unsigned int testcount = 0;

        while(n)
        {
            assert(n->level == 0);

            for(unsigned short slot = 0; slot < n->slotuse - 1; ++slot)
            {
                assert(key_lessequal(n->slotkey[slot], n->slotkey[slot + 1]));
            }

            testcount += n->slotuse;

            if (n->nextleaf)
            {
                assert(key_lessequal(n->slotkey[n->slotuse-1], n->nextleaf->slotkey[0]));

                assert(n == n->nextleaf->prevleaf);
            }
            else
            {
                assert(tailleaf == n);
            }

            n = n->nextleaf;
        }

        assert(testcount == size());
    }

private:
    // *** Dump and Restore of B+ Trees

    struct dump_header
    {
        char            signature[12];

        unsigned short  version;

        unsigned short  key_type_size;

        unsigned short  data_type_size;

        unsigned short  leafslots;

        unsigned short  innerslots;

        bool            allow_duplicates;

        size_type       itemcount;

        inline void fill()
        {
            // don't want to include string.h just for this signature
            *reinterpret_cast<unsigned int*>(signature+0) = 0x2d787473;
            *reinterpret_cast<unsigned int*>(signature+4) = 0x65727462;
            *reinterpret_cast<unsigned int*>(signature+8) = 0x00000065;

            version = 0;
            key_type_size = sizeof(typename btree_self::key_type);
            data_type_size = sizeof(typename btree_self::data_type);
            leafslots = btree_self::leafslotmax;
            innerslots = btree_self::innerslotmax;
            allow_duplicates = btree_self::allow_duplicates;
        }

        inline bool same(const struct dump_header &o) const
        {
            return (*reinterpret_cast<const unsigned int*>(signature+0) ==
                    *reinterpret_cast<const unsigned int*>(o.signature+0))
                && (*reinterpret_cast<const unsigned int*>(signature+4) ==
                    *reinterpret_cast<const unsigned int*>(o.signature+4))
                && (*reinterpret_cast<const unsigned int*>(signature+8) ==
                    *reinterpret_cast<const unsigned int*>(o.signature+8))

                && (version == o.version)
                && (key_type_size == o.key_type_size)
                && (data_type_size == o.data_type_size)
                && (leafslots == o.leafslots)
                && (innerslots == o.innerslots)
                && (allow_duplicates == o.allow_duplicates);
        }
    };

public:

    void dump(std::ostream &os) const
    {
        struct dump_header header;
        header.fill();
        header.itemcount = size();

        os.write(reinterpret_cast<char*>(&header), sizeof(header));

        if (root)
            dump_node(os, root);
    }

    bool restore(std::istream &is)
    {
        struct dump_header fileheader;
        is.read(reinterpret_cast<char*>(&fileheader), sizeof(fileheader));
        if (!is.good()) return false;

        struct dump_header myheader;
        myheader.fill();
        myheader.itemcount = fileheader.itemcount;

        if (!myheader.same(fileheader))
        {
            BTREE_PRINT("btree::restore: file header does not match instantiation signature." << std::endl);
            return false;
        }

        clear();

        if (fileheader.itemcount > 0)
        {
            root = restore_node(is);
            if (root == NULL) return false;

            stats.itemcount = fileheader.itemcount;
        }

        if (debug) print();
        if (selfverify) verify();

        return true;
    }

private:

    void dump_node(std::ostream &os, const node* n) const
    {
        BTREE_PRINT("dump_node " << n << std::endl);

        if (n->isleafnode())
        {
            const leaf_node *leaf = static_cast<const leaf_node*>(n);

            os.write(reinterpret_cast<const char*>(leaf), sizeof(*leaf));
        }
        else // !n->isleafnode()
        {
            const inner_node *inner = static_cast<const inner_node*>(n);

            os.write(reinterpret_cast<const char*>(inner), sizeof(*inner));

            for(unsigned short slot = 0; slot <= inner->slotuse; ++slot)
            {
                const node *subnode = inner->childid[slot];
                
                dump_node(os, subnode);
            }
        }
    }

    node* restore_node(std::istream &is)
    {
        union {
            node        top;
            leaf_node   leaf;
            inner_node  inner;
        } nu;

        // first read only the top of the node
        is.read(reinterpret_cast<char*>(&nu.top), sizeof(nu.top));
        if (!is.good()) return NULL;

        if (nu.top.isleafnode())
        {
            // read remaining data of leaf node
            is.read(reinterpret_cast<char*>(&nu.leaf) + sizeof(nu.top), sizeof(nu.leaf) - sizeof(nu.top));
            if (!is.good()) return NULL;
            
            leaf_node *newleaf = allocate_leaf();

            // copy over all data, the leaf nodes contain only their double linked list pointers
            *newleaf = nu.leaf;

            // reconstruct the linked list from the order in the file
            if (headleaf == NULL) {
                BTREE_ASSERT(newleaf->prevleaf == NULL);
                headleaf = tailleaf = newleaf;
            }
            else {
                newleaf->prevleaf = tailleaf;
                tailleaf->nextleaf = newleaf;
                tailleaf = newleaf;
            }

            return newleaf;
        }
        else
        {
            // read remaining data of inner node
            is.read(reinterpret_cast<char*>(&nu.inner) + sizeof(nu.top), sizeof(nu.inner) - sizeof(nu.top));
            if (!is.good()) return NULL;

            inner_node *newinner = allocate_inner(0);

            // copy over all data, the inner nodes contain only pointers to their children
            *newinner = nu.inner;

            for(unsigned short slot = 0; slot <= newinner->slotuse; ++slot)
            {
                newinner->childid[slot] = restore_node(is);
            }

            return newinner;
        }
    }
};

} // namespace stx

#endif // _STX_BTREE_H_

---