#ifndef PREFIX_TREE_NODE_INCLUDED
#define PREFIX_TREE_NODE_INCLUDED

/**
 * A single node on the prefix tree.
 *
 * @note [asutton] Extracted this as a top-level class in case it gets a little
 * too big for the prefix_tree. Besides, it might be reusable.
 *
 * @note [asutton] Would it not be more worthwhile to consider a node as a map,
 * or some other kind of associative (or searchable) container that relates a
 * key to a pointer to a child node? I think so. Maybe rewrite this to use
 * a std::map, and we'll generalize later.
 */
struct prefix_tree_node
{
    typedef char key_element;
    typedef int  value_type;

    /** @name Public data members */
    //@{
    key_element key;    ///< The node's key.
    value_type value;   ///< The node's value.
    bool term;          ///< If true, then the node represents the end of a word
 
    /// The node's 'children.'
    std::map<key_element, prefix_tree_node> child;
    //@}

    /** The default constructor. */
    prefix_tree_node()
        : key(), value(), term(false), child()
    { }

    /**
     * The node's convenience constructor.
     * @note [asutton] always use member init lists.
     */
    prefix_tree_node(key_element key, bool term, value_type value)
        : key(key), value(value), term(term), child()
    { }

    /** The node's destructor should take care of such things now. */
    ~prefix_tree_node()
    { }

    /**
     * Writes a node to an ostream.
     * This is a debugging function and is likely to disappear.
     */
    void write(std::ostream& out, int indent) const
    {
        // Add spaces nicely.
        for (int i = 0; i < indent; ++i) {
            out << ' ';
        }

        out << key;
        
        // Output the value if relevant
        if (term) {
            out << " -> " << value;
        }

        out << std::endl;

        // lookin' forward to them range based for loops,
        // and to support for the new use of the auto keyword.
        typedef std::map<key_element, prefix_tree_node>::const_iterator ite;
        for (ite i = child.begin(); i != child.end(); i++)
        {
            i->second.write(out, indent + 3);
        }
    }
};

#endif