///////////////////////////////////////////////////////////////////////////////

/// \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

