boost/xpressive/detail/utility/symbols.hpp
/////////////////////////////////////////////////////////////////////////////// /// \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; 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