///////////////////////////////////////////////////////////////////////////////
/// \file symbols.hpp
///   Contains the Ternary Search Trie implementation.
/// Based on the following papers:
/// J. Bentley and R. Sedgewick. (1998) Ternary search trees. Dr. Dobbs Journal
/// G. Badr and B.J. Oommen. (2005) Self-Adjusting of Ternary Search Tries Using
///     Conditional Rotations and Randomized Heuristics
//
//  Copyright 2007 David Jenkins.
//  Copyright 2007 Eric Niebler.
//
//  Distributed under 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_XPRESSIVE_DETAIL_SYMBOLS_HPP_DRJ_06_11_2007
#define BOOST_XPRESSIVE_DETAIL_SYMBOLS_HPP_DRJ_06_11_2007

// MS compatible compilers support #pragma once
#if defined(_MSC_VER) && (_MSC_VER >= 1020)
# pragma once
#endif

#include <boost/range/begin.hpp>
#include <boost/range/end.hpp>
#include <boost/range/value_type.hpp>
#include <boost/range/const_iterator.hpp>
#include <boost/shared_ptr.hpp>

namespace boost { namespace xpressive { namespace detail
{

    ///////////////////////////////////////////////////////////////////////////////
    // symbols (using a ternary search trie)
    //
    template<typename Map>
    struct symbols
    {
        typedef typename range_value<Map>::type::first_type key_type;
        typedef typename range_value<Map>::type::second_type value_type;
        typedef typename range_value<key_type>::type char_type;
        typedef typename range_const_iterator<Map>::type iterator;
        typedef typename range_const_iterator<key_type>::type key_iterator;
        typedef value_type const *result_type;

        // copies of this symbol table share the TST

        template<typename Trans>
        void load(Map const &map, Trans trans)
        {
            iterator begin = boost::begin(map);
            iterator end = boost::end(map);
            node* root_p = this->root.get();
            for(; begin != end; ++begin)
            {
                key_iterator kbegin = boost::begin(begin->first);
                key_iterator kend = boost::end(begin->first);
                root_p = this->insert(root_p, kbegin, kend, &begin->second, trans);
            }
            this->root.reset(root_p);
        }

        template<typename BidiIter, typename Trans>
        result_type operator ()(BidiIter &begin, BidiIter end, Trans trans) const
        {
            return this->search(begin, end, trans, this->root.get());
        }

        template<typename Sink>
        void peek(Sink const &sink) const
        {
            this->peek_(this->root.get(), sink);
        }

    private:
        ///////////////////////////////////////////////////////////////////////////////
        // struct node : a node in the TST. 
        //     The "eq" field stores the result pointer when ch is zero.
        // 
        struct node
            : boost::noncopyable
        {
            node(char_type c)
              : ch(c)
              , lo(0)
              , eq(0)
              , hi(0)
              #ifdef BOOST_DISABLE_THREADS
              , tau(0)
              #endif
            {}

            ~node()
            {
                delete lo;
                if (ch)
                    delete eq;
                delete hi;
            }

            void swap(node& that)
            {
                std::swap(ch, that.ch);
                std::swap(lo, that.lo);
                std::swap(eq, that.eq);
                std::swap(hi, that.hi);
                #ifdef BOOST_DISABLE_THREADS
                std::swap(tau, that.tau);
                #endif
            }

            char_type ch;
            node* lo;
            union
            {
                node* eq;
                result_type result;
            };
            node* hi;
            #ifdef BOOST_DISABLE_THREADS
            long tau;
            #endif
        };

        ///////////////////////////////////////////////////////////////////////////////
        // insert : insert a string into the TST
        // 
        template<typename Trans>
        node* insert(node* p, key_iterator &begin, key_iterator end, result_type r, Trans trans) const
        {
            char_type c1 = 0;

            if(begin != end)
            {
                c1 = trans(*begin);
            }

            if(!p)
            {
                p = new node(c1);
            }

            if(c1 < p->ch)
            {
                p->lo = this->insert(p->lo, begin, end, r, trans);
            }
            else if(c1 == p->ch)
            {
                if(0 == c1)
                {
                    p->result = r;
                }
                else
                {
                    p->eq = this->insert(p->eq, ++begin, end, r, trans);
                }
            }
            else
            {
                p->hi = this->insert(p->hi, begin, end, r, trans);
            }

            return p;
        }

        #ifdef BOOST_DISABLE_THREADS
        ///////////////////////////////////////////////////////////////////////////////
        // conditional rotation : the goal is to minimize the overall
        //     weighted path length of each binary search tree
        // 
        bool const cond_rotation(bool left, node* const i, node* const j) const
        {
            // don't rotate top node in binary search tree
            if (i == j)
                return false;
            // calculate psi (the rotation condition)
            node* const k = (left ? i->hi : i->lo);
            long psi = 2*i->tau - j->tau - (k ? k->tau : 0);
            if (psi <= 0)
                return false;

            // recalculate the tau values
            j->tau += -i->tau + (k ? k->tau : 0);
            i->tau +=  j->tau - (k ? k->tau : 0);
            // fixup links and swap nodes
            if (left)
            {
                j->lo = k;
                i->hi = i;
            }
            else
            {
                j->hi = k;
                i->lo = i;
            }
            (*i).swap(*j);
            return true;
        }
        #endif

        ///////////////////////////////////////////////////////////////////////////////
        // search : find a string in the TST
        // 
        template<typename BidiIter, typename Trans>
        result_type search(BidiIter &begin, BidiIter end, Trans trans, node* p) const
        {
            result_type r = 0;
            node* p2 = p;
            bool left = false;
            char_type c1 = (begin != end ? trans(*begin) : 0);
            while(p)
            {
                #ifdef BOOST_DISABLE_THREADS
                ++p->tau;
                #endif
                if(c1 == p->ch)
                {
                    // conditional rotation test
                    #ifdef BOOST_DISABLE_THREADS
                    if (this->cond_rotation(left, p, p2))
                        p = p2;
                    #endif
                    if (0 == p->ch)
                    {
                        // it's a match!
                        r = p->result;
                    }
                    if(begin == end)
                        break;
                    ++begin;
                    p = p->eq;
                    // search for the longest match first
                    r = search(begin,end,trans,p);
                    if (0 == r)
                    {
                        // search for a match ending here
                        r = search(end,end,trans,p);
                        if (0 == r)
                        {
                            --begin;
                        }
                    }
                    break;
                }
                else if(c1 < p->ch)
                {
                    left = true;
                    p2 = p;
                    p = p->lo;
                }
                else // (c1 > p->ch)
                {
                    left = false;
                    p2 = p;
                    p = p->hi;
                }
            }
            return r;
        }

        template<typename Sink>
        void peek_(node const *const &p, Sink const &sink) const
        {
            if(p)
            {
                sink(p->ch);
                this->peek_(p->lo, sink);
                this->peek_(p->hi, sink);
            }
        }

        boost::shared_ptr<node> root;
    };

}}} // namespace boost::xpressive::detail

#endif