map.h

/***************************************************************************
 * include/stxxl/bits/containers/map.h
 *
 * Part of the STXXL. See http://stxxl.sourceforge.net
 *
 * Copyright (C) 2006 Roman Dementiev <[email protected]>
 * Copyright (C) 2008, 2009 Andreas Beckmann <[email protected]>
 *
 * Distributed under the Boost Software License, Version 1.0.
 * (See accompanying file LICENSE_1_0.txt or copy at
 * http://www.boost.org/LICENSE_1_0.txt)
 **************************************************************************/

#ifndef STXXL_MAP_HEADER
#define STXXL_MAP_HEADER

#include <stxxl/bits/noncopyable.h>
#include <stxxl/bits/containers/btree/btree.h>


__STXXL_BEGIN_NAMESPACE

namespace btree
{
 template <class KeyType,
 class DataType,
 class CompareType,
 unsigned LogNodeSize,
 unsigned LogLeafSize,
 class PDAllocStrategy
 >
 class btree;
}



template <class KeyType,
 class DataType,
 class CompareType,
 unsigned RawNodeSize = 16 * 1024, // 16 KBytes default
 unsigned RawLeafSize = 128 * 1024, // 128 KBytes default
 class PDAllocStrategy = stxxl::SR
 >
class map : private noncopyable
{
 typedef btree::btree<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> impl_type;

 impl_type Impl;

public:
 typedef typename impl_type::node_block_type node_block_type;
 typedef typename impl_type::leaf_block_type leaf_block_type;

 typedef typename impl_type::key_type key_type;
 typedef typename impl_type::data_type data_type;
 typedef typename impl_type::data_type mapped_type;
 typedef typename impl_type::value_type value_type;
 typedef typename impl_type::key_compare key_compare;
 typedef typename impl_type::value_compare value_compare;
 typedef typename impl_type::pointer pointer;
 typedef typename impl_type::const_pointer const_pointer;
 typedef typename impl_type::reference reference;
 typedef typename impl_type::const_reference const_reference;
 typedef typename impl_type::size_type size_type;
 typedef typename impl_type::difference_type difference_type;
 typedef typename impl_type::iterator iterator;
 typedef typename impl_type::const_iterator const_iterator;
 typedef std::reverse_iterator<iterator> reverse_iterator;
 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

 iterator begin() { return Impl.begin(); }
 iterator end() { return Impl.end(); }
 const_iterator begin() const { return Impl.begin(); }
 const_iterator end() const { return Impl.end(); }
 const_iterator cbegin() const { return begin(); }
 const_iterator cend() const { return end(); }

 reverse_iterator rbegin()
 {
 return reverse_iterator(end());
 }
 const_reverse_iterator rbegin() const
 {
 return const_reverse_iterator(end());
 }
 const_reverse_iterator crbegin() const
 {
 return const_reverse_iterator(end());
 }
 reverse_iterator rend()
 {
 return reverse_iterator(begin());
 }
 const_reverse_iterator rend() const
 {
 return const_reverse_iterator(begin());
 }
 const_reverse_iterator crend() const
 {
 return const_reverse_iterator(begin());
 }

 size_type size() const { return Impl.size(); }
 size_type max_size() const { return Impl.max_size(); }
 bool empty() const { return Impl.empty(); }
 key_compare key_comp() const { return Impl.key_comp(); }
 value_compare value_comp() const { return Impl.value_comp(); }

 map(unsigned_type node_cache_size_in_bytes,
 unsigned_type leaf_cache_size_in_bytes
 ) : Impl(node_cache_size_in_bytes, leaf_cache_size_in_bytes)
 { }

 map(const key_compare & c_,
 unsigned_type node_cache_size_in_bytes,
 unsigned_type leaf_cache_size_in_bytes
 ) : Impl(c_, node_cache_size_in_bytes, leaf_cache_size_in_bytes)
 { }

 template <class InputIterator>
 map(InputIterator b,
 InputIterator e,
 unsigned_type node_cache_size_in_bytes,
 unsigned_type leaf_cache_size_in_bytes,
 bool range_sorted = false,
 double node_fill_factor = 0.75,
 double leaf_fill_factor = 0.6
 ) : Impl(b, e, node_cache_size_in_bytes, leaf_cache_size_in_bytes,
 range_sorted, node_fill_factor, leaf_fill_factor)
 { }

 template <class InputIterator>
 map(InputIterator b,
 InputIterator e,
 const key_compare & c_,
 unsigned_type node_cache_size_in_bytes,
 unsigned_type leaf_cache_size_in_bytes,
 bool range_sorted = false,
 double node_fill_factor = 0.75,
 double leaf_fill_factor = 0.6
 ) : Impl(b, e, c_, node_cache_size_in_bytes, leaf_cache_size_in_bytes,
 range_sorted, node_fill_factor, leaf_fill_factor)
 { }

