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