1 ///////////////////////////////////////////////////////////////////////////////
3 /// Contains the Ternary Search Trie implementation.
4 /// Based on the following papers:
5 /// J. Bentley and R. Sedgewick. (1998) Ternary search trees. Dr. Dobbs Journal
6 /// G. Badr and B.J. Oommen. (2005) Self-Adjusting of Ternary Search Tries Using
7 /// Conditional Rotations and Randomized Heuristics
9 // Copyright 2007 David Jenkins.
10 // Copyright 2007 Eric Niebler.
12 // Distributed under the Boost Software License, Version 1.0. (See
13 // accompanying file LICENSE_1_0.txt or copy at
14 // http://www.boost.org/LICENSE_1_0.txt)
16 #ifndef BOOST_XPRESSIVE_DETAIL_SYMBOLS_HPP_DRJ_06_11_2007
17 #define BOOST_XPRESSIVE_DETAIL_SYMBOLS_HPP_DRJ_06_11_2007
19 // MS compatible compilers support #pragma once
24 #include <boost/noncopyable.hpp>
25 #include <boost/range/begin.hpp>
26 #include <boost/range/end.hpp>
27 #include <boost/range/value_type.hpp>
28 #include <boost/range/const_iterator.hpp>
29 #include <boost/shared_ptr.hpp>
31 namespace boost { namespace xpressive { namespace detail
34 ///////////////////////////////////////////////////////////////////////////////
35 // symbols (using a ternary search trie)
37 template<typename Map>
40 typedef typename range_value<Map>::type::first_type key_type;
41 typedef typename range_value<Map>::type::second_type value_type;
42 typedef typename range_value<key_type>::type char_type;
43 typedef typename range_const_iterator<Map>::type iterator;
44 typedef typename range_const_iterator<key_type>::type key_iterator;
45 typedef value_type const *result_type;
47 // copies of this symbol table share the TST
49 template<typename Trans>
50 void load(Map const &map, Trans trans)
52 iterator begin = boost::begin(map);
53 iterator end = boost::end(map);
54 node* root_p = this->root.get();
55 for(; begin != end; ++begin)
57 key_iterator kbegin = boost::begin(begin->first);
58 key_iterator kend = boost::end(begin->first);
59 root_p = this->insert(root_p, kbegin, kend, &begin->second, trans);
61 this->root.reset(root_p);
64 template<typename BidiIter, typename Trans>
65 result_type operator ()(BidiIter &begin, BidiIter end, Trans trans) const
67 return this->search(begin, end, trans, this->root.get());
70 template<typename Sink>
71 void peek(Sink const &sink) const
73 this->peek_(this->root.get(), sink);
77 ///////////////////////////////////////////////////////////////////////////////
78 // struct node : a node in the TST.
79 // The "eq" field stores the result pointer when ch is zero.
89 #ifdef BOOST_DISABLE_THREADS
102 void swap(node& that)
104 std::swap(ch, that.ch);
105 std::swap(lo, that.lo);
106 std::swap(eq, that.eq);
107 std::swap(hi, that.hi);
108 #ifdef BOOST_DISABLE_THREADS
109 std::swap(tau, that.tau);
121 #ifdef BOOST_DISABLE_THREADS
126 ///////////////////////////////////////////////////////////////////////////////
127 // insert : insert a string into the TST
129 template<typename Trans>
130 node* insert(node* p, key_iterator &begin, key_iterator end, result_type r, Trans trans) const
146 p->lo = this->insert(p->lo, begin, end, r, trans);
156 p->eq = this->insert(p->eq, ++begin, end, r, trans);
161 p->hi = this->insert(p->hi, begin, end, r, trans);
167 #ifdef BOOST_DISABLE_THREADS
168 ///////////////////////////////////////////////////////////////////////////////
169 // conditional rotation : the goal is to minimize the overall
170 // weighted path length of each binary search tree
172 bool cond_rotation(bool left, node* const i, node* const j) const
174 // don't rotate top node in binary search tree
177 // calculate psi (the rotation condition)
178 node* const k = (left ? i->hi : i->lo);
179 long psi = 2*i->tau - j->tau - (k ? k->tau : 0);
183 // recalculate the tau values
184 j->tau += -i->tau + (k ? k->tau : 0);
185 i->tau += j->tau - (k ? k->tau : 0);
186 // fixup links and swap nodes
202 ///////////////////////////////////////////////////////////////////////////////
203 // search : find a string in the TST
205 template<typename BidiIter, typename Trans>
206 result_type search(BidiIter &begin, BidiIter end, Trans trans, node* p) const
209 #ifdef BOOST_DISABLE_THREADS
213 char_type c1 = (begin != end ? trans(*begin) : 0);
216 #ifdef BOOST_DISABLE_THREADS
221 // conditional rotation test
222 #ifdef BOOST_DISABLE_THREADS
223 if (this->cond_rotation(left, p, p2))
235 // search for the longest match first
236 r = search(begin,end,trans,p);
239 // search for a match ending here
240 r = search(end,end,trans,p);
250 #ifdef BOOST_DISABLE_THREADS
258 #ifdef BOOST_DISABLE_THREADS
268 template<typename Sink>
269 void peek_(node const *const &p, Sink const &sink) const
274 this->peek_(p->lo, sink);
275 this->peek_(p->hi, sink);
279 boost::shared_ptr<node> root;
282 }}} // namespace boost::xpressive::detail