/*=============================================================================
    Copyright (c) 2001-2003 Joel de Guzman
    http://spirit.sourceforge.net/

    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 BOOST_SPIRIT_TST_IPP
#define BOOST_SPIRIT_TST_IPP

///////////////////////////////////////////////////////////////////////////////
#include <memory> // for std::auto_ptr
#include <boost/spirit/core/assert.hpp>

///////////////////////////////////////////////////////////////////////////////
namespace boost { namespace spirit {

    namespace impl
    {

///////////////////////////////////////////////////////////////////////////////
//
//  tst class
//
//      Ternary Search Tree implementation. The data structure is faster than
//      hashing for many typical search problems especially when the search
//      interface is iterator based. Searching for a string of length k in a
//      ternary search tree with n strings will require at most O(log n+k)
//      character comparisons. TSTs are many times faster than hash tables
//      for unsuccessful searches since mismatches are discovered earlier
//      after examining only a few characters. Hash tables always examine an
//      entire key when searching.
//
//      For details see http://www.cs.princeton.edu/~rs/strings/.
//
//      *** This is a low level class and is
//          not meant for public consumption ***
//
///////////////////////////////////////////////////////////////////////////////
    template <typename T, typename CharT>
    struct tst_node
    {
        tst_node(CharT value_)
        : value(value_)
        , left(0)
        , right(0)
        { middle.link = 0; }

        ~tst_node()
        {
            delete left;
            delete right;
            if (value)
                delete middle.link;
            else
                delete middle.data;
        }

        tst_node*
        clone() const
        {
            std::auto_ptr<tst_node> copy(new tst_node(value));

            if (left)
                copy->left = left->clone();
            if (right)
                copy->right = right->clone();

            if (value && middle.link)
            {
                copy->middle.link = middle.link->clone();
            }
            else
            {
                std::auto_ptr<T> mid_data(new T(*middle.data));
                copy->middle.data = mid_data.release();
            }

            return copy.release();
        }

        union center {

            tst_node*   link;
            T*          data;
        };

        CharT       value;
        tst_node*   left;
        center      middle;
        tst_node*   right;
    };

    ///////////////////////////////////////////////////////////////////////////
    template <typename T, typename CharT>
    class tst
    {
    public:

        struct search_info
        {
            T*          data;
            std::size_t length;
        };

        tst()
        : root(0) {}

        tst(tst const& other)
        : root(other.root ? other.root->clone() : 0) {}

        ~tst()
        { delete root; }

        tst&
        operator=(tst const& other)
        {
            if (this != &other)
            {
                node_t* new_root = other.root ? other.root->clone() : 0;
                delete root;
                root = new_root;
            }
            return *this;
        }

        template <typename IteratorT>
        T* add(IteratorT first, IteratorT const& last, T const& data)
        {
            if (first == last)
                return 0;

            node_t**  np = &root;
            CharT   ch = *first;

            BOOST_SPIRIT_ASSERT(first == last || ch != 0
                && "Won't add string containing null character");

            for (;;)
            {
                if (*np == 0 || ch == 0)
                {
                    node_t* right = 0;
                    if (np != 0)
                        right = *np;
                    *np = new node_t(ch);
                    if (right)
                        (**np).right = right;
                }

                if (ch < (**np).value)
                {
                    np = &(**np).left;
                }
                else
                {
                    if (ch == (**np).value)
                    {
                        if (ch == 0)
                        {
                            if ((**np).middle.data == 0)
                            {
                                (**np).middle.data = new T(data);
                                return (**np).middle.data;
                            }
                            else
                            {
                                //  re-addition is disallowed
                                return 0;
                            }
                       }
                        ++first;
                        ch = (first == last) ? CharT(0) : *first;
                        BOOST_SPIRIT_ASSERT(first == last || ch != 0
                            && "Won't add string containing null character");
                        np = &(**np).middle.link;
                    }
                    else
                    {
                        np = &(**np).right;
                    }
                }
            }
        }

        template <typename ScannerT>
        search_info find(ScannerT const& scan) const
        {
            search_info result = { 0, 0 };
            if (scan.at_end()) {
                return result;
            }

            typedef typename ScannerT::iterator_t iterator_t;
            node_t*     np = root;
            CharT       ch = *scan;
            iterator_t  save = scan.first;
            iterator_t  latest = scan.first;
            std::size_t latest_len = 0;

            while (np)
            {

                if (ch < np->value) // => go left!
                {
                    if (np->value == 0)
                    {
                        result.data = np->middle.data;
                        if (result.data)
                        {
                            latest = scan.first;
                            latest_len = result.length;
                        }
                    }

                    np = np->left;
                }
                else if (ch == np->value) // => go middle!
                {
                    // Matching the null character is not allowed.
                    if (np->value == 0)
                    {
                        result.data = np->middle.data;
                        if (result.data)
                        {
                            latest = scan.first;
                            latest_len = result.length;
                        }
                        break;
                    }

                    ++scan;
                    ch = scan.at_end() ? CharT(0) : *scan;
                    np = np->middle.link;
                    ++result.length;
                }
                else // (ch > np->value) => go right!
                {
                    if (np->value == 0)
                    {
                        result.data = np->middle.data;
                        if (result.data)
                        {
                            latest = scan.first;
                            latest_len = result.length;
                        }
                    }

                    np = np->right;
                }
            }

            if (result.data == 0)
            {
                scan.first = save;
            }
            else
            {
                scan.first = latest;
                result.length = latest_len;
            }
            return result;
        }

    private:

        typedef tst_node<T, CharT> node_t;
        node_t* root;
    };

///////////////////////////////////////////////////////////////////////////////
    } // namespace impl

}} // namespace boost::spirit

#endif