detail/utility/symbols.hpp

0001 ///////////////////////////////////////////////////////////////////////////////
0002 /// \file symbols.hpp
0003 ///   Contains the Ternary Search Trie implementation.
0004 /// Based on the following papers:
0005 /// J. Bentley and R. Sedgewick. (1998) Ternary search trees. Dr. Dobbs Journal
0006 /// G. Badr and B.J. Oommen. (2005) Self-Adjusting of Ternary Search Tries Using
0007 ///     Conditional Rotations and Randomized Heuristics
0008 //
0009 //  Copyright 2007 David Jenkins.
0010 //  Copyright 2007 Eric Niebler.
0011 //
0012 //  Distributed under the Boost Software License, Version 1.0. (See
0013 //  accompanying file LICENSE_1_0.txt or copy at
0014 //  http://www.boost.org/LICENSE_1_0.txt)
0015
0016 #ifndef BOOST_XPRESSIVE_DETAIL_SYMBOLS_HPP_DRJ_06_11_2007
0017 #define BOOST_XPRESSIVE_DETAIL_SYMBOLS_HPP_DRJ_06_11_2007
0018
0019 // MS compatible compilers support #pragma once
0020 #if defined(_MSC_VER)
0021 # pragma once
0022 #endif
0023
0024 #include <boost/noncopyable.hpp>
0025 #include <boost/range/begin.hpp>
0026 #include <boost/range/end.hpp>
0027 #include <boost/range/value_type.hpp>
0028 #include <boost/range/const_iterator.hpp>
0029 #include <boost/shared_ptr.hpp>
0030
0031 namespace boost { namespace xpressive { namespace detail
0032 {
0033
0034     ///////////////////////////////////////////////////////////////////////////////
0035     // symbols (using a ternary search trie)
0036     //
0037     template<typename Map>
0038     struct symbols
0039     {
0040         typedef typename range_value<Map>::type::first_type key_type;
0041         typedef typename range_value<Map>::type::second_type value_type;
0042         typedef typename range_value<key_type>::type char_type;
0043         typedef typename range_const_iterator<Map>::type iterator;
0044         typedef typename range_const_iterator<key_type>::type key_iterator;
0045         typedef value_type const *result_type;
0046
0047         // copies of this symbol table share the TST
0048
0049         template<typename Trans>
0050         void load(Map const &map, Trans trans)
0051         {
0052             iterator begin = boost::begin(map);
0053             iterator end = boost::end(map);
0054             node* root_p = this->root.get();
0055             for(; begin != end; ++begin)
0056             {
0057                 key_iterator kbegin = boost::begin(begin->first);
0058                 key_iterator kend = boost::end(begin->first);
0059                 root_p = this->insert(root_p, kbegin, kend, &begin->second, trans);
0060             }
0061             this->root.reset(root_p);
0062         }
0063
0064         template<typename BidiIter, typename Trans>
0065         result_type operator ()(BidiIter &begin, BidiIter end, Trans trans) const
0066         {
0067             return this->search(begin, end, trans, this->root.get());
0068         }
0069
0070         template<typename Sink>
0071         void peek(Sink const &sink) const
0072         {
0073             this->peek_(this->root.get(), sink);
0074         }
0075
0076     private:
0077         ///////////////////////////////////////////////////////////////////////////////
0078         // struct node : a node in the TST.
0079         //     The "eq" field stores the result pointer when ch is zero.
0080         //
0081         struct node
0082             : boost::noncopyable
0083         {
0084             node(char_type c)
0085               : ch(c)
0086               , lo(0)
0087               , eq(0)
0088               , hi(0)
0089               #ifdef BOOST_DISABLE_THREADS
0090               , tau(0)
0091               #endif
0092             {}
0093
0094             ~node()
0095             {
0096                 delete lo;
0097                 if (ch)
0098                     delete eq;
0099                 delete hi;
0100             }
0101
0102             void swap(node& that)
0103             {
0104                 std::swap(ch, that.ch);
0105                 std::swap(lo, that.lo);
0106                 std::swap(eq, that.eq);
0107                 std::swap(hi, that.hi);
0108                 #ifdef BOOST_DISABLE_THREADS
0109                 std::swap(tau, that.tau);
0110                 #endif
0111             }
0112
0113             char_type ch;
0114             node* lo;
0115             union
0116             {
0117                 node* eq;
0118                 result_type result;
0119             };
0120             node* hi;
0121             #ifdef BOOST_DISABLE_THREADS
0122             long tau;
0123             #endif
0124         };
0125
0126         ///////////////////////////////////////////////////////////////////////////////
0127         // insert : insert a string into the TST
0128         //
0129         template<typename Trans>
0130         node* insert(node* p, key_iterator &begin, key_iterator end, result_type r, Trans trans) const
0131         {
0132             char_type c1 = 0;
0133
0134             if(begin != end)
0135             {
0136                 c1 = trans(*begin);
0137             }
0138
0139             if(!p)
0140             {
0141                 p = new node(c1);
0142             }
0143
0144             if(c1 < p->ch)
0145             {
0146                 p->lo = this->insert(p->lo, begin, end, r, trans);
0147             }
0148             else if(c1 == p->ch)
0149             {
0150                 if(0 == c1)
0151                 {
0152                     p->result = r;
0153                 }
0154                 else
0155                 {
0156                     p->eq = this->insert(p->eq, ++begin, end, r, trans);
0157                 }
0158             }
0159             else
0160             {
0161                 p->hi = this->insert(p->hi, begin, end, r, trans);
0162             }
0163
0164             return p;
0165         }
0166
0167         #ifdef BOOST_DISABLE_THREADS
0168         ///////////////////////////////////////////////////////////////////////////////
0169         // conditional rotation : the goal is to minimize the overall
0170         //     weighted path length of each binary search tree
0171         //
0172         bool cond_rotation(bool left, node* const i, node* const j) const
0173         {
0174             // don't rotate top node in binary search tree
0175             if (i == j)
0176                 return false;
0177             // calculate psi (the rotation condition)
0178             node* const k = (left ? i->hi : i->lo);
0179             long psi = 2*i->tau - j->tau - (k ? k->tau : 0);
0180             if (psi <= 0)
0181                 return false;
0182
0183             // recalculate the tau values
0184             j->tau += -i->tau + (k ? k->tau : 0);
0185             i->tau +=  j->tau - (k ? k->tau : 0);
0186             // fixup links and swap nodes
0187             if (left)
0188             {
0189                 j->lo = k;
0190                 i->hi = i;
0191             }
0192             else
0193             {
0194                 j->hi = k;
0195                 i->lo = i;
0196             }
0197             (*i).swap(*j);
0198             return true;
0199         }
0200         #endif
0201
0202         ///////////////////////////////////////////////////////////////////////////////
0203         // search : find a string in the TST
0204         //
0205         template<typename BidiIter, typename Trans>
0206         result_type search(BidiIter &begin, BidiIter end, Trans trans, node* p) const
0207         {
0208             result_type r = 0;
0209             #ifdef BOOST_DISABLE_THREADS
0210             node* p2 = p;
0211             bool left = false;
0212             #endif
0213             char_type c1 = (begin != end ? trans(*begin) : 0);
0214             while(p)
0215             {
0216                 #ifdef BOOST_DISABLE_THREADS
0217                 ++p->tau;
0218                 #endif
0219                 if(c1 == p->ch)
0220                 {
0221                     // conditional rotation test
0222                     #ifdef BOOST_DISABLE_THREADS
0223                     if (this->cond_rotation(left, p, p2))
0224                         p = p2;
0225                     #endif
0226                     if (0 == p->ch)
0227                     {
0228                         // it's a match!
0229                         r = p->result;
0230                     }
0231                     if(begin == end)
0232                         break;
0233                     ++begin;
0234                     p = p->eq;
0235                     // search for the longest match first
0236                     r = search(begin,end,trans,p);
0237                     if (0 == r)
0238                     {
0239                         // search for a match ending here
0240                         r = search(end,end,trans,p);
0241                         if (0 == r)
0242                         {
0243                             --begin;
0244                         }
0245                     }
0246                     break;
0247                 }
0248                 else if(c1 < p->ch)
0249                 {
0250                     #ifdef BOOST_DISABLE_THREADS
0251                     left = true;
0252                     p2 = p;
0253                     #endif
0254                     p = p->lo;
0255                 }
0256                 else // (c1 > p->ch)
0257                 {
0258                     #ifdef BOOST_DISABLE_THREADS
0259                     left = false;
0260                     p2 = p;
0261                     #endif
0262                     p = p->hi;
0263                 }
0264             }
0265             return r;
0266         }
0267
0268         template<typename Sink>
0269         void peek_(node const *const &p, Sink const &sink) const
0270         {
0271             if(p)
0272             {
0273                 sink(p->ch);
0274                 this->peek_(p->lo, sink);
0275                 this->peek_(p->hi, sink);
0276             }
0277         }
0278
0279         boost::shared_ptr<node> root;
0280     };
0281
0282 }}} // namespace boost::xpressive::detail
0283
0284 #endif