comparison DEPENDENCIES/generic/include/boost/xpressive/detail/utility/symbols.hpp @ 16:2665513ce2d3

Add boost headers

+///////////////////////////////////////////////////////////////////////////////
+/// \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/noncopyable.hpp>
+#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 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;
+            #ifdef BOOST_DISABLE_THREADS
+            node* p2 = p;
+            bool left = false;
+            #endif
+            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)
+                {
+                    #ifdef BOOST_DISABLE_THREADS
+                    left = true;
+                    p2 = p;
+                    #endif
+                    p = p->lo;
+                }
+                else // (c1 > p->ch)
+                {
+                    #ifdef BOOST_DISABLE_THREADS
+                    left = false;
+                    p2 = p;
+                    #endif
+                    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