// (C) Copyright 2008-2009 SDML (www.sdml.info)
//
// Use, modification and distribution is subject to 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 PREFIX_MAP_INCLUDED
#define PREFIX_MAP_INCLUDED

#include <iterator>
#include <utility>

#include "prefix_tree.hpp"
#include "key_traits.hpp"

namespace gpld {

/** 
 * The traits class for a prefix_map.
  */
template
   <typename KeyT,
    typename ValueT,
    typename KeyComp>
class prefix_map_traits
{
public:
    /** The key type and value type are the same in this case. */
    typedef KeyT key_type;
    typedef
        typename key_traits<key_type>::iterator
        iterator_type;
    typedef
        typename std::iterator_traits<iterator_type>::value_type
        key_element;
    typedef std::pair<key_type, ValueT>    value_type;
    typedef std::pair<key_element, ValueT> element_type;
    typedef KeyComp     key_comp;
    
    /** Used to get the key that we're comparing. */
    static key_type const& key_of(const value_type& val)
    { return val.first; }
    
    /** Used to get the key in other contexts. */ 
    static key_type& key_of(value_type& val)
    { return val.first; }
    
    /** Used to get the key element that we're comparing. */
    static key_element const& key_of(const element_type& val)
    { return val.first; }
    
    /** Used to get the key element in other contexts. */ 
    static key_element& key_of(element_type& val)
    { return val.first; }
    
    /** Sets the 'value' part of element_type. */
    static void set_value(element_type& ele, value_type const& val)
    { ele.second = val.second; }
};

/**
 * The prefix_map class is derived from prefix_tree, using traits specific
 * for the prefix_map.
 */
template
    <typename KeyT,
     typename ValueT,
     typename KeyComp =
        std::less<typename std::iterator_traits<typename key_traits<KeyT>::iterator>::value_type>
    >
class prefix_map
    : public prefix_tree< prefix_map_traits<KeyT, ValueT, KeyComp> >
{
public:
    typedef
        prefix_map_traits<KeyT, ValueT, KeyComp> traits_type;
    typedef
        typename traits_type::key_type    key_type;
    typedef
        typename traits_type::key_element key_element;
    typedef
        typename traits_type::value_type  value_type;
    typedef std::size_t                   size_type;
    typedef prefix_tree_node<traits_type> node_type;
    typedef prefix_tree<traits_type>      base_type;
    
    // Constructor
    prefix_map() : base_type() { }
    ~prefix_map() { } 
    
private:
};

}; // end of GPLD namespace

#endif