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