// (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_SET_HPP
#define PREFIX_SET_HPP

#include <iterator>

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

namespace gpld {

/*template <typename Node>
struct UnpairedPrefixElement
{
    typedef typename Node::tree tree_type;
};*/

// NOTE [asutton] Traits classes are typically external to (not inherited from)
// the classes they describe. This looks more to me like a standard base class
// than a traits class.
//
// Parameter names could be a little more clear. I would suggest Key and
// KeyIter.
//
// Also, there seems to be a requirement that the key is, in some way, iterable
// like a string or vector. If the type is not inherently iterable, why not
// treat the object like a bit string - which is iterable. Instead of iterating
// discreet elements of a sequence as the key, you can iterate over the bits
// of the value. This means that you can parameterize your tree over nearly
// any object (e.g., ints). It also means that for those values, your
// operational cost is fixed at O(lg sizeof(T)).
// DO NOT IMPLEMENT THIS YET. Assume for now, that all Keys will be iterable.
//
// You're defining a lot of information in these classes. I think that the
// ideal situation would be to put most of the implementation into the treee
// and then pull type and functions from there.
/**
 * The traits class for a prefix_set.
 */
template
   <typename Key,
    typename KeyComp>
class prefix_set_traits
{
public:
    /** The key type and value type are the same in this case. */
    typedef Key key_type;
    typedef 
        typename key_traits<Key>::iterator
        iterator_type;

    
    typedef key_type      value_type;
    
    typedef
        typename std::iterator_traits<iterator_type>::value_type
        key_element;
    typedef key_element element_type;
        
    typedef KeyComp       key_comp;

    /** Used to get the key that we're comparing. */
    static key_type const& key_of(value_type const& val)
    { return val; }

    /** Used to get the key in other contexts. */
    static key_type& key_of(value_type& val)
    { return val; }

    /** Used to get the key element that we're comparing. */
    static key_element const& key_of(element_type const& val)
    { return val; }

    /** Used to get the key element in other contexts. */
    static key_element& key_of(element_type& val)
    { return val; }

    /** No-op, since there's no 'value' to speak of. */
    static void set_value(element_type& ele, value_type const& val)
    { return; }
};

// NOTE [asutton] I would not parameterize the KeyIterter. This is a great place
// to use a traits class to determine the iterability of Key. For example, you
// might define KeyIterter as key_traits<Key>::iterator. By default, the nested
// iterator can be defined as Key::const_iterator. For non-iterable objects like
// int, it could be something like bitstring_iterator<Key>.
// See the new key_traits.hpp header for a basic implementation.
/**
 * The prefix_set class is derived from prefix_tree, using traits specific
 * for the prefix_set.
 */
template
<typename Key,
 typename KeyComp = std::less
    <typename std::iterator_traits<typename key_traits<Key>::iterator>::value_type>
>
class prefix_set
    : public prefix_tree< prefix_set_traits<Key, KeyComp> >
{
public:
    typedef prefix_set_traits<Key, 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_set() : base_type() { }
    ~prefix_set() { }

private:
};

}; // end of GPLD namespace

#endif