// (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_HPP
#define PREFIX_TREE_HPP

//#include <iostream>

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

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

// Include key traits header.
#include "key_traits.hpp"

namespace gpld {

// 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.
/**
 * 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.
 */
template <typename Traits>
class prefix_tree : public Traits
{
public:
    /// The traits class.
    typedef Traits traits_type;
     
    /// The value type.
    typedef
        typename traits_type::value_type
        value_type;
    
    /// The type of a key.
    typedef
        typename traits_type::key_type
        key_type;
    
    /// The type that iterates over keys.
    typedef
        typename key_traits<key_type>::iterator
        key_iterator;
    
    /// An element of the key type.
    typedef
        typename std::iterator_traits<key_iterator>::value_type
        key_element;
   
    /// The tree's iterator type.
    typedef prefix_tree_iterator<Traits> iterator;

    typedef std::size_t                  size_type;
    typedef prefix_tree_node<Traits>     node_type;

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

    prefix_tree<Traits>& swap(prefix_tree<Traits>&& other);

    prefix_tree<Traits>& operator=(prefix_tree<Traits> const& other);
    prefix_tree<Traits>& operator=(prefix_tree<Traits> && other);

    iterator find(key_type const& key);

    /** @name Insertion / Removal Operators */    
    /// @todo: Don't assume there is a 'real' container with begin() and end()
    std::pair<iterator, bool> insert(value_type const& value);

    void clear();

    /** @name Size-Query Methods */
    //@{
    size_type size() const;
    bool empty() const;
    //@}
    
    /** @name Debugging Methods */
    //@{
    void write(std::ostream& out) const
    { _root.write(out, 0); }
    //@}

protected:    
    node_type* get_existing_node(key_iterator const& begin, key_iterator const& end);
    node_type* get_node(key_iterator const& begin, key_iterator const& end);

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

/** The default constructor. */
template <typename Traits>
prefix_tree<Traits>::prefix_tree()
    : _root(), _size(0)
{ }

/** The copy constructor. */
template <typename Traits>
prefix_tree<Traits>::prefix_tree(prefix_tree<Traits> const& other)
    : _root(other._root), _size(other._size)
{ }

/** The move constructor. */
template <typename Traits>
prefix_tree<Traits>::prefix_tree(prefix_tree<Traits> && other)
    : _root(), _size(0)
{
    swap(other);
}

/** The destructor. */
template <typename Traits>
prefix_tree<Traits>::~prefix_tree()
{ }

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

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

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

/**
 * Finds a key within the tree and returns an iterator to it, if possible.
 */
template <typename Traits>
typename prefix_tree<Traits>::iterator
prefix_tree<Traits>::find(key_type const& key)
{
    // Not found until it is
    node_type *first_node  = 0;
    node_type *last_node   = 0;

    // First find the terminal position of the key. If it does not exist,
    // then the item is not in the tree.
    /// @todo prefix_tree.end()
    if ((last_node = get_existing_node(key.begin(), key.end())))
    {
        key_element key_first = *key.begin();

        // The first node exists and should be set appropriately.
        first_node = &(_root.child[key_first]);
    }

    // Return the appropriate iterator.
    return iterator(first_node, last_node);
}

/**
 * Inserts a value_type into the trie.
 */
template <typename Traits>
std::pair<typename prefix_tree<Traits>::iterator, bool>
prefix_tree<Traits>::insert(value_type const& value)
{
    // Find the node to insert.
    /// @todo: Don't assume that our contained type actually has .begin()
    ///     and .end(); this will not be the case with C-style arrays.

    // The element that we stoped at is the last character in the string,
    // and where our value ought to be.
    node_type *pos = get_node(key_of(value).begin(), key_of(value).end());

    /// @todo Do not assume that there is a front.

    // Get the first character of the key.
    key_element first = *key_of(value).begin();

    // Construct the iterator 
    iterator iter = iterator(&_root.child[first], pos);

    // If 'term' is already set, then the key already exists.
    /// @todo Handle multisets and multimaps.
    if (pos->term) {
        // Return a pair with the iterator's position and false, because
        // Nothing was inserted.
        return std::make_pair(iter, false);
    }
    
    // Now we can set 'term' and value appropriately.
    set_value(pos->value, value);
    pos->term  = true;

    // Increment size.
    ++_size;

    return std::make_pair(iter, true);
}

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

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

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

/// @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 Traits>
typename prefix_tree<Traits>::node_type*
prefix_tree<Traits>::get_existing_node(key_iterator const& begin, key_iterator const& end)
{
    // Start our insertion at the root.
    node_type *pos = &_root;

    // Iterate through the key being inserted.
    for (key_iterator 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 Traits>
typename prefix_tree<Traits>::node_type*
prefix_tree<Traits>::get_node(key_iterator const& begin, key_iterator const& end)
{
    // Start our insertion at the root.
    node_type *pos = &_root;
    
    // Iterate through the key being inserted.
    for (key_iterator i = begin; i != end; ++i)
    {
        // Elements will be inserted as necessary if they don't exist.
        if (pos->child.find(*i) == pos->child.end()) {
            // Set value and parent as appropriate.
            node_type *child = &pos->child[*i];
            key_of(child->value) = *i;
            child->parent = pos;
        }

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

} // End of the gpld namespace

#endif