#ifndef PREFIX_TREE_INCLUDED
#define PREFIX_TREE_INCLUDED

#include <iostream>

#include <string>
#include <algorithm>
#include <functional>
#include <map>
#include <memory>

namespace gpld {

// Include the prefix tree node class.
#include "prefix_tree_node.hpp"

// NOTE [asutton] Are you settting up the prefix tree in the same manner as the
// set/map? Could you build the associative containers set *and* map over the
// prefix tree?
//
// If that's what you're aiming for, then remember that a map is just a set
// who's value type is an ordered pair. The only difference is the comparison
// function. For maps, it just compares the key of the value_type (first). For
// sets, it compares the entire value_type.
/**
 * The currently non-generic implementation of the tree, to work on
 * getting the interface right first.
 *
 * Comparison of equality is defined as (!(x<y) && !(y<x), so that
 * the user of the library only needs to worry about providing
 * one equality operator. I am not sure if that is the best idea.
 */
class prefix_tree
{
public:
    typedef std::string         key_type;
    typedef char                key_element;
    typedef int                 value_type;
    typedef std::size_t         size_type;
    typedef prefix_tree_node    node_type;

    /** @name Constructors and Destructors */
    //@{
    prefix_tree();
    prefix_tree(prefix_tree const& other);
    prefix_tree(prefix_tree && other);
    ~prefix_tree();
    //@}

    prefix_tree& operator=(prefix_tree const& other);
    prefix_tree& operator=(prefix_tree && other);

    prefix_tree& swap(prefix_tree&& other);

    /** @name Access Operators */
    //@{
    value_type&       at  (key_type const& key);
    value_type const& at  (key_type const& key) const;
    value_type&       operator[](key_type const& key);
    value_type const& operator[](key_type const& key) const;
    //@}

    /** @name Insertion / Removal Operators */
    /// @todo iterators
    template <typename T>
    void insert(T const& begin, T const& end, value_type const& value);

    /// @todo: Don't assume this is a 'real' container with begin() and end()
    void insert(key_type const& key, value_type const& value);

    void clear();

    /** @name Size-Query Methods */
    //@{
    size_type size() const;
    bool empty() const;
    //@}

    /** @name Debugging Things */
    //@{
    void write(std::ostream& out) const;
    //@}

private:
    template <typename T>
    node_type* get_existing_node(T begin, T end) const;

    template <typename T>
    node_type* get_node(T begin, T end);

    node_type   _root;      ///< The root of the trie.
    size_type   _size;      ///< The number of keys stored in the trie.
};

/** The default constructor. */
prefix_tree::prefix_tree()
    : _root(0, 1, 0), _size(0)
{ }

/** The copy constructor. */
prefix_tree::prefix_tree(prefix_tree const& other)
    : _root(other._root), _size(other._size)
{ }

/** The move constructor. */
prefix_tree::prefix_tree(prefix_tree && other)
    : _root(std::move(other._root)), _size(other._size)
{ other.swap(prefix_tree()); }

/** The destructor. */
prefix_tree::~prefix_tree()
{ }

/** The copy assignment operator. */
prefix_tree& prefix_tree::operator=(prefix_tree const& other)
{ return swap(prefix_tree(other)); }

/** The move assignmnent operator. */
prefix_tree& prefix_tree::operator=(prefix_tree && other)
{
    clear();
    return swap(other);
}

/** The swap operation. */
prefix_tree& prefix_tree::swap(prefix_tree&& other)
{
    using std::swap;
    swap(_root, other._root);
    swap(_size, other._size);
    return *this;
}

/**
 * Returns the value at an existing position in the trie.
 * If the position does not exist, it will be created with the default value.
 */
prefix_tree::value_type& prefix_tree::operator[](key_type const& key)
{
    node_type *pos = get_node(key.begin(), key.end());
    pos->term = true;
    return pos->value; 
}

/**
 * Inserts a key into the prefix, iterating over key_elements in [start, end).
 * Begin and end should be iterators or pointers.
 */
template <typename T>
void prefix_tree::insert(T const& begin, T const& end, value_type const& value)
{
    // Find the node to insert.
    node_type *pos = get_node(begin, end); 

    // The element that we stopped at is the last character in the string,
    // and where our value ought to be.

    // If 'term' is already set, then the key already exists, and our insert
    // should fail somehow.
    if (pos->term) {
        /// @todo fail! Throw an exception or return a null iterator.
    }

    // Now we can set 'term' and value appropriately.
    pos->value = value;
    pos->term  = true;

    // Increment size.
    ++_size;
}

/** Inserts a key into the prefix tree. */
void prefix_tree::insert(key_type const& key, value_type const& value)
{
    insert(key.begin(), key.end(), value);
}

/**
 * Clears the prefix tree.
 */
void prefix_tree::clear()
{
    _root.child.clear();
    _size = 0;
}

/** Returns the number of items in the trie. */
prefix_tree::size_type prefix_tree::size() const
{ return _size; }

/** Returns whether or not the trie is empty. */
bool prefix_tree::empty() const
{ return !_size; }

/**
 * Writes the prefix tree to an ostream.
 * This is a debugging function and is likely to go away.
 */
void prefix_tree::write(std::ostream& out) const
{ _root.write(out, 0); }

/// @todo: next two functions are a candidate for templating

/**
 * Gets the position of a node.
 * Will not insert if the node does not exist.
 */
template <typename T>
prefix_tree::node_type* prefix_tree::get_existing_node(T begin, T end) const
{
    // Start our insertion at the root.
    node_type *pos = &_root;

    // Iterate through the key being inserted.
    for (T i = begin; i != end; ++i)
    {
        // Elements will be inserted as necessary if they don't exist.
        if (pos->child.find(*i) == pos->child.end()) {
            pos = 0;
            break;
        }

        // Get the next appropriated child.
        pos = &(pos->child[*i]);
    }
    
    return pos;
}

/**
 * Gets the address of the node, inserting as necessary.
 */
template <typename T>
prefix_tree::node_type* prefix_tree::get_node(T begin, T end)
{
    // Start our insertion at the root.
    node_type *pos = &_root;

    // Iterate through the key being inserted.
    for (T i = begin; i != end; ++i)
    {
        // Elements will be inserted as necessary if they don't exist.
        if (pos->child.find(*i) == pos->child.end()) {
            pos->child[*i].key = *i;
        }

        // Get the next appropriated child.
        pos = &(pos->child[*i]);
    }
    
    return pos;
}

} // End of the gpld namespace

#endif