stx/btree_map.h

Go to the documentation of this file.

// $Id: btree_map.h 128 2011-05-18 07:23:35Z tb $
/*
 * STX B+ Tree Template Classes v0.8.6
 * Copyright (C) 2008-2011 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_MAP_H_
#define _STX_BTREE_MAP_H_

#include <stx/btree.h>

namespace stx {

template <typename _Key, typename _Data,
          typename _Compare = std::less<_Key>,
          typename _Traits = btree_default_map_traits<_Key, _Data>,
          typename _Alloc = std::allocator<std::pair<_Key, _Data> > >
class btree_map
{
public:
    // *** Template Parameter Types

    typedef _Key                        key_type;

    typedef _Data                       data_type;

    typedef _Compare                    key_compare;

    typedef _Traits                     traits;

    typedef _Alloc                      allocator_type;

    // The macro BTREE_FRIENDS can be used by outside class to access the B+
    // tree internals. This was added for wxBTreeDemo to be able to draw the
    // tree.
    BTREE_FRIENDS

public:
    // *** Constructed Types

    typedef btree_map<key_type, data_type, key_compare, traits, allocator_type> self;

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

    typedef stx::btree<key_type, data_type, value_type, key_compare, traits, false, allocator_type> btree_impl;

    typedef typename btree_impl::value_compare  value_compare;

    typedef typename btree_impl::size_type      size_type;

    typedef typename btree_impl::tree_stats     tree_stats;

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

    static const unsigned short         leafslotmax =  btree_impl::leafslotmax;

    static const unsigned short         innerslotmax =  btree_impl::innerslotmax;

    static const unsigned short         minleafslots = btree_impl::minleafslots;

    static const unsigned short         mininnerslots = btree_impl::mininnerslots;

    static const bool                   selfverify = btree_impl::selfverify;

    static const bool                   debug = btree_impl::debug;

    static const bool                   allow_duplicates = btree_impl::allow_duplicates;

public:
    // *** Iterators and Reverse Iterators

    typedef typename btree_impl::iterator               iterator;

    typedef typename btree_impl::const_iterator         const_iterator;

    typedef typename btree_impl::reverse_iterator       reverse_iterator;

    typedef typename btree_impl::const_reverse_iterator const_reverse_iterator;

private:
    // *** Tree Implementation Object

    btree_impl  tree;

public:
    // *** Constructors and Destructor

    explicit inline btree_map(const allocator_type &alloc = allocator_type())
        : tree(alloc)
    {
    }

    explicit inline btree_map(const key_compare &kcf,
                              const allocator_type &alloc = allocator_type())
        : tree(kcf, alloc)
    {
    }

    template <class InputIterator>
    inline btree_map(InputIterator first, InputIterator last,
                     const allocator_type &alloc = allocator_type())
        : tree(first, last, alloc)
    {
    }

    template <class InputIterator>
    inline btree_map(InputIterator first, InputIterator last, const key_compare &kcf,
                     const allocator_type &alloc = allocator_type())
        : tree(first, last, kcf, alloc)
    {
    }

    inline ~btree_map()
    {
    }

    void swap(self& from)
    {
        std::swap(tree, from.tree);
    }

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

    inline key_compare key_comp() const
    {
        return tree.key_comp();
    }

    inline value_compare value_comp() const
    {
        return tree.value_comp();
    }

public:
    // *** Allocators

    allocator_type get_allocator() const
    {
        return tree.get_allocator();
    }

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

    void clear()
    {
        tree.clear();
    }

public:
    // *** STL Iterator Construction Functions

    inline iterator begin()
    {
        return tree.begin();
    }

    inline iterator end()
    {
        return tree.end();
    }

    inline const_iterator begin() const
    {
        return tree.begin();
    }

    inline const_iterator end() const
    {
        return tree.end();
    }

    inline reverse_iterator rbegin()
    {
        return tree.rbegin();
    }

    inline reverse_iterator rend()
    {
        return tree.rend();
    }

    inline const_reverse_iterator rbegin() const
    {
        return tree.rbegin();
    }

    inline const_reverse_iterator rend() const
    {
        return tree.rend();
    }

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

    inline size_type size() const
    {
        return tree.size();
    }

    inline bool empty() const
    {
        return tree.empty();
    }

    inline size_type max_size() const
    {
        return tree.max_size();
    }

    inline const tree_stats& get_stats() const
    {
        return tree.get_stats();
    }

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

    bool exists(const key_type &key) const
    {
        return tree.exists(key);
    }

    iterator find(const key_type &key)
    {
        return tree.find(key);
    }

    const_iterator find(const key_type &key) const
    {
        return tree.find(key);
    }

    size_type count(const key_type &key) const
    {
        return tree.count(key);
    }

    iterator lower_bound(const key_type& key)
    {
        return tree.lower_bound(key);
    }

    const_iterator lower_bound(const key_type& key) const
    {
        return tree.lower_bound(key);
    }

    iterator upper_bound(const key_type& key)
    {
        return tree.upper_bound(key);
    }

    const_iterator upper_bound(const key_type& key) const
    {
        return tree.upper_bound(key);
    }

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

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

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

    inline bool operator==(const self &other) const
    {
        return (tree == other.tree);
    }

    inline bool operator!=(const self &other) const
    {
        return (tree != other.tree);
    }

    inline bool operator<(const self &other) const
    {
        return (tree < other.tree);
    }

    inline bool operator>(const self &other) const
    {
        return (tree > other.tree);
    }

    inline bool operator<=(const self &other) const
    {
        return (tree <= other.tree);
    }

    inline bool operator>=(const self &other) const
    {
        return (tree >= other.tree);
    }

public:

    inline self& operator= (const self &other)
    {
        if (this != &other)
        {
            tree = other.tree;
        }
        return *this;
    }

    inline btree_map(const self &other)
        : tree(other.tree)
    {
    }

public:
    // *** Public Insertion Functions

    inline std::pair<iterator, bool> insert(const value_type& x)
    {
        return tree.insert2(x.first, x.second);
    }

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

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

    inline iterator insert(iterator hint, const value_type &x)
    {
        return tree.insert2(hint, x.first, x.second);
    }

    inline iterator insert2(iterator hint, const key_type& key, const data_type& data)
    {
        return tree.insert2(hint, key, data);
    }

    inline data_type& operator[](const key_type& key)
    {
        iterator i = insert( value_type(key, data_type()) ).first;
        return i.data();
    }

    template <typename InputIterator>
    inline void insert(InputIterator first, InputIterator last)
    {
        return tree.insert(first, last);
    }

public:
    // *** Public Erase Functions

    bool erase_one(const key_type &key)
    {
        return tree.erase_one(key);
    }

    size_type erase(const key_type &key)
    {
        return tree.erase(key);
    }

    void erase(iterator iter)
    {
        return tree.erase(iter);
    }

#ifdef BTREE_TODO


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

#ifdef BTREE_DEBUG
public:
    // *** Debug Printing

    void print(std::ostream &os) const
    {
        tree.print(os);
    }

    void print_leaves(std::ostream &os) const
    {
        tree.print_leaves(os);
    }
#endif

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

    void verify() const
    {
        tree.verify();
    }

public:

    void dump(std::ostream &os) const
    {
        tree.dump(os);
    }

    bool restore(std::istream &is)
    {
        return tree.restore(is);
    }
};

} // namespace stx

#endif // _STX_BTREE_MAP_H_