stx/btree_multiset.h

Go to the documentation of this file.

// $Id: btree_multiset.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_MULTISET_H_
#define _STX_BTREE_MULTISET_H_

#include <stx/btree.h>

namespace stx {

template <typename _Key,
          typename _Compare = std::less<_Key>,
          typename _Traits = btree_default_set_traits<_Key>,
          typename _Alloc = std::allocator<_Key> >
class btree_multiset
{
public:
    // *** Template Parameter Types

    typedef _Key                        key_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

private:
    // *** The Data_Type

    struct empty_struct
    {
    };

public:
    // *** Constructed Types

    typedef struct empty_struct         data_type;

    typedef key_type                    value_type;

    typedef btree_multiset<key_type, key_compare, traits, allocator_type> self;

    typedef stx::btree<key_type, data_type, value_type, key_compare, traits, true, 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_multiset(const allocator_type &alloc = allocator_type())
        : tree(alloc)
    {
    }

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

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

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

    inline ~btree_multiset()
    {
    }

    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_multiset(const self &other)
        : tree(other.tree)
    {
    }

public:
    // *** Public Insertion Functions

    inline iterator insert(const key_type& x)
    {
        return tree.insert2(x, data_type()).first;
    }

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

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

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_MULTISET_H_