// (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_TREE_NODE_INCLUDED
#define PREFIX_TREE_NODE_INCLUDED

#include <iostream>

namespace gpld {

/// @todo Remove this.
std::ostream& operator<<(std::ostream& out, std::pair<char, unsigned int> const& p)
{
    return out << '(' << p.first << ',' << p.second << ')';
} 

/**
 * @todo Now that I'm thinking about it, there's no particular reason for the nodes to store their own
 *  key -- we can just let the map take care of this.
 */

/**
 * A single node on the prefix tree, specialized over a traits
 * class.
 */
template <typename Traits>
struct prefix_tree_node
{
/** @name Typedefs */
    //@{
    typedef Traits   traits;                                ///< The traits type 
    typedef typename traits::key_comp     key_comp;         ///< The key-element comparator.
    typedef typename traits::key_element  key_element;      ///< An element of the key type.
    typedef typename traits::element_type element_type;     ///< The element-value type. (...)('a', value)
    typedef typename traits::value_type   value_type;       ///< The value type. ("asdfasdf", value)
    typedef
        std::map<key_element, prefix_tree_node<Traits>, key_comp> 
        container_type;
    //@}

/** @name Public data members */
    //@{
    /** The value of the node, which may or may not be a key-value pair. */
    element_type value;
    
    /** Whether or not the node is the end of an item. */
    bool       term;
 
    /// The node's 'children.'
    container_type child;
    
    /// The node's parent.
    prefix_tree_node<Traits> *parent;
    //@}

/** @name Constructors and Destructors */
    //@{
    prefix_tree_node();
    prefix_tree_node(element_type const& value, bool term, prefix_tree_node *parent);
    prefix_tree_node(prefix_tree_node<Traits> const& other);
    prefix_tree_node(prefix_tree_node<Traits> && other);
    ~prefix_tree_node();
    //@}

/** @name Other methods  */
    //@{
    /** Swap. */
    prefix_tree_node<Traits>& swap(prefix_tree_node<Traits> && other)
    {
        using std::swap;
        swap(child, other.child);
        swap(value, other.value);
        return *this;
    }
    //@}
    
    /**
     * Writes a node to an ostream.
     * @remarks This is a debugging function and is likely to disappear.
     */
    void write(std::ostream& out, int indent) const
    {
        // Add spaces as appropriate.
        for (int i = 0; i < indent; ++i) {
            out << ' ';
        }
        
        // Output the value
        out << value;
        if (term) {
            out << " <in set>";
        }
        out << std::endl;

        // Iterate over children and output them as well, with a higher
        // level of indentation.
        typedef typename container_type::const_iterator ite;
        for (ite i = child.begin(); i != child.end(); i++)
        {
            i->second.write(out, indent + 1);
        }
    }
};

/** The default constructor. */
template <typename Traits>
prefix_tree_node<Traits>::prefix_tree_node()
    : value(), term(false), child(), parent(0)
{ }

/** The node's convenience constructor. */
template <typename Traits>
prefix_tree_node<Traits>::prefix_tree_node(element_type const& value, bool term,
        prefix_tree_node *parent)
    : value(value), term(term), child(), parent(parent)
{ }

/** Copy constructor. */
template <typename Traits>
prefix_tree_node<Traits>::prefix_tree_node(prefix_tree_node<Traits> const& other)
    : value(other.value), term(other.term), child(other.child), parent(other.parent)
{ }

/** Move constructor. */
template <typename Traits>
prefix_tree_node<Traits>::prefix_tree_node(prefix_tree_node<Traits> && other)
    : value(std::move(other.value)), term(other.term), child(std::move(other.child))
    , parent(std::move(other.parent))
{ }

/** The node's destructor should take care of such things now. */
template <typename Traits>
prefix_tree_node<Traits>::~prefix_tree_node()
{ }


}; // end of GPLD namespace

#endif