1 /////////////////////////////////////////////////////////////////////////////// 2 /// \file symbols.hpp 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 8 // 9 // Copyright 2007 David Jenkins. 10 // Copyright 2007 Eric Niebler. 11 // 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) 15 16 #ifndef BOOST_XPRESSIVE_DETAIL_SYMBOLS_HPP_DRJ_06_11_2007 17 #define BOOST_XPRESSIVE_DETAIL_SYMBOLS_HPP_DRJ_06_11_2007 18 19 // MS compatible compilers support #pragma once 20 #if defined(_MSC_VER) 21 # pragma once 22 #endif 23 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> 30 31 namespace boost { namespace xpressive { namespace detail 32 { 33 34 /////////////////////////////////////////////////////////////////////////////// 35 // symbols (using a ternary search trie) 36 // 37 template<typename Map> 38 struct symbols 39 { 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; 46 47 // copies of this symbol table share the TST 48 49 template<typename Trans> loadboost::xpressive::detail::symbols50 void load(Map const &map, Trans trans) 51 { 52 iterator begin = boost::begin(map); 53 iterator end = boost::end(map); 54 node* root_p = this->root.get(); 55 for(; begin != end; ++begin) 56 { 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); 60 } 61 this->root.reset(root_p); 62 } 63 64 template<typename BidiIter, typename Trans> operator ()boost::xpressive::detail::symbols65 result_type operator ()(BidiIter &begin, BidiIter end, Trans trans) const 66 { 67 return this->search(begin, end, trans, this->root.get()); 68 } 69 70 template<typename Sink> peekboost::xpressive::detail::symbols71 void peek(Sink const &sink) const 72 { 73 this->peek_(this->root.get(), sink); 74 } 75 76 private: 77 /////////////////////////////////////////////////////////////////////////////// 78 // struct node : a node in the TST. 79 // The "eq" field stores the result pointer when ch is zero. 80 // 81 struct node 82 : boost::noncopyable 83 { nodeboost::xpressive::detail::symbols::node84 node(char_type c) 85 : ch(c) 86 , lo(0) 87 , eq(0) 88 , hi(0) 89 #ifdef BOOST_DISABLE_THREADS 90 , tau(0) 91 #endif 92 {} 93 ~nodeboost::xpressive::detail::symbols::node94 ~node() 95 { 96 delete lo; 97 if (ch) 98 delete eq; 99 delete hi; 100 } 101 swapboost::xpressive::detail::symbols::node102 void swap(node& that) 103 { 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); 110 #endif 111 } 112 113 char_type ch; 114 node* lo; 115 union 116 { 117 node* eq; 118 result_type result; 119 }; 120 node* hi; 121 #ifdef BOOST_DISABLE_THREADS 122 long tau; 123 #endif 124 }; 125 126 /////////////////////////////////////////////////////////////////////////////// 127 // insert : insert a string into the TST 128 // 129 template<typename Trans> insertboost::xpressive::detail::symbols130 node* insert(node* p, key_iterator &begin, key_iterator end, result_type r, Trans trans) const 131 { 132 char_type c1 = 0; 133 134 if(begin != end) 135 { 136 c1 = trans(*begin); 137 } 138 139 if(!p) 140 { 141 p = new node(c1); 142 } 143 144 if(c1 < p->ch) 145 { 146 p->lo = this->insert(p->lo, begin, end, r, trans); 147 } 148 else if(c1 == p->ch) 149 { 150 if(0 == c1) 151 { 152 p->result = r; 153 } 154 else 155 { 156 p->eq = this->insert(p->eq, ++begin, end, r, trans); 157 } 158 } 159 else 160 { 161 p->hi = this->insert(p->hi, begin, end, r, trans); 162 } 163 164 return p; 165 } 166 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 171 // cond_rotationboost::xpressive::detail::symbols172 bool cond_rotation(bool left, node* const i, node* const j) const 173 { 174 // don't rotate top node in binary search tree 175 if (i == j) 176 return false; 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); 180 if (psi <= 0) 181 return false; 182 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 187 if (left) 188 { 189 j->lo = k; 190 i->hi = i; 191 } 192 else 193 { 194 j->hi = k; 195 i->lo = i; 196 } 197 (*i).swap(*j); 198 return true; 199 } 200 #endif 201 202 /////////////////////////////////////////////////////////////////////////////// 203 // search : find a string in the TST 204 // 205 template<typename BidiIter, typename Trans> searchboost::xpressive::detail::symbols206 result_type search(BidiIter &begin, BidiIter end, Trans trans, node* p) const 207 { 208 result_type r = 0; 209 #ifdef BOOST_DISABLE_THREADS 210 node* p2 = p; 211 bool left = false; 212 #endif 213 char_type c1 = (begin != end ? trans(*begin) : 0); 214 while(p) 215 { 216 #ifdef BOOST_DISABLE_THREADS 217 ++p->tau; 218 #endif 219 if(c1 == p->ch) 220 { 221 // conditional rotation test 222 #ifdef BOOST_DISABLE_THREADS 223 if (this->cond_rotation(left, p, p2)) 224 p = p2; 225 #endif 226 if (0 == p->ch) 227 { 228 // it's a match! 229 r = p->result; 230 } 231 if(begin == end) 232 break; 233 ++begin; 234 p = p->eq; 235 // search for the longest match first 236 r = search(begin,end,trans,p); 237 if (0 == r) 238 { 239 // search for a match ending here 240 r = search(end,end,trans,p); 241 if (0 == r) 242 { 243 --begin; 244 } 245 } 246 break; 247 } 248 else if(c1 < p->ch) 249 { 250 #ifdef BOOST_DISABLE_THREADS 251 left = true; 252 p2 = p; 253 #endif 254 p = p->lo; 255 } 256 else // (c1 > p->ch) 257 { 258 #ifdef BOOST_DISABLE_THREADS 259 left = false; 260 p2 = p; 261 #endif 262 p = p->hi; 263 } 264 } 265 return r; 266 } 267 268 template<typename Sink> peek_boost::xpressive::detail::symbols269 void peek_(node const *const &p, Sink const &sink) const 270 { 271 if(p) 272 { 273 sink(p->ch); 274 this->peek_(p->lo, sink); 275 this->peek_(p->hi, sink); 276 } 277 } 278 279 boost::shared_ptr<node> root; 280 }; 281 282 }}} // namespace boost::xpressive::detail 283 284 #endif 285