 void swap(map & obj) { std::swap(Impl, obj.Impl); }
 std::pair<iterator, bool> insert(const value_type & x)
 {
 return Impl.insert(x);
 }
 iterator insert(iterator pos, const value_type & x)
 {
 return Impl.insert(pos, x);
 }
 template <class InputIterator>
 void insert(InputIterator b, InputIterator e)
 {
 Impl.insert(b, e);
 }
 void erase(iterator pos)
 {
 Impl.erase(pos);
 }
 size_type erase(const key_type & k)
 {
 return Impl.erase(k);
 }
 void erase(iterator first, iterator last)
 {
 Impl.erase(first, last);
 }
 void clear()
 {
 Impl.clear();
 }
 iterator find(const key_type & k)
 {
 return Impl.find(k);
 }
 const_iterator find(const key_type & k) const
 {
 return Impl.find(k);
 }
 size_type count(const key_type & k)
 {
 return Impl.count(k);
 }
 iterator lower_bound(const key_type & k)
 {
 return Impl.lower_bound(k);
 }
 const_iterator lower_bound(const key_type & k) const
 {
 return Impl.lower_bound(k);
 }
 iterator upper_bound(const key_type & k)
 {
 return Impl.upper_bound(k);
 }
 const_iterator upper_bound(const key_type & k) const
 {
 return Impl.upper_bound(k);
 }
 std::pair<iterator, iterator> equal_range(const key_type & k)
 {
 return Impl.equal_range(k);
 }
 std::pair<const_iterator, const_iterator> equal_range(const key_type & k) const
 {
 return Impl.equal_range(k);
 }
 data_type & operator [] (const key_type & k)
 {
 return Impl[k];
 }

 void enable_prefetching()
 {
 Impl.enable_prefetching();
 }

 void disable_prefetching()
 {
 Impl.disable_prefetching();
 }

 bool prefetching_enabled()
 {
 return Impl.prefetching_enabled();
 }

 void print_statistics(std::ostream & o) const
 {
 Impl.print_statistics(o);
 }

 void reset_statistics()
 {
 Impl.reset_statistics();
 }

 template <class KeyType_,
 class DataType_,
 class CompareType_,
 unsigned RawNodeSize_,
 unsigned RawLeafSize_,
 class PDAllocStrategy_>
 friend bool operator == (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & a,
 const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & b);
 template <class KeyType_,
 class DataType_,
 class CompareType_,
 unsigned RawNodeSize_,
 unsigned RawLeafSize_,
 class PDAllocStrategy_>
 friend bool operator < (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & a,
 const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & b);
 template <class KeyType_,
 class DataType_,
 class CompareType_,
 unsigned RawNodeSize_,
 unsigned RawLeafSize_,
 class PDAllocStrategy_>
 friend bool operator > (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & a,
 const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & b);
 template <class KeyType_,
 class DataType_,
 class CompareType_,
 unsigned RawNodeSize_,
 unsigned RawLeafSize_,
 class PDAllocStrategy_>
 friend bool operator != (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & a,
 const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & b);
 template <class KeyType_,
 class DataType_,
 class CompareType_,
 unsigned RawNodeSize_,
 unsigned RawLeafSize_,
 class PDAllocStrategy_>
 friend bool operator <= (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & a,
 const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & b);
 template <class KeyType_,
 class DataType_,
 class CompareType_,
 unsigned RawNodeSize_,
 unsigned RawLeafSize_,
 class PDAllocStrategy_>
 friend bool operator >= (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & a,
 const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_> & b);
};

template <class KeyType,
 class DataType,
 class CompareType,
 unsigned RawNodeSize,
 unsigned RawLeafSize,
 class PDAllocStrategy
 >
inline bool operator == (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a,
 const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b)
{
 return a.Impl == b.Impl;
}

template <class KeyType,
 class DataType,
 class CompareType,
 unsigned RawNodeSize,
 unsigned RawLeafSize,
 class PDAllocStrategy
 >
inline bool operator < (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a,
 const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b)
{
 return a.Impl < b.Impl;
}

template <class KeyType,
 class DataType,
 class CompareType,
 unsigned RawNodeSize,
 unsigned RawLeafSize,
 class PDAllocStrategy
 >
inline bool operator > (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a,
 const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b)
{
 return a.Impl > b.Impl;
}

template <class KeyType,
 class DataType,
 class CompareType,
 unsigned RawNodeSize,
 unsigned RawLeafSize,
 class PDAllocStrategy
 >
inline bool operator != (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a,
 const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b)
{
 return a.Impl != b.Impl;
}

template <class KeyType,
 class DataType,
 class CompareType,
 unsigned RawNodeSize,
 unsigned RawLeafSize,
 class PDAllocStrategy
 >
inline bool operator <= (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a,
 const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b)
{
 return a.Impl <= b.Impl;
}

template <class KeyType,
 class DataType,
 class CompareType,
 unsigned RawNodeSize,
 unsigned RawLeafSize,
 class PDAllocStrategy
 >
inline bool operator >= (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a,
 const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b)
{
 return a.Impl >= b.Impl;
}


__STXXL_END_NAMESPACE

namespace std
{
 template <class KeyType,
 class DataType,
 class CompareType,
 unsigned RawNodeSize,
 unsigned RawLeafSize,
 class PDAllocStrategy
 >
 void swap(stxxl::map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & a,
 stxxl::map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> & b
 )
 {
 a.swap(b);
 }
}

#endif // !STXXL_MAP_HEADER