//
// map and multimap based on B+ tree
//
// Copyright (c) 2005-? by Yang Xiaodong. ALL RIGHTS RESERVED.
// Consult your license regarding permissions and restrictions.
// V1.0.0
//

//
// History:
// Yang Xiaodong created 2005-6-7 mail:EastdawnYang@gmail.com
//

#ifdef _MSC_VER
#pragma once
#endif

#ifndef _MAP_24677C16_D3D8_4ce6_908B_D333526CE11B_
#define _MAP_24677C16_D3D8_4ce6_908B_D333526CE11B_

#include "btree.h"

#pragma pack(push,8)

namespace stdex
{

// Template Class: map
template
<
class t_Key,
class t_Value,
class t_Traits = ::stdex::compare< t_Key >,
template < class > class t_Allocator = ::std::allocator,
unsigned int t_nOrder = 8
>
class map: public ::stdex::btree< t_Key, t_Value, t_nOrder >= 3 ? t_nOrder : 3, t_Traits, t_Allocator, false >
{
enum { _order = t_nOrder >= 3 ? t_nOrder : 3 };
typedef ::stdex::btree< t_Key, t_Value, _order, t_Traits, t_Allocator, false > base_type;
public:
typedef typename base_type::iterator iterator;
typedef typename base_type::const_iterator const_iterator;
typedef typename base_type::reverse_iterator reverse_iterator;
typedef typename base_type::const_reverse_iterator const_reverse_iterator;
typedef typename base_type::key_type key_type;
typedef typename base_type::value_type value_type;
typedef typename base_type::pairib_type pairib_type;

public:
map() {}

value_type& operator[]( const key_type &key )
{
iterator it = find( key );
if ( end() != it ) return it->second;
pairib_type ret = insert( key, value_type() );
return ret.first->second;
}
};

// Template Class: multimap
template
<
class t_Key,
class t_Value,
class t_Traits = ::stdex::compare< t_Key >,
template < class > class t_Allocator = ::std::allocator,
unsigned int t_nOrder = 8
>
class multimap: public ::stdex::btree< t_Key, t_Value, t_nOrder >= 3 ? t_nOrder : 3, t_Traits, t_Allocator, true >
{
enum { _order = t_nOrder >= 3 ? t_nOrder : 3 };
typedef ::stdex::btree< t_Key, t_Value, _order, t_Traits, t_Allocator, false > base_type;
public:
typedef typename base_type::iterator iterator;
typedef typename base_type::const_iterator const_iterator;
typedef typename base_type::reverse_iterator reverse_iterator;
typedef typename base_type::const_reverse_iterator const_reverse_iterator;
typedef typename base_type::key_type key_type;
typedef typename base_type::value_type value_type;
typedef typename base_type::pairib_type pairib_type;

multimap() {}

value_type& operator[]( const key_type &key )
{
pairib_type ret = insert( key, value_type() );
return ret.first->second;
}
};


}//namespace stdex

#pragma pack(pop)

#endif//#ifndef _MAP_24677C16_D3D8_4ce6_908B_D333526CE11B